List of Algorithms
2.1
Mark-sweep: allocation
2.2
Mark-sweep: marking
2.3
Mark-sweep: sweeping
2.4
Printezis and Detlefs’s bitmap marking
2.5
Lazy sweeping with a block structured heap
2.6
Marking with a FIFO prefetch buffer
2.7
Marking graph edges rather than nodes
3.1
The Two-Finger compaction algorithm
3.2
The Lisp 2 compaction algorithm
3.3
Jonkers’s threaded compactor
3.4
Compressor
4.1
Copying collection: initialisation and allocation
4.2
Semispace copying garbage collection
4.3
Copying with Cheney’s work list
4.4
Approximately depth-first copying
4.5
Online object reordering
5.1
Simple reference counting
5.2
Deferred reference counting
5.3
Coalesced reference counting: write barrier
5.4
Coalesced reference counting: update reference counts
5.5
The Recycler
6.1
Abstract tracing garbage collection
6.2
Abstract reference counting garbage collection
6.3
Abstract deferred reference counting garbage collection
7.1
Sequential allocation
7.2
First-fit allocation
7.3
First-fit allocation: an alternative way to split a cell
7.4
Next-fit allocation
7.5
Best-fit allocation
7.6
Searching in Cartesian trees
7.7
Segregated-fits allocation
7.8
Incorporating alignment requirements
9.1
Abstract generational garbage collection
10.1
Allocation in immix
11.1
Callee-save stack walking
11.2
Stack walking for non-modifying func
11.3
No callee-save stack walking
11.4
Recording stored pointers with a sequential store buffer
11.5
Misaligned access boundary check
11.6
Recording stored pointers with a card table on SPARC
11.7
Recording stored pointers with Hölzle’s card table on SPARC
11.8
Two-level card tables on SPARC
11.9
Search a crossing map for a slot-recording card table
11.10
Traversing chunked lists
11.11
Frame-based generational write barrier
12.1
Process finalisation queue
13.1
AtomicExchange spin lock
AtomicExchange
13.2
Test-and-Test-and-Set AtomicExchange spin lock
13.3
Spin locks implemented with the TestAndSet primitive
TestAndSet
13.4
The CompareAndSwap and CompareAndSet primitives
CompareAndSwap
CompareAndSet
13.5
Trying to advance state atomically with compare-and-swap
13.6
Semantics of load-linked/store-conditionally
13.7
Atomic state transition with load-linked/store-conditionally
13.8
Implementing compare-and-swap with load-linked/store-conditionally
13.9
Atomic arithmetic primitives
13.10
Fallacious test and set patterns
13.11
CompareAndSwapWide
13.12
CompareAndSwap2
13.13
Wait-free consensus using compare-and-swap
13.14
Peterson’s algorithm for mutual exclusion
13.15
Peterson’s algorithm for N threads
13.16
Consensus via mutual exclusion
13.17
Simplified αβγ shared-memory termination
13.18
An αβγ-style work stealing termination algorithm
13.19
Delaying scans until useful
13.20
Delaying idle workers
13.21
Symmetric termination detection
13.22
Symmetric termination detection repaired
13.23
Termination via a counter
13.24
Rendezvous via a counter
13.25
Rendezvous with reset
13.26
Counting lock
13.27
Lock-free implementation of a single-linked-list stack
13.28
Fine-grained locking for a single-linked-list queue
13.29
Fine-grained locking for a single-linked-list bounded queue
13.30
Lock-free implementation of a single-linked-list queue
13.31
Fine-grained locking of a circular buffer
13.32
Circular buffer with fewer variables
13.33
Circular buffer with distinguishable empty slots
13.34
Single reader/single writer lock-free buffer
13.35
Unbounded lock-free buffer implemented with an array
13.36
Unbounded lock-free array buffer with increasing scan start
13.37
Bounded lock-free buffer implemented with an array
13.38
Lock-free work stealing deque
13.39
Transactional memory version of a single-linked-list queue
14.1
The Endo et al parallel mark-sweep algorithm
14.2
Parallel marking with a bitmap
14.3
The Flood et al parallel mark-sweep algorithm
14.4
Grey packet management
14.5
Parallel allocation with grey packets
14.6
Parallel tracing with grey packets
14.7
Parallel tracing with channels
14.8
Parallel copying
14.9
Push/pop synchronisation with rooms
15.1
Grey mutator barriers
(a) Steele barrier
(b) Boehm et al barrier
(c) Dijkstra et al barrier
15.2
Black mutator barriers
(a) Baker barrier
(b) Appel et al barrier
(c) Abraham and Patel / Yuasa barrier
15.3
Pirinen black mutator hybrid barrier
16.1
Mostly-concurrent mark-sweep allocation
16.2
Mostly-concurrent marking
16.3
Doligez-Leroy-Gonthier write barriers
16.4
Mostly-concurrent incremental tracing garbage collection
17.1
Mostly-concurrent copying
17.2
Brooks’s indirection barriers
17.3
Herlihy and Moss owner update in place
17.4
Sapphire phases
17.5
Sapphire pointer equality
(a) Fast path
(b) Flip phase slow path
(c) Pointer forwarding
17.6
Sapphire write barriers
(a) The Mark phase barrier
(b) The Copy phase barrier
(c) The Flip phase barrier
17.7
Sapphire word copying procedure
17.8
Pauseless read barrier
18.1
Eager reference counting with locks
18.2
Eager reference counting with CompareAndSwap is broken
18.3
Eager reference counting with CompareAndSwap2
18.4
Concurrent buffered reference counting
18.5
Sliding views: update reference counts
18.6
Sliding views: the collector
18.7
Sliding views: Write
Write
18.8
Sliding views: New
New
19.1
Copying in the Blelloch and Cheng work-based collector
19.2
Mutator operations in the Blelloch and Cheng collector
19.3
Collector code in the Blelloch and Cheng work-based collector
19.4
Stopping and starting the Blelloch and Cheng work-based collector
19.5
The Henriksson slack-based collector
19.6
Mutator operations in the Henriksson slack-based collector
19.7
Replication copying for a uniprocessor
19.8
Copying and mutator barriers (while copying) in Staccato
19.9
Heap access (while copying) in Staccato
19.10
Copying and mutator barriers (while copying) in Chicken
19.11
Copying and mutator barriers (while copying) in Clover
