The memory used is very high

efficient / libcuckoo

A high-performance, concurrent hash table

Other

1.62k stars 275 forks source link

The memory used is very high #134

Open gyd-a opened 3 years ago

gyd-a commented 3 years ago

data type(key: long, value: int)
data size(4200w)
CuckooHash uses 13GB of memory.
std::unordered_map uses 4GB of memory. What is the reason? thank you

manugoyal commented 3 years ago

Hi @gyd-a! Do you have a code sample I can run which reproduces the issue?

In general, there are two ways I can think of to reduce the maximum memory usage of the table:

Reserve the appropriate table size ahead of time. This improves performance by reducing the number of resize operations, and also reduces max memory usage because the newly resized table doesn't need to keep the memory of the old table around when lazily rehashing.
Use a larger SLOT_PER_BUCKET value (the default can be configured in libcuckoo/cuckoohash_config.hh. Roughly speaking, increasing SLOT_PER_BUCKET should improve memory utilization (higher load factor) at the cost of slower hashtable operations.

gyd-a commented 3 years ago

Thank you very much. We changed SLOT_PER_BUCKET from 4 to 8. Memory went from 13GB to 2.2GB. Replay test, unordered_map memory is 1.8g. SLOT_PER_BUCKET =16 is error. error: static assertion failed: pathcode may not be large enough to encode a cuckoo path static_assert(const_pow(slot_per_bucket(), MAX_BFS_PATH_LEN) <

gyd-a commented 3 years ago

As the file is relatively large, you can send your email to my email. I will send the file to your email. 1666066431@qq.com

manugoyal commented 3 years ago

Glad to hear that helped! Regarding the static_assert error, this is intentional, since we must encode any possible cuckooing path within an integer of size decltype(pathcode). You might be able to bump up the maximum SLOT_PER_BUCKET by changing pathcode from uint16_t to say uint64_t, but I haven't really experimented with this. Again it would be trading performance for memory utilization.