Super high performance C/C++ hash map (table, dictionary) [closed]

Question

I need to map primitive keys (int, maybe long) to struct values in a high-performance hash map data structure.

My program will have a few hundred of these maps, and each map will generally have at most a few thousand entries. However, the maps will be "refreshing" or "churning" constantly; imagine processing millions of add and delete messages a second.

What libraries in C or C++ have a data structure that fits this use case? Or, how would you recommend building your own? Thanks!

Starlight

Do you need to process search by keys into your data ? – Typecase

will updates or retrievals be more frequent? (add/delete, or read/update which is not changing the key) – Lusty

#266706 . This maybe a good place to start. – Splice

@Guillaume Lebourgeois: All the operations will be on a per-key basis. Eventually I'll be processing across large sets of keys or values, but I suspect that would be better suited to a tree structure. – Starlight

@roe: The add/delete operations are much (100x) more frequent than the get operation. – Starlight

Will multiple threads be used to access each hashmap? Or can we assume they will be accessed by a single thread only. – Lactoprotein

@Caspin: Good question; it's single-threaded access only. – Starlight

@Haywood: I would suggest to enhance your question with more information on application field and some sample data. You might be asking wrong question. Or in your application field there might be already well known methods to work the problems around. – Mortify

After four and a half years it would be interesting to know what did fit your needs best. If none of the current answers was satisfactory, you can write your own and accept it. – Sighted

Thanks for closing such a useful question @ StackOverflow Mods – Hobart

Following benchmark might help to choose the right one: martin.ankerl.com/2022/08/27/hashmap-bench-01 – Trulatrull

Answer 1

I would recommend you to try Google SparseHash (or the C11 version Google SparseHash-c11) and see if it suits your needs. They have a memory efficient implementation as well as one optimized for speed. I did a benchmark a long time ago, it was the best hashtable implementation available in terms of speed (however with drawbacks).

Momism

Can you elaborate on what the drawbacks were? – Starlight

IIRC, it was a memory problem, when removing an element, the element was destructed but its memory was still alive (used as a cache I guess). – Momism

@Haywood Jablomey: The main drawback is that it requires you to split off one or two (if you ever erase elements) values and never use those. In some cases this is easy to do, e.g. negative ints or like that, but in other cases not quite so. – Platinize

Would you stand by this recommendation today? – Greatnephew

Answer 2

What libraries in C or C++ have a data structure that fits this use case? Or, how would you recommend building your own? Thanks!

Check out the LGPL'd Judy arrays. Never used myself, but was advertised to me on few occasions.

You can also try to benchmark STL containers (std::hash_map, etc). Depending on platform/implementation and source code tuning (preallocate as much as you can dynamic memory management is expensive) they could be performant enough.

Also, if performance of the final solution trumps the cost of the solution, you can try to order the system with sufficient RAM to put everything into plain arrays. Performance of access by index is unbeatable.

The add/delete operations are much (100x) more frequent than the get operation.

That hints that you might want to concentrate on improving algorithms first. If data are only written, not read, then why write them at all?

Mortify

Answer 3

Just use boost::unordered_map (or tr1 etc) by default. Then profile your code and see if that code is the bottleneck. Only then would I suggest to precisely analyze your requirements to find a faster substitute.

Copycat

It is. VS2013's std::unordered_map is taking 90+% of my entire execution time, even though I only use the maps for a relatively small part of the processing. – Dinodinoflagellate

Answer 4

If you have a multithreaded program, you can find some useful hash tables in intel thread building blocks library. For example, tbb::concurrent_unordered_map has the same api as std::unordered_map, but it's main functions are thread safe.

Also have a look at facebook's folly library, it has high performance concurrent hash table and skip list.

Explicate

Answer 5

khash is very efficient. There is author's detailed benchmark: https://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/ and it also shows khash beats many other hash libraries.

Monostylous

Answer 6

from android sources (thus Apache 2 licensed)

https://github.com/CyanogenMod/android_system_core/tree/ics/libcutils

look at hashmap.c, pick include/cutils/hashmap.h, if you don't need thread safety you can remove mutex code, a sample implementation is in libcutils/str_parms.c

Ytterbite

Answer 7

First check if existing solutions like libmemcache fits your need.

If not ...

Hash maps seems to be the definite answer to your requirement. It provides o(1) lookup based on the keys. Most STL libraries provide some sort of hash these days. So use the one provided by your platform.

Once that part is done, you have to test the solution to see if the default hashing algorithm is good enough performance wise for your needs.

If it is not, you should explore some good fast hashing algorithms found on the net

1. good old prime number multiply algo
2. http://www.azillionmonkeys.com/qed/hash.html
3. http://burtleburtle.net/bob/
4. http://code.google.com/p/google-sparsehash/

If this is not good enough, you could roll a hashing module by yourself, that fixes the problem that you saw with the STL containers you have tested, and one of the hashing algorithms above. Be sure to post the results somewhere.

Oh and its interesting that you have multiple maps ... perhaps you can simplify by having your key as a 64 bit num with the high bits used to distinguish which map it belongs to and add all key value pairs to one giant hash. I have seen hashes that have hundred thousand or so symbols working perfectly well on the basic prime number hashing algorithm quite well.

You can check how that solution performs compared to hundreds of maps .. i think that could be better from a memory profiling point of view ... please do post the results somewhere if you do get to do this exercise

I believe that more than the hashing algorithm it could be the constant add/delete of memory (can it be avoided?) and the cpu cache usage profile that might be more crucial for the performance of your application

good luck

Gyroplane

Answer 8

Try hash tables from Miscellaneous Container Templates. Its closed_hash_map is about the same speed as Google's dense_hash_map, but is easier to use (no restriction on contained values) and has some other perks as well.

Platinize

Answer 9

I would suggest uthash. Just include #include "uthash.h" then add a UT_hash_handle to the structure and choose one or more fields in your structure to act as the key. A word about performance here.

Pennipennie

Answer 10

http://incise.org/hash-table-benchmarks.html gcc has a very very good implementation. However, mind that it must respect a very bad standard decision :

If a rehash happens, all iterators are invalidated, but references and pointers to individual elements remain valid. If no actual rehash happens, no changes.

http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/

This means basically the standard says that the implementation MUST BE based on linked lists. It prevents open addressing which has better performance.

I think google sparse is using open addressing, though in these benchmarks only the dense version outperforms the competition. However, the sparse version outperforms all competition in memory usage. (also it doesn't have any plateau, pure straight line wrt number of elements)

His

See also this, which discusses how the bucket interface also requires chaining. The point about references is very good. It's tempting to argue & say it's a useful guarantee, but in many cases we only want references to avoid looking up elements again, & the usual reason is because lookup is too slow... which it wouldn't be if it didn't have to keep references valid and hence could use open addressing! So it seems a bit chicken-and-egg. This cites the 2003 proposal, explicitly discussing the choice. – Amaral