Here we provide a list of corrections and improvements to the text of the 2012 printing of the book. The authors would be grateful for any corrections.
Last updated: January 2016
- Page xxv, line 1: Chapter 1 starts... 
- Chapter 1 Introduction
- Page 5, Table 1.1: This table should also include Lisp (1958) and its dialects .
- Chapter 2 Mark-sweep garbage collection
- Page 22, penultimate paragraph, first line: Bit maps should be Bitmaps.
- Page 23, line 6: Bitmap marking pre-dates conservative GC. Lisp 1.5 used bitmap marking
for full word space (Appendix G of the
Lisp 1.5 manual, page 90) .
- Page 25, Algorithm 2.4, line 1: add a colon after
- Page 25, last paragraph, 3rd line: the word class is duplicated.
- Page 26, line 5: The reference should be to Algorithm 7.7 .
- Page 26, line 19: the reclaimed should be be reclaimed
- Chapter 3 Mark-compact garbage collection
- Page 34: The last paragraph of section 3.1 raises the question of parsing the heap 'backwards'. Since the algorithm under discussion, Edwards's Two-Finger algorithm, requires objects to be a fixed size, this should not be a problem, although it maybe for algorithms that permit arbitrarily sized objects
- Page 38, section 3.4, line 6: delete can be
- Pages 38-40 and Figure 3.3: every bit corresponding to a live object in
the heap should be marked. The figure in the book used the mark-bits
inconsistently. The text on these pages should be updated to match .
On page 38, last paragraph:
"Marking sets the bits corresponding to all (or, more efficiently,
the first and the last) granules of each live object. For example, bits 44–51 are set for the object marked old in Figure 3.3."
On page 39, second paragraph:
"Bits 4–7, and 12–15 are set in the first block, and bits 6–11 in the second (in this example,
each block comprises 16 slots). This represents 14 granules (words) that are marked in the bitmap
before this object. Thus the first live object in block 2 will be relocated to the
fourteenth slot in the heap."
On page 40, last sentence of section 3.4:
"For example, the
old object in the figure has an offset of 6 marked slots in its block
so it is moved to slot 20:
- Page 41, line 5: sequential-fits should be segregated-fits
Repeated word of [5,2,6].
- Chapter 4, Copying Garbage Collection
- Page 43,
line 3 from the bottom:
copy should be
- Page 49, line 18: reserves should be preserves
- Page 53, line 7 from the bottom: implemented should be incremented .
- Page 55, line 2: that should be than .
- Chapter 5 Reference Counting
- Page 58, line 3 from the bottom: overload should be override .
- Page 63: note that a coalescing reference counter need not log initialising writes to an object as the reference fields are initially null. Indeed, to do so would be prohibitively expensive in time and space. Instead, it suffices to mark the object as initialised dirty.
- Page 69, Algorithm 5.5, line 41: add a colon after
- Page 72, Figure 5.4 should use camel-case names rather than underscores (as below).
- Chapter 7, Allocation
- Page 94, line 21: sk should be sk-1 [5,2,6].
- Chapter 9, Generational Garbage Collection
- Page 114, line 2: Smalltalk should be Smalltalk objects .
- Page 118, Figure 9.3: will be not be should be will not be [5,2,6].
- Page 118, footnote: The ExactVM paper has moved to http://dl.acm.org/citation.cfm?id=974971.
- Page 129, line 10 from the bottom: more precisely phrased as blocks older than the GC window have a higher time of death than younger ones
- Page 135, Algorithm 9.1, line 22: add a colon after
- Chapter 10 Other Partitioned Schemes
- Page 139, line 17: missing word the.
- Page 139, line 22: missing word the.
- Page 147, line 10 from the bottom: write buffer should be write barrier.
- Page 150, line 8 from the bottom, omitted word: in order provide compaction should be in order to provide compaction.
- Chapter 11 Run-time Interface
- Page 171, line 14: one kind of another should be one kind or another [5,2,6].
- Page 200 [5,2,6]:
- line 3: end of the card should be start of the card
- Algorithm 11.9, insert after line 3:
card ← card - 1
- Algorithm 11.9, delete line 8 (which assumed the offset was from the end of the card).
- Page 195, Algorithm 11.4, line 2 has a comma missing:
add %src, %i, %fld [5,2,6]
- Page 200, line 10: repeated word a [5,2,6].
- Page 201, Table 11.3: repeated word of.
- Page 201, line 9: greater that 384 should be greater than 384 [5,2,6].
- Page 208, line 9 from the bottom: the comma should be a full-stop.
- Page 210, penultimate line: if should be it [5,2,6].
- Chapter 12, Language-Specific Concerns
- Page 223, line 18: (α+1)-reachable should be (α+1)*-reachable [5,2,6].
- Chapter 13, Concurrency Preliminaries
- Page 243, line 15: the order of the progress guarantees,from strongest to weakest, should be wait-freedom, lock-freedom, obstruction-freedom.
- Chapter 14, Parallel Garbage Collection
- Page 281, Algorithm 14.1, line 18:
stealableWorkQueue[me] should be
- Page 284, line 14: the definitive citation is Petrank and Kolodner .
- Page 284, line 9 from the bottom: The suggestion to use a count of active threads was due to Peter Kessler [5,2,6].
- Page 286, Algorithm 14.4, line 28: should be
outPacket ← remove(halfFullPool) [5,2,6].
- Page 288, Algorithm 14.7, line 24:
needsWork(k) should be
- Page 288, Algorithm 14.7, line 25:
add(channel[me,j] should be
add(channel[me,j], ref) [5,2,6].
- Page 289, line 15: the definitive citation is Petrank and Kolodner .
- Page 293, Figure 14.4: the caption should refer to Threads 0 to 2, coloured grey, white and black respectively [5,2,6].
- Page 296, line 21: partially filled should be empty [5,2,6].
- Chapter 15, Concurrent Garbage Collection
- Page 319, line 23: repeated word might [5,2,6].
- Chapter 16, Concurrent Mark-Sweep
- Page 325, line 2: the example refers to Algorithm 16.2.
- Page 333, Algorithm 16.4: to be more consistent, all instances of
addOrigins() could have a parameter
- Chapter 17 Concurrent Copying & Compaction
- Page 346, line 13: for consistency, installation write barrier should be insertion write barrier.
- Page 346, line 7 from the bottom: the reference to the memory model for C++ should be
[Boehm and Adve, 2008]
- Chapter 18 Concurrent Reference Counting
- Page 370, lines 24 from the bottom:
ref black. Objects are allocated grey...
ref grey. Objects are allocated dirty ...
- Page 372, Algorithm 18.8, line 4: allocate dirty.
- Page 373, last paragraph, the parenthetical remark duplicates those and should read: (that is, they represent a snapshot of the modified object as it was before the collection cycle started).
- Chapter 19 Real-time garbage collection
- Page 385, line 4: collector should be mutator.
- Page 394, second line from the bottom: for consistency, installation write barrier should be insertion write barrier.
- Page 395, after equation (19.5): real t is better as real time t [5,2,6].
- Page 397, line 2: delete increment.
- Page 407, line 11: to be precise,
without requiring any locks, and without requiring atomic operations
is better as
without requiring the mutators to use locks or atomic operations
- Page 414, Figure 19.10(c): the word offset in the caption is misspelt. The negative offset from the spine is the same as in (d), not (b) [5,2,6].
We thank the following for drawing our attention to these errors:
- Carl Shapiro
- Atusi Maeda
- Roberto Cometti
- Raffaello Giulietti
- Tomoharu Ugawa
- Tsuneyasu Komiya