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

61–70 of 70 posts

Re: Optimizing Open Addressing

#61

Post by Joker_vD »

rkangel wrote: post #60
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 t…

> hardware [...] wants a range of virtual addresses to work with

Pretty sure DMA can not use virtual addresses since that'd require cooperation from the CPU. I guess there can be some IOMMU device that would present some sort of separate address space specifically for peripherals?

Re: Optimizing Open Addressing

#62

Post by yencabulator »

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?

Perfect Hash Functions are possible, but in my limited experience they rarely out-perform the naive thing where you pre-size the hash table to fit all your data (avoid grow-on-insert overhead).

PHFs have two downsides: Finding a PHF for your data can take a bunch of CPU time so it's frustrating to have in your build, and the resulting hash function can be much more costly than a simpler hash function. That is, the cost of hashing can more than dominate an extra lookup in a tiny fraction of cases.

I'd say the use case for PHF is more when you're absolutely memory-bound, e.g. in an embedded ROM. For anything else, just bump up your hash table size a little, to not have those collisions.

Re: Optimizing Open Addressing

#63

Post by rkangel »

Joker_vD wrote: post #61
rkangel wrote: post #60

Earlier quoted context omitted.

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 t…

> hardware [...] wants a range of virtual addresses to work with Pretty sure DMA can not use virtual addresses since that'd require cooperation from the CPU. I guess there can be some IOMMU device that would present some sort of separate address space specifically for peripherals?

Yeah, the only time I've done it, it was an ARM based chip that didn't actually have a full MMU (i.e. full virtual addressing), but did have an IOMMU.

Re: Optimizing Open Addressing

#64

Post by hgs3 »

It's not discussed in the article but there is also coalesced hashing [1] which is a hybrid of separate chaining and open addressing. Coalesced hashing makes the best use of space as you can fill a table to capacity before resizing. Speed wise, it provides consistent performance for all operations (insert, search, delete) rather than being optimized for only one or some of them.

Another topic the article doesn't touch on is the difference between dense and sparse hashmaps. The former stores values and keys together but the latter stores values in separate array(s) which is more cache friendly when probing keys.

[1] https://en.wikipedia.org/wiki/Coalesced_hashing

Re: Optimizing Open Addressing

#65

Post by matheusmoreira »

rkangel wrote: post #60
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 t…

Yeah, it's a lot like the address mirroring I often see in electronics. I'm just wondering if it can be done with Linux mmap or some other system call.

Re: Optimizing Open Addressing

#67

Post by mananaysiempre »

KerrAvon wrote: post #45
citizen_friend wrote: post #28

Earlier quoted context omitted.

This is an advantage of C style programming. If you understand the problem and tailor a solution you can utilize simplifying assumptions which make the code easier and faster. General libraries have to handle all kinds cases you might not care about. The most egregious example is assuming every piece of code might be threaded so everything needs to be protected by locks. (I would guess > 75% of dictionaries never rem…

Locks require enough of a performance hit on enough architectures that it’s better to document the dictionary as _not_ being threadsafe and require external synchronization. You’ll frequently need external locking anyway to enforce atomicity with changes to other related data structures

And yet most stdio implementations on systems capable of multithreading add locking around every operation (with the notable exception of Microsoft’s single-threaded C runtime when it still existed, as well as a handful of distinct *_unlocked functions on Unix that were added specifically to mitigate this problem).

There are probably multiple reasons for this, including historical precedent and the need for misuse resistance in a language’s standard library, but I’d guess that in part this is simply because locks used to be much cheaper, especially before systems with multiple hardware threads became ubiquitous.

Re: Optimizing Open Addressing

#68

Post by citizen_friend »

mananaysiempre wrote: post #67
KerrAvon wrote: post #45

Earlier quoted context omitted.

Locks require enough of a performance hit on enough architectures that it’s better to document the dictionary as _not_ being threadsafe and require external synchronization. You’ll frequently need external locking anyway to enforce atomicity with changes to other related data structures

And yet most stdio implementations on systems capable of multithreading add locking around every operation (with the notable exception of Microsoft’s single-threaded C runtime when it still existed, as well as a handful of distinct *_unlocked functions on Unix that were added specifically to mitigate this problem). There are probably multiple reasons for this, including historical precedent and the need for misuse re…

I would include malloc in that list of regrets (or at least not having a lock free alternative).

I think historically it wasn't clear what role threads would take. If you look at Java they expected application programmers to be using threads haphazardly. Now we know that isn't a good idea.

Re: Optimizing Open Addressing

#69

Post by anonymoushn »

hgs3 wrote: post #64

It's not discussed in the article but there is also coalesced hashing [1] which is a hybrid of separate chaining and open addressing. Coalesced hashing makes the best use of space as you can fill a table to capacity before resizing. Speed wise, it provides consistent performance for all operations (insert, search, delete) rather than being optimized for only one or some of them. Another topic the article doesn't touc…

Coalesced hashing is just worse than robin hood tables.

Re: Optimizing Open Addressing

#70

Post by [deleted] »

Joker_vD wrote: post #58
stabbles wrote: post #52

Earlier quoted context omitted.

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/…

[deleted]
Post reply on HN