I just found a funny failure mode in the garbage collector and thought readers might be amused.Whippet Say you have a semi-space nursery and a semi-space old generation. Both are block-structured. You are allocating live data, say, a long linked list. Allocation fills the nursery, which triggers a minor GC, which decides to keep everything in the nursery another round, because that’s policy: Whippet gives new objects another cycle in which to potentially become unreachable. This causes a funny situation! Consider that the first minor GC doesn’t actually free anything. But, like, : it’s impossible to allocate anything in the nursery after collection, so you run another minor GC, which promotes everything, and you’re back to the initial situation, wash rinse repeat. Copying generational GC is strictly a pessimization in this case, with the additional insult that it doesn’t preserve object allocation order.nothing Consider also that because , any one of your minor GCs might require more blocks after GC than before. Unlike in the case of a major GC in which this essentially indicates out-of-memory, either because of a mutator bug or because the user didn’t give the program enough heap, for minor GC this is just what we expect when allocating a long linked list.copying collectors with block-structured heaps are unreliable Therefore we either need to allow a minor GC to allocate fresh blocks – very annoying, and we have to give them back at some point to prevent the nursery from growing over time – or we need to maintain some kind of margin, corresponding to the maximum amount of fragmentation. Or, or, we allow evacuation to fail in a minor GC, in which case we fall back to promotion. Anyway, I am annoyed and amused and I thought others might share in one or the other of these feelings. Good day and happy hacking!

Happy new year, hackfolk! Today, a note about . I thought I was done with them, but it seems they are not done with me. The question at hand is, how do we efficiently and correctly implement ephemerons in a generational collector? ‘s answer turns out to be simple but subtle.ephemeronsWhippet The deal is, I want to be able to evaluate different collector constructions and configurations, and for that I need a performance oracle: a known point in performance space-time against which to compare the unknowns. For example, I want to know how a does relative to the conventional state of the art. To do that, I need to build a conventional system to compare against! If I manage to do a good job building the conventional evacuating nursery, it will have similar performance characteristics as other nurseries in other unlike systems, and thus I can use it as a point of comparison, even to systems I haven’t personally run myself.sticky mark-bit approach to generational collection So I am adapting the to have generational support: a copying (evacuating) young space and a copying old space. Ideally then I’ll be able to build a collector with a copying young space (nursery) but a mostly-marking old space.parallel copying collector I described last Julynofl A copying nursery has different operational characteristics than a sticky-mark-bit nursery, in a few ways. One is that a sticky mark-bit nursery will promote all survivors at each minor collection, leaving the nursery empty when mutators restart. This has the pathology that objects allocated just before a minor GC aren’t given a chance to “die young”: a sticky-mark-bit GC over-promotes. Contrast that to a copying nursery, which can decide to promote a survivor or leave it in the young generation. In Whippet the current strategy for the parallel-copying nursery I am working on is to keep freshly allocated objects around for another collection, and only promote them if they are live at the next collection. We can do this with a cheap per-block flag, set if the block has any survivors, which is the case if it was allocated into as part of evacuation during minor GC. This gives objects enough time to die young while not imposing much cost in the way of recording per-object ages. Recall that during a GC, all inbound edges from outside the graph being traced must be part of the root set. For a minor collection where we just trace the nursery, that root set must include all old-to-new edges, which are maintained in a data structure called the . Whereas for a sticky-mark-bit collector the remembered set will be empty after each minor GC, for a copying collector this may not be the case. An existing old-to-new remembered edge may be unnecessary, because the target object was promoted; we will clear these old-to-old links at some point. (In practice this is done either in bulk during a major GC, or the next time the remembered set is visited during the root-tracing phase of a minor GC.) Or we could have a new-to-new edge which was not in the remembered set before, but now because the source of the edge was promoted, we must adjoin this old-to-new edge to the remembered set.remembered set To preserve the invariant that all edges into the nursery are part of the roots, we have to pay special attention to this latter kind of edge: we (should?) remove old-to-promoted edges from the remembered set, but we add promoted-to-survivor edges. The field tracer has to have specific logic that applies to promoted objects during a minor GC to make the necessary remembered set mutations.couldmust In Whippet, “small” objects (less than 8 kilobytes or so) are allocated into block-structed spaces, and large objects have their own space which is managed differently. Notably, large objects are never moved. There is generational support, but it is currently like the sticky-mark-bit approach: any survivor is promoted. Probably we should change this at some point, at least for collectors that don’t eagerly promote all objects during minor collections. Finalizers keep their target objects alive until the finalizer is run, which effectively makes . Ideally we would have a separate finalizer table for young and old objects, but currently Whippet just has one table, which we always fully traverse at the end of a collection. This effectively adds the finalizer table to the remembered set. This is too much work—there is no need to visit finalizers for old objects in a minor GC—but it’s not incorrect.each finalizer part of the root set So what about ephemerons? Recall that . Implementing this conjunction is surprisingly gnarly; you really want to discover live ephemerons while tracing rather than maintaining a global registry as we do with finalizers. Whippet’s algorithm is derived from , but .an ephemeron is an object ×⇒ in which there is an edge from to if and only if both and are liveEKVEVEKwhat SpiderMonkey doesextended to be parallel The question is, how do we implement ephemeron-reachability while also preserving the invariant that all old-to-new edges are part of the remembered set? For Whippet, the answer turns out to be simple: an ephemeron is never older than its or , by construction, and we never promote without also promoting (if necessary) and . (Ensuring this second property is somewhat delicate.) In this way you never have an old and a young or , so no edge from an ephemeron need ever go into the remembered set. We still need to run the ephemeron tracing algorithm for any ephemerons discovered as part of a minor collection, but we don’t need to fiddle with the remembered set. Phew!EKVEKVEKV As long all promoted objects are older than all survivors, and that all ephemerons are younger than the objects referred to by their key and value edges, Whippet’s will efficiently and correctly trace ephemeron edges in a generational collector. This applies trivially for a sticky-mark-bit collector, which always promotes and has no survivors, but it also holds for a copying nursery that allows for survivors after a minor GC, as long as all survivors are younger than all promoted objects.parallel ephemeron tracing algorithm Until next time, happy hacking in 2025! on oracles notes on a copying nursery other object kinds finalizers? ephemerons conclusion

