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

Classical data structures that can outperform learned indexes (2018)

dawn.cs.stanford.edu

Post reply on HN
Print view View original

21–30 of 43 posts

Re: Classical data structures that can outperform learned indexes (2018)

#21

Post by j-pb »

toxik wrote: post #20
the_duke wrote: post #4

It wasn't clear to me how Cuckoo hash tables are supposed to work if both locations are full. Here is the relevant explanation from Wikipedia : > The new key is inserted in one of its two possible locations, "kicking out", that is, displacing, any key that might already reside in this location. This displaced key is then inserted in its alternative location, again kicking out any key that might reside there. The proc…

Ah, O(wildly erratic) insertion. Great for that jittery feel to your programs.

Since you double the table size after failing to insert/displace above a constant threshhold, e.g. 8. You have O(1) insert performance. You don't need to rehash the table either, you can add additional hash functions on each grow, or reuse your existing hash function and use bit masking, (that one does require a copy of the table, albeit no rehashing, and copying chunks is something our CPUs are really good at)

Re: Classical data structures that can outperform learned indexes (2018)

#22

Post by adrianN »

toxik wrote: post #20
the_duke wrote: post #4

It wasn't clear to me how Cuckoo hash tables are supposed to work if both locations are full. Here is the relevant explanation from Wikipedia : > The new key is inserted in one of its two possible locations, "kicking out", that is, displacing, any key that might already reside in this location. This displaced key is then inserted in its alternative location, again kicking out any key that might reside there. The proc…

Ah, O(wildly erratic) insertion. Great for that jittery feel to your programs.

Most popular data structures only provide average case guarantees with bad worst-case bounds. Dynamic arrays also have O(wildly erratic) append. I think for most use cases this is perfectly fine and does not result in any perceivable jitter in programs.

Re: Classical data structures that can outperform learned indexes (2018)

#23

Post by toxik »

adrianN wrote: post #22
toxik wrote: post #20

Earlier quoted context omitted.

Ah, O(wildly erratic) insertion. Great for that jittery feel to your programs.

Most popular data structures only provide average case guarantees with bad worst-case bounds. Dynamic arrays also have O(wildly erratic) append. I think for most use cases this is perfectly fine and does not result in any perceivable jitter in programs.

They do in fact not have erratic behavior, they are quite predictable. The cuckooing process, on the other hand, is not predictable by design.

Re: Classical data structures that can outperform learned indexes (2018)

#24

Post by touisteur »

toxik wrote: post #23
adrianN wrote: post #22

Earlier quoted context omitted.

Most popular data structures only provide average case guarantees with bad worst-case bounds. Dynamic arrays also have O(wildly erratic) append. I think for most use cases this is perfectly fine and does not result in any perceivable jitter in programs.

They do in fact not have erratic behavior, they are quite predictable. The cuckooing process, on the other hand, is not predictable by design.

Recently went on a deep dive about sorting algorithm actual predictability and for latency-sensitive workloads, most things you'd use because 'simple/standard' (quicksort, mergesort...) don't shine, with their horrid /worst case/ complexity, but also depending a lot on your input data. Quicksort with a badly chosen pivot, for example, has caused me headaches recently.

Re: Classical data structures that can outperform learned indexes (2018)

#25

Post by pclmulqdq »

The learned index paper struck me as a bit of a marketing gimmick, but this paper also smells a bit. The central sleight of hand that both papers pull without admitting it is that they are creating mostly-read data structures (or in the first half of the learned index paper, read-only data structures). The learned index paper then compares them to read-write data structures and claims a win.

Due to cache locality, cuckoo hashing usually underperforms compared to linear probing hash tables, except when you want super high density and you don't expect to do much inserting. It gets especially bad if the keys or values are large. 99% of the time, you're better off with something other than cuckoo hashing.

Re: Classical data structures that can outperform learned indexes (2018)

#27

Post by pclmulqdq »

dicroce wrote: post #26

As I read this I thought "interesting. I would have thought probing would be better on modern computers with memory pre-fetching"... Then I come to the comments and find out im not the only one thinking that.

You're right, benchmarks have shown that probing is better until you reach ~90% capacity. Cuckoo hashing sufferers from terrible memory locality, and you can only make up for it when a probing table would have worse locality.

Re: Classical data structures that can outperform learned indexes (2018)

#28

Post by karpierz »

touisteur wrote: post #24
toxik wrote: post #23

Earlier quoted context omitted.

They do in fact not have erratic behavior, they are quite predictable. The cuckooing process, on the other hand, is not predictable by design.

Recently went on a deep dive about sorting algorithm actual predictability and for latency-sensitive workloads, most things you'd use because 'simple/standard' (quicksort, mergesort...) don't shine, with their horrid /worst case/ complexity, but also depending a lot on your input data. Quicksort with a badly chosen pivot, for example, has caused me headaches recently.

Mergesort worst case is O(nlog(n)). If there's a downside to it, it's that you need to allocate memory.

Re: Classical data structures that can outperform learned indexes (2018)

#29

Post by resters »

pclmulqdq wrote: post #25

The learned index paper struck me as a bit of a marketing gimmick, but this paper also smells a bit. The central sleight of hand that both papers pull without admitting it is that they are creating mostly-read data structures (or in the first half of the learned index paper, read-only data structures). The learned index paper then compares them to read-write data structures and claims a win. Due to cache locality, cu…

Learned indexes are an optimization technique that can help a lot in specific scenarios, but the authors were not under the impression that they are applicable to most use-cases.
Post reply on HN