4 ms·

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++'

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.

4 ms·

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++'

by badsectoracula 4y ago

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.