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

Optimizing Open Addressing

thenumb.at

Post reply on HN
Print view View original

51–60 of 70 posts

Re: Optimizing Open Addressing

#51

Post by flohofwoe »

unwind wrote: post #48
pornel wrote: post #29

Modern CPUs keep making optimal algorithms weirder. Speculative superscalar execution and the colossal gap between the CPU and memory speed means that often a brute-force solution that fits in a cache line wins over solutions that would feel more elegant or efficient.

That lacks a "theoretically", then? If an algorithm is optimal but still out-performed by something that is not, then the definition of "optimal" is not so helpful and might need revision. I do not follow the computer science development at all, but I guess people are working on ways of modelling caching as that becomes (as you point out) harder and harder to ignore. Not memory accesses cost the same.

A specific software implementation for a specific algorithm may be the optimal solution for one specific type of hardware, but not for others. Or: it doesn't make much sense to think about software performance without taking into account the specific hardware it needs to run on.

Not sure if this is at all surprising for the more academical 'computer science types', but for low level coders it's been very obvious since pretty much forver.

Re: Optimizing Open Addressing

#52

Post by stabbles »

unwind wrote: post #48
pornel wrote: post #29

Modern CPUs keep making optimal algorithms weirder. Speculative superscalar execution and the colossal gap between the CPU and memory speed means that often a brute-force solution that fits in a cache line wins over solutions that would feel more elegant or efficient.

That lacks a "theoretically", then? If an algorithm is optimal but still out-performed by something that is not, then the definition of "optimal" is not so helpful and might need revision. I do not follow the computer science development at all, but I guess people are working on ways of modelling caching as that becomes (as you point out) harder and harder to ignore. Not memory accesses cost the same.

In theory of cache oblivious algorithms this is modeled; for optimality the complexity should also be independent of block / cache size

Re: Optimizing Open Addressing

#53

Post by ototot »

anonymoushn wrote: post #46
kazinator wrote: post #42

Nobody talks about the possibility of chained hashing, where the chains are vectors and not linked lists. After hashing the key, you chase only one extra pointer. First the pointer to the table, as usual, from which you get a pointer to the "chain", which is another cache-friendly array. Open Addressing has an ugly problem with deletion. You can never delete anything, because any present node might be a needed steppi…

TFA describes a deletion scheme for open addressing in the first paragraph.

Sorry what is TFA?

Re: Optimizing Open Addressing

#54

Post by jnwatson »

kccqzy wrote: post #47
infinet wrote: post #26

I learned about Open Addressing a long time ago when I was optimizing Dnsmasq. The scenario involved looking up a very large list of domain names to block or combine with ipset in order to customize routing based on domain names. Open addressing worked very well on these large immutable lists.

If the lists are immutable, could you not just construct a special hash function a priori that will guarantee no collisions?

Yes. The term of art is “perfect hash”.

Re: Optimizing Open Addressing

#55

Post by Joker_vD »

flohofwoe wrote: post #51
unwind wrote: post #48

Earlier quoted context omitted.

That lacks a "theoretically", then? If an algorithm is optimal but still out-performed by something that is not, then the definition of "optimal" is not so helpful and might need revision. I do not follow the computer science development at all, but I guess people are working on ways of modelling caching as that becomes (as you point out) harder and harder to ignore. Not memory accesses cost the same.

A specific software implementation for a specific algorithm may be the optimal solution for one specific type of hardware, but not for others. Or: it doesn't make much sense to think about software performance without taking into account the specific hardware it needs to run on. Not sure if this is at all surprising for the more academical 'computer science types', but for low level coders it's been very obvious sinc…

And then you quickly reach the conclusion that the only way to assess whether one of the implementation choices will be faster/less memory consuming/etc. in production is to implement both, deploy to production and observe the performance on the actual workloads. And the findings don't generalize, so you can't actually learn from them and build a predictive theory.

And this conclusion doesn't sit well with quite a number of developers, myself included, because I personally would like to be able to do the "right" choice without the brute force of "try everything and see what works better".

Re: Optimizing Open Addressing

#58

Post by Joker_vD »

stabbles wrote: post #52
unwind wrote: post #48

Earlier quoted context omitted.

That lacks a "theoretically", then? If an algorithm is optimal but still out-performed by something that is not, then the definition of "optimal" is not so helpful and might need revision. I do not follow the computer science development at all, but I guess people are working on ways of modelling caching as that becomes (as you point out) harder and harder to ignore. Not memory accesses cost the same.

In theory of cache oblivious algorithms this is modeled; for optimality the complexity should also be independent of block / cache size

Yeah, and then somebody took care to actually implement and benchmark those cache-oblivious algorithms against the classic algorithms with hard-coded chunk sizes and somehow the cache-oblivious ones decisively lost in every single case [0].

[0] Kamen Yotov, Tom Roeder, Keshav Pingali, John Gunnels, and Fred Gustavson "An experimental comparison of cache-oblivious and cache-conscious programs" (2007). https://doi.org/10.1145/1248377.1248394

Re: Optimizing Open Addressing

#59

Post by matheusmoreira »

I wish this article had been available a few weeks ago when I was implementing my own hash table for my language. The explanations of the algorithms are great. It's given me enough confidence to try to implement Robin Hood probing. Should be a nice upgrade.

I'm also wondering how to implement that virtual memory trick...

Re: Optimizing Open Addressing

#60

Post by rkangel »

matheusmoreira wrote: post #59

I wish this article had been available a few weeks ago when I was implementing my own hash table for my language. The explanations of the algorithms are great. It's given me enough confidence to try to implement Robin Hood probing. Should be a nice upgrade. I'm also wondering how to implement that virtual memory trick...

I'm guessing the virtual memory trick it to set up a page mapping so that the next bit of virtual address space after your hash table, is the same physical memory of the hash table again. The power of 2 restriction is needed to make this mapping always meet alignment rules.

If you do this, you can skip out the modulo arithmetic that wraps accesses back to the start of the table. Instead you just read off the end of the table and the next (virtual) memory address after the end of the table is equivalent to reading the first address of the table.

This trick can be useful when setting up some form of DMA into a circular buffer - you've got hardware that will write data into a chunk of memory (or read from it) and wants a range of virtual addresses to work with. If your destination is a circular buffer (which is pretty common) the free space might wrap around the end. Your options are to only read enough to get to the end, use two entries in a scatter-gather DMA to do the two parts, or use this trick.

Post reply on HN