Decrease HashMap Load Factor

[pssalmeida]

Currently HashMap uses a load factor of approximately 0.9. While this is appropriate for reads (get), as Robin Hood Hashing gives a low distance from the starting point with very low, effectively fixed variance, such is not the case for writes (insert).

When writing over an occupied bucked, it will incur a displacement involving reads and writes over several buckets, either for the new value or the values already in the map. Not only this number is larger than for reads, but also has an increasing variance, quickly becoming very large as load approaches 1.

For a load factor a: (UPDATED, previous lookup values were for random probing)

• the average number of probes in a read is 1/a*ln(1/1-a)) (1+1/(1-a))/2
• the average number of written buckets in a write is 1/(1-a)
• the probability of writing no more than k buckets in a write is 1 - a^k

In a table, the average buckets written, the 95th percentile buckets written, and the average buckets probed in a get, for different load factors:

a	Avg W	95% W	Avg R
0.500	2	4.3	1.39 1.5
0.666	3	7.4	1.65 2.0
0.750	4	10.4	1.84 2.5
0.800	5	13.4	2.01 3.0
0.833	6	16.4	2.15 3.5
0.857	7	19.4	2.27 4.0
0.875	8	22.4	2.38 4.5
0.888	9	25.4	2.47 5.0
0.900	10	28.4	2.56 5.5
0.950	20	58.4	3.15 10.5
0.990	100	298.1	4.65 50.5

It can be seen that for a = 0.9, the average probes when reading is just 2.56 5.5, but the average number of buckets written when inserting is 10 and the 95th percentile is 28 buckets. For deletes it will not be much better when doing the backwards shift, as most keys will be displaced from their origin (the very low variance behaviour or RH).

While for many cases, the average over the map lifetime may not be much impacted, if it happens that a map is being operated near capacity, with elements constantly being inserted and others removed, e.g., when implementing an LRU cache, the number of buckets (re)written per insert (and also per delete) will be manifestly higher than desired.

While the exact load factor choice can be argued about, it seems that 0.9 is manifestly too high. Going from 0.9 to 0.8 would have a 12.5% memory overhead, while going from 0.8 to 0.9 doubles the average number of buckets written when inserting, and more than doubles the 95th percentile. Therefore, a load factor around 0.8 seems more reasonable.

[sfackler]

Concrete performance numbers for various load factors would probably be helpful.

[abonander]

Honestly, why isn't the load factor configurable to begin with? That would make it quite a bit easier to tune for specific use cases.

[arthurprs]

I was going to propose 0.833 (5/6) based on some tests I ran earlier, but we need more numbers to take an informed decision.

[funny-falcon]

Looks like 0.8 gives 20% improvement on read (ok, number of buckets readed is not directly transfers to performance, but still).

[pczarn]

I don't know the distribution for the number of buckets accessed by insertion, but here are accurate numbers for lookup.

a	50% R	90% R	95% R
0.8	1.8	5.5	7.0
0.833	2.1	6.7	8.7
0.9	3.5	10.9	14.5

[funny-falcon]

So, 0.8 compared to 0.833 consumes 5% more memory and gives 15-20% less collision chain.

[arthurprs]

@funny-falcon how did you come up with these numbers?

[pssalmeida]

@abonander I also found surprising not being able to choose load factor, something that would be a good idea. Anyway, the question about what the sensible default should be remains.

@pczarn I find strange such long tails for lookup distribution ... I had the impression the variance would be much less. Also the shape does not look right. For high load factor it should start by a gentle slope and have a steep slope near the average.

Anyway, lookups are not the problem, as we are talking about 1 cache line most times, sometimes 2, rarely more than 2. I would also point out that for inserts, the cost is "amplified" by the payload size. We are not talking about only traversing hashes. An average of 10 means, in addition to the hashes, displacing 10 times the size of key and value. This makes such large numbers even more scary.

[funny-falcon]

@arthurprs only with mathematics and numbers from a table above. (Not, I've edited my comment: 15-20% less collision chain, not performance. Cause of great cache locality of Robin-Hood hashing, performance difference will be usually lesser).

For used space:

• 0.833 fill rate means one need 1/0.833=1.2 space, or 20% excess space.
• 0.8 fill rate means one need 1/0.8=1.25 space, or 25% excess space.
• 1.25/1.2 = 1.042, so it means, 0.8 fill rate uses 4.2% more space (in average) than 0.833 fill rate.

[matklad]

@pssalmeida are those back of an envelope calculations? They feel a bit odd to me, because they say that the average probe count for reading at 0.9 load factor should be 2.56. I've recently measured plain linear probing and robin hood hashing and I get 5.48 as the average probe length (for the elements which are in the table). Perhaps my measurements are wrong, but it still might be a good idea to instrument and measure the current implementation, as suggested by @sfackler .

[arthurprs]

@matklad I was checking your test-repo, I can't wrap my head around the timing/cache results. It should take less time and put less pressure on the cache, it makes no sense to me whatsoever.

[matklad]

@arthurprs this puzzles me as well! I want to plot the actual distribution of probe lengths and to run some specific tests about cache access (basically execute queries like "sum of the elements from i to k + i" with different distributions of k). But at least the paper you've linked to from another issues seems to imply that RH is not automatically better than plain LP?

We can conclude that RH provides a very interesting trade-off: for a small penalty (often within 1-5%) in peak performance on the best of cases (all lookups successful), RH significantly improves on the worst-case over LP in general, up to more than a factor 4.