gc — garbage collection in toy programming language lathe (a lisp dialect plus smalltalk class system, using þ library using the mu-babel license; context: see mu).
Wil plans to use a Cheney (wikipedia) style garbage collector — a breadth-first version of stop-and-copy gc. On this site the term is sometimes shortened to copy-gc, as opposed to mark-and-sweep as described column right.
Here's a basic summary of Cheney's 1970 algorithm, later expanded below with more detail specific to Lathe (and underlying þ code like the book demo). Note this approach corresponds to an image in Wil's mind because it's not yet coded. (Actual gc code might appear later.)
When gc is invoked, content to be collected lives in from-space F; another empty to-space T of at least equal size is both empty and available to receive a copy of all live content from F that stays alive. Anything not copied to space T is garbage.
A root set R of pointers to boxes in from-space F defines an initial set of reachable boxes that must remain alive. The box pointers in R must include all global and stack-based references to content in F still being used. All boxes pointed to by R hold still more box pointers — and all boxes reachable directly and indirectly from them are also still in use. Once gc is done, to-space T must contain copies of all boxes reachable from root set R in from-space F.
(That description pretends all pointers are strong as opposed to weak. But in fact some objects are only reachable by weak pointers alone, and these will be discarded. So only boxes strongly reachable from R get preserved in T.)
Note both root set R and from-space F may point to boxes not inside F. (Any box pointer not inside F is considered part of a global environment G which is not collected and never moves.) Spaces F and T support a boolean is-member-of predicate saying whether a given box pointer is inside the space. For box pointer b, notation F[b] is the predicate: true when b is a box inside F and false otherwise.
The first step in Cheney gc consists of this: for every box pointer b in R, if F[b] is true, copy that box from F to T, but only one time if b appears multiple times. In to-space T, the new copy is located at b'. Once copied, the old box at b in F is updated to hold a forwarding pointer to b', so in effect every old box maps itself to the new location, so F becomes a map of b to b' for each box as copying progresses, and this is how the copy-once-only rule is satisfied.
Output from the first step has three parts: 1) every b in R copied from F to T is replaced with b' to show the new location; 2) every copied box at b in F is updated to forward to b' in T; and 3) all box copies in T appear consecutively starting at σ and ending before ε (such that ε marks the first available box in T free space after copied boxes).
Pointers σ and ε in to-space T — called fingers — delimit boxes copied from F not yet examined themselves for box pointers inside to be copied. In effect, the boxes between start σ and end ε replace the role of root set R, and contain all the remaining box pointers into F that need the same treatment as performed in the first Cheney gc step.
In the second step of Cheney gc, the collector enters a loop continuing as long as σ remains less than ε. Once σ reaches ε, all boxes copied from F will themselves have been processed in T to pull in more boxes, replacing all b pointers in F with corresponding b' pointers in T. Fingers σ and ε delimit a todo list of boxes to be scanned, growing as more F boxes are appended at ε, and shrinking as boxes at σ are passed.
While start finger σ is less than end finger ε, each box at σ in T is examined to see if it contains any pointers. If it does, the set of pointers inside is treated like a new small root set R' to be handled the same way as roots in step one above: for every pointer b in R', if F[b] is true, replace b with b' if it was copied earlier, or else copy that box from b in F to b'=ε in T, then advance ε by the size of this box so it becomes a member of boxes between σ and ε to be processed. Each b in R' so copied is replaced with b', and the old box at b in F is updated with a forwarding pointer to b' when first copied to T.
When start σ hits end ε, all copying is done — provided no weakly referenced boxes were seen earlier. (Weak boxes are described separately below, so pretend all pointers were strong.) When σ hits ε, to-space T contains copies of all boxes in F strongly reachable from original root set R; therefore from-space F is no longer needed and can be deallocated. Space T takes the place of F in the VM, and gc is finished.
Any box with weak bit yt::e_w set in the tag is called a weak box; all pointers in a weak box are weak pointers; and any box in from-space F reachable only by weak pointers is weakly, not strongly, reachable. But only strongly reachable boxes remain alive after copy-gc. So boxes only reached by weak pointers are garbage and vanish in gc.
(The purpose of weak pointers is specfically to make objects collectable when no one currently holds a strong reference. Weak pointers can be used in caches that otherwise might keep far too much content in memory.)
To prevent dangling pointers to boxes not copied when only only weakly referenced, weak pointers must be replaced with nil when the box did not survive gc.
This means when any weak boxes are seen, our final gc step is not truly finished when start finger σ reaches end finger ε, because weak boxes in T must be examined once again to see which of the weak pointers are still good because someone else had a strong pointer to the same box, causing it to be copied from F to T.
In fact, none of the weak boxes in the first pass could be used as small root sets R' as described, since that would force early copying of weakly referenced boxes. To efficiently handle weak boxes, they should not appear between fingers σ and ε in the earlier algorithm. Instead, it's best if a completely separate weak-space W is used as a peer for to-space T. Then every weak box copied during gc can land in W instead of T, and W can have it's own start finger σ and end finger ε.
When finger σ reaches finger ε in T, the gc method can then process all weak boxes between finger σ and ε in weak-space W. But a scan of boxes in W only has one purpose: either nil out a pointer when the box was not copied, or replace pointer b in F with b' in T (or W) if it was copied. When finger σ reaches finger ε in W, merge W and T as one space. (In fact, you can think of W as a subspace of T all along.)
Weak-space W can be a disjoint set of books in Lathe. In old style monolithic spaces, W can be placed at the end of to-space T, so T and W grow toward one another.
Object finalization is another wrinkle ignored in the Cheney gc algorithm described above. It was simpler to ignore the issue of destroying objects when collected as garbage. But when finalization is added to a language as a feature, any object with a finalization method cannot vanish instantly when gc fails to copy it to space T.
Instead, finalizable objects to be collected must be preserved at least one gc cycle so finalization can be called — and if they become strongly reachable again before the next gc occurs, they might not even be collected.
Wil likes the idea of having yet another T sub-space — say a departing-space D — into which finalizable objects can be copied when they are not strongly reachable. Then after gc, these objects scheduled for finalization will be gathered nicely in one place for code iterating over them for destruction.
(To find finalizable objects not copied by gc to space T, it might be necessary to chain all of them together in memory for scanning after gc. Or they might simply be stored in a different subspace at all times, to touch less memory and hit fewer pages when scanning for dead finalizable objects.)
However, finalization is likely to be added late as a feature in Lathe, especially if Wil doesn't write any code needing it before early toy language milestones.
mu, toy, peg, imm, tag, box, symbol, token, number, bigint, class, method, reader, writer, eval, env, vm, gc « Þ, world, pcode, compiler, asm, lathe, lisp, smalltalk, design, weight, jar, card, harp, debug, profile
(thorn, todo, names, fd, iovec, assert, log, run, hex, crc, buf, in, out, quote, escape, compare, file, deck, cow, arc, blob, tree, slice, rand, time, stat, hash, heap, node, primes, page, book, pile, stack, atomic, lock, mutex, thread, map, meter, list, iter, ctype)
"I'm not going to write a mark-and-sweep garbage collector for Lathe," Wil insisted. "FYI, I'll say mark-gc from now on."
"Then why did you bring it up?" Zé asked. "Are you going to say copy-gc when you mean stop-and-copy? Why not do both? What harm would it do?"
"Yes, let's say copy-gc, or just c-gc, for stop-and-copy," Wil nodded. "I brought it up because it will be impossible to stop it from arising when folks discuss copy-gc in Lathe."
"What's wrong with mark-gc?" Zé asked. "It was good enough for XLisp and it's still prevalent in many dynamic languages. What's the problem? Don't you like it?"
"I like mark and sweep fine," Wil countered. "I even re-worked an old mark-gc a couple times. Last time (1991?) I used reversing pointers in-place for a node stack in mark phase."
Zé twirled a finger and prompted, "So what's wrong?"
"I think it's slower," Wil said, "touching more memory during gc and losing the ability to improve locality during a copy. But mark-gc does have one big advantage."
"People like it more?" Zé teased. "Spit it out man."
"Mark-gc leaves nodes alone: they don't move," Wil explained. "This is friendly to C, since moving objects is dangerous. But copy-gc moves all reachable objects subject to collection."
"So it's critical all pointers to boxes moved get updated, I see," Zé nodded. "Why is copy-gc worth the trouble?"
"I don't want to justify why I like copy-gc better," Wil protested. "I only want to explain how it differs from mark-gc. But my motive is more speed and less fragmentation."
"What if I don't agree those are better with copy-gc?" Zé needled. "What if I need to be persuaded?"
"I could not care less," Wil said. "I'd still say that if I didn't know you were just testing. Your bias is your problem."
"Refresh my memory of how mark-gc works?" Zé asked. "I think I recall, but I like to hear you talk."
"Starting from the root set," Wil said, "you visit every reachable node (aka box) and mark it as visited. That pass is called the mark phase, obviously."
"Like dropping breadcrumbs," Zé suggested.
"Yes," Wil nodded. "Then you visit all nodes in a second sweep phase, freeing every un-visited node and unmarking each visited node. Then you're done. Two passes."
"I like the simplicity," Zé appreciated.
"What's not to like?" Wil shrugged. "The algorithm would also work in Lathe's book-oriented gc space, but when 'freeing' a box requires moving to compact, it would be like copy-gc."
"Aha!" Zé prodded. "You're saying the book-oriented heap is the problem. You really just don't like C style heaps."
"Do you know anybody who does like C style heaps?" Wil grimaced. "They're easy to corrupt, and the per-block overhead for allocation is almost always more than four bytes."
"Ha, ha," Zé wagged a finger. "Everyone loves their C heaps. In fact, it's lese majesty to voice criticism. I hear a lynch mob in the distance now," Zé cupped a hand to one ear.
"Do they have pitchforks?" Wil emoted mock-worry. "I hate those eviscerating pointy tines. Peasants."
"Since most everyone is mixing and matching libraries written in C," Zé noted, "It seems a mite unfriendly not to write more tools suiting popular demand. It's a civic duty."
Wil worked his jaw a little while resisting a sharp rejoinder to the phrase civic duty. Zé watched in amusement.
"Do you always have such insight into what folks don't like to hear?" Wil asked while calming down.
"Pretty much," Zé acknowledged. "Folks wear intellectual affiliations on their sleeves like merit badges."
"Brothers in cynicism," Wil said while rubbing his eyes. "Okay, I'm done with mark and sweep."
"Who was that masked man?" Zé mocked.
"I've had enough of your lip, Tonto," Wil quipped, then froze. "Tell me you won't turn that into a racial thing."
"I realize you didn't have cycles to present actual gc code right now," Dex allowed. "But pseudocode is still required, whether or not you post the actual C++ code."
|
"Required?" Wil asked. "Is that an oddly indirect demand? Like, give me pseudocode right now, damn it?"
"Any self-respecting gc expert would be ashamed to show gc algorithms without pseudocode," Dex insisted.
"You have a respect fixation," Wil noted. "I'm not an expert, and I'm not overly concerned about self-respect."
"Well, you should be — that's your problem," Dex asserted. "So when can you have the pseudocode done?"
"Most likely, um, when I feel like it," Wil said. "You need to work on your persuasion skills. Why don't you google Cheney and read the pseudocode you find?"
"I was hoping you'd feel obligated," Dex admitted.
"Traditional Cheney algorithm recaps assume large monolithic memory formats, don't they?" Stu asked.
"Yes, start and end fingers in to-space T are typically two pointers in contiguous memory," Wil replied.
"Weren't you going to break memory into book sized pieces?" Stu recalled. "How does that affect Cheney gc?"
"Well, each space won't be contiguous: it will be a collection of books in which boxes are allocated," Wil said. "And each book won't be complete full except by chance."
"Won't the algorithm still work as long as each space is a sequence of boxes?" Stu asked.
"Sure," Wil agreed. "But the 'next' box after the last one might be in a different book — a trivial issue."
Stu massaged his chin while thinking, then asked, "What else could go wrong? How do you know a to-space T to receive a copy will be as big as from-space F?"
"You'd need to reserve enough books to cover the space to be collected, I guess," Wil replied. "You'd have options to game it a little, but games can be complex."
"What games?" Stu prompted, then back-pedaled when Wil looked put out. "That is, if you care right now."
"Given more than one space, you can collect a smaller one first if you have insufficient books," Wil suggested. "Or you could just allocate more books from the host system."
"Yeah, I guess it would depend on policy configurations, too," Stu puzzled while staring into thin air.
"Policy management will be a pain," Wil guessed.
