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

2 files changed, 36 insertions, 11 deletions

diff --git a/erts/emulator/beam/erl_bif_info.c b/erts/emulator/beam/erl_bif_info.c
index d750e34be3..0774ab51af 100644
--- a/erts/emulator/beam/erl_bif_info.c
+++ b/erts/emulator/beam/erl_bif_info.c
@@ -3597,6 +3597,26 @@ BIF_RETTYPE erts_debug_get_internal_state_1(BIF_ALIST_1)
 
 		BIF_RET(erts_debug_reader_groups_map(BIF_P, (int) groups));
 	    }
+	    else if (ERTS_IS_ATOM_STR("internal_hash", tp[1])) {
+		Uint hash = (Uint) make_internal_hash(tp[2]);
+		Uint hsz = 0;
+		Eterm* hp;
+		erts_bld_uint(NULL, &hsz, hash);
+		hp = HAlloc(BIF_P,hsz);
+		return erts_bld_uint(&hp, NULL, hash);
+	    }
+	    else if (ERTS_IS_ATOM_STR("atom", tp[1])) {
+		Uint ix;
+		if (!term_to_Uint(tp[2], &ix))
+		    BIF_ERROR(BIF_P, BADARG);
+		while (ix >= atom_table_size()) {
+		    char tmp[20];
+		    erts_snprintf(tmp, sizeof(tmp), "am%x", atom_table_size());
+		    erts_atom_put((byte *) tmp, strlen(tmp), ERTS_ATOM_ENC_LATIN1, 1);
+		}
+		return make_atom(ix);
+	    }
+
 	    break;
 	}
 	default:
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 */
 }