Specializing write-barriers for objects in a garbage...

Details Specializing write-barriers for objects in a garbage... Specializing write-barriers for objects in a garbage...

2006-08-08

2006-08-08

Robinson, Greta (Department: 2167)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

07089272

ABSTRACT:
A technique is provided for reducing the number of write barriers executed in mutator code without compromising garbage collector performance. Advantageously, a compiler generates two forms of a mutator code—a first version with write barriers and a second version substantially without write barriers. In operation, the first version of the code may be accessed by a vtable in a “mature” near-class and the second version may be accessed by a vtable in a “nascent” near-class. According to the invention, mapping of functionally equivalent points in the first and second versions of the mutator code may be facilitated by an associated pcmap. Further, each of the first and second versions may also be associated with a respective nr_map that facilitates mapping functionally equivalent points within different branches of guard code sequences corresponding to reference-writes to non-receiver objects.

REFERENCES:
patent: 4724521 (1988-02-01), Carron et al.
patent: 4797810 (1989-01-01), McEntee et al.
patent: 4912629 (1990-03-01), Shuler, Jr.
patent: 4989134 (1991-01-01), Shaw
patent: 5088036 (1992-02-01), Ellis et al.
patent: 5333318 (1994-07-01), Wolf
patent: 5392432 (1995-02-01), Engelstad et al.
patent: 5485613 (1996-01-01), Engelstad et al.
patent: 5560003 (1996-09-01), Nilson et al.
patent: 5687370 (1997-11-01), Garst et al.
patent: 5801943 (1998-09-01), Nasburg
patent: 5845276 (1998-12-01), Emerson et al.
patent: 5845298 (1998-12-01), O'Connor et al.
patent: 5857210 (1999-01-01), Tremblay et al.
patent: 5873104 (1999-02-01), Tremblay et al.
patent: 5873105 (1999-02-01), Tremblay et al.
patent: 5900001 (1999-05-01), Wolczko et al.
patent: 5903900 (1999-05-01), Knippel et al.
patent: 5930807 (1999-07-01), Ebrahim et al.
patent: 5953736 (1999-09-01), O'Connor et al.
patent: 5960087 (1999-09-01), Tribble et al.
patent: 5999974 (1999-12-01), Ratcliff et al.
patent: 6021415 (2000-02-01), Cannon et al.
patent: 6047125 (2000-04-01), Agesen et al.
patent: 6049390 (2000-04-01), Notredame et al.
patent: 6049810 (2000-04-01), Schwartz et al.
patent: 6065020 (2000-05-01), Dussud
patent: 6098089 (2000-08-01), O'Connor et al.
patent: 6148309 (2000-11-01), Azagury et al.
patent: 6148310 (2000-11-01), Azagury et al.
patent: 6173294 (2001-01-01), Azagury et al.
patent: 6185581 (2001-02-01), Garthwaite
patent: 6226653 (2001-05-01), Alpern et al.
patent: 6243720 (2001-06-01), Munter et al.
patent: 6260120 (2001-07-01), Blumenau et al.
patent: 6289358 (2001-09-01), Mattis et al.
patent: 6308185 (2001-10-01), Grarup et al.
patent: 6314436 (2001-11-01), Houldsworth
patent: 6321240 (2001-11-01), Chilimbi et al.
patent: 6353838 (2002-03-01), Sauntry et al.
patent: 6381738 (2002-04-01), Choi et al.
patent: 6393439 (2002-05-01), Houldsworth et al.
patent: 6424977 (2002-07-01), Garthwaite
patent: 6434576 (2002-08-01), Garthwaite
patent: 6434577 (2002-08-01), Garthwaite
patent: 6442661 (2002-08-01), Dreszer
patent: 6449626 (2002-09-01), Garthwaite et al.
patent: 6496871 (2002-12-01), Jagannathan et al.
patent: 6529919 (2003-03-01), Agesen et al.
patent: 6567905 (2003-05-01), Otis
patent: 6640278 (2003-10-01), Nolan et al.
patent: 6757890 (2004-06-01), Wallman
patent: 6769004 (2004-07-01), Barrett
patent: 6820101 (2004-11-01), Wallman
patent: 6826583 (2004-11-01), Flood et al.
patent: 6868488 (2005-03-01), Garthwaite
patent: 6892212 (2005-05-01), Shuf et al.
patent: 6928450 (2005-08-01), Mogi et al.
patent: 6931423 (2005-08-01), Sexton et al.
patent: 2002/0032719 (2002-03-01), Thomas et al.
patent: 2002/0095453 (2002-07-01), Steensgaard
patent: 2002/0133533 (2002-09-01), Czajkowski et al.
patent: 2002/0138506 (2002-09-01), Shuf et al.
patent: 2003/0088658 (2003-05-01), Davies et al.
patent: 2003/0200392 (2003-10-01), Wright et al.
patent: 2003/0217027 (2003-11-01), Farber et al.
patent: 2004/0010586 (2004-01-01), Burton et al.
patent: 2004/0039759 (2004-02-01), Detlefs et al.
patent: 2004/0215914 (2004-10-01), Dussud
patent: 0 969 377 (2000-01-01), None
patent: WO0188713 (2001-11-01), None
Richard Jones, et al., Garbage Collection: Algorithms for Automatic Dynamic Memory Management, 1996, John Wiliey & Sons Ltd., England.
Steffen Grarup, et al., Incremental Mature Garbage Collection: M.Sc. Thesis, Aug. 1993, Aarhus Univerisity, Computer Science Department, Denmark.
Paul R. Wilson, Uniprocessor Garbage Collection Techniques [Submitted to ACM Computing Surveys], pp. 1-67.
Richard L. Hudson, et al., Incremental Collection of Mature Objects, University Computing Services, University of Massachusetts, Amherst, Massachusetts.
Jacob Seligmann, et al., Incremental Mature Garbage Collection Using the Train Algorithm, Computer Science Department, Aarhus University, Denmark.
Antony L. Hosking, et al., Protection Traps and Alternatives for Memory Management of an Object-Oriented Language, pp. 1-14, Object Systems Labratory, Department of Computer Science, University of Massachusetts, Amherst, Massachusetts.
Antony L. Hosking, et al., A Comparative Performance Evaluation of Write Barrier implementations, pp. 92-107, Object Systems Labratory, Department of Computer Science, University of Massachusetts, Amherst, Massachusetts.
Henry Lieberman, et al., A Real-Time Garbage Collector Based on the Lifetimes of Objects, 1983, MIT Artificial Intelligence Labratory.
David Ungar, Generation Scavenging: A Non-disruptive High Performance Storage Reclamation Algorithm, 1984, pp. 157-167, Computer Science Division, Department of Electrical Engineering and Computer Sciences, University of California, Berkley, California.
Andrew W. Appel, Simple Generational Garbage Collection and Fast Allocation, Mar. 1988, revised Sep. 1988, Department of Computer Science, Princeton University, Princeton, New Jersey.
Richard Hudson, et al., Adaptive Garbage Collection for Modula-3 and Smalltalk, Oct. 27, 1990, pp. 1-5, Object Oriented Systems Laboratory, Department of Computer and Information Science, University of Massachusetts, Amherst, Massachusetts.
Antony L. Hosking, Remembered Sets Can Also Play Cards, pp. 1-8, Object Systems Laboratory, Department of Computer Science, University of Massachusetts, Amherst, Massachusetts.
Patrick G. Sobalvarro, A Lifetime-Based Garbage Collector for LISP Systems on General-Purpose Computers, Sep. 1988, pp. 1-59, Department of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology.
Pekka P. Pirinen, Barrier Techniques for Incremental Tracing, pp. 20-25, Harlequin Limited, Barrington Hall, Barrington, Cambridge CB2 5 RG, UK.
P. T. Withington, How Real is “Real-Time” GC?, Oct. 6, 1991, Symbolics, Inc., Burlington, Massachusetts.
Urs Holzle, A Fast Write Barrier for Generational Garbage Collectors, Oct. 1993, pp. 1-6, Computer Systems Laboratory, Stanford University, California.
Benjamin Zorn, Barrier Methods for Garbage Collection, Nov. 1990, pp. 1-37, Department of Computer Science, University of Colorado at Boulder, Boulder, Colorado.
Richard L. Hudson et al., Sapphire: Copying GC Without Stopping the World, Concurrency and Computation: Practice and Experience Special Issue: Java Grande/ISCOPE.
Scott Nettles, et al., Real-Time Replication Garbage Collection, Avionics Lab, Wright research and Development Center, Aeronautical Systems Division (AFSC), U.S. Air Force, Wright Patterson AFB, Ohio.
U.S. Appl. No. 10/287,851, filed Nov. 5, 2002, Garthwaite, et al.
Arora, et al., “Thread Scheduling for Multiprogrammed Multiprocessors”, Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architecture, Jun. 1998.
Bacon, et al., “Java without the Coffee Breaks: A nonintrusive Multiprocessor Garbage Collector”, SIGPLAN Conference on Programming Language Design and Implementation, Jun. 2001, Snowbird, UT.
Baker, “List Processing in Real Time on a Serial Computer”, Communications of the ACM 21, Apr. 1978, 280-294.
Barrett, et al., “Using Lifetime Predictors to Improve Memory Allocation Performance”, SIGPLAN'93 Conference on Programming Languages Design and Implementatio

Affiliated with

Also associated with

Rating

Specializing write-barriers for objects in a garbage... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Specializing write-barriers for objects in a garbage..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Specializing write-barriers for objects in a garbage... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3640301