Right sizing HashSet ctor is allocating too many elements

[ViktorHofer]

When initializing a HashSet like this:

new HashSet<string>(80_000_000);

the underlying arrays (buckets and slots) will not have the size of ~80M (its next prime number) but the size of the next prime number in the pre-computed list, which is 92_434_613. This is an oversize of 11.55% and is not expected by the user. The worst case is that the array gets oversized by 20% because of the layout of the pre-computed prime numbers.

This was introduced by dotnet/corefx#6203

cc @jkotas @stephentoub @danmosemsft

[stephentoub]

I commented on this in that PR:
dotnet/corefx#6203 (comment)

@vancem countered he didn't think it was a problem:
dotnet/corefx#6203 (comment)

[vancem]

I am always open to new data, but there is a rationale for my statement in dotnet/corefx#6203. The rational is that explicitly setting the size of a data table to a large value is pretty rare, and knowing that that size accurately is rarer still (often you only know that the table will be 'big' but not know accurately how bit it will grow). Without a scenario where you know an accurate size, on average any particular number is as good as any other (it will make some instances improve, and some will regress, but no number has a clear advantage or disadvantage on average). In addition for this to matter, it has to be the case that in the scenario HashSet is a important part of the overall memory usage for the scenario, and that memory is an important metric (many times it is not).

Now as I said, I am open to new data. If we have some concrete evidence that there are scenarios that I was arguing above are more common that I am suggesting that they are, then we can certainly talk about mitigations (e.g. we could make the table finer grained, or put back the more expensive prime test or use a probabilistic (efficient) prime generation scheme).

But I think we need more before we prioritize this work. There are plenty of perf improvements we CAN make, and we should have some evidence that this is worthwhile before investing.

[ViktorHofer]

@vancem My naive approach to fix this (by bringing back the calculation can be find here): dotnet/corefx#25509

cc @jkotas

[vancem]

How did you find this issue? Was it code inspection or did you actually run into an issue?

A surprising about of discussion happened associated with dotnet/corefx#6203, because frankly it was a inconsequential issue that as a perf optimization was of dubious value. However it WAS demonstrably SIMPLER, and that is what made me argue for ACCEPTING it (Because simplicity is the ONE thing you should do by default)

However going the other direction (adding complexity to the code base), DOES require justification. Yes, it is small, but for better or worse at this point it is NEW work, and NEW complexity and NEW risk of bugs etc.

Basically the easiest thing do to is NOTHING and to KEEP simplicity.

Do we have some (cheap) evidence that there is interesting value in adding this complexity?

[jkotas]

explicitly setting the size of a data table to a large value is pretty rare

I agree that they are rare, but I do not see the point in regressing them by replacing 15 lines of code by 150 bytes of inline data.

perf optimization was of dubious value

Agree. The most likely user observable effect of dotnet/corefx#6203 is performance regression (more memory consumption) - if you went into trouble to preallocate large dictionary of the right size. Nobody else will see a difference.

Basically the easiest thing do to is NOTHING and to KEEP simplicity.

@ViktorHofer notice that we are inconsistent - some of the collections use the precise prime computation and others do not. He opened this issue in his attempt to unify.

[vancem]

I agree that they are rare, but I do not see the point in regressing them by replacing 15 lines of code by 150 bytes of inline data.

Although not captured in the original issue, I believe someone actually noticed the CPU usage in that IsPrime function because it is roughly N*N algorithm for large N, which ultimately started the issue. That also should be rare, but it would be nice not to ping-pong between trading off two rare users. I can't document how important that case is, but I could certainly imagine wasting many milliseconds and maybe more if the N is in the 10s of millions. For this user I think startup time was important.

