🔒 Locked

open address hash map

Started by Lightness1024 Jun 18, 2015 at 3:50 PM 2 replies 4.2k views

Original Post

Jun 18, 2015 at 3:50 PM

Hi guys, I also have a piece of code tooling to give out.

https://sourceforge.net/projects/cgenericopenaddresshashmap/

I found that it is not so obivous to find a simple, integrable, open address hash map to a C++ project without going into crazy setups or extensive build fixings, or godknowswhat™ (licensing issues etc., you name it).

First let's link two stackoverflow threads for reference about other libraries that does similar things: https://stackoverflow.com/questions/3300525/super-high-performance-c-c-hash-map-table-dictionary

https://stackoverflow.com/questions/4573566/a-map-and-set-which-uses-contiguous-memory-and-has-a-reserve-function

rationale:

1. In game development, caring about memory is a huge must. Notably one very good rule of thumb is to never allow fragmentation to go rampant.

2. we need associative containers in many algorithms.

So if 1. and 2. met, the child they would have together would be called open address hash map.

vanilla std::unordered just doesn't cut it, because it is closed address and therefore allocates per element. (node based containment.) A problem to be mitigated by the use of allocators or something called burst allocation. Please c.f. this document: http://igaztanaga.vosi.biz/allocplus/ So anyway, for those who want to avoid headaches, why not give my hash map a try ?

Here is the page

https://sourceforge.net/projects/cgenericopenaddresshashmap/

bests to all

Pink Horror

Jun 18, 2015 at 10:31 PM

I could be missing it somewhere, but it looks like your erase function is missing the adjustment necessary for an open addressing hash table to continue to find everything after a cluster has formed from hash collisions, and an entry is removed from the middle of the cluster.

Lightness1024

Jun 18, 2015 at 11:38 PM

Oh my, and so it seems indeed !

You've got to love peer reviewing.

What is a good strategy for that in your experience ?

Seems like I will need to add a state bit to mark the zone as "free but followed". Damn it was so pure with just one bit.

Lightness1024

Jun 19, 2015 at 4:16 PM

Alright I worked a lot on it today, and made it pass the GCC test suite that exists for gcc's unordered_map.

The test is in samples/example.cpp, there is also an included benchmark. I made a linux cmakelists.txt too. I checked for errors in valgrind (there are none).

I have a reasonably good API conformance now, especially the range inserters that I didn't have before. or range erase.

(though for ranged erase, if you check cppreference.com they say the behavior is unclear.)

bench: (my oahm is marked with *)

with gcc 4.9 -O3 -DNDEBUG

AMD 6800k CPU


== 1 million int pushes ==
std vector:             13.5705 ms
reserved vector:        10.6002 ms
*open address:          266.702 ms
*reserved openaddr:     104.992 ms
std unordered:          273.966 ms
std map:                706.413 ms

== 100k random erasures ==
*openaddr:              8.72512 ms
std unordered:          21.1096 ms
std map:                71.8747 ms

== 1M iteration ==
*openaddr:              181.742 ms
std unordered:          989.945 ms
std map:                1707.21 ms

== 50k random finds among 1M contenance ==
*openaddr:              4.24008 ms
std unordered:          10.4447 ms
std map:                35.7247 ms

though, without optimizations (O0):


== 1 million int pushes ==
std vector:             58.4812 ms
reserved vector:        32.5 ms
*open address:          2431.55 ms
*reserved openaddr:     569.404 ms
std unordered:          592.048 ms
std map:                1365.31 ms

== 100k random erasures ==
*openaddr:              50.4781 ms
std unordered:          32.0725 ms
std map:                137.922 ms

== 1M iteration ==
*openaddr:              1985.11 ms
std unordered:          1324 ms
std map:                2050.55 ms

== 50k random finds among 1M contenance ==
*openaddr:              30.1838 ms
std unordered:          17.1743 ms
std map:                58.6488 ms

viva optimizers. don't get out without your -O2/3 folks.

missing the adjustment necessary for an open addressing hash table to continue to find everything after a cluster has formed from hash collisions, and an entry is removed from the middle of the cluster

Now about that, I read google's dense hash table implementation for a long while, and discovered that it is becoming quite crazy because of this problem. Indeed we need to track the state with a 'deleted' state, on top of just busy/free state. And keep a count of the total deleted slots, so that we can "garbage collect" some time in the future, either during rehash or later inserts. There is also some madness about checking for the next hash key while probing (to establish the limits of the cluster) on top of just the states.

google uses "find_position" which returns a pair, one pos for search and one pos for insertion.

It's funny I have almost the same helper, called "find_placement", which I am in progress of modifying to fix the bug.

EDIT: Status update - I fixed the bug, the map is now "behavior correct". But it is still incomplete because of "deleted" flag pollution. I need to improve that by garbage cleaning maybe during insert calls.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.