When you have a generational collector, you aim to trace only the part of the object graph that has been allocated recently. To do so, you need to keep a : a set of old-to-new edges, used as roots when performing a minor collection. A language run-time maintains this set by adding : little bits of collector code that run when a mutator writes to a field.remembered setwrite barriers Whippet’s is a block-structured space that is appropriate for use as an old generation or as part of a sticky-mark-bit generational collector. It used to have a card-marking write barrier; see my , for more background.nofl spacearticle diving into V8’s new write barrier Unfortunately, when running benchmarks, I was seeing no improvement for generational configurations relative to whole-heap collection. Generational collection was doing fine in my tiny microbenchmarks that are part of Whippet itself, but when translated to larger programs (that aren’t yet proper macrobenchmarks), it was a lose.whiffle I had planned on doing some serious tracing and instrumentation to figure out what was happening, and thereby correct the problem. I still plan on doing this, but instead for this issue I used the old noggin technique instead: just, you know, thinking about the thing, eventually concluding that unconditional card-marking barriers are inappropriate for sticky-mark-bit collectors. As I mentioned in the earlier article: That’s three problems. The second is well-known. But the first and last are specific to sticky-mark-bit collectors, where pages mix old and new objects. Back in 2019, Steve Blackburn’s paper took a look at the state of the art in precise barriers that record not regions of memory that have been updated, but the precise edges (fields) that were written to. He ends up re-using this work later in (see §3.4), where the write barrier is used for deferred reference counting and a snapshot-at-the-beginning (SATB) barrier for concurrent marking. All in all field-logging seems like an interesting strategy. Relative to card-marking, work during the pause is much less: you have a precise buffer of all fields that were written to, and you just iterate that, instead of iterating objects. Field-logging does impose some mutator cost, but perhaps the payoff is worth it.Design and Analysis of Field-Logging Write Barriersthe 2022 LXR paper To log each old-to-new edge precisely once, you need a bit per field indicating whether the field is logged already. Blackburn’s 2019 write barrier paper used bits in the object header, if the object was small enough, and otherwise bits before the object start. This requires some cooperation between the collector, the compiler, and the run-time that I wasn’t ready to pay for. The 2022 LXR paper was a bit vague on this topic, saying just that it used “a side table”. In Whippet’s nofl space, we have a side table already, :used for a number of purposes Well. Why not add another thing? The nofl space’s granule size is two words, so we can use two bits of the byte for field logging bits. If there is a write to a field, a barrier would first check that the object being written to is old, and then check the log bit for the field being written. The old check will be to a byte that is nearby or possibly the same as the one to check the field logging bit. If the bit is unsert, we call out to a slow path to actually record the field. I disassembled the fast path as compiled by GCC and got something like this on x86-64, in AT&T syntax, for the young-generation test: The first five instructions compute the location of the mark byte, from the address of the object (which is known to be in the nofl space). If it has any of the bits in set, then it’s in the old generation.0xe Then to test a field logging bit it’s a similar set of instructions. In one of my tests the data type looks like this: Writing the field will be in the same granule as the object itself, so we can just test the byte we fetched for the logging bit directly with against . For , we should be able to know it’s in the same slab (aligned 4 MB region) and just add to the previously computed byte address, but the C compiler doesn’t know that right now and so recomputes. This would work better in a JIT. Anyway I think these bit-swizzling operations are just lost in the flow of memory accesses.lefttestb$0x80right For the general case where you don’t statically know the offset of the field in the object, you have to compute which bit in the byte to test: Is it good? Well, it improves things for my whiffle benchmarks, relative to the card-marking barrier, seeing a 1.05×-1.5× speedup across a range of benchmarks. I suspect the main advantage is in avoiding the “unconditional” part of card marking, where a write to a new object could cause old objects to be added to the remembered set. There are still quite a few whiffle configurations in which the whole-heap collector outperforms the sticky-mark-bit generational collector, though; I hope to understand this a bit more by building a more classic semi-space nursery, and comparing performance to that. Implementation links: , , and the . (At some point I need to make it so that allocating edge buffers in the field set causes the nofl space to page out a corresponding amount of memory, so as to be honest when comparing GC performance at a fixed heap size.)the barrier fast-paththe slow pathsequential store buffers Until next time, onwards and upwards! An unconditional card-marking barrier applies to stores to slots in all objects, not just those in oldspace; a store to a new object will mark a card, but that card may contain old objects which would then be re-scanned. Or consider a store to an old object in a more dense part of oldspace; scanning the card may incur more work than needed. It could also be that Whippet is being too aggressive at re-using blocks for new allocations, where it should be limiting itself to blocks that are very sparsely populated with old objects. a precise field-logging write barrier preliminary results Mark bits. Iterability / interior pointers: is there an object at a given address? If so, it will have a recognizable bit pattern. End of object, to be able to sweep without inspecting the object itself Pinning, allowing a mutator to prevent an object from being evacuated, for example because a hash code was computed from its address A hack to allow fully-conservative tracing to identify ephemerons at trace-time; this re-uses the pinning bit, since in practice such configurations never evacuate Bump-pointer allocation into holes: the mark byte table serves the purpose of Immix’s line mark byte table, but at finer granularity. Because of this though, it is swept lazily rather than eagerly. Generations. Young objects have a bit set that is cleared when they are promoted. mov %rax,%rdx and $0xffffffffffc00000,%rdx shr $0x4,%rax and $0x3ffff,%eax or %rdx,%rax testb $0xe,(%rax) struct Node { uintptr_t tag; struct Node *left; struct Node *right; int i, j; }; mov %r13,%rcx mov $0x40,%eax shr $0x3,%rcx and $0x1,%ecx shl %cl,%eax test %al,%dil

Hey all, I had a fun bug this week and want to share it with you. First, though, some background. Guile’s numeric operations are defined over the complex numbers, not over e.g. a finite field of integers. This is generally great when writing an algorithm, because you don’t have to think about how the computer will actually represent the numbers you are working on. In practice, Guile will represent a small exact integer as a , which is a machine word with a low-bit tag. If an integer doesn’t fit in a word (minus space for the tag), it is represented as a heap-allocated bignum. But sometimes the compiler can realize that e.g. the operands to a specific bitwise-and operation are within (say) the 64-bit range of unsigned integers, and so therefore we can use instead of the more generic functions that do run-time dispatch on the operand types, and which might perform heap allocation.fixnumunboxed operations Unboxing is important for speed. It’s also tricky: under what circumstances can we do it? In the example above, there is information that flows from defs to uses: the operands of are known to be exact integers in a certain range and the operation itself is closed over its domain, so we can unbox.logand But there is another case in which we can unbox, in which information flows backwards, from uses to defs: if we see , we know:(logand n #xff) Together, these observations let us transform the more general to an unboxed operation, having first truncated to a . And actually, the information can flow from use to def: if we know that will be an exact integer but don’t know its range, we can transform the potentially heap-allocating computation that produces to instead truncate its result to the range where it is defined, instead of just truncating at the use; and potentially this information could travel farther up the dominator tree, to inputs of the operation that defines , their inputs, and so on.logandu64u64nnnn Let’s say we have a numerical operation that produces an exact integer, but we don’t know the range. We could truncate the result to a and use unboxed operations, if and only if only bits are used. So we need to compute, for each variable in a program, what bits are needed from it.u64u64 I think this is generally known a , though both Google and my textbooks are failing me at the moment; perhaps this is because dynamic languages and flow analysis don’t get so much attention these days. Anyway, the analysis can be local (within a basic block), global (all blocks in a function), or interprocedural (larger than a function). Guile’s is global. Each CPS/SSA variable in the function starts as needing 0 bits. We then compute the fixpoint of visiting each term in the function; if a term causes a variable to flow out of the function, for example via return or call, the variable is recorded as needing all bits, as is also the case if the variable is an operand to some primcall that doesn’t have a specific needed-bits analyser.needed-bits analysis Currently, only has a needed-bits analyser, and this is because sometimes you want to do modular arithmetic, for example in a hash function. Consider Bon Jenkins’ :logandlookup3 string hash function If we , we get something like:transcribe this to Scheme These calls are like , to tell the compiler that we really just want the low 32 bits of the number, as an integer. Guile’s compiler will propagate that information down to uses of the defined values but also back up the dominator tree, resulting in unboxed arithmetic for all of these operations.u32the JavaScript idiom|0 (When writing this, I got all the way here and then realized . Oh well, consider this your lucky day, you get two scoops of prose!)I had already written quite a bit about this, almost a decade ago ago All that was just prelude. So I said that needed-bits is a fixed-point flow analysis problem. In this case, I want to compute, for each variable, what bits are needed for its definition. Because of loops, we need to keep iterating until we have found the fixed point. We use a worklist to represent the conts we need to visit. Visiting a cont may cause the program to require more bits from the variables that cont uses. :Consider This is the sigbits (needed-bits) handler for when one of its operands () is a constant and the other () is variable. It adds an entry for to the analysis , which is an intmap from variable to a bitmask of needed bits, or for all bits. If already has some computed sigbits, we add to that set via . The interesting point comes in the call: the bits that we will need from are first the bits that we infer to have, by forward type-and-range analysis; intersected with the bits from the immediate ; intersected with the needed bits from the result value .logand#fsigbits-unionsigbits-intersectparamaaoutaaaparamres If the call is idempotent—i.e., already contains for —then is returned as-is. So we can check for a fixed-point by comparing with the resulting analysis, via . If they are not equal, we need to add the cont that defines to the worklist.intmap-addeq?outsigbitsaoutouta The bug? The bug was that we were not enqueuing the def of , but rather the predecessors of . This works when there are no cycles, provided we visit the worklist in post-order; and regardless, it works for many other analyses in Guile where we compute, for each labelled cont (basic block), . In that case, enqueuing a predecessor on the worklist will cause all nodes up and to including the variable’s definition to be visited, because each step adds more information (relative to the analysis computed on the previous visit). But it doesn’t work for this case, because we aren’t computing a per-label analysis.alabelsome set of facts about all other labels or about all other variables The solution was to .rewrite that particular fixed-point to enqueue labels that define a variable (possibly multiple defs, because of joins and loop back-edges), instead of just the predecessors of the use Et voilà ! If you got this far, bravo. Type at y’all again soon! numbers and representations needed-bits: the of scheme|0 the bug the result will be in [0, 255] that will be an exact integer (or an exception will be thrown)n we are only interested in a subset of ‘s bits.n #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) #define mix(a,b,c) \ { \ a -= c; a ^= rot(c, 4); c += b; \ b -= a; b ^= rot(a, 6); a += c; \ c -= b; c ^= rot(b, 8); b += a; \ a -= c; a ^= rot(c,16); c += b; \ b -= a; b ^= rot(a,19); a += c; \ c -= b; c ^= rot(b, 4); b += a; \ } ... (define (jenkins-lookup3-hashword2 str) (define (u32 x) (logand x #xffffFFFF)) (define (shl x n) (u32 (ash x n))) (define (shr x n) (ash x (- n))) (define (rot x n) (logior (shl x n) (shr x (- 32 n)))) (define (add x y) (u32 (+ x y))) (define (sub x y) (u32 (- x y))) (define (xor x y) (logxor x y)) (define (mix a b c) (let* ((a (sub a c)) (a (xor a (rot c 4))) (c (add c b)) (b (sub b a)) (b (xor b (rot a 6))) (a (add a c)) (c (sub c b)) (c (xor c (rot b 8))) (b (add b a)) ...) ...)) ... (define-significant-bits-handler ((logand/immediate label types out res) param a) (let ((sigbits (sigbits-intersect (inferred-sigbits types label a) param (sigbits-ref out res)))) (intmap-add out a sigbits sigbits-union)))