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

41–50 of 70 posts

Re: Optimizing Open Addressing

#41

Post by [deleted] »

dragontamer wrote: post #37
kazinator wrote: post #34

Earlier quoted context omitted.

It is not necessary for an allocator to have any hidden overhead inside an allocated block. That would be quite unacceptable for small blocks like a 32 byte block holding four pointer-sized values. In any case, applications can do their own aggregation for small allocations: allocate the nodes in an array and dole it out from that. It can recycle unused nodes itself.

> In any case, applications can do their own aggregation for small allocations: allocate the nodes in an array and dole it out from that. It can recycle unused nodes itself. Or you could just write the open-addressing HashMap, which is easier than implementing your own custom small allocation malloc()/free()? That's the thing. To make chaining competitive against open-addressing HashMaps, you've got to bend-over back…

[deleted]

Re: Optimizing Open Addressing

#42

Post by kazinator »

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 stepping stone to another entry. Chained hashing has no problem with deletion: an item is just spliced out of the list. Similarly, chained hashing with vectors could do the same thing. In any given secondary vector, we know that all the entries hashed to the same slot; we don't have to leave any tombstones. We don't have to move entries to close the gap; we can move the last element of the array to the deleted position and decrement the length.

Chained hashing with linked lists has a nice property when you reorganize the table; you don't have to reallocate any memory or do a lot of writes; just reshuffle the linked list pointers to reassign the nodes to the new chains of the resized table. If chains are vectors, this becomes more of a hassle. When growing the table, we allocate new vectors for the odd chains and then move about half the items from old chains to new chains.

Re: Optimizing Open Addressing

#44

Post by dragontamer »

kazinator wrote: post #33
mgaunard wrote: post #2

I find that there is too much of an emphasis on open-addressing in blog articles and such. There are a lot of real and common data structures where chaining is much better suited. For example whenever you have data part of one or multiple other node-based data structures, and you layer an index on top of that. Chaining also tends to waste a lot less memory.

Chaning still requires a flat table, which can change in size, and is proportional to the number of entries in the table (to keep the average chain length ("load factor") bounded). Thus, this can still cause memory fragmentation, even though the hash table chain nodes can all be the same size and so reduce fragmentation. In terms of absolute bytes, ignoring fragmentation, it depends on the load factors. In chaining,…

Hmm.

I think the main difference between your calcs and mine is that you have implemented a HashMap, while I was assuming a HashSet (so I only need to store the value, while in your case, you store (key,value)).

In any case, the larger the "entry", the less the 8-byte pointer matters. The smaller the "entry", the more the 8-byte pointer matters.

Re: Optimizing Open Addressing

#45

Post by KerrAvon »

citizen_friend wrote: post #28
mananaysiempre wrote: post #21

Earlier quoted context omitted.

TCC has the advantage of being a batch process, so it can insert things using open addressing without ever considering how it intends to delete them, then just drop the whole thing on the floor at the end. Of course, if you are also a batch process, you absolutely should do that too.

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

Re: Optimizing Open Addressing

#46

Post by anonymoushn »

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.

Re: Optimizing Open Addressing

#47

Post by kccqzy »

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?

Re: Optimizing Open Addressing

#48

Post by unwind »

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.

Re: Optimizing Open Addressing

#49

Post by mgaunard »

a1369209993 wrote: post #31
mgaunard wrote: post #5

Earlier quoted context omitted.

Nodes don't have to be allocated with malloc (that is actually the worst thing you could possibly do). An open-addressing hash table only performs well up to 50-75% bucket usage. Chaining doesn't care and performs the same up to 100%.

> (that is actually the worst thing you could possibly do) Nonsense, there are many worse things you could do. For example, you could allocate nodes with mmap, at 4KB per node. (Which is a thing I've actually done in the context of cursed bootstrap code where malloc isn't available and having more than a handful of (in that case doubly-linked-list) nodes means the environment is deranged anyway.)

Now that seems plain silly.

Re: Optimizing Open Addressing

#50

Post by [deleted] »

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…

[deleted]
Post reply on HN