4 ms·

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 provab

by amenn 4mo 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.

Retr0id 4mo 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.
jrmg 4mo 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?)
- Retr0id 4mo ago
  It's just a regular hash table with linear probing https://github.com/yon-language/yon/blob/aa4617ced3abc92ac53afb4d49b258df52e84e24/runtime/xleech2_heap.c#L280-L285 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).
  - jrmg 4mo 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.

by amenn 4mo ago

Retr0id 4mo 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.

jrmg 4mo 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?)

Retr0id 4mo ago
It's just a regular hash table with linear probing https://github.com/yon-language/yon/blob/aa4617ced3abc92ac53afb4d49b258df52e84e24/runtime/xleech2_heap.c#L280-L285 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).
- jrmg 4mo 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.