Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Scientists find optimal space-time balance for hash tables

quantamagazine.org

Post reply on HN
Print view View original

31–40 of 67 posts

Re: Scientists find optimal space-time balance for hash tables

#31

Post by randomizedalgs »

vlovich123 wrote: post #2

For anyone curious this is about a 2023 paper proving that a 2022 theoretical hash table construction achieved not only an upper bound in performance in terms of time and space, the construction also achieved a lower bound. It’s a theoretical construction so not actually a practical one you’d find in your software toolkit (constants are too large for most applications, likely even realistic databases). The referenced…

IcebergHT isn't just for persistent memory (although I can see why you might think it is based on the paper's title). The paper also gives experiments showing that the hash table performs very well in standard RAM, much better than other concurrent implementations.

Re: Scientists find optimal space-time balance for hash tables

#32

Post by randomizedalgs »

mabster wrote: post #19
jiggawatts wrote: post #6

This kind of thing is unfortunately not useful at any scale. Real computer systems have performance that varies due to memory locality and size. Locality because of things such as cache hierarchy and even the size of cache lines and memory pages. Size because of physical implementation: larger memories are physically bigger and hence further away. The speed of light makes access to larger memories inescapably slower.…

I haven't kept up in this space, but there was a bunch of papers under "cache agnostic algorithms" that were actually taking the concept of cache into account. The cache agnostic here being regardless of cache size, sort of treating cache in the O() sense. You could still beat them by tweaking for your hardware. But for the first time there was research into why Q sort is faster than heap sort

I think these are more-often called "cache oblivious" algorithms

Re: Scientists find optimal space-time balance for hash tables

#33

Post by tdstein »

andrewp123 wrote: post #20

In my opinion space limited solutions are not very interesting. Time complexity is always >= space complexity, so finding optimal time solutions is always more interesting. And we already knew the optimal time complexity. I appreciate a theoretical time vs space relation, but it doesn’t seem applicable to other areas.

It’s a great thing that this report addresses both space and time!

Re: Scientists find optimal space-time balance for hash tables

#34

Post by FabHK »

wenc wrote: post #29
yalok wrote: post #28

Earlier quoted context omitted.

(from https://python-fiddle.com/saved/lN9D7DOQl0bQ8sqnDA94?code=tr... )

> come up with the most efficient data structure to store highly sparse data (say vector), that will need to be access only sequentially. There's something even more efficient -- a sparse array. I worked in the sparse linear algebra space, and you can gain a lot from sparsity. Add this to your fiddle: from scipy.sparse import csc_array sp_array = csc_array(my_list, dtype=np.int32) print(SZ, " values sparse array size…

Sorry, you have a sorted list of 10,000 Int32, so each of them needs around 32 bits, for a total of 40 KB. I can see how you can store them in 80 KB. I could also see how you would only store the distance to the next one (say 32-log_2(10,0000) = 20 bits on average), for a total of 200,000 bits or 25 KB, if you manage to package it very efficiently.

But how do you store that info in 264 bytes? Something is off there.

Re: Scientists find optimal space-time balance for hash tables

#35

Post by anonymoushn »

FabHK wrote: post #34
wenc wrote: post #29

Earlier quoted context omitted.

> come up with the most efficient data structure to store highly sparse data (say vector), that will need to be access only sequentially. There's something even more efficient -- a sparse array. I worked in the sparse linear algebra space, and you can gain a lot from sparsity. Add this to your fiddle: from scipy.sparse import csc_array sp_array = csc_array(my_list, dtype=np.int32) print(SZ, " values sparse array size…

Sorry, you have a sorted list of 10,000 Int32, so each of them needs around 32 bits, for a total of 40 KB. I can see how you can store them in 80 KB. I could also see how you would only store the distance to the next one (say 32-log_2(10,0000) = 20 bits on average), for a total of 200,000 bits or 25 KB, if you manage to package it very efficiently. But how do you store that info in 264 bytes? Something is off there.

You put all the other bytes outside of python's heap :)

Re: Scientists find optimal space-time balance for hash tables

#37

Post by [deleted] »

FabHK wrote: post #34
wenc wrote: post #29

Earlier quoted context omitted.

> come up with the most efficient data structure to store highly sparse data (say vector), that will need to be access only sequentially. There's something even more efficient -- a sparse array. I worked in the sparse linear algebra space, and you can gain a lot from sparsity. Add this to your fiddle: from scipy.sparse import csc_array sp_array = csc_array(my_list, dtype=np.int32) print(SZ, " values sparse array size…

Sorry, you have a sorted list of 10,000 Int32, so each of them needs around 32 bits, for a total of 40 KB. I can see how you can store them in 80 KB. I could also see how you would only store the distance to the next one (say 32-log_2(10,0000) = 20 bits on average), for a total of 200,000 bits or 25 KB, if you manage to package it very efficiently. But how do you store that info in 264 bytes? Something is off there.

[deleted]

Re: Scientists find optimal space-time balance for hash tables

#38

Post by wenc »

FabHK wrote: post #34
wenc wrote: post #29

Earlier quoted context omitted.

> come up with the most efficient data structure to store highly sparse data (say vector), that will need to be access only sequentially. There's something even more efficient -- a sparse array. I worked in the sparse linear algebra space, and you can gain a lot from sparsity. Add this to your fiddle: from scipy.sparse import csc_array sp_array = csc_array(my_list, dtype=np.int32) print(SZ, " values sparse array size…

Sorry, you have a sorted list of 10,000 Int32, so each of them needs around 32 bits, for a total of 40 KB. I can see how you can store them in 80 KB. I could also see how you would only store the distance to the next one (say 32-log_2(10,0000) = 20 bits on average), for a total of 200,000 bits or 25 KB, if you manage to package it very efficiently. But how do you store that info in 264 bytes? Something is off there.

Thanks for pointing that out. It was my mistake (corrected in parent post)

Re: Scientists find optimal space-time balance for hash tables

#39

Post by TheDudeMan »

yalok wrote: post #27

Hash tables are nice & all, and it's very convenient to use them, BUT I really regret how they create propensity for junior developers to use them even in cases where they are not really needed and more memory-efficient (and perf too) data structure could be used. Anecdotally, in my recent year of interviewing new candidates, I keep asking this simple question: come up with the most efficient data structure to store…

OK but what is your point?

Re: Scientists find optimal space-time balance for hash tables

#40

Post by Dylan16807 »

vlovich123 wrote: post #16
andersa wrote: post #11

Earlier quoted context omitted.

Yep, it's the same thing every time. "We propose this new thing with optimal time complexity blah blah blah" - don't care. Show benchmark. What do you mean it's slower than this basic but cache efficient hash table implemented in 100 lines of c++?

This is a totally different result. It’s providing a proof of an algorithmic complexity. So let’s say you have 10^18 items, it’s likely you’d be using this even if certain algorithms are faster at smaller numbers. It’s also important to note the particularly interesting result is how the mathematicians proved that the earlier design was optimal (upper and lower bound). The technique is the valuable part as it adds to…

> let’s say you have 10^18 items

You won't. Not on a single node.

> The technique is the valuable part as it adds to the mathematician tool kit of how to prove such results.

Agreed.

Post reply on HN