Deferring and combining write barriers for a...

Details Deferring and combining write barriers for a... Deferring and combining write barriers for a...

2008-07-22

2008-07-22

Zhen, Wei Y. (Department: 2191)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C707S793000

Reexamination Certificate

active

07404182

ABSTRACT:
The present invention provides a technique for reducing the number of write barriers without compromising garbage collector performance or correctness. To that end, a compiler defers emitting write barriers until it reaches a subsequent instruction in the mutator code. At this point, the compiler may elide repeated or unnecessary write-barrier code so as to emit only those write barriers that provide useful information to the garbage collector. By eliminating write-barrier code in this manner, the amount of write-barrier overhead in the mutator can be minimized, consequently enabling the mutator to execute faster and more efficiently. Further, collocating write barriers after the predetermined instruction also enables the compiler to generate object code having better cache performance and more efficient use of guard code than is possible using conventional write-barrier implementations.

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: 5845278 (1998-12-01), Kirsch 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: 6308319 (2001-10-01), Bush et al.
patent: 6314436 (2001-11-01), Houldsworth
patent: 6321240 (2001-11-01), Chilimbi et al.
patent: 6341293 (2002-01-01), Hennessey
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: 6415302 (2002-07-01), Garthwaite 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: 6510440 (2003-01-01), Alpern 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: 6928460 (2005-08-01), Nagarajan et al.
patent: 6931423 (2005-08-01), Sexton et al.
patent: 7013454 (2006-03-01), Bush et al.
patent: 7089272 (2006-08-01), Garthwaite et al.
patent: 2002/0032719 (2002-03-01), Thomas et al.
patent: 2002/0087590 (2002-07-01), Bacon et al.
patent: 2002/0095453 (2002-07-01), Steensgaarad
patent: 2002/0107880 (2002-08-01), Bacon
patent: 2002/0133533 (2002-09-01), Czajkowski et al.
patent: 2002/0138506 (2002-09-01), Shuf et al.
patent: 2002/0138507 (2002-09-01), Shuf et al.
patent: 2003/0005027 (2003-01-01), Borman et al.
patent: 2003/0069905 (2003-04-01), Dussud
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 940755 (1999-09-01), None
patent: 0 969 377 (2000-01-01), None
patent: WO-0188713 (2001-11-01), None
Richard L. Hudson et al. “Cycles to Recycle: Garbage Collection on the IA-64” Oct. 2000, ACM Press, ISMM'00, vol. 36, Issue 1, pp. 101-110.
Yoav Ossia et al. “A parallel, Incremental and Concurrent GC for Servers”, May 2002, ACM Press, PLDI'02 vol. 37 Issue 5, pp. 129-140.
Stephen M Blackburn et al. “Ulterior Reference Counting: Fast Garbage Collection without a Long Wait” Oct. 2003, ACM Press, OOPSLA '03, vol. 38, Issue 11, pp. 344-358.
U.S. Appl. No. 10/287,851, filed Nov. 5, 2002, Garthwaite et al.
Printezis, et al., “Visualising the Train Garbage Collector”, ISMM '02, 2002, pp. 50-63, Berlin, Germany.
Jones, Richard, et al., Garbage Collection: Algorithms for Automatic Dynamic Memory Management, 1996, pp. 1-319, John Willfey & Sons Ltd., England.
Oriented Language, Object Systems Laboratory, Dec. 1993, 1-14, Dept. Of Comp. Sci., Amherst, MA.
Appel, Andrew W., Simple Generational Garbage Collection and Fast Allocation, Mar. 1988, revised Sep. 1988, Department of Computer Science, Princeton University, Princeton, New Jersey, 1-16.
Hosking, et al., “Remembered Sets Can Also Play Cards,” OOPSLA/ECOOP Workshop on Garbage Collection in Object-Oriented Systems, Oct. 1993, 1-8.
Sobalvarro, Patrick G., A Lifetime-Based Garbage Collector for LISP Systems on General-Purpose Computers, Sep. 1988, pp. 1-59, Massachusetts Institute of Technology.
Pirinen, Pekka P., Barrier Techniques for Incremental Tracing, ISMM '98, Oct. 1998, Vancouver, B.C., 20-25.
Withington, P.T., How Real Is “Real-Time” GC?, Oct. 6, 1991, OOPSLA '91, GC Workshop, 1-8.
Hudson, Richard L., et al., Sapphire: Copying GC Without Stopping the World, Concurrency and Computation: Practice and Experience Special Issue: Java Grand/ISCOPE, 2001, 48-57.
Muchnick, Steven S., Advanced Compiler Design Implementaion, 1997, Chapters 7, 8, and 12, Morgan Kaufmann Publishers, 169-266 and 329-375.
Appel, et al., “Real-Time Concurrent Collection on Stock Multiprocessors”, ACM SIGPLAN Notices, 1988, 1-24.
Appleby, Karen, Garbage Collection for Prolog Based on WAM, vol. 31, No. 6, Communications of the ACM, Jun. 1, 1988, 719-741.
Arora, et al. “Thread Scheduling for Multiprogrammed Multiprocessors”, Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures, Jun. 1998, 1-11.
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, 1-12.
Baker, “List Processing in Real Time on a Serial Computer”, Communications of the ACM, vol. 21, No. 4, Apr. 1978, 280-294.
Barrett, et al., “Using Lifetime Predictors to Improve Memory Allocation Performance”, SIGPLAN'93 Conference on Programming Language Design and Implementation, Jun. 1993, 187-196, ACM Press, Albuquerque, NM.
Blackburn & McKinley, “In or Out? Putting Write Barriers in Their Place”, ISMM '03, Jun. 20, 2002, Berlin, Germany, 175-184.
Brooks, “Trading Data Space for Reduced Time and Code Space in Real-Time Garbage Collection on Stock Hardware”, ACM Software Engineering Symposium on Practical Software Development Environments, 1984, 256-262.
Chilimbi, et al., “Using Generational Garbage Collection to Implement Cache-Conscious Data Placement”, International Symposium on Memory Management, Oct. 1998, 37-48.
Clark, An Efficient List-Moving Algorithm Using C

Affiliated with

Also associated with

Rating

Deferring and combining write barriers for a... does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2814070