Printings: June 2000
Last updated 29 September 2003
These errors appear in the June 2000 reprinting.
Page 23, Diagram 2.5, the new free list should be S, U, V, ... (i.e. the order is reversed) [18]. Thus,
Diagram 2.5 AfterUpdate(rught(R), nil).
Pages 33 and 34, in the left-hand diagrams, the arrow from A' to B' in Diagram 2.10 and from A' to C' in Diagram 2.11 should be removed: the pointers are not written until the recursive step is complete [15].
Page 47, Algorithm 3.4, the test x>t is better written
y>t
[14].
Thus,
gcd(x,y) = -- assert: x >= y >= 0
if y == 0
return x
t = x - y
if y > t
return gcd(y,t)
else return gcd(t,yyuasa)
Algorithm 3.4 Greatest common divisor.
mark_grey
(not scan_grey)
[19].
Page 124, Diagram 6.5, the caption should read
[22]
"left(F') is updated with the forwarding address found in
A." (not C).
Page 148, Diagram 7.3, in attempting to correct a minor labelling error in the earlier printings, Diagram 7.3 instead repeats Diagram 7.2 [16]. It should of course be:
Diagram 7.3 OverwritingRcreates old-young pointers.
Page 194: The discussion of how Steele allocates cells omits an account of allocation during the sweep phase, although this is described in Algorithm 8.6 [21]. In summary,
Page 195, Algorithm 8.7,
colour(X) = black
should be
mark_bit(X) = true -colour(X) is now black
Note also the omitted (if obvious) definitions,
marked(X) == (mark_bit(X) == true) unmarked(X) == (mark_bit(X) == false)
Page 204, Algorithm 8.12, the final test on B should be
B>=T-n
[6].
Thus,
New(n) =
if B >= T - n - Flip phase
if scan < B
abort "Haven't finished scavenging"
flip()
for root R
R = copy(R)
repeat k times while scan < B - scavenge a bit
for P in Children(scan)
*P = copy(*P)
scan = scan + size(scan)
if B >= T
abort "Heap full"
T = T - n
return T
read(T) =
T' = copy(T)
return T'
Algorithm 8.12 Baker's incremental copying algorithm.
Page 204, line 2: the reference should be to Diagram 8.8 on the previous page [17].
Page 242, second paragraph: the block's count of free slots should be decremented, not incremented, and the allocator decrements the number of free, rather than allocated, blocks [19].
Page 262, last paragraph, second sentence, should refer to
"A or B",
not "A of B"
[19].
Printings: June 1996, February 1997, November 1997.
Last updated 4 January 1999
The errors below were corrected in the January 1999 reprinting.
Page 3, first paragraph, last sentence: occam does not use static allocation.
Page 21, Algorithm 2.2, Update should increment the reference
count of the new target before deleting the pointer to the old target to
prevent incorrect reclamation in the case that both targets are one and the
same and that this is the only reference to it. Thus,
Update(R, S) =
RC(S) = RC(S) + 1
delete(*R)
*R = S
Algorithm 2.2 Updating pointer fields under reference counting
eMS = (1-r) / (br+c)Similarly, the y-intercept for the Mark-Sweep curve in the graph in Diagram 2.12 should be 1/c [9].
Page 46, Algorithm 3.2
Update(R,S) = - R and S are heap objects
incrementRC(S)
delete(*R)
remove S from ZCT
*R = S
Algorithm 3.2 Deferred Reference Counting: updating pointer values.
Update(R,S) =
T = sticky(*S)
if RC(*S) == unique
*S = T
delete(*R)
*R = T
Algorithm 3.7 One-bit reference counting with tagged pointers.
Update(R,S) =
T = *R
gr = group_no(R)
if gr != group_no(S) - external reference
increment_groupRC(S)
if gr != group_no(T) - external reference
decrement_groupRC(T)
if groupRC(T) == 0
reclaim_group(T)
*R = S
Algorithm 3.9 Bobrow's algorithm.
Update(R,S) = WRC(S) = WRC(S) + 1 delete(*R) *R = S weaken(*R)Algorithm 3.11 Salkild'sUpdate.
Update(R,S) = RC(S) = RC(S) + 1 colour(R) = black - `remove' R,S from control set colour(S) = black delete(*R) *R = SAlgorithm 3.15 Cyclic reference countingUpdate.
collect_white(S) = if colour(S) == white colour(S) = black for T in Children(S) collect_white(*T) free(S)Algorithm 3.20collect_whitesweeps white cells into the free-list.
Update should paint cells black not purple.
Page 78, Algorithm 4.2: if this version of mark is used,
mark_heap should not set mark bits
[11].
Page 80, second paragraph, the figures given are in milliseconds, not microseconds as stated. The reference should be to [Zorn, 1990a], not to [Zorn, 1990b] [10].
Page 81, last paragraph, fifth sentence should read [10]:
"If none of the node's children are unmarked, that stack slot is deemed to be empty and is squeezed out by sliding up the next useful entry."
allocate() =
while sweep < Heap_top -- continue sweep
if mark_bit(sweep) == marked
mark_bit(sweep) = unmarked
sweep = sweep + size(sweep)
else
result = sweep
sweep = sweep + size(sweep)
return result
mark_heap() -- heap is full
sweep = Heap_bottom
while sweep < Heap_top -- try again
if mark_bit(sweep) == marked
mark_bit(sweep) = unmarked
sweep = sweep + size(sweep)
else
result = sweep
sweep = sweep + size(sweep)
return result
abort "Memory exhausted"
Algorithm 4.4
Lazy sweeping.
mark_bit(p) =
return bitmap[p>>3]
sub does not set the condition codes, and
bgz and load
are not standard SPARC assembly instructions.
Furthermore, brackets were omitted from ld and st
instructions
[2].
The correct versions are:
-- is a collection needed?
subcc %g_allocated, ConsSize, %g_allocated
bg,a noCollect
subcc %g_freeConsIndex, 4, %g_free_ConsIndex
call Collect
nop
subcc %g_freeConsIndex, 4, %g_free_ConsIndex
noCollect:
-- need to sweep?
bg,a done
ld [%g_freeCons + %g_freeConsIndex], %result
call lazySweep
nop
ld [%g_freeCons + %g_freeConsIndex], %result
done: ...
Algorithm 4.5
Zorn's allocation sequence for cons cells
lazySweep:
...
-- %bitsLeft contains the remaining bits
andcc %bitsLeft, 1, %thisBit
bnz,a nextBit
add %currentRef, ConsSize, %currentRef
-- sweep the word into the cons free-list
st %currentRef, [%g_freeCons + %g_freeConsIndex]
add %g_freeConsIndex, 4, %g_free_ConsIndex
add %currentRef, ConsSize, %currentRef
nextBit:
-- on to the next bit
srl %bitsLeft, 1,%bitsLeft
Algorithm 4.6
The inner loop of Zorn's lazy-sweep allocator processes one bit of the bitmap.
Page 102, Algorithm 5.2 does not clear mark-bits [11].
relocate() =
free=heap_bottom
live=heap_top
mark_bit(Heap[heap_top+1]) = unmarked - sentinel
repeat
while marked(free) - find the next hole
mark_bit(Heap[free]) = unmarked
free=free+1
while not marked(live) and live > free - find the previous live cell
live=live-1
if live>free
mark_bit(Heap[live]) = unmarked - unmark it
move(live, free)
Heap[live] = free - leave forwarding address
free=free+1
live=live-1
until live <= free
Algorithm 5.2
The first pass of the Two-Finger compaction algorithm
Page 104, Algorithm 5.5, the second line of compute_addresses should read
[11]:
P = Heap_bottom
Page 113, subsection Handling abnormal residencies should read: "Sansom has proposed..." [2].
Page 123, Algorithm 6.1 [7].
In order to fit with the procedure New given in
Algorithm 2.7 on page 29 of Chapter 2 the flip should also
reset the top_of_space to
Tospace+space_size.
C in the last two sentences should
be replaced by references to A. Thus:
"The scan finds a pointer to A at left(F').
This pointer is updated with the forwarding address A'
found in A (see diagram 6.5 on the next page)."
Page 125, Algorithm 6.3: the first line should be indented by one tab [2].subcc %g_allocated, ConsSize, %g_allocated bg,a noCollect
New, Moon's
flip should set top_of_space.
flip() = Fromspace, Tospace = Tospace, Fromspace top_of_space = Tospace + space_size scan, partial, free = TospaceAlgorithm 6.4 Moon's approximately depth-first algorithm.
for R in Roots R = copy(R)
while scan < free scan_partial() scan_all()
"Although they accepted Appel's general case, they found that heap allocation of procedure activation frames required an extra two instructions per call (to save the frame pointer and move the heap pointer) -- 18 percent more instructions than was needed for stack allocation."
Page 145: Apple's Smalltalk was never released.
Page 146, paragraph two should read [1]:
"On the other hand, the strong generational hypothesis, that the older an object is the less likely it is to die, does not appear to hold generally."
a,
b,
c
and R.
"Third, the minor collection successfully reclaimed all short-lived cells in the graph."
Diagram 7.9 Immediately after a major collection, but before the old generation is compacted.
st %ptr, [%obj] -- store ptr into obj st %obj, [%ssb] -- add obj to SSB add %ssb, 4, %ssbAlgorithm 7.4 The write-barrier for a sequential store buffer.
"Notice that hashing prevents duplicate entries from being introduced from the SSB."
st,
use of sll instead of srl for division
and
st instead of stb for clearing bytes
[2].
Thus,
st %ptr, [%obj + offset] -- store ptr into obj's field add %obj, offset, %temp -- calculate address of updated word srl %temp, k, %temp -- divide by card size, 2^k stb %g0, [%byte_map + %temp] -- clear byte in byte_mapAlgorithm 7.5 Chamber's write-barrier. k is log_2(card size).
st %ptr, [%obj + offset] -- store ptr into obj's field srl %temp, k, %temp -- calculate approximate byte index stb %g0, [%byte_map + %temp] -- clear byte in byte_mapAlgorithm 7.6 Hölzle's write-barrier.
k3 throughout
the procedure sweep [8].
The algorithm is also clearer, and more consistent stylistically with
Algorithm 8.3 if free_count is explicitly incremented by
sweep rather than implicitly in free.
Thus
sweep(k3) = sweep k3 items
i = 0
while i<k3 and sweeper <= Heap_top
if mark_bit(sweeper) == unmarked
free(sweeper)
increment free_count
else mark_bit(sweeper) = unmarked
increment sweeper
i = i+1
Algorithm 8.2
Auxiliary procedures for Yuasa's algorithm.
There's also a stylistic inconsistency between Algorithms 8.2 and 8.3 on the
page [8].
It would be better if mark in Algorithm 8.3 also took
k1 as a parameter (rather than as a global variable).
save_stack rather than
saved_stack [8].
"The conservatism ..."
mark,
finished should be set to mark_stack==empty
[8].
Thus,
mark() =
phase = mark_phase
for R in Roots
gcpush(R,mark_stack)
mark1()
for S in system_stack
LOCK S, system_stack
gcpush(S,mark_stack)
mark1()
LOCK gcstate
finished = mark_stack==empty
while not finished
mark1()
LOCK gcstate
finished = mark_stack==empty
Algorithm 8.7
Steele's concurrent marker.
Page 230, penultimate paragraph, penultimate sentence: for code read data [8].
Diagram 9.6 Space leaks in a cons-list are limited to the target of the false reference.
Diagram 9.9 Mostly Copying garbage collection.
"A drawback is that other objects in those blocks have also been retained (for example, object
Xin Diagram 9.9)."
Page 248, Algorithm 9.3: the first line should be indented by one tab [2].
Pages 260, 264 and 269, Algorithms 10.2 to 10.4: the first lines should be indented by one tab [2].
Page 289 says, "Goncalves and Appel confirm these predictions, using Appel's generational copying collector for SML/NJ." SML/NJ no longer uses the two-generation collector described in his 1989 paper Simple Generational Garbage Collection and Fast Allocation, but now uses a multigeneration collector implemented by John Reppy and described in A High-Performance Garbage Collector for Standard ML. It was this many-generation collector that the FPCA'95 paper measured [1].
Richard Jones
|
|
|
| [ book ] | [ GC page ] | [ home ] |