Скачать или смотреть Andrew Turley on Incremental Mature Garbage Collection Using the Train Algorithm

Meetup: http://www.meetup.com/papers-we-love/...
Paper: http://bit.ly/1E88PO4
Slides: http://bit.ly/1M1e0yx
Audio: http://bit.ly/1ANbytM
-----------------------------------------------------------------------------
Sponsored by Two Sigma (@twosigma) and The Ladders (@TheLaddersDev)
-----------------------------------------------------------------------------

Description
---------------
Automatic garbage collection has spared programmers from an entire class of programming errors related to memory leaks and attempting to access objects that were incorrectly freed. As programs have grown in size and complexity, so have the systems that manage garbage collection. Each algorithm makes a different set of tradeoffs between factors such as the space used by objects, the space used by bookkeeping, the number of unused objects (garbage) that remain uncollected, the time spent in allocation, and the time spent in
collection.

The Train Algorithm is an incremental generational garbage collector that was designed to deal with the long and unpredictable pause times caused by other algorithms. It does this by grouping objects together on "cars" in "trains". The algorithm provides a strategy for moving objects from the younger generation into different cars, moving objects from one car to another, and collecting cars and trains. It was first described by Hudson and Moss in the paper "Incremental
Collection of Mature Objects".

In their paper "Incremental Mature Garbage Collection Using the Train Algorithm," Seligmann and Grarup describe what they believe is the first implementation of the Train Algorithm, which they used to replace the traditional mark-and-sweep collector that was used in the BETA programming language. They discuss their implementation and present information about the performance characteristics of the new algorithm as compared to the original.

Bio
----
Andrew Turley (@casio_juarez) is a lead software engineer on the platform team at TheLadders, where he builds infrastructure by linking Storm topologies together using RabbitMQ. He has also had numerous professional brushes with lower levels of the software stack, including building embedded systems for processing audio at DigiDesign, and helping to improve the performance of iOS at
Apple.

Related Papers mentioned by Steve Heller
---------------------------------------------------------
Early GC (for Lisp): [mcca60] John McCarthy. Recursive functions of symbolic expressions and their computation by machine, Part I. Communications of the ACM, 3(4):184-195, April 1960.

Partitioned heap: [bish77] Peter B. Bishop. Computer Systems with a Very Large Address Space and Garbage Collection. PhD thesis, MIT Laboratory for Computer Science, May 1977. Technical report MIT/LCS/TR-178.

Incremental Collection: [bake78] Henry G. Baker. List processing in real-time on a serial computer. Communications of the ACM, 21(4):280-294, 1978. Also AI Laboratory Working Paper 139, 1977.

U Kent Prof. Richard Jones has compiled an excellent online source of GC info (also he's written a book): http://www.cs.kent.ac.uk/people/staff..., including an amazing GC bibliography: http://www.cs.kent.ac.uk/people/staff...

Generational Collection (2):
[lieb83] Henry Lieberman and Carl E. Hewitt. A real-time garbage collector based on the lifetimes of objects. Communications of the ACM, 26(6):419-429, June 1983. Also report TM-184, Laboratory for Computer Science, MIT, Cambridge, MA, July 1980 and AI Lab Memo 569, 1981.
[moon84] David A. Moon. Garbage collection in a large LISP system. In Steele [LFP84], 1984, pages 235-245

Train algorithm:[huds92] Richard L. Hudson and J. Eliot B. Moss. Incremental collection of mature objects. In Bekkers and Cohen [IWMM92], 1992, pages 388-403

Implemented Train with guaranteed progress: [seli95] Jacob Seligmann and Steffen Grarup. Incremental mature garbage collection using the train algorithm. In Nierstrasz [ECOOP95], 1995, pages 235-252.

Efficient Trains: [gart05a] Alex Garthwaite. Making the Trains Run On Time. PhD thesis, University of Pennsylvania, 2005.