Hacker News new | ask | show | jobs
by Retr0id 3 days ago
I have a strong understanding of content addressing, memory allocation, data structures, and a superficial understanding of lattices. It is not clear how one has anything to do with the other. If there is any meaningful link or benefit, it has not been explained.

Perhaps some magical insight is waiting for me if I understand the Leech lattice better, but given PhD category theorists are also scratching their heads I think I'll pass https://news.ycombinator.com/item?id=48436251
1 comments
amenn 3 days ago
Still writing the docs. Content addressing is the mechanism, that is: same content lands in the same slot, equality is a handle compare. The allocator is provably extensional so distinct content never aliases even though the hash itself can collide. The Leech part: the heap is sized to the lattice's 196,560 minimal vectors, the coordinate-to-slot map is a collision-free perfect hash built from the Conway group's mm_op tables, and that fixed universe is what makes sets into 196,560-bit bitmaps with O(1) membership and bitwise ops.
link
Retr0id 3 days ago
I understand that you can hash any object into a 196,560-slot space (that's how regular hash tables work), but I'm not sure why you'd want to do that. Regular hash tables can be resized when they get full (or less-full), yours cannot. How is this any different from a hash table with a fixed capacity of 196,560 entries?

"provably extensional" is not an established term in this context and communicates nothing about the design. I simply do not believe that this design doesn't have trivial collision issues, or that it makes efficient use of memory.

link
jrmg 3 days ago
Are you saying that two distinct pieces of content can never collide? That seems obviously incorrect.

For example, take the integers 0 - 196,561, and put them into your lattice-based map. Something’s got to give. There are only 196,560 containers in the map (right?)

link
Retr0id 3 days ago
It's just a regular hash table with linear probing https://github.com/yon-language/yon/blob/aa4617ced3abc92ac53...

The only relation to the Leech group appears to be the number of slots.

When a table gets full they allocate a second one, and so on, up until 256 tables when allocations start silently failing (after exactly 50319104 allocations).

link
jrmg 3 days ago
Ha! Well that answers my question.

I hope OP is seriously considering what’s actually been built here, and how their interactions with whatever LLM they’ve been using really reflects that. I’m genuinely a bit concerned for them.

link