aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/erl_map.c
diff options
context:
space:
mode:
authorSverker Eriksson <[email protected]>2015-06-02 19:23:49 +0200
committerSverker Eriksson <[email protected]>2015-06-15 14:48:22 +0200
commit02d0ce034598297565f2b35ecc3d1af121787f33 (patch)
treea415e4b7d21c240352ae8737806e516caa2f2b43 /erts/emulator/beam/erl_map.c
parent512c321bdaf25b685124405e287a3839be467149 (diff)
downloadotp-02d0ce034598297565f2b35ecc3d1af121787f33.tar.gz
otp-02d0ce034598297565f2b35ecc3d1af121787f33.tar.bz2
otp-02d0ce034598297565f2b35ecc3d1af121787f33.zip
erts: Remove hashmap probabilistic heap overestimation
by adding a dynamic heap factory. "binary_to_term" is now a hybrid solution with both a call to decoded_size() to calculate needed heap space AND possible dynamic allocation of more heap space if needed for big maps. The heap size returned from decoded_size() is guaranteed to be sufficient for all term heap data except for hashmap nodes. All hashmap nodes are created at the end of dec_term() by invoking the heap factory interface that may allocate more heap space on process heap or in fragments. With this commit it is no longer guaranteed that a message is confined to only one heap fragment.
Diffstat (limited to 'erts/emulator/beam/erl_map.c')
-rw-r--r--erts/emulator/beam/erl_map.c27
1 files changed, 17 insertions, 10 deletions
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index a1bd39dbc8..09fc9a2ad6 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -410,8 +410,9 @@ static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) {
}
UnUseTmpHeap(2,p);
- factory.p = p;
+ erts_factory_proc_init(&factory, p);
res = hashmap_from_unsorted_array(&factory, hxns, size, 0);
+ erts_factory_close(&factory);
erts_free(ERTS_ALC_T_TMP, (void *) hxns);
ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
@@ -515,8 +516,9 @@ Eterm erts_hashmap_from_ks_and_vs_extra(Process *p, Eterm *ks, Eterm *vs, Uint n
hxns[i].i = i;
}
- factory.p = p;
+ erts_factory_proc_init(&factory, p);
res = hashmap_from_unsorted_array(&factory, hxns, sz, 0);
+ erts_factory_close(&factory);
erts_free(ERTS_ALC_T_TMP, (void *) hxns);
ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
@@ -1063,8 +1065,9 @@ static Eterm flatmap_merge(Process *p, Eterm nodeA, Eterm nodeB) {
hxns[i].i = i;
}
- factory.p = p;
+ erts_factory_proc_init(&factory, p);
res = hashmap_from_unsorted_array(&factory, hxns, n, 0);
+ erts_factory_close(&factory);
erts_free(ERTS_ALC_T_TMP, (void *) hxns);
ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
@@ -1107,8 +1110,9 @@ static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args)
hxns[i].i = i;
}
- factory.p = p;
+ erts_factory_proc_init(&factory, p);
res = hashmap_from_unsorted_array(&factory, hxns, n, 0);
+ erts_factory_close(&factory);
erts_free(ERTS_ALC_T_TMP, (void *) hxns);
ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
@@ -2504,6 +2508,9 @@ int erts_validate_and_sort_flatmap(flatmap_t* mp)
return 1;
}
+#if 0 /* Can't get myself to remove this beautiful piece of code
+ for probabilistic overestimation of nr of nodes in a hashmap */
+
/* Really rough estimate of sqrt(x)
* Guaranteed not to be less than sqrt(x)
*/
@@ -2525,7 +2532,10 @@ static int int_sqrt_ceiling(Uint x)
}
}
-Uint hashmap_over_estimated_heap_size(Uint k)
+/* May not be enough if hashing is broken (not uniform)
+ * or if hell freezes over.
+ */
+Uint hashmap_overestimated_node_count(Uint k)
{
/* k is nr of key-value pairs.
N(k) is expected nr of nodes in hamt.
@@ -2539,12 +2549,9 @@ Uint hashmap_over_estimated_heap_size(Uint k)
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 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 */
+ return 2*k/5 + 1 + (15/3)*int_sqrt_ceiling(k);
}
-
+#endif
BIF_RETTYPE erts_debug_map_info_1(BIF_ALIST_1) {
if (is_hashmap(BIF_ARG_1)) {