4 ms·

How would pre-allocating affect the lookup time? Am I naive in thinking it would only be insert time that would be affected by pre-allocating? Also I would rec

by eterm 4y ago

How would pre-allocating affect the lookup time? Am I naive in thinking it would only be insert time that would be affected by pre-allocating? Also I would recommend swapping the order in which you are testing them, just in case there are any issues there. While I would expected the std implementation to be slower, that certainly feels like an order of magnitude too slow for the standard library.

badsectoracula 4y ago
You specify the number of buckets but it can still affect how they're built and thus how they are used. This is a guess TBH since i don't know exactly what G++'s unordered_set does. You are right about execution order, not sure what is going on since both are isolated (i literally just swapped the code around) but doing that almost doubled the std version performance :-/ - the custom one didn't change at all though. Perhaps the optimizer somehow interferes with both tests since the code is next to each and they use the same source data - a way to work around that might be to implement the lookup tests in separate shared objects with the "fill set" and "lookup set" to be in separate functions. I might do that at some point later.
- eterm 4y ago
  Oh I see, how many did you choose for the bucket numbers? ( I assumed pre-allocate was a capacity allocation rather than bucket parameter ) I'd recommend 82139 which is the closest prime above 82137 which is Sqrt(Pi/2 * 2^32) which is the expected number of items before a collision. I'd also be interested to hear the performance under the hash function: hash(x) = x This is the CLR and JRE's prefered int32 hash. It's a poor hash for cryptographic purposes or wanting random bits but it has stellar performance for the most part.
  - badsectoracula 4y ago
    I linked the source above. The bucket count is a bit highter than 82139... just 101473717 :-P. Changing it with 82139 does make it twice as slow though. I used 101473717 because that was the number i got from bucket_count() after running it with the default buckets. About hash(x)=x, that is interesting, i never thought to just use x itself as the hash :-P. The performance is actually a tiny bit better (~17%) for checking if a number is in the set.

by eterm 4y ago

badsectoracula 4y ago

You specify the number of buckets but it can still affect how they're built and thus how they are used. This is a guess TBH since i don't know exactly what G++'s unordered_set does. You are right about execution order, not sure what is going on since both are isolated (i literally just swapped the code around) but doing that almost doubled the std version performance :-/ - the custom one didn't change at all though. Perhaps the optimizer somehow interferes with both tests since the code is next to each and they use the same source data - a way to work around that might be to implement the lookup tests in separate shared objects with the "fill set" and "lookup set" to be in separate functions. I might do that at some point later.

eterm 4y ago
Oh I see, how many did you choose for the bucket numbers? ( I assumed pre-allocate was a capacity allocation rather than bucket parameter ) I'd recommend 82139 which is the closest prime above 82137 which is Sqrt(Pi/2 * 2^32) which is the expected number of items before a collision. I'd also be interested to hear the performance under the hash function: hash(x) = x This is the CLR and JRE's prefered int32 hash. It's a poor hash for cryptographic purposes or wanting random bits but it has stellar performance for the most part.
- badsectoracula 4y ago
  I linked the source above. The bucket count is a bit highter than 82139... just 101473717 :-P. Changing it with 82139 does make it twice as slow though. I used 101473717 because that was the number i got from bucket_count() after running it with the default buckets. About hash(x)=x, that is interesting, i never thought to just use x itself as the hash :-P. The performance is actually a tiny bit better (~17%) for checking if a number is in the set.