With all of the recent performance improvements, around 50% of the time for creating frozen dictionaries/sets is now spent in FrozenHashTable.CalcNumBuckets.

The rest is now optimal, so my last effort was on optimizing FrozenHashTable.CalcNumBuckets.

To understand my approaches it's crucial to understand what the method is supposed to do and how it was achieving this goal so far.

The method tries to find a prime number of buckets that provide less than 5% collision rate for unique hash codes.

The first thing it does, it creates a hash set of integers and iterates over all hash codes to filter out the duplicates. It's important because no increase in buckets will avoid collisions from duplicate input hash codes.

Once we have the number of unique hash codes, it iterates over a precomputed array of prime numbers and find first prime number than is bigger than the unique hash code count.

Then it chooses a multiplier for the max bucket count, which is 16 for small bucket count (1_000) and 3 for larger inputs.

Then it sets the best number of collisions found so far to unique hash codes count, which means "so far the best result we found has given us 100% collision rate".

And finally it iterates over all of the prime numbers from selected range, and in the nested loop it iterates over every unique hash code and marks buckets as seen.

When it finds a bucket that was already visited, it increases collision count.
When the collision count becomes equal to the best known collision count, it bails and continues the search for next prime number.

When none of the prime numbers meet our 5% collision rate criteria, it returns the bucket count with the lowest collision count found for all prime numbers.

The approaches that I've tried:

• Setting initial best number of collisions to one more collision than 5%. It meant "find me the first bucket that meets the criteria" and was originally a part of Faster optimized frozen dictionary creation (3/n) #87688, but I've reverted the change. Why? Because for some inputs, it never finds a bucket that meets our criteria. And because of the fact that the inner loop stops when the collision count becomes equal to the best known collision rate, we had 0 fully-verified buckets at the end. So the process would need to be repeated with the initial best number of collisions found set to unique hash codes count. I added the fallback and wrote an app that was generating random sets of hash codes for an hour and benchmarking the old vs new approach and it turned out to be slower overall.
• Binary search, as it's more likely to find matching prime number for larger prime numbers. The perf gains were very nice, but again my app for random hash set generation proven that it's possible that binary search is going to miss the prime number that meets our goal.
• Based on the "it's more likely to find matching prime number for larger prime numbers" assumption, I've reverted the outer loop. It was starting at the largest acceptable prime number and ending at the smallest. The CPU time gains were great (up to 4x faster), but at the cost of increased memory consumption (in theory in worst case 16x for small inputs and x3 for large inputs).
• Increasing the min bucket count to 2x unique hash code count (from x1). I've modified my random hash code generator app to print me distributions of the selected prime numbers and bucket counts. It turned out that for small inputs (less than 1000 items), only 0.05% of prime numbers that were less than 2x unique hash code count were meeting the criteria. For larger inputs, it was just 0.01%. That is why I decided to narrow the range and keep everything else. On average this gives us a 10% perf gain for small inputs, 20% for medium and 30-40% for large inputs. It's a tradeoff, since 0.05% of cases are going to use larger arrays.

In the table below you can see perf numbers for #87688 as baseline, the mentioned loop reverse and proposed change: