Errata and Addenda

Here, we include any corrections to the book. We also include as addenda points that we consider worthy of further clarification.

The authors would be grateful for any corrections.

Second edition

Chapter 3 Mark-Compact
Page 39, Algorithm 3.2: As written, relocate() may overwrite part of the object it just moved if scan-dest<size(scan); this might prevent obtaining the object's size on line 36. The solution is to calculate the next value of scan before move() is called [8].
Chapter 14 Concurrent garbage collection
A further issue to consider: Note that weak references add further complication to concurrent garbage collection [11]. As we explained in Section 17.4 in the discussion of Transactional Sapphire, a mutator acquiring a weak reference (e.g. Java's get()) causes the referent to become strongly-reachable. Thus, a deletion barrier on its own cannot maintain correctness, although an insertion barrier suffices. A deletion-barrier solution is to protect get() with a read barrier that shades the referent.
Chapter 20 Energy-aware garbage collection
Page 465: The model for dynamic power should be Pdyn = aCV2f [10]. As V must increase more or less linearly with f, Pdyn scales more like f α for some α where 2 < α < 3, as before.

Last updated: September 2023

First edition


2016 revised printing and e-book

Here we provide a list of corrections and improvements to the text of the 2016 revised printing and e-book, further to those of the 2012 edition.

Last updated: March 2023

Chapter 3 Mark-Compact
Page 35, Algorithm 3.2: As written, relocate() may overwrite part of the object it just moved if scan-dest<size(scan); this might prevent obtaining the object's size on line 36. The solution is to to calculate the next value of scan before move() is called [8].
Chapter 5 Reference Counting
Page 67: The asynchronous Recycler algorithm is discussed in Chapter 18, not Chapter 15.
Chapter 12 Language-Specific Concerns
Page 223, Footnote 5: The reference to Tomoharu et al [2014] has the first name rather than the surname of the first author. It should be Ugawa et al [2014], and similarly in the bibliography.
Chapter 10 Other Partitioned Schemes
Page 143, line 17: that are part should be they are part.
Chapter 11 Run-time Interface
Page 171, line 25: The systems named by the citations should be Non-Stop Haskell [Cheadle et al, 2000] and its later optimisation [Cheadle et al, 2004].
Chapter 12 Language-Specific Concerns
Page 223, line 6: delete the second is [9].
Chapter 17 Concurrent Copying & Compaction
Page 356, Algorithm 17.8: GCtrap() did not return a value but it should return newRef.
Chapter 18 Concurrent Reference Counting
Page 365, Algorithm 18.3: although the code correctly uses CompareAndSet2 (which returns a boolean), the caption and the paragraph of discussion incorrectly refer to CompareAndSwap2 (which returns the original value).
Bibliography
Page 463: The authors of Tomoharu, Richard Jones, and Carl G. Ritson. Reference object processing in on-the-fly garbage collection, ISMM 2014 should be Tomoharu Ugawa, Richard Jones, and Carl G. Ritson; other details are correct.

2012 printing

Here we provide a list of corrections and improvements to the text of the 2012 printing of the book.

Last updated: January 2016

Preface
Page xxv, line 1: Chapter 1 starts... [4]
Chapter 1 Introduction
Page 5, Table 1.1: This table should also include Dart (2011), Lisp (1958) and its dialects [1] and R (1993).
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) [1].
Page 24, Algorithm 2.4, line 1: add a colon after mark() [5,2,6].
Page 25, last paragraph, 3rd line: the word class is duplicated.
Page 26, line 5: The reference should be to Algorithm 7.7 [4].
Page 26, line 19: the reclaimed should be be reclaimed [5,2,6].
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 [4].
Page 38, section 3.4, line 6: delete can be [4].
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 [3].
Figure 3.3 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: offset[block]=14 plus offsetInBlock(old)=6."
Page 41, line 5: sequential-fits should be segregated-fits [4]. Repeated word of [5,2,6].
Chapter 4, Copying Garbage Collection
Page 43, line 3 from the bottom: copy should be forward [4].
Page 49, line 18: reserves should be preserves [4].
Page 53, line 7 from the bottom: implemented should be incremented [2].
Page 55, line 2: that should be than [2].
Chapter 5 Reference Counting
Page 58, line 3 from the bottom: overload should be override [2].
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 64, line 11 from the bottom: increments should be applied before decrements (as per Algorithm 5.4) in order to avoid adding unnecessary entries to the ZCT; similarly, on page 66, line 4, the reference counts of B and D should be incremented before those of B and C are decremented [7].
Page 69, Algorithm 5.5, line 41: add a colon after markCandidates() [5,2,6].
Page 72, Figure 5.4 should use camel-case names rather than underscores (as below).
Figure 5.4
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 [2].
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 [5,2,6].
Page 135, Algorithm 9.1, line 22: add a colon after rootsNursery() [5,2,6].
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 195, Algorithm 11.4, line 2 has a comma missing: add %src, %i, %fld [5,2,6]
Page 200 [5,2,6]:
    1. line 3: end of the card should be start of the card
    2. Algorithm 11.9, insert after line 3: card ← card - 1
    3. Algorithm 11.9, delete line 8 (which assumed the offset was from the end of the card).
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 stealableWorkQueue[j].
Page 284, line 14: the definitive citation is Petrank and Kolodner [2004].
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 needsWork(j) [5,2,6].
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 [2004].
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 W.
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] [1].
Chapter 18 Concurrent Reference Counting
Page 370, lines 24 from the bottom: ...marks ref black. Objects are allocated grey... should be ...marks ref grey. Objects are allocated dirty ... [5,2,6].
Page 372, Algorithm 18.8, line 4: the comment should be 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].

Acknowledgements

We thank the following for drawing our attention to these errors:

  1. Carl Shapiro
  2. Atusi Maeda
  3. Roberto Cometti
  4. Raffaello Giulietti
  5. Tomoharu Ugawa
  6. Tsuneyasu Komiya
  7. Neil Dhar
  8. Hayley Patton
  9. Daniel Bendix
  10. Zixian Cai
  11. Michael Lippautz