Is there a peer reviewed version of this or does Hacker News exclusively post non peer reviewed works?
Tiny Pointers
31–38 of 38 posts
Re: Tiny Pointers
#32Is there a peer reviewed version of this or does Hacker News exclusively post non peer reviewed works?
[deleted]
Re: Tiny Pointers
#33> How large do the pointers need to be? The natural answer is that each pointer uses log nbits. However, the fact that each pointer has a distinct owner makes it possible to compress the pointers to o(log n) bits.
What if you have to debug the whole situation, such that you don't always know who is the owner of a pointer you are looking at?
> A user k can call Allocate(k) in order to get a tiny pointer p; they can dereference the tiny pointer pby computing a function Dereference(k,p) whose value depends only on k, p, and random bits; and they can free a tiny pointer p by calling a function Free(k,p).
That is tantamount ot saying that the pointer is not actually p but the tuple , and so its size consists of the number of bits in k, the number of bits in p plus an indication of where the division between these bits lie: where k ends and p begins.
We can abbreviate to p in contexts where k can be implicitly understood.
Re: Tiny Pointers
#34Re: Tiny Pointers
#35I 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...
That paper was front page 2 days ago. It's the reason this paper is front page today. And while it is fantastic work, it has no obvious break-through application, as was discussed: https://news.ycombinator.com/item?id=43004955
Re: Tiny Pointers
#36I 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…
That's just called a hash map.
Re: Tiny Pointers
#37Earlier quoted context omitted.
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...
That paper was front page 2 days ago. It's the reason this paper is front page today. And while it is fantastic work, it has no obvious break-through application, as was discussed: https://news.ycombinator.com/item?id=43004955
Yeah, I posted about that algorithm on Nim Lang forum. Someone used deepseek to create a Nim version [1]. It seems the constant factor overhead is quite large. Well presuming deepseek implemented it correctly. There's obvious easy perf tweaks, but still seems to have high overhead.