Combining write-barriers within an inner loop with fixed step

Details Combining write-barriers within an inner loop with fixed step Combining write-barriers within an inner loop with fixed step

2007-05-29

2007-05-29

Vo, Ted T. (Department: 2191)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S106000, C717S140000, C707S793000

Reexamination Certificate

active

10394812

ABSTRACT:
The present invention provides a technique for reducing the number of write barriers executed in mutator code without compromising garbage collector performance. To that end, when mutator instructions located within an inner-most nested loop (“inner loop”) modify references stored in one or more arrays, a compiler defers emitting write barriers corresponding to the reference modifications until after the inner loop is emitted. By deferring emission of write barriers, the mutator may execute a write barrier for each card spanned by the array instead of executing a typically larger number of write barriers corresponding to each reference modification made in an array. Thus, the invention enables the compiler to reduce the amount of write-barrier overhead performed by the mutator, consequently enabling the mutator to execute faster and more efficiently.

REFERENCES:
patent: 5920876 (1999-07-01), Ungar et al.
patent: 6115782 (2000-09-01), Wolczko 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: 6192517 (2001-02-01), Agesen et al.
patent: 6226653 (2001-05-01), Alpern et al.
patent: 6243720 (2001-06-01), Munter et al.
patent: 6289358 (2001-09-01), Mattis et al.
patent: 6308185 (2001-10-01), Grarup et al.
patent: 6363403 (2002-03-01), Roy et al.
patent: 6381738 (2002-04-01), Choi et al.
patent: 6424977 (2002-07-01), Garthwaite
patent: 6453466 (2002-09-01), Eidt et al.
patent: 6457019 (2002-09-01), Sexton et al.
patent: 6490599 (2002-12-01), Kolodner et al.
patent: 6804762 (2004-10-01), Dussud et al.
patent: 6826757 (2004-11-01), Steele et al.
patent: 6845437 (2005-01-01), Borman et al.
patent: 6868488 (2005-03-01), Garthwaite
patent: 6925637 (2005-08-01), Thomas et al.
patent: 6978448 (2005-12-01), Plummer et al.
patent: 2002/0138506 (2002-09-01), Shuf et al.
patent: 2002/0138507 (2002-09-01), Shuf et al.
patent: 2003/0033498 (2003-02-01), Borman et al.
patent: 2003/0208500 (2003-11-01), Daynes et al.
patent: 2004/0003014 (2004-01-01), Nagarajan et al.
Howden, Weak Mutation Testing and Completeness of Test Sets, IEEE, vol. SE-8 Issue: 4 Jul. 1982 pp. 371-379.
Zeil, Testing for Perturbations of Program Statements, IEEE, vol. SE-9 Issue: 3 May 1983 pp. 335-346.
Gourlay, A Mathematical Framework for the Investigation of Testing, IEEE, vol. SE-9 Issue: 6 Nov. 1983 pp. 686-709.
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.
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.
Appel, et al., “Real-Time Concurrent Collection on Stock Multiprocessors”, ACM SIGPLAN Notices, 1988.
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.
Brooks, “Trading Data Space for Reduced Time and Code Space in Real-Time Garbage Collection on Stock Hardware”, Proceedings of the 1984 Acm Symposium on Lisp and Funcional Programming, Aug. 1984, 108-113, Austin, TX.
Chilimbi, et al., “Using Generational Garbage Collection to Implement Cache-Conscious Data Placement”, International Symposium on Memory Management, Oct. 1998.
Clark, et al., “Compacting Garbage Collection can be Fast and Simple”, Software-Practice and Experience, vol. 26, No. 2, Feb. 1996, 177-194.
Courts, “Improving Locality of Reference in a Garbage-Collecting Memory Management System”, Communications of the ACM, vol. 31, No. 9, Sep. 1988, 1128-1138.
Herlihy, et al., “Lock-Free Garbage Collection for Multiprocessors”, ACM SPAA, 1991, 229-236.
Moon, “Garbage Collection in a Large Lisp System”, Conference Record of the 1984 ACM Symposium on LISP and Functional Programming, Aug. 1984, 235-246, Austin, TX.
Stamos, “Static Grouping of Small Objects to Enhance Performance of a Paged Virtual Memory”, ACM Transactions on Computer Systems, vol. 2, No. 2, May 1984, 155-180.
Ungar, “Generation Scavenging: A Non-Disruptive High Performance Storage Reclaration Algorithm”, ACM SIGPLAN Notices, Apr. 1984, 19(5).
Lam, et al., “Object Type Directed Garbage Collection to Improve Locality”, Proceedings of the International Workshop on Memory Management, Sep. 1992, 404-425, St. Malo, France.
Wilson, et al., “Effective Static-Graph Reorganization to Improve Locality in Garbage Collected Systems”, Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation, Jun. 1991, Canada.
Detlefs, et al., “Concurrent Remembered Set Refinement in Generational Garbage Collection”, Proceedings of the USENIX Java VM '02 Conference, Aug. 1-2, 2002, 14 pages, San Francisco, CA, USA.

Affiliated with

Also associated with

Rating

Combining write-barriers within an inner loop with fixed step does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Combining write-barriers within an inner loop with fixed step, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combining write-barriers within an inner loop with fixed step will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3742539