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

61–67 of 67 posts

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

#61

Post by vlovich123 »

randomizedalgs wrote: post #31
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.

But the other implementations were against other PMEM hash tables unless I misread? Like no comparison against common c++ or rust implementations.

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

#63

Post by randomizedalgs »

vlovich123 wrote: post #61
randomizedalgs wrote: post #31

Earlier quoted context omitted.

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.

But the other implementations were against other PMEM hash tables unless I misread? Like no comparison against common c++ or rust implementations.

I think you may have a backwards. Libcuckoo, CLHT, and TBB are widely used high performance C/C++ DRAM hash tables. I think TBB is the hash table Intel maintains, if I remember right.

So the DRAM experiments are apples to apples. It's actually the PMEM experiments, I think, that are comparing a new hash table on a new technology to previous hash tables that weren't designed specifically for that technology.

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

#64

Post by jojohohanon »

Qwertious wrote: post #57
NooneAtAll3 wrote: post #44

Earlier quoted context omitted.

...spacebar? shouldn't "down a page" be done with PageDown? who came up with binding this behavior to a spacebar as well??

>shouldn't "down a page" be done with PageDown? PageDown doesn't reliably exist - plenty of laptops put it behind a function-key combo, making the only action you're doing on the page a two-handed affair. > who came up with binding this behavior to a spacebar as well?? Apparently, it comes from the `more` command[1], because they couldn't reliably assume terminals would have a PageDown key, and because spacebar was t…

Spacebar is next page is old-as-ages terminal convention.

But it has no place in a browser.

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

#66

Post by vlovich123 »

randomizedalgs wrote: post #63
vlovich123 wrote: post #61

Earlier quoted context omitted.

But the other implementations were against other PMEM hash tables unless I misread? Like no comparison against common c++ or rust implementations.

I think you may have a backwards. Libcuckoo, CLHT, and TBB are widely used high performance C/C++ DRAM hash tables. I think TBB is the hash table Intel maintains, if I remember right. So the DRAM experiments are apples to apples. It's actually the PMEM experiments, I think, that are comparing a new hash table on a new technology to previous hash tables that weren't designed specifically for that technology.

You’re right. I didn’t see later in the paper where they compare against TBB.

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

#67

Post by NotSammyHagar »

kolinko wrote: post #47
iamflimflam1 wrote: post #45

Earlier quoted context omitted.

The trap with asking these kind of questions is that you have spent a long time thinking of your optimum solution and the arguments for and against it. You now have an expectation that it should be obvious and easy.

This solution is/should be obvious and easy to anyone who knows algorithms and data structures. I didn't invent op's question, but an answer that it should be a list is obvious right after reading the question. The question is very similar to the most basic exercises from the very first lessons of any basic algorithmics course. If I was programming in python, I'd still probably use a hashmap because it's the quickest…

I was thinking some simple structure to deal with repeated values when I saw the 10k / a million are different than, but I feel the person you are replying too is making a universal point that so many interviewers are convinced their problem is obvious and any decent dev should do it "their way". The data struct also should come with some use case about it, what else is it doing than 'storing' and enumerating results.
Post reply on HN