search

martinus / unordered_dense

A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion
MIT License
898 stars 72 forks source link

[BUG] reserve does not call m_values.reserve(...) #14

Closed jcelerier closed 2 years ago

jcelerier commented 2 years ago

Describe the bug I'd expect a call to map / set :: reserve to preallocate the memory of the m_values vector. Right now it does not happen - if I add a blanket m_values.reserve(capa) in there, I immediately get a few % improvements - for instance, for an input of ~100k strings (every filename in /usr/include), I get

insert: 5148us  (inserting the 100k elements)
find: 4740us (finding every individual element in a random order)

while if I add the call to m_values.reserve in map::reserve, I get:

insert: 4284us 
find: 4288us
jcelerier commented 2 years ago

(for reference, std::unordered_map gives me things that look like this so.. nice!):

insert: 11374us 
find: 9526us