Find-grain capability addressing is a natural monopoly

[Jonathan S. Shapiro]

In response to William yesterday, I suggested that it would be nice to shrink the capability structure. I'm doubtful that we can rearrange everything enough to do so, but a reasonable approach to thinking about it would be to figure out how many items the current capabilities can address to find out where we stand today. Then we can look at what we need and figure out how many bits are re-claimable. Have a seat and pull up a blackboard!

Current estimates say there are between 2^78 and 2^82 atoms in the observable universe. We declare that the non-observable universe is both unseen and not heard for purposes of this exercise.

Our current OID field is 64 bits. Each OID can name a distinct page. We also have a 20 bit allocation count per object. I think we can reasonably append those allocation count bits to the OID. That gets us to 84 bits of OID, so we're good on address bits with two to spare. 0/1 values are stored on the atoms by flipping their spin and using the resulting value as an index into an immutable false/true lookup table (the so-called universal constants). If we want to be able to reallocate atoms we will need an incremental background GC on the observable universe so that atoms can be returned to the free list.

The "change the spin" approach raises a concern about energy leakage as the value of an atom changes over time, so a small number of the current page offset bits can be reserved for this. At the same time, we can reduce the rate of wear by letting some of these bits serve as a generation marker, reducing GC latency.

Of course, we need a place to store the OID representation, and the encoding proposed requires 88 bits of address for every atom after wear state is considered. The capabilities get copied around, so we have the same wear leveling issues for the OIDs that we have for the addressible atoms. Re-using the "spin storage" concept, we propose to store these bits using atoms, which will require us to invent an 88:8 compression scheme so as not to oversubscribe the observable universe. The compression scheme remains an unsolved engineering problem.

Note that this approach would give us a natural market monopoly, since any other implementation of universal atomic addressing would necessarily need to use atoms we already own.

Suggested Projects:

• The initial formatting pass is left as an exercise for the undergraduate.
• Implementing the GC seems more like a Masters level thesis project.

Jonathan

[Mark S. Miller]

(Head spinning! Did you post this a month early?)

--
You received this message because you are subscribed to the Google Groups "cap-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cap-talk+u...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/cap-talk/CAAP%3D3QOZMVNBDpEZH%3DBx5zO18z%3DmCGa5WHiLPLNZkT4tePH7Ow%40mail.gmail.com.

[Jonathan S. Shapiro]

On Mon, Mar 2, 2026 at 3:13 PM 'Mark S. Miller' via cap-talk <cap-...@googlegroups.com> wrote:

(Head spinning! Did you post this a month early?)

I did think about waiting. :-)

Jonathan

[Jonathan S. Shapiro]

Well, almost everything I posted today was wrong. Powers of 2 vs. powers of 10.

We return you now to your regularly scheduled Coyotos effort.