aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/erl_map.c
diff options
context:
space:
mode:
authorSverker Eriksson <[email protected]>2015-03-20 20:02:16 +0100
committerSverker Eriksson <[email protected]>2015-03-20 20:02:16 +0100
commit74099492bee421c4829537bca3c4bc0c4fbec031 (patch)
tree091301e2213ded2d211ee4ad451c1ede1b9da49c /erts/emulator/beam/erl_map.c
parentc0d3f4cbb5775a9214366e0d9cb76847d69c3459 (diff)
parentc1be2e5baed4794f7017dab9558afe8a737b63ee (diff)
downloadotp-74099492bee421c4829537bca3c4bc0c4fbec031.tar.gz
otp-74099492bee421c4829537bca3c4bc0c4fbec031.tar.bz2
otp-74099492bee421c4829537bca3c4bc0c4fbec031.zip
Merge branch 'sverk/hamt-overestimate/OTP-12585'
* sverk/hamt-overestimate/OTP-12585: erts: Add test map_SUITE:t_hashmap_balance erts: Fix hashmap overestimation erts: Silence valgrind warning in nif_SUITE.c
Diffstat (limited to 'erts/emulator/beam/erl_map.c')
-rw-r--r--erts/emulator/beam/erl_map.c27
1 files changed, 16 insertions, 11 deletions
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index bd6da0a6f1..bcbda65da0 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -2549,19 +2549,24 @@ static int int_sqrt_ceiling(Uint x)
}
}
-Uint hashmap_over_estimated_heap_size(Uint n)
+Uint hashmap_over_estimated_heap_size(Uint k)
{
- /* n is nr of key-value pairs.
- Average nr of nodes is about n/3.
- Standard deviation is about sqrt(n)/3.
- Assuming normal probability distribution,
- we overestimate nr of nodes by 14 std.devs, which gives a probability
- for overrun of 1.0e-49 (same magnitude as a git SHA1 collision).
+ /* k is nr of key-value pairs.
+ N(k) is expected nr of nodes in hamt.
+
+ Observation:
+ For uniformly distributed hash values, average of N varies between
+ 0.3*k and 0.4*k (with a beautiful sine curve)
+ and standard deviation of N is about sqrt(k)/3.
+
+ Assuming normal probability distribution, we overestimate nr of nodes
+ by 15 std.devs above the average, which gives a probability for overrun
+ less than 1.0e-49 (same magnitude as a git SHA1 collision).
*/
- Uint nodes = (n + int_sqrt_ceiling(n)*14) / 3;
- return (n*2 + /* leaf cons cells */
- n + /* leaf list terms */
- nodes*2); /* headers + parent refs */
+ Uint max_nodes = 2*k/5 + (15/3)*int_sqrt_ceiling(k);
+ return (k*2 + /* leaf cons cells */
+ k + /* leaf list terms */
+ max_nodes*2); /* headers + parent boxed terms */
}