I happen to have a homegrown system I use as a foundation for builds writ large (atomic tree snapshots with recursively derived build artifacts), which has some similarities to Irmin. The major feature I don’t have (and don’t need) in that system is Irmin’s mergeable replicated data types, which in my mind is Irmin’s most notable feature: https://www.youtube.com/watch?v=_1zFtB4HSwU.

Unlike Irmin, my system’s support for “custom data types” is the bare minimum needed to walk the object graph in a generic way: an object has an array of links to other objects in a uniform format, in addition to its blob body. IMO, one of Git’s flaws as a generic object store is that facilities like garbage collection require knowledge of a closed set of object kinds and kind-specific format parsing to traverse their links.

score 2 · canonical

“I now understand that git not only comes with an append-only (“immutable”) content-addressable database, but is also a boring mutable key-value store.”

I learned Git from Scott Chacon’s Git Internals book from 2007. It was great if you’re a systems programmer and you prefer to learn how things work bottom up. Very early in the book on page 21:

“In addition to the Git objects, which are immutable – that is, they cannot ever be changed, there are references also stored in Git. Unlike the objects, references can constantly change. They are simple pointers to a particular commit, something like a tag, but easily moveable. Examples of references are branches and remotes.”

As an aside, the minimal design for a mutable key-value store on top of an immutable object store needs only 1 ref (the root). Or 2 refs (the old root and new root) for crash recovery if your durable storage doesn’t provide atomic ref updates. Then the recovery protocol reads both root descriptors and selects the newest (by logical timestamp) whose checksum passes. The embedded database system lmdb uses this kind of design, with 2 alternating root pages, although its object model is not content addressed.

score 5 · canonical

“Arena indices” in the post you’re replying to was referring to exactly that; I assumed people would know what that was shorthand for and didn’t elaborate. I was just pointing out that you can also easily do x32-style 32-bit absolute pointers within the standard 64-bit host ABI.

score 2 · canonical

If you just want to use 32-bit pointers for a subset of the process’s heap allocations, like in a VM, you can do it without such an intrusive change to the system ABI. In fact, mmap on Linux makes it easy with MAP_32BIT and on other operating systems without that feature you can emulate it by trying MAP_FIXED with different base addresses and allocation sizes, ideally right after program startup, to carve out chunks from the 0…2^32 address range which are then sub-allocated.

With this approach you won’t use the standard pointer types for the small pointer-at-rest representation, just like you wouldn’t for 32-bit relative offsets or arena indices. You lose some provenance fidelity in the transition between the at-rest and in-flight forms, but that’s pretty much exactly where provenance isn’t as useful as a compiler optimization enabler, and your in-flight form (which is what lives in registers and on the stack and travels across function boundaries, including to FFI endpoints in something like a VM) can and should be the regular pointer type.

score 1 · canonical

I think it’s almost universally the case that, whenever there’s a choice, the amortized approach is simpler and has better throughput; it’s a textbook latency vs throughput trade-off. Think of something as basic as the classic table doubling algorithm for dynamic arrays, where push is amortized O(1) time but worst-case O(n) time, compared to the simplest worst-case O(1) time incrementalized design. Similarly, relaxed deletion is an entire genre of throughput vs latency trade-offs in data structure design that increases throughput (and average-case latency, like with O(1) amortized array push) and lowers implementation complexity at the expense of worst-case latency.

score 3 · canonical

See also @pkhuong’s https://pvk.ca/Blog/2025/08/19/monoid-augmented-fifos/ for a deamortized approach. As a lead-in, he summarizes the classic two-stack approach in a paragraph (and goes on to explain why it’s a dead-end for deamortization):

"There’s a cute construction in the purely functional (strict or lazy, doesn’t matter) data structure folklore for a FIFO queue augmented with a monoid. The construction builds on two observations:

• It’s trivial to augment a stack with a monoid such that we can always get the product of all the values in the stack: multiply the previous product by the new value when pushing, and keep a pointer to the previous (cons-)stack. Pop dereferences the CDR.
• We can construct an amortised queue from two stacks, an ingestion stack that accepts new values and an excretion stack for exiting values: popping from stack A and pushing onto stack B ends up reversing the contents of A on top of B."

The non-augmented two-stack queue by itself is of course even more classic, including outside of the purely functional world. I remember first learning about it as a kid when doing the exercises in Knuth, where it shows up in at least one exercise, so I assume its vintage dates back to the 1960s. But as Paul says, the augmented two-stack queue is just that plus the even simpler idea of stack augmentation; I’m not sure when that specific combination first showed up in the folklore, but I wouldn’t be shocked if it’s ancient history as well.

score 4 · canonical

Whiteout is a really common term for any kind of merged dictionary (filesystem or otherwise) where a newer layer needs a mechanism for deleting an entry from an older one. And it’s another one of these culture-specific terms leaking into generic discourse.

Huh, I admit I’ve never heard “whiteout” used to describe this! TIL.

By the way, I consider traditional tombstones as the in-place version, and the tombstone concept thereby captures the same idea for me when applied append-only in LSM-like data structures (except perhaps for an in-place level 0, e.g. the memtable in an LSM store). Append-only deletions via tombstones is in the original Bentley-Saxe paper on decomposable search problems. And similar to how tombstone slots are garbage collected implicitly (same idea as a copying or compacting GC) when rehashing a hash table (which I’m guessing is where most people know tombstones from), the same applies to LSM sort-merges, or RH hash table sort-merges, generalizing the rehashing idea.

score 2 · canonical

I guess I could be non-lazy and look this up but in the spirit of engaging: Does CHICKEN still use the “Cheney on the MTA” approach where it compiles to C and implements continuations with CPS and dynamic allocations with alloca on the C stack, treating stack overflows as a trigger for stack-copying GC? Assuming I’m remembering that correctly. If so, how has that worked out over the years? I mostly stopped using or following Scheme in the mid-2000s, so the quirky compilation approach is what I remember it for the most, as a compiler nerd.

score 2 · canonical

This is really cool to see. Back when C++ compatibility in compilers was generally terrible in the late 1990s and early 2000s, you’d always hear stories about the compatibility level of EDG’s frontend. I didn’t get to use an EDG-based compiler until working with the Green Hills toolchains for some of Nintendo’s consoles.

At least as far as my knowledge extends this is one of the four still extant C++ front ends (Clang, GCC, and MSVC being the others).

One thing that surprised me when I asked him about it years ago is that Sean Baxter’s Circle is an independent C++ front-end implementation, in addition to the Circle-specific features. I’d previously assumed that he’d started with the Clang front-end.

score 2 · canonical

There’s already an intrinsic for that: https://doc.rust-lang.org/std/intrinsics/fn.breakpoint.html. And if that didn’t exist, you could implement it in a library with an inline asm one-liner per ISA (e.g. int3 on x86).

score 1 · canonical