Stop-and-copy and one-bit reference counting

DOI10.1016/0020-0190(93)90103-GMaRDI QIDQ685532zbMATH OpenFDO

Authors David S. Wise

Publication date 23 January 1994

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90103-G

zbMATH Keywords

allocation/deallocationlinked representationMRBmultiple reference bitstorage management

Mathematics Subject Classification ID

Theory of software (68N99) Theory of data (68P99)

Review text

A stop-and-copy garbage collector updates one-bit reference counting with essentially no extra space and minimal memory cycles beyong the conventional collection algorithm. Any object that is uniquely referenced during a collection becomes a candidate for cheap recovery before the next one, or faster recopying if it remains uniquely referenced, subsequent collections run faster even if none are recycled between collections. This algorithm extends to generation scavenging, it admits uncounted references from roots, and it corrects conservatively stuck counters, that result from earlier uncertainty wheter references were unique.

Recommendations

• scientific article; zbMATH DE number 1728241
• Cyclic reference counting
• scientific article; zbMATH DE number 1956465
• Algorithms for on-the-fly garbage collection
• The space cost of lazy reference counting

Cites work

• A LISP garbage-collector for virtual-memory computer systems
• A method for overlapping and erasure of lists
• A nonrecursive list compacting algorithm
• On-the-fly garbage collection
• Shifting garbage collection overhead to compile time
• Symmetric list processor

Cited in

(2)

• Generational cyclic reference counting
• Cyclic reference counting with local mark-scan

This page was built for publication: Stop-and-copy and one-bit reference counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685532)