My resolution to this quandary was to let simplicity be the guide. The resulting fix was simpler and does not have perf cliffs (in this case on startup), and is simpler (the original code already had a table, we just grew it from about 120 bytes to probably 280 bytes.

If you could JUST use the primality test, I agree that would be simpler. But that leaves us with what is really a silly perf issue when N is large (spinning doing prime tests really does look like wasted CPU. I don't really like that as an option give that we KNOW that we have had complaints (justified or not).

For what it is worth, the argument for having primes for the hash table size is actually not that strong. It only matters when your hash function is poor, or you have a closed hash table with linear probing (which we don't do), and even then, the bad results are proportional to the 1/GCD, which if we insure that is bigger than say 10K we should be more than fine (or using a fast prime probing using https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test).

Like I said, I am OK with exploring things like this, but it is at a least some work, and so I would want be clear about the data that justifies the investment.

My personal solution here is to do nothing (including leaving this issue open). Either we get complaints/find real scenarios, or we don't. If we do, we pursue one of the suggested fixes, but in the mean time we have kept costs to a minimum.

OK, I am going back to other work now....

[jkotas]

I could certainly imagine wasting many milliseconds and maybe more if the N is in the 10s of millions

GetPrime takes 0.1s milliseconds on my machine for numbers near Int32.MaxInt. It is nothing compared to allocating and filling in gigabytes of memory that will follow call to this method and that is going to take seconds.

[ViktorHofer]

Please only pay attention to the allocated tab!

Test code:

// This is a prime number which we increment by one to get the worst result back.
int capacity = 7_199_369 + 1;
var hashSet = new HashSet<string>(capacity);

.NET Core 2.1.0-preview1-25919-02

Method	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
HashSet_PrimePlus1	1.020 ms	1.527 ms	0.0863 ms	1000.0000	1000.0000	1000.0000	164.78 MB

.NET Core 4.5.0-preview1-25927-0 (locally build private package from the PR dotnet/corefx#25509)

Method	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
HashSet_PrimePlus1	750.1 us	2,437.0 us	137.7 us	1000.0000	1000.0000	1000.0000	137.32 MB

[vancem]

GetPrime takes 0.1s milliseconds on my machine for numbers near Int32.MaxInt. It is nothing compared to allocating and filling in gigabytes of memory that will follow call to this method and that is going to take seconds

Did you try fairly large swatch of numbers (e.g. the top 1GB probing every 10K numbers for 100K probes looking for the max? You definitely could be 'lucky' at any particular number because the next prime 'happens' to be close.

If we find that it is uniformly small enough, then I am OK with switching to that. Note that I would argue, however that we should uniformly compute the prime (thus drop the table completely). Again it is simpler, and your arguments are actually more compelling for the small cases (the ratio of the overhead of getPrime to the allocation cost should be smaller).

[ViktorHofer]

private readonly int randomHighNumber = new Random().Next(int.MaxValue - 500_000_000, int.MaxValue);

[Benchmark]
public void HashSet_PrimeRandomMax()
{
     GetPrime(randomHighNumber);
}

BenchmarkDotNet=v0.10.10, OS=Windows 10.0.17046
Processor=Intel Core i7-6600U CPU 2.60GHz (Skylake), ProcessorCount=4
Frequency=2742188 Hz, Resolution=364.6723 ns, Timer=TSC
.NET Core SDK=2.1.1
  [Host]     : .NET Core ? (Framework 4.6.25917.03), 64bit RyuJIT
  Job-GNPLZZ : .NET Core 2.1.0-preview1-25919-02 (Framework 4.6.25917.03), 64bit RyuJIT

Runtime=Core  Toolchain=Core 2.1.0-preview1-25919-02  InvocationCount=10  
LaunchCount=1  TargetCount=3  UnrollFactor=1  
WarmupCount=1  

Method	Mean	Error	StdDev	Allocated
HashSet_PrimeRandomMax	55.94 us	20.86 us	1.178 us	0 B

[vancem]

The data above is certainly encouraging, but it only has 10 samples so is not really telling us 'worse case' like what we want. It is not hard to use Stopwatch to do a more thorough test. If this is kept below 0.1 msec I am happy enough.

We should insure that everyone on dotnet/corefx#6203 is mentioned on this issue so they get to chime in with their concerns.

As I mentioned, I am for simplicity, which argues that if you want to use this, use it everywhere (so a profile showing that GetPrime costs 'nothing' in that case would be good.

[ViktorHofer]

Thanks Vance, you are right, I forgot to adjust the config. This sample should now be representative. The benchmark had a TargetCount of 17, which was automatically chosen.

BenchmarkDotNet=v0.10.10, OS=Windows 10.0.17046
Processor=Intel Core i7-6600U CPU 2.60GHz (Skylake), ProcessorCount=4
Frequency=2742188 Hz, Resolution=364.6723 ns, Timer=TSC
.NET Core SDK=2.1.1
  [Host]     : .NET Core ? (Framework 4.6.25917.03), 64bit RyuJIT
  Job-EWPZSU : .NET Core 2.1.0-preview1-25919-02 (Framework 4.6.25917.03), 64bit RyuJIT

Runtime=Core  Toolchain=Core 2.1.0-preview1-25919-02  InvocationCount=100000  
LaunchCount=1  UnrollFactor=10  WarmupCount=10  

Method	Mean	Error	StdDev	Allocated
HashSet_PrimeRandomMax	57.47 us	1.126 us	1.157 us	0 B

We should insure that everyone on dotnet/corefx#6203 is mentioned on this issue so they get to chime in with their concerns.

cc @SunnyWar @JonHanna @stephentoub @weshaggard

[SunnyWar]

The original algorithm would always use the nearest predefined values regardless of what you initialized it to, unless it feel outside a very large size at the time: 7199369. Only in this case would it compute the nearest prime. The problem with this approach is that as the table expands there are many more and expansive IsPrime calcuations. The change in dotnet/corefx#6203 was to expand the table so that no computation has to be done. This is to accommodate the most common use case: an expanding hashtable with an unknown upper bounds.

Clearly this does not address that case where a table is initialized to a specific value. I don't think it's ever been well suited to this. I've thought from the beginning that this was an oversight. As a matter of fact, I've assumed from the beginning that a GetNextPrime function will be put in using a reanimated IsPrime function that will be used only by explicit initialization.

Recommended heuristic:

1. Current algorithm is used when hashtable dynamically grows: bucket size increases by table lookup.
2. Explicitly initialized value is used to find the next greatest prime, bucket size is set to this value. If table grows greater than this value then Issue - corefx#1 is used. (this is a change to how it works today)

[vancem]

@SunnyWar do we have a scenario with perf data that shows that the prime calculation is ever a problem? It seems to me that the 'worse case' that is realistic would be to set the size to the last size in the static table and then keep adding elements (which will cause growth each time the table gets full).

However it is my strong suspicion that the prime calculation will always be small in comparison to the other work (the adding of the elements, and the copying to the new tables each time it resizes). We should test my hypothesis before we bother to optimize it.

My expectation is that uniformly computing primes rather than looking them up would also be fine (again because it seems that finding primes is cheap with respect to the other work and that only gets better (it is easier to find a prime) when the numbers are small.