diff options
Diffstat (limited to 'erts/emulator/beam')
| -rw-r--r-- | erts/emulator/beam/erl_bif_info.c | 20 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_map.c | 27 |
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 */ } |