Note that this is not the paper by Krapivin that https://news.ycombinator.com/item?id=43002511 is about.
It’s the paper mentioned in the same article and one of the author’s is his professors.
Tiny Pointers
21–30 of 38 posts
Re: Tiny Pointers
#22I looked a bit into this a few years back and found it quite interesting. Despite them calling them "Tiny Pointers" I would say it's closer to a open addressing hash map. You have a specific key, and then you can "allocate" an entry in the hash map. This gives you back a "pointer". You can then later use the original key and the pointer together to determine the index of the entry. There's also a slight chance that t…
It isn't hard to make a datastructure that indexes into itself. BDDs, for example, are often coded in this way. I did an admittedly poor job of one at https://taeric.github.io/trading-with-bdds.html, but I think it is enough to see the idea well enough.
Re: Tiny Pointers
#23Re: Tiny Pointers
#24Can someone ELI5?
Zoomers invented indexes.
Re: Tiny Pointers
#25Re: Tiny Pointers
#26Here's a somewhat related post where I argue that logic that _can_ have small pointers has lower entropy and is more optimal as bayesian model of the domain: https://benoitessiambre.com/entropy.html
Re: Tiny Pointers
#27Earlier quoted context omitted.
But the idea is still the same? You can make "smart pointers" that are attached to arenas or whatever you want to call them. On those, the addressable size of the pointer is confined to how large the arena is.
Eh, you underestimate my naivety. To rephrase: are these just array indexes, then? I mean I presume it's something cleverer than just "let's bit-pack our indexes to save space". ..."and make it dynamic" (arenas) Oh wait, variable-size tiny pointers. Yes. Now it's getting satisfyingly complicated. Maybe like how UTF-8 works?
How is this novel?
This is like using a fixed sharding scheme plus delta-compression for indices relative to shard addresses plus varint encoding the deltas.
Re: Tiny Pointers
#28Is there a peer reviewed version of this or does Hacker News exclusively post non peer reviewed works?
Re: Tiny Pointers
#29Earlier quoted context omitted.
Eh, you underestimate my naivety. To rephrase: are these just array indexes, then? I mean I presume it's something cleverer than just "let's bit-pack our indexes to save space". ..."and make it dynamic" (arenas) Oh wait, variable-size tiny pointers. Yes. Now it's getting satisfyingly complicated. Maybe like how UTF-8 works?
How is this novel? This is like using a fixed sharding scheme plus delta-compression for indices relative to shard addresses plus varint encoding the deltas.
After reading more, it seems the novelty is in the two specific schemes that use these techniques to store data with high probability into tables of extremely high load factors with bounded pointer sizes, which are more complex than simple array indices due to having to resolve which fallback table is storing the key-value pair.
One scheme proves tiny pointer size bounds for fixed length tiny pointers. The other proves bounds for variable length pointers.
Re: Tiny Pointers
#30I looked a bit into this a few years back and found it quite interesting. Despite them calling them "Tiny Pointers" I would say it's closer to a open addressing hash map. You have a specific key, and then you can "allocate" an entry in the hash map. This gives you back a "pointer". You can then later use the original key and the pointer together to determine the index of the entry. There's also a slight chance that t…
This guy used that paper to create a new hash table which is much faster at high load that current implementations:
https://www.quantamagazine.org/undergraduate-upends-a-40-yea...