Note: If an entry has particular defining occurrences, the page numbers appear in bold, such as 17, and if it has occurrences deemed primary, their page numbers appear in italics, such as 53.
$ (notation), 246
ABA problem, 2, 238, 239, 285, 374, see also Concurrency, hardware primitives: CompareAndSwap; LoadLinked and StoreConditionally
Abstract concurrent collection, 331–335
collect, 333
scan, 333
write barriers, 334
Abstract generational collection, 134–136
Abstract reference counting, 82–85
deferred, 84
Acquire-release, see Concurrency, memory consistency
acquireWork, 278, 281, 283, 287, 288, 290
Adaptive systems, 80
generational collection, 121–123, 156
ThruMax algorithm, 123
addOrigins, 333
Affinity, see Memory affinity; Processor affinity scheduling
Age-based collection, 103, 127, see also Beltway collector; Generational collection; Older-first collection
Algorithmic complexity, 78, see also specific collection algorithms
allocate, 14
Cartesian trees, 92
free-list allocation
best-fit, 91
first-fit, 89
next-fit, 91
immix, 153
lazy sweeping, 25
real-time collection, replicating, 380, 382
segregated-fits allocation, 95
semispace copying, 44
sequential allocation, 88, 287
asymptotic complexity, 93
advantages, 93
bump a pointer, see Sequential allocation
concurrent mark-sweep, 324
copying collection, 53
different in garbage collected systems, 87
free-list, see Free-list allocation
hash consing, 169
heap parsability, 98–100, see also Crossing maps
linear, see Sequential allocation
local allocation buffers, 53, 101–102, 150, 151, 153, 165, 285, 292, 293, 320, 400
performance of various schemes, 94
segregated-fits, see Segregated-fits allocation
sequential, see Sequential allocation
sequential fits, see Free-list allocation
size classes, 94
size constraints, 98
space overhead, 98
stack, see Stack allocation
zeroing, see Zeroing
Allocation colour (black or grey), see Tricolour abstraction, allocation colour
Allocation threshold, see Hybrid mark-sweep, copying
Allocators, custom, 3
Ambiguous pointers, see Pointers, ambiguous
Ambiguous roots, 104, 338, see also Boehm-Demers-Weiser collector
AMD processors, 298
Amdahl’s law, 303
Anthracite (colour), 283
Appel, see Concurrent collection, read barriers
Appel-style collection, see Generational collection, Appel-style
Arraylets, 385, 393, 404, 413, 414
atomic, 245
Atomic operations, 15
Atomic primitives, see Concurrency, hardware primitives
AtomicDecrement, 241
Atomicity, see Concurrency; Transactions
awk, 58
Azul Systems, 147, 355, see also Concurrent copying and compaction, Pauseless collector
Baker’s algorithm, 277, 337–338, 377, 384
Brooks’s variant, see Brooks’s indirection barriers
Cheney scanning, 338
collect, 339
copy, 339
flip, 339
read barrier, 338
time and space bounds, 377
Baker’s Treadmill, see Treadmill collector
barrier (rendezvous barrier), 253
Barriers, see Brooks’s indirection barriers; Read barriers; Stack barriers; Write barriers
Beltway collector, 129–131, 140, see also Age-based collection
Benchmarks, 10
Best-fit, see Free-list allocation, best-fit
BiBoP, see Big bag of pages technique
Big bag of pages technique, 27, 168–169, 183, 294, 295, see also Sequential-fits allocation, block-based
Bitmapped-fits, see Allocation, bitmaps
Black (colour), see Tricolour abstraction
Black mutator, see Tricolour abstraction, mutator colour
Black-listing, 168
Block-structured heaps, see Heaps, block-structured
Blocks, 12
BMU, see Bounded mutator utilisation
Boehm, see Concurrent collection, insertion barriers
Boehm-Demers-Weiser collector, 166, 167, 168, 209, 280
Bookmarking collector, 108, 110, 156–157, 208
Bounded mutator utilisation, 7
Brooks’s indirection barriers, 340–341, 386, 391, 393, 404–407
Read, 341
Write, 341
Buddy system allocation, see Segregated-fits allocation, splitting cells
Buffered reference counting, see Concurrent reference counting, buffered
C, 104, 106, 161, 162, 165, 168, 170, 171, 182, 185, 188
C++, 3, 59, 104, 170, 185, 188, 340, 346
C++0x, 3
destructors, 220
Standard Template Library, 3
C4 collector, see Concurrent copying and compaction, Pauseless collector
Cache behaviour, 78–80, 133, 191, 208, see also Locality
alignment effects, 97
block-based allocation, 95
mutator performance, see Copying, improves mutator performance
next-fit allocation, 90
partitioning by kind, 105
sequential allocation, 88
threaded compaction, 38
Treadmill collector, 139
Two-Finger algorithm, 34
Cache hits, 231
Cache lines, 12, 152, 230, 231
dirty, 231
false sharing, 232
victim, 231
Caches
associativity
direct-mapped, 231
fully-associative, 231
set-associative, 231
contention, 233
exclusive/inclusive, 231
levels, 231
replacement policy, 231
write-through, 231
Canonicalisation tables, 221, 222
Card tables, 12, 124, 151, 156, 193, 197–201, see also Crossing maps
concurrent collection, 318–321
space overhead, 198
two-level, 199
Write, 198
Cards, 12
Cartesian trees, see Free-list allocation, Cartesian trees
Cells, 12
Cheney scanning, see Baker’s algorithm, Copying; Copying, work list
for partitioning, 108
Circular buffers, see Concurrent data structures: queues, bounded; buffers
Closures, 1, 8, 99, 125, 132, 162, 170, 190, 216, 341
Cold, see Hot and cold
collect, 174
Baker’s algorithm, 339
basic mark-sweep, 18
concurrent mark-sweep (collectEnough), 324
concurrent reference counting
age-oriented, 371
buffered, 367
sliding views, 371
copying, 52
semispace, 45
generational, abstract, 135
incremental tracing (collectTracingInc), 333
mark-compact, 32
real-time collection, replicating, 382
reference counting
abstract, 83
abstract deferred, 84
coalesced, 65
deferred, 62
tracing, abstract, 82
collectNursery, 135
Collector, 12
collectorOn/Off, real-time collection, replicating, 382, 383
compact
Compressor, 40
threaded compaction (Jonkers), 37
concurrent, see Concurrent copying and compaction
incremental, see Hybrid mark-sweep, copying
need for, 40
Compressor, 302, see also Concurrent copying and compaction, compaction, Compressor
Compare-and-swap, 237–238, 243, see also Concurrency, hardware primitives, CompareAndSwap
CompareAndSet, 237
CompareAndSet2, 242
compareAndSetByLLSC, 239
CompareAndSetWide, 242
CompareAndSwap, 237, 239, 243, 252, 254, 257, 260, 281, 283, 285, 292, 343–345, 358, 360, 364–366, 378, 382, 406, 407, 409–412
CompareAndSwap2, 241, 242, 344, 365, 374
compareAndSwapByLLSC, 239
CompareAndSwapWide, 241, 242, 257, 406, 412
compareThenCompareAndSwap, 238
Compiler analysis, 132, 144–146
Compiler optimisations, 6, 10, 53, 61, 104, 148, 168, 187, 190, 192, 211, 218, 226, 235, 270, 323, 341, 382, 394
Compiler replay, 10
partitioned collection, 109
computeLocations, mark-compact, 35
Concurrency, 56, see also Lock-free algorithms; Wait-free algorithms
consensus algorithms, 240, 243, 247, 248
consensus number, 240
happens-before, 236
hardware primitives, 233, 234, 237–242, see also top-level entries for primitives
AtomicAdd, 241
AtomicDecrement, 241
AtomicExchange, 233
AtomicIncrement, 241
CompareAndSet2, 242
CompareAndSetWide, 242
CompareAndSet, 237
CompareAndSwap, 237
CompareAndSwap2, 242
CompareAndSwapWide, 242
FetchAndAdd, 241
LoadLinked, 238
relative power, 240
StoreConditionally, 238
TestAndSet, 234
linearisability, see Linearisability
livelock, 244
memory consistency, 234–237, 378
acquire-release model, 236
causal, 236
memory order, 235
program order, 235
relaxed, 237, 265, 331, 373–374
release, 236
sequential, 236
strict, 236
memory fences, 236, 245, 246, 285, 374, 407
mutual exclusion, 246–248, 253, 254
Peterson’s algorithm, 247
lock-free, 243
mutual exclusion, 246
obstruction-free, 243
wait-free, 243
shared memory, 231
Concurrent algorithms, see also Concurrent collection
Concurrent collection, 7, 244, 275, 276, 307–321, see also specific concurrent collection algorithms
abstract, see Abstract concurrent collection
collector liveness, 309, 313, 344
compaction, see Concurrent copying and compaction
copying, see Concurrent copying and compaction
deletion barriers, 317, 318, 328, 329, 345, 391
Abraham and Patel, see Yuasa
logging, 331
Yuasa, 317, 318, 323, 329, 330, 335, 378
handshakes, 328, 329, 331, 343, 369–371, 373, 394
incremental update approach, 314
Dijkstra et al, 315, 318, 323, 326, 329, 330, 335, 340, 370, 386, 413
Steele, 315, 318, 323, 326, 335
mark-sweep, see Concurrent mark-sweep
on-the-fly, 107, 308, 309, 313, 332, see also specific concurrent collection algorithms
progress guarantees, 244
read barriers, 314–321, 323, 346
Brooks’s indirection barriers, see Brooks’s indirection barriers
Pauseless, 355
replicating, see Concurrent copying and compaction, replicating collection
snapshot-at-the-beginning approach, 314
termination, 244, 248–252, 313, 332
work list, 319
write barriers, 314–321, 330, 348
on-the-fly mark-sweep, 329
time overhead, 342
Concurrent copying and compaction, 337–361
Baker’s algorithm, see Baker’s algorithm
C4 collector, see Concurrent copying and compaction, Pauseless collector
compaction, 351–361, 391, see also Concurrent copying and compaction, Pauseless collector
Compressor, 352–354, see also Compaction, parallel, Compressor
mostly-concurrent, see Baker’s algorithm
fromspace and tospace invariants, 337, 341, 345, 378
mostly-copying collection, 338–340
multi-version copying, 342–345
real-time, see Real-time collection, compaction
replicating collection, 289, 341–351, see also multi-version copying
real-time, see Real-time collection, replicating
Sapphire collector, 345–351, 386
copyWord, 350
Java volatile fields, 351
Write, see Write, Sapphire phases
write barriers, 349
Concurrent data structures, 253–267
circular buffers, see queues, bounded; buffers
coarse-grained locking, see Locks, coarse-grained locking
fine-grained locking, see Locks, fine-grained locking
lazy update, 255
non-blocking, 255
optimistic locking, see Locks, optimistic locking
bounded, 256, 259, 261–268, 271
double-ended, see deques
Concurrent mark-sweep, 323–335, 391
abstract, see Abstract concurrent collection
collect (collectEnough), 324
insertion barriers
Dijkstra et al, 331
New, 324
sliding views, 331
sweeping, 330
concurrently with marking, 326–328
termination, 324–326, 328, 330
triggering collection, 323–324
Concurrent reference counting, 363–374
New, 372
Write, 372
collect, 367
Write, 367
coalesced, 368–369, see also sliding views
Write, 370
cycles, 366–369, 372–373, see also Recycler algorithm, asynchronous
deferred, 366, see also buffered
generational, 369, see age-oriented
on-the-fly, see sliding views
collect, 371
New, 372
snapshot of heap, see coalesced
snooping write barrier, 370
trial deletion, 373, see also Recycler algorithm
Connectivity-based collection, 143–144
time overhead, 144
Conservative collection, 30, 104, 105, see also Boehm-Demers-Weiser collector
bitmap marking, 23
copy
Baker’s algorithm, 339
copying, semispace, 45
Copy reserve, see Copying, copy reserve
Copying, 17, 43–56, 79, 126, 127, 140, 152, 157, 158, see also Hybrid mark-sweep, copying
allocate, 44
approximately depth-first, see traversal order
asymptotic complexity, 54
breadth-first, see traversal order
Cheney scanning, 46–48, 139, 145, 146, 150, 156, 294, 295, 338, 386
parallel, 289
termination, 46
concurrent, 312, see Concurrent copying and compaction
copy, 45
copy reserve, 54, 116, 119, 121, 122, 126–128, 137, 139, 149, 154
depth-first, see traversal order
flip, 45
flipping, 139
forwarding addresses, see Forwarding addresses, copying collection
fragmentation solution, 43
hierarchical decomposition, see Hierarchical decomposition
improves mutator performance, 49–53, 106
mostly-copying collection, 30, 104
moving objects, 55
optimal object order, 49
order, see traversal order
paging behaviour, 50
card tables, 298
Cheng, see Blelloch and Cheng
Cheng and Blelloch, see Blelloch and Cheng
dominant-thread tracing, 293
generational, 298
Marlow et al, 296
Oancea et al, see channels
Ogasawara, see dominant-thread tracing
remembered sets, 298
rooms, 382, see Blelloch and Cheng
online, 52
replicating collection, see Concurrent copying and compaction, replicating collection
scan, 45
semispace, 43–56, 78, 102, 139, 192
allocation issues, 53
flipping, 43
overview, 43
termination, 44
traversal order, 46–53, 139, see also Hierarchical decomposition
approximately depth-first, 50, 51
stack, 44
copyWord (Sapphire), 350
countingLock, 254
Critical sections, see Concurrency, mutual exclusion
Crossing maps, 101, 182, 199–201, see also Card tables; Heap parsing
search, 200
Custom allocators, see Allocators,
custom
Cyclic data structures, 3, 140, 157, see also Reference counting, cycles
segregating, 105
Cyclone, 106
Dangling pointers, see Pointers, dangling
Deadlock, 2
decNursery, 136
decrementOld, reference counting, coalesced, 65
Demographics, of objects, 105
Dependent loads, 235
Deques, see Concurrent data structures: deques; queues
Derived pointers, see Pointers, derived
Dijkstra, see Concurrent collection, insertion barriers
Dynamic memory allocation
description, 1
heap allocation, 1
Eden, see Generational collection: generation, young; nursery
enterRoom, 291
Ephemeral collection, see Generational collection
Ephemerons, 227, see also References, weak
Ergonomic collector, see HotSpot collector
Erlang, 146, see also Functional languages
Escape analysis, see Compiler analysis, escape analysis
Evacuating, 43
Evacuation threshold, see Hybrid mark-sweep, copying
exchangeLock, 233
exitRoom, 291
Explicit deallocation, see Deallocation, explicit
Explicit freeing, see Deallocation, explicit
External pointers, see Pointers, external
False sharing, see Cache lines, false sharing
Fast and slow path, 80, 164, 165, 191
block-structured allocation, 53
Fast-fits allocation, see Free-list allocation, Cartesian trees
Fat pointers, see Pointers, fat
FetchAndAdd, 241, 264, 265, 289–291, 377, 382, 383
Fields, 12
Finalisation, 13, 213–221, 223, 224, 330
C++, 220
context, 216
cycles of objects, 218
errors, 217
Lisp, 220
reference counting, 214, 216, 220
First-fit, see Free-list allocation, first-fit
Fixed-points, 81
flip
Baker’s algorithm, 339
concurrent copying and compaction
multi-version copying, 343
copying, semispace, 45
Floating garbage, 7, 79, 106, 113, 313, 327, 328, 330
Forwarding addresses, 8, 36, 42, 126, 147, 299, 390, 405, 406
allocation, 98
Baker’s algorithm, 339
copying collection, 44, 292, 300, 305, 340, 342–345, 378–379, 389
Sapphire, 349
Two-Finger algorithm, 32
Fragmentation, 30–31, 53, 78, 93, 105, 149, 152, 154, 296, 300, 391, 415
asymptotic lower bound, 30
block-based allocation, 96
copying eliminates, 43
external and internal, 95
large objects, 137
mark-sweep, 41
negative effects, 93
next-fit allocation, 90
old generation, 126
pinned objects, 186
segregated-fits allocation, 95
generational write barrier, 205
partitioning, 109
free, 14
Free pointer, 87
Free-list allocation, 87–93, 102, 105, 126, 137, 151, 299
balanced trees, 92
best-fit, 91
allocate, 91
Cartesian trees, 92
allocate, 92
circular first-fit, see next-fit
combining multiple schemes, 96–97
allocate, 89
characteristics of, 90
locality, 54
multiple lists, 93
allocate, 91
cache behaviour, 90
drawbacks of, 90
space overhead, 89
splay trees, 92
Fromspace, 43
Fromspace invariant, see Concurrent copying and compaction, fromspace and tospace invariants
Functional languages, 73, 115, 161, 190, see also Erlang; Haskell; ML
pure, 66
Fundamental algorithms for garbage collection, 17
Garbage, 14
Garbage collection
abstract algorithms, 81–85, see also Abstract specific collection algorithms
advantages, 4
chaotic nature, 11
correctness, 6
criticisms, 4
experimental methodology, 10
importance, 3
memory leaks, 4
optimisations for specific languages, 8
partitioning the heap, see Partitioned collection
performance, 9
portability, 9
safety issues, 6, 309, 313, 344
scalability, 9
space overhead, 8
tasks of, 17
Garbage collection of code, 190
Garbage-First collector, see Generational collection, Garbage-First collector
GC-points, 179–180, 187–189, 279, 355, 356, 358, 378, 394, 400, 402, 403, 405, 407
GC-safe points, see GC-points
generateWork, 278, 281, 283, 287, 288, 290
Generational collection, 103, 107, 109, 111–135, 146, 154, 157, 158, 171, 191, 192, 296, 322, see also Age-based collection
abstract, see Abstract generational collection
high water mark, 120
in header word, 118
Appel-style, 121–122, 126, 127, 144, 208, 209
defining, 122
bucket, 114
bucket brigade system, 118–120
card marking and scanning, see Card tables
Eden, see generation, young; nursery
full heap collection, 115, 121–123, 126, 127, 133
Garbage-First collector, 151
generation, 111
young, 106, 111, 119, 125, 126, 133, 145
generational hypothesis, 113–114
strong, 114
weak, 106, 111, 113, 121, 130, 370
inter-generational pointers, see Pointers, inter-generational
large object space, 114
major collection, see full heap collection
Mature Object Space, see Mature Object Space collector
measuring time, 113
minor collection, 112, 113, 115, 116, 119, 120, 122, 123
nursery collection, 112, 121, 126, 127, 133, 141, 146, 157
promoting, 110, 111, 112–117, 121, 127, 130, 132–134
feedback, 123
read barriers, see Read barriers
reference counting, see Concurrent reference counting, age-oriented
remembered sets, see Remembered sets
sequential store buffers, see Remembered sets, sequential store buffers
space overhead, 119, 121, 122, 126–127, 133
step, 114, 118, 119, 128, 132, 134, 296
survival rate, see Survival rate
tenuring, 111
threatening boundary scheme, 123
throughput, 111
Ulterior reference counting, see Ulterior reference counting
write barriers, see Write barriers
Generational hypothesis, see Generational collection, generational hypothesis
Granules, 11
Grey (colour), see Tricolour abstraction
Grey mutator, see Tricolour abstraction, mutator colour
Grey packets, see Marking, parallel, grey packets
Grey protected, see Objects, grey protected
advantages, 1
happens-before, see Concurrency, happens-before
Hash consing, see Allocation, hash consing
Haskell, 8, 113, 118, 125, 161, 162, 165, 170, 171, 228, 292, 296, 341, see also Functional languages
Heap layout, 203–205, see also Virtual memory techniques and specific collection algorithms
Heap nodes, 12
Heap parsing, 20, 166, 168, 170, 182, see also Allocation, heap parsability
Heaplets, see Thread-local heaps
Heaps, 11
block-structured, 22, 31, 122, 152, 166–168, 183, 294–297
relocating, 205
Hierarchical decomposition, 51–53, 55, 296, 297
objects, 53
HotSpot collector, 41, 107, 108, 119, 150, 165, 201
Ergonomics, 123
Hybrid copying, reference-counting, see Ulterior reference counting
Hybrid mark-sweep, copying, 149–156, see also Copying, mostly-copying collection; Immix; Mark-Copy
Garbage-First collector, 150–151
incremental incrementally compacting collector, 150
Hybrid reference counting, mark-sweep, 366, 370
Hyperthreading, see Multithreading, simultaneous
IBM, 151
allocate, 153
Immortal data, 41
Implementation, difficulty, 79–80
incNursery, 136
Incremental collection, 7, 139, 275, 307–308
Baker’s algorithm, see Baker’s algorithm
incremental incrementally compacting collector, 150
Treadmill collector, see Treadmill collector
Incremental compaction, see Hybrid mark-sweep, copying
incrementNew
concurrent reference counting
coalesced, 369
reference counting, coalesced, 65
Interesting pointers, see Pointers, interesting
Interior pointers, see Pointers, interior
J9, 296
Jamaica (Java virtual machine), 282, 412, 415
Java, 106, 113, 124, 125, 145, 151, 152, 162–165, 169–172, 179, 185, 190, 201, 209, 215, 216, 218, 219, 223, 224, 234, 282, 296, 330, 341, 346, 356, 360, 391, 405, 406, 412
pointer equality, 347
Real-Time Specification for, 148
volatile fields, 346, 351, 406
Java Native Interface, 104, 394
Java virtual machines, 116, 138, see also ExactVM; HotSpot; J9; Jamaica; Jikes RVM; JRockit
switching collectors, 6
JavaScript, 228
Jonkers’s threaded compactor, see Mark-compact, Jonkers
JRockit, 138
JVM, see Java virtual machine
Large object space, 94, 104, 110, 137–140, 152, see also Objects, large; Treadmill collector
generational collection, 114, 124
Large objects, see Objects, large
Lazy sweeping, see Sweeping, lazy
lazySweep, 25
Lifetime of objects, 105, 114, 121, 132, 143, 147, see also Generational collection, measuring time
Linearisability, 253
Lisp, 50, 58, 113, 115, 124, 162, 164, 169, 171, 190, 220, 226, 323, 384, see also Scheme
Lisp 2 algorithm, see Mark-compact, Lisp 2 algorithm
Livelock, 2, see Concurrency, livelock
concurrent collector, see Concurrent collection, collector liveness
Load balancing, 277–278, 279, 280, 282, 285, 288, 294, 298–300, 303–305
dynamic, 277
over-partitioning, 278
static, 277
Load-linked/store-conditionally, 238–239, 245, 289, 350, 378, see also Concurrency, hardware primitives: LoadLinked; StoreConditionally
LoadLinked, 238, 239, 257, 260, 264–266, 268, 350, see also Concurrency, hardware primitives, LoadLinked
Local allocation buffers, see Allocation, local allocation buffers
Locality, 78, 279, 296, 297, 304, see also Cache behaviour; Paging behaviour
after copying, 46
copying, 46
free-list allocation, 54
lazy sweeping, 26
parallel copying, 292
sequential allocation, 54
Two-Finger algorithm, 34
Lock-free algorithms, 243, 244, 249, 251, 255–257, 260, 261, 263–268, 271, 280, 342–345, 374, 406, 410, see also Concurrency, progress guarantees, lock-free
coarse-grained locking, 254
exchangeLock, 233
fine-grained locking, 254, 256, 258, 259, 261–263
lock coupling, 255
optimistic locking, 255
spin, 232
AtomicExchange, 233
TestAndSet, 234
test then test then set, 240
test then test-and-set, 240
test-and-test-and-set, 233
testAndSetLock, 234
testAndTestAndSetExchangeLock, 233
Logic programming languages, 9, 299
Lost object problem, see Concurrent collection, lost object problem
Mach operating system, 209
Machine learning, 80
Major collection, see Generational collection, full heap collection
Managed languages, 1
Managed run-time systems, 1
Managing machine code, 105
Many-core processors, 230
mark
basic, 24
basic mark-sweep, 19
marking edges, 28
Mark-compact, 17, 31–42, 79, 111, 126, 127, 184, see also Hybrid; Mark-sweep
arbitrary order, 31
collect, 32
compact phase, 31
compaction
cache behaviour, 38
one-pass, 38
three-pass, 34
computeLocations, 35
limitations, 42
linearising compaction, 31
locality, 32
mark phase, 31
parallel compactors, 36
sliding compaction, 31
threaded compaction, 32, 36–38
parallel, 299
threading pointers, 36
Two-Finger algorithm, 32–34, 36, 184
Mark-compact, time overhead, 32
space overhead, 154
Mark-sweep, 17–30, 122, 126, 137, 146, see also Mark-compact; Marking; Sweeping
asymptotic complexity, 24
basic algorithm, 18
concurrent, 296, see Concurrent mark-sweep
heap layout, 20
lazy sweeping, see Sweeping, lazy
mutator overhead, 29
sweep, 20
termination of basic algorithm, 19
throughput, 29
time overhead, 24
tricolour marking, 20
Mark/cons ratio, 6, 54, 111, 129, 144
copying and mark-sweep compared, 55
markFromRoots, basic mark-sweep, 19
Marking, 153
asymptotic complexity, 276
atomicity, 22
concurrent, see Concurrent mark-sweep
incremental, 155
mark, 28
overflow, 24
order (breadth-first, depth-first), 27
paging, 23
Barabash et al, see grey packets
Endo et al, 280, 281, 283, 289
Flood et al, 278, 280, 282–284, 288, 289
grey packets, 282, 284–288, 296
Ossia et al, see grey packets
Siebert [2008], 276
termination, see Concurrent collection, termination
Wu and Li, see using channels
prefetching, see Prefetching, marking
time overhead, 27
Marmot, 138
Mature Object Space collector, 109, 130, 140–143, 151, 194, 208
time overhead, 143
Measurement bias, 10
Memory affinity, 293
Memory consistency, see Concurrency, memory consistency
Memory fences, 243, see Concurrency, memory fences
Memory leaks, 2
Mercury, 171
Metronome collector, 391–399, 402, 407, 413, see also Real-time collection, Tax-and-Spend
generational collection, 399
handshakes, 394
mutator utilisation, 391–393, 395
read barriers, 393
robustness, 399
root scanning, 394
scheduling, 394
sensitivity, 397
syncopation, 399
time and space analysis, 395–399
write barriers, 397
Minimum mutator utilisation, 7, 377, 384, 391–393, 396, 398–400, 409
Minor collection, see Generational collection, minor collection
ML, 8, 106, 113, 121, 124, 125, 146, 148, 162, 165, 170, 171, 201, 208, 209, 228, 329, 330, 342, 384, see also Functional languages
MMTk, 26, 116, 195, 196, see also Jikes RVM
MMU, see Minimum mutator utilisation
Moon’s algorithm, see Copying, Moon’s algorithm
Mortality of objects, 105
Mostly-concurrent collection, see Baker’s algorithm
Mostly-copying collection, see Copying, mostly-copying collection; Concurrent copying and compaction, mostly-copying collection
Motorola MC68000, 169
Moving objects, 55
Multi-tasking virtual machine, 107
Multi-version copying, see Concurrent copying and compaction, multi-version copying
Multiprocessors, 230
chip, 230
many-core, 230
multicore, 230
symmetric, 230
Multiprogramming, 230
Multisets, definition and notation, 15
Multithreading, 230
simultaneous, 230
Mutator, 12
performance, see Copying, improves mutator performance
threads, see Mutator threads
Mutator colour (black or grey), see Tricolour abstract, mutator colour
Mutator overhead, see specific collection algorithms
Mutator suspension, see GC-points
Mutator utilisation, 7, 385, 391–393, 395, see also Bounded mutator utilisation; Minimum mutator utilisation
Tax-and-Spend, 400
Mutual exclusion, see Concurrency, mutual exclusion
Nepotism, see Generational collection, nepotism
New
basic mark-sweep, 18
concurrent mark-sweep, 324
concurrent reference counting
age-oriented, 372
sliding views, 372
generational, abstract, 136
incremental tracing, 333
real-time collection
slack-based, 389
reference counting, abstract, 83
tracing, abstract, 82
Next-fit, see Free-list allocation, next-fit
NMT, see Not-Marked-Through
Non-uniform memory access, 230, 292–293, 298, 344, 345
Nursery, see Generational collection, generation, young
Object inlining, see Scalar replacement
Object layout, bidirectional, 170
Object-oriented languages, 169
per-class GC methods, 170, 341
Objects, 12
cold, see Hot and cold, objects
grey, 43
grey protected, 312
hot, see Hot and cold, objects
immortal, 110, 124, 126, 132–134
Java Reference, see References, weak
large, 56, 114, 138, 151, 152, 201, see also Large object space
pointer-free, 140
pointer-free, 140
Obstruction-free algorithms, 243, 255, see also Concurrency, progress guarantees, obstruction-free
Old generation, see Generational collection, generation, old
Older-first collection, 127–129, 131, see also Age-based collection
renewal older-first, 128
On-stack replacement (of method code), 190
On-the-fly collection, see Concurrent collection, on-the-fly and specific concurrent collection algorithms
Opportunistic collector, 120, 121
Over-partitioning, see Load balancing, over-partitioning
Ownership of objects, 3
Page faults, see Paging behaviour
Pages, 12
Paging behaviour, see Bookmarking collector; Copying, paging behaviour; Marking, paging
Parallel collection, 7, 244, 275–306, 308
correctness, 278
grey packets, see Marking, parallel, grey packets
load balancing, see Load balancing
memory-centric, 279
parallel sweeping, see Sweeping, parallel
parallelisation concerns, 276–277
processor-centric, 279
termination, 279, 283–284, 289, 300
Partitioned collection, 103–110
non-age-based schemes, 137–159, see also Conectivity-based collection; Hybrid mark-sweep, copying; Large object space; Mature Object Space collection; Thread-local collection
partitioning approaches, 108–109
partitioning by age, 109
partitioning by availability, 107–108
partitioning by kind, 105
cache behaviour, 105
partitioning by mobility, 104
partitioning by mutability, 108
partitioning by size, 104
partitioning by thread, 107
partitioning for locality, 106–107
partitioning for space, 104–105
partitioning for yield, 105–106
partitioning to reduce pause time, 106
reclaiming whole regions, 106, 148
space overhead, 105
Pause time, 7, 78, 140, 144, 156, 275, 335, 342, 375, 384, 391, 393, 394, 415
generational collection, 111, 123, 133
sweeping, 24
Pauseless collector, see Concurrent copying and compaction, Pauseless collector
performWork, 278, 281, 283, 287, 288, 290
perl, 58
Peterson’s algorithm, see Concurrency, Peterson’s algorithm
Pinning objects, 104, 109, 183, 185–186
ambiguous, 166
dangling, garbage collection as prevention for, 3
derived, 173, 181, 183–184, 186
direction, 125–126, 128, 144–146
fat, 2
in global roots, 171
stack maps, 172–173, 175, 176, 178, 179
hazard, 374
inter-generational, 112, 113, 115, 123–126, 134, 154, 191
interesting, 124, 125, 128, 130, 132, 151, 191–193
interior, 32, 34, 38, 166, 168, 173, 181, 182–183, 184, 186
shared, 59
strong, see References, strong
tidy, 183
weak, see References, weak
Pointers, 13
Poor Richard’s Memory Manager, 210
PowerPC architecture, 262, 298, 407
Precision, of concurrent collection, 313, 334–335
compaction, 36
reference counting, coalesced, 64
Two-Finger algorithm, 34
Pretenuring, see Generational collection, pretenuring
Primitives, see Concurrency, hardware primitives
Processor affinity scheduling, 293
Processors, 229
finalisation, 217
generational collection, 111
reference counting, 73
Pseudo-code for algorithms, 14
Queues, see Concurrent data structures, queues
α-reachable, 223
phantom-reachable, 224
softly-reachable, 223
strongly reachable, 221
weakly-reachable, 221
Read, 15
Brooks’s indirection barriers, 341
concurrent reference counting, 364, 365
Pauseless collector, 356
real-time collection
Chicken, 410
Clover, 411
incremental replicating, 405
slack-based, 389
Staccato, 409
Read barriers, 14, 53, 110, 147, 170, 191–192
Baker’s algorithm, 338
concurrent collection, see Concurrent collection, read barriers
Metronome, 393
time overhead, 323
Real-time collection, 245, 375–415
Blelloch and Cheng, see replicating
Read, 410
Write, 410
Read, 411
Write, 411
combined scheduling strategies, see Tax-and-Spend
incremental replicating, 405–406
Read, 405
Write, 405
lock-free, see Clover and Stopless
Metronome, see Metronome collector
replicating, 377–384, see also incremental replicating
collect, 382
time and space bounds, 384
slack-based, 377, 386–391, 401
collector, 388
lazy evacuation, 387
New, 389
Read, 389
time overheads, 390
Write, 389
write barriers, 386
Read, 409
Write, 409
mutator utilisation, 400
termination, 403
time-based, 377, see also Metronome collector
wait-free, see Chicken and Staccato
work-based, 377–385, 391, see also replicating
time and space analysis, 398–399
hard and soft, 375
multitasking, 376
schedulability analysis, 376, 384
tasks, 376
WCET, see worst-case execution time
worst-case execution time, 376, 384, 385, 390, 413
Recycler algorithm, 68–70, 157
asymptotic complexity, 72
Reference counting, 3, 17, 18, 57–75, 79, 108, 146, 157, 275
abstract, see Abstract reference counting
advantages and disadvantages, 58, 73
buffered, 60, see Buffered reference counting
coalesced, 63–66, 74, 78, 82, 157
collect, 65
decrementOld, 65
incrementNew, 65
Write, 64
concurrent, see Concurrent reference counting
counter overflow, 73
cycles, 59, 66–72, 74, 79, see also Recycler algorithm
deferred, 60, 61–66, 74, 78, 79, 157, 366
collect, 62
performance, 63
Write, 62
zero count table, 61, 366, 372
generational, see Concurrent reference counting, age-oriented
lazy, 60
promptness, 73
simple, 79
Write, 58
sliding views, 60
smart pointers, see Pointers, smart
sticky counts, 73
throughput, 74
trial deletion, 67–72, 373, see also Recycler algorithm
ulterior, see Ulterior reference counting
weak pointer algorithms, 67
weak references, 224
References, 12
accessing heap allocated objects, 1
counting, see Reference counting
phantom, 224
strong, 221
weak, 67, 169, 218, 221–228, 330, 360
Region inference, see Partitioned collection, reclaiming whole regions
relocate, mark-compact, 33, 35
Remembered sets, 113, 124–125, 126, 128, 134, 141, 143, 144, 151, 154, 157, 191, 192, 193, see also Card tables; Chunked lists
card tables, see Card tables
sequential store buffers, see Sequential store buffers
Remsets, see Remembered sets
Rendezvous barriers, 251–253, 382
Replicating collection, see Copying, concurrent, replicating
Resurrection of objects, see Finalisation, resurrection
Roots, 12
Roots, 13
rootsNursery, 135
Run-times
interface, see Run-time interface
managed, 1
Sapphire collector, see Concurrent copying and compaction, Sapphire collector
Scalar replacement, 148
Scalars, 12
scan
copying, semispace, 45
incremental tracing (scanTracingInc), 333
scanNursery, 135
Scheme, 121, 128, 170, see also Lisp
Segregated-fits allocation, 23, 30, 41, 54, 93–95, 102, 104, 157, 165, 299
allocate, 95
cache behaviour, 95
space overhead, 96
buddy system, 96
splitting cells, 96
Self-adjusting trees, 92
Semispace copying, see Copying, semispace
Sequences, definition and notation, 15
Sequential allocation, 31, 44, 54, 87–88, 102, 105, 126, 133, 151–153, 157, 164, 165, 294, 301
cache behaviour, 88
locality, 54
Sequential store buffers, 156, 193, 195–196, 207, see also Chunked lists
Write, 195
Sequential-fits allocation, see Free-list allocation
Sets, definition and notation, 15
shared, 245
Shared pointers, see Pointers, shared
SITBOL, 41
Sliding views, see Reference counting, coaleseced; Concurrent mark-sweep, sliding views
Slow path, see Fast and slow path
Smalltalk, 50, 58, 113, 115, 168, 171, 185, 193, 228
Smart pointers, see Pointers, smart
Space leak, see Memory leak
Space overhead, see specific collection algorithms
SPARC architecture, 168, 197, 300
Splay trees, 92
Staccato collector, see Real-time collection, Staccato
Stack barriers, 170, 186–187, 328, 384
Stack frames, 171–179, 186–187
Stack maps, 188, see Pointers, finding, stack maps
Stacks, see Concurrent data structures, stacks
Standard Template Library, see C++, Standard Template Library
Steele, see Concurrent collection, insertion barriers
Step, see Generational collection, step
Stop-the-world collection, 275, 276
Stopless collector, see Real-time collection, Stopless
Store buffers, see Write buffers
StoreConditionally, 238, 239, 257, 260, 264–268, 350, see also Concurrency, hardware primitives, StoreConditionally
Survivor spaces, see Generational Collection, survivor spaces
sweep, basic mark-sweep, 20
allocate, 25
bitmaps, 23
concurrent, see Concurrent mark-sweep
lazy, 24–26, 55, 78, 95, 299, 326
lazySweep, 25
parallel, 299
pause time, 24
sweepNursery, 135
Tax-and-Spend scheduling, see Real-time collection, Tax-and-Spend
Tenuring objects, see Generation collection, promoting objects
testAndExchange, 233
TestAndSet, 233, 234, 241, 377, 379, 382
testAndSetLock, 234
testAndTestAndSet, 234
testAndTestAndSetExchangeLock, 233
testAndTestAndSetLock, 234
Thread-local collection, 144–147
space overhead, 147
Thread-local heaps, 101, 107, 108, 109, 110, 144–147, 230, 329
Thread-local log buffers, 342
Threaded compaction, see Mark-compact, threaded compaction
Throughput, 6, 77–78, 208, see also specific collection algorithms
ThruMax algorithm, see Adaptive systems, ThruMax algorithm
Time overhead, see specific collection algorithms
Time, measuring, see Generational collection, measuring time
Tospace, 43
Tospace invariant, see Concurrent copying and compaction, fromspace and tospace invariants
Tracing, see Copying; Mark-compact; Mark-sweep
abstract, see Abstract tracing
Train collector, see Mature Object Space collector
hardware, 271
abort and commit, 269
transitionRooms, 291
Traversal order, see Copying, traversal order
Treadmill collector, 104, 138–139, 361, see also Large object space
cache behaviour, 139
space overhead, 139
time overhead, 139
Tricolour abstraction, 20–21, see also Anthracite; Purple; Yellow
abstract concurrent collection, 334
abstract tracing, 81
concurrent collection, 309–313, 352
concurrent reference counting, 370
mutator colour, 313, 314, 324, 325, 328, 329, 336, 337, 340
strong and weak tricolour invariants, 312–313, 324, 325, 391
Treadmill collector, 138
Tuples, definition and notation, 15
Two-finger algorithm, see Mark-compact, Two-Finger algorithm
cache behaviour, 34
Type information
BiBoP, see Big Bag of Pages technique
Type-accurate collection, 23, 104
Ulterior reference counting, 157–158
UMass GC Toolkit, 118
Unique pointers, see Pointers, unique
Unreachable, 14
updateReferences, mark-compact, 33, 35
Virtual machine, see Java virtual machine; Multi-tasking virtual machine
Virtual memory, see also Paging behaviour
Virtual memory techniques, 140, 165, 193, 202, 203–210
double mapping, 206, 352, 355–361
guard pages, see page protection
page protection, 140, 195, 205–208, 317, 340, 352–361
Wait-free algorithms, 243, 255, 261, 271, 301, 302, 410, 415, see also Concurrency, progress guarantees, wait-free
Wavefront, 20
concurrent collection, 310, 334, 338, 340
Weak references, see References, weak
White (colour), see Tricolour abstraction
Wilderness preservation, 100, 152
Work lists, 324, 338, see also Chunked lists
Work pulling, see Work stealing
Work pushing, see Work sharing
Work sharing, 248–252, 303–305, see also Work stealing
Work stealing, 248–252, 267–268, 279–284, 292, 299, 303–305, 342, see also Work sharing
stealable work queue, 280
termination, see Concurrent collection, termination
Brooks’s indirection barriers, 341
card table on SPARC, 198
concurrent reference counting, 364, 365
age-oriented, 372
concurrent reference counting, coalesced, 370
generational, abstract, 136
generational, with frames, 205
incremental tracing, 333
multi-version copying, 344
real-time collection
Chicken, 410
Clover, 411
incremental replicating, 405
slack-based, 389
reference counting
abstract, 83
abstract deferred, 84
coalesced, 64
deferred, 62
simple, 58
sequential store buffer, 195
Staccato, 409
Write barriers, 14, 57, 67, 109, 110, 132, 144, 146–148, 151, 154, 155, 157, 162, 188, 191–205
abstract concurrent collection, 334
card tables, see Card tables
concurrent collection, see Concurrent collection, write barriers
generational, 112, 115, 119, 124–126, 133, 134
Metronome, 397
reference counting
deferred, 62
performance, 61
simple, 58
sequential store buffers, see Sequential store buffers
when required, 57
Write buffers, 235
Yellow (colour), 326
Young generation, see Generational collection, generation, young
Yuasa, see Concurrent collection, deletion barriers
Zero count table, see Reference counting, deferred, zero count table
Colophon
This book was set in Palatino (algorithms in Courier) with PDFLATEX (from the TEX Live 2015 distribution). The Illustrations were drawn with Adobe Illustrator CS3. We found the following packages to be useful: comment (comments), paralist (in-paragraph lists), geometry (page size), crop (crop marks), xspace (space suppression), setspace (line spacing), fnbreak (detect footnotes spread over more than one page), afterpage (page break control), tabularx (tabular material), multicol (multiple columns), multirow (multiple rows/columns in tables), dcolumn (“decimal points” in tables), caption and subcaption (captions), graphicx and epstopdf (graphics), listings (algorithm listings), rotating (rotate objects), mathpazo (typesetting mathematics to match Palatino body text), amssymb and amsmath (mathematics), hyperref (hyperlinks), glossaries (glossaries), natbib (bibliography), makeidx and index (index).