aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator
diff options
context:
space:
mode:
Diffstat (limited to 'erts/emulator')
-rw-r--r--erts/emulator/beam/erl_map.c37
-rw-r--r--erts/emulator/beam/erl_map.h1
-rw-r--r--erts/emulator/beam/erl_utils.h1
-rw-r--r--erts/emulator/beam/external.c60
-rw-r--r--erts/emulator/beam/utils.c11
5 files changed, 81 insertions, 29 deletions
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index 3ccfc61b08..5eafa69b06 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -2437,6 +2437,43 @@ int erts_validate_and_sort_map(map_t* mp)
return 1;
}
+/* Really rough estimate of sqrt(x)
+ * Guaranteed not to be less than sqrt(x)
+ */
+static int int_sqrt_ceiling(Uint x)
+{
+ int n;
+
+ if (x <= 2)
+ return x;
+
+ n = erts_fit_in_bits_uint(x-1);
+ if (n & 1) {
+ /* Calc: sqrt(2^n) = 2^(n/2) * sqrt(2) ~= 2^(n/2) * 3 / 2 */
+ return (1 << (n/2 - 1)) * 3;
+ }
+ else {
+ /* Calc: sqrt(2^n) = 2^(n/2) */
+ return 1 << (n / 2);
+ }
+}
+
+Uint hashmap_over_estimated_heap_size(Uint n)
+{
+ /* 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).
+ */
+ Uint nodes = (n + int_sqrt_ceiling(n)*14) / 3;
+ return (n*2 + /* leaf cons cells */
+ n + /* leaf list terms */
+ nodes*2); /* headers + parent refs */
+}
+
+
BIF_RETTYPE erts_debug_map_info_1(BIF_ALIST_1) {
if (is_hashmap(BIF_ARG_1)) {
BIF_RET(hashmap_info(BIF_P,BIF_ARG_1));
diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h
index 39d98b9e03..659295184d 100644
--- a/erts/emulator/beam/erl_map.h
+++ b/erts/emulator/beam/erl_map.h
@@ -99,6 +99,7 @@ Eterm erts_hashmap_insert_up(Eterm *hp, Eterm key, Eterm value,
Uint *upsz, struct ErtsEStack_ *sp);
int erts_validate_and_sort_map(map_t* map);
+Uint hashmap_over_estimated_heap_size(Uint n);
void hashmap_iterator_init(struct ErtsWStack_* s, Eterm node);
Eterm* hashmap_iterator_next(struct ErtsWStack_* s);
int hashmap_key_hash_cmp(Eterm* ap, Eterm* bp);
diff --git a/erts/emulator/beam/erl_utils.h b/erts/emulator/beam/erl_utils.h
index c772a750f1..7cb8972e29 100644
--- a/erts/emulator/beam/erl_utils.h
+++ b/erts/emulator/beam/erl_utils.h
@@ -113,6 +113,7 @@ void erts_silence_warn_unused_result(long unused);
int erts_fit_in_bits_int64(Sint64);
int erts_fit_in_bits_int32(Sint32);
+int erts_fit_in_bits_uint(Uint);
int erts_list_length(Eterm);
int erts_is_builtin(Eterm, Eterm, int);
Uint32 make_broken_hash(Eterm);
diff --git a/erts/emulator/beam/external.c b/erts/emulator/beam/external.c
index 9bcd9a7a50..bd9ad65086 100644
--- a/erts/emulator/beam/external.c
+++ b/erts/emulator/beam/external.c
@@ -2945,13 +2945,11 @@ struct dec_term_hamt_placeholder
struct dec_term_hamt_placeholder* next;
Eterm* objp; /* write result here */
Uint size; /* nr of leafs */
- Eterm* leaf_array;
-
- Eterm _heap_capacity_[1];
+ Eterm leafs[1];
};
-#define DEC_TERM_HAMT_PLACEHOLDER_SIZE(SZ) \
- (offsetof(struct dec_term_hamt_placeholder, _heap_capacity_) + (SZ))
+#define DEC_TERM_HAMT_PLACEHOLDER_SIZE \
+ (offsetof(struct dec_term_hamt_placeholder, leafs) / sizeof(Eterm))
/* Decode term from external format into *objp.
** On failure return NULL and *hpp will be unchanged.
@@ -3646,8 +3644,7 @@ dec_term_atom_common:
holder->objp = objp;
holder->size = size;
- hp += DEC_TERM_HAMT_PLACEHOLDER_SIZE(size);
- holder->leaf_array = hp;
+ hp += DEC_TERM_HAMT_PLACEHOLDER_SIZE;
for (n = size; n; n--) {
CDR(hp) = (Eterm) COMPRESS_POINTER(next);
@@ -3899,30 +3896,33 @@ dec_term_atom_common:
maps_list = next;
}
- while (hamt_list) {
- ErtsHeapFactory factory;
- int residue;
-
- factory.p = NULL;
- factory.hp = (Eterm*) hamt_list;
- factory.hp_end = hamt_list->leaf_array;
+ /* Iterate through all the hamts and build tree nodes.
+ */
+ if (hamt_list) {
+ struct dec_term_hamt_placeholder* hamt = hamt_list;
+ ErtsHeapFactory factory;
+
+ factory.p = NULL;
+ factory.hp = hp;
+ /* We assume heap will suffice (see hashmap_over_estimated_heap_size) */
+ factory.hp_end = hp + (ERTS_SWORD_MAX / sizeof(Eterm));
+
+ do {
+ *hamt->objp = erts_hashmap_from_array(&factory,
+ hamt->leafs,
+ hamt->size,
+ 1);
+ if (is_non_value(*hamt->objp))
+ goto error;
- next = (Eterm *) hamt_list->next;
- objp = hamt_list->objp;
+ hamt_list = hamt->next;
- *objp = erts_hashmap_from_array(&factory,
- hamt_list->leaf_array,
- hamt_list->size,
- 1);
- if (is_non_value(*objp))
- goto error;
+ /* Yes, we waste a couple of heap words per hamt
+ for the temporary placeholder */
+ *(Eterm*)hamt = make_pos_bignum_header(DEC_TERM_HAMT_PLACEHOLDER_SIZE-1);
+ } while (hamt_list);
- residue = factory.hp_end - factory.hp;
- if (residue) {
- ASSERT(residue > 0);
- *factory.hp = make_pos_bignum_header(residue-1);
- }
- hamt_list = (struct dec_term_hamt_placeholder*) next;
+ hp = factory.hp;
}
if (ctx) {
@@ -4292,6 +4292,8 @@ encode_size_struct_int(TTBSizeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj,
return 0;
}
+
+
static Sint
decoded_size(byte *ep, byte* endp, int internal_tags, B2TContext* ctx)
{
@@ -4488,7 +4490,7 @@ init_done:
if (n <= MAP_SMALL_MAP_LIMIT) {
heap_size += 3 + n + 1 + n;
} else {
- heap_size += DEC_TERM_HAMT_PLACEHOLDER_SIZE(n) + 2*n;
+ heap_size += hashmap_over_estimated_heap_size(n);
}
break;
case STRING_EXT:
diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c
index 674dddc86f..66f13461a1 100644
--- a/erts/emulator/beam/utils.c
+++ b/erts/emulator/beam/utils.c
@@ -352,6 +352,17 @@ int erts_fit_in_bits_int32(Sint32 value)
return fit_in_bits((Sint64) (Uint32) value, 4);
}
+int erts_fit_in_bits_uint(Uint value)
+{
+#if ERTS_SIZEOF_ETERM == 4
+ return fit_in_bits((Sint64) (Uint32) value, 4);
+#elif ERTS_SIZEOF_ETERM == 8
+ return fit_in_bits(value, 5);
+#else
+# error "No way, Jose"
+#endif
+}
+
int
erts_print(int to, void *arg, char *format, ...)
{
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-02 14:41:17 +0000