diff options
-rw-r--r-- | erts/emulator/beam/erl_bif_info.c | 7 | ||||
-rw-r--r-- | erts/emulator/beam/erl_db_util.c | 99 | ||||
-rw-r--r-- | erts/emulator/beam/erl_map.c | 680 | ||||
-rw-r--r-- | erts/emulator/beam/erl_map.h | 32 | ||||
-rw-r--r-- | erts/emulator/beam/erl_term.h | 2 | ||||
-rw-r--r-- | erts/emulator/beam/erl_utils.h | 7 | ||||
-rw-r--r-- | erts/emulator/beam/external.c | 49 | ||||
-rw-r--r-- | erts/emulator/beam/utils.c | 112 | ||||
-rw-r--r-- | erts/emulator/test/map_SUITE.erl | 70 |
9 files changed, 693 insertions, 365 deletions
diff --git a/erts/emulator/beam/erl_bif_info.c b/erts/emulator/beam/erl_bif_info.c index a95bb46af0..9e8fb267a6 100644 --- a/erts/emulator/beam/erl_bif_info.c +++ b/erts/emulator/beam/erl_bif_info.c @@ -4172,6 +4172,13 @@ BIF_RETTYPE erts_debug_get_internal_state_1(BIF_ALIST_1) BIF_RET(uword_to_big(size, hp)); } } + else if (ERTS_IS_ATOM_STR("hashmap_collision_bonanza", BIF_ARG_1)) { +#ifdef DBG_HASHMAP_COLLISION_BONANZA + return am_true; +#else + return am_false; +#endif + } } else if (is_tuple(BIF_ARG_1)) { Eterm* tp = tuple_val(BIF_ARG_1); diff --git a/erts/emulator/beam/erl_db_util.c b/erts/emulator/beam/erl_db_util.c index 8bace68d0f..9162329c8a 100644 --- a/erts/emulator/beam/erl_db_util.c +++ b/erts/emulator/beam/erl_db_util.c @@ -878,8 +878,8 @@ static Eterm dmc_lookup_bif_reversed(void *f); static int cmp_uint(void *a, void *b); static int cmp_guard_bif(void *a, void *b); static int match_compact(ErlHeapFragment *expr, DMCErrInfo *err_info); -static Uint my_size_object(Eterm t); -static Eterm my_copy_struct(Eterm t, Eterm **hp, ErlOffHeap* off_heap); +static Uint my_size_object(Eterm t, int is_hashmap_node); +static Eterm my_copy_struct(Eterm t, Eterm **hp, ErlOffHeap* off_heap, int); /* Guard subroutines */ static void @@ -3786,11 +3786,11 @@ static void do_emit_constant(DMCContext *context, DMC_STACK_TYPE(UWord) *text, if (is_immed(t)) { tmp = t; } else { - sz = my_size_object(t); + sz = my_size_object(t, 0); if (sz) { emb = new_message_buffer(sz); hp = emb->mem; - tmp = my_copy_struct(t,&hp,&(emb->off_heap)); + tmp = my_copy_struct(t,&hp,&(emb->off_heap), 0); emb->next = context->save; context->save = emb; } @@ -5251,33 +5251,39 @@ static int match_compact(ErlHeapFragment *expr, DMCErrInfo *err_info) /* ** Simple size object that takes care of function calls and constant tuples */ -static Uint my_size_object(Eterm t) +static Uint my_size_object(Eterm t, int is_hashmap_node) { Uint sum = 0; - Eterm tmp; Eterm *p; switch (t & _TAG_PRIMARY_MASK) { case TAG_PRIMARY_LIST: - sum += 2 + my_size_object(CAR(list_val(t))) + - my_size_object(CDR(list_val(t))); + sum += 2 + my_size_object(CAR(list_val(t)), 0) + + my_size_object(CDR(list_val(t)), 0); break; case TAG_PRIMARY_BOXED: if (is_tuple(t)) { - if (tuple_val(t)[0] == make_arityval(1) && is_tuple(tmp = tuple_val(t)[1])) { - Uint i,n; - p = tuple_val(tmp); - n = arityval(p[0]); - sum += 1 + n; - for (i = 1; i <= n; ++i) - sum += my_size_object(p[i]); - } else if (tuple_val(t)[0] == make_arityval(2) && - is_atom(tmp = tuple_val(t)[1]) && - tmp == am_const) { + Eterm* tpl = tuple_val(t); + Uint i,n; + + if (is_hashmap_node) { + /* hashmap collision node, no matchspec syntax here */ + } + else if (tpl[0] == make_arityval(1) && is_tuple(tpl[1])) { + tpl = tuple_val(tpl[1]); + } + else if (tpl[0] == make_arityval(2) && tpl[1] == am_const) { sum += size_object(tuple_val(t)[2]); - } else { + break; + } + else { erts_exit(ERTS_ERROR_EXIT,"Internal error, sizing unrecognized object in " "(d)ets:match compilation."); } + + n = arityval(tpl[0]); + sum += 1 + n; + for (i = 1; i <= n; ++i) + sum += my_size_object(tpl[i], 0); break; } else if (is_map(t)) { if (is_flatmap(t)) { @@ -5290,7 +5296,7 @@ static Uint my_size_object(Eterm t) n = arityval(p[0]); sum += 1 + n; for (int i = 1; i <= n; ++i) - sum += my_size_object(p[i]); + sum += my_size_object(p[i], 0); /* Calculate size of values */ p = (Eterm *)mp; @@ -5298,18 +5304,19 @@ static Uint my_size_object(Eterm t) sum += n + 3; p += 3; /* hdr + size + keys words */ while (n--) { - sum += my_size_object(*p++); + sum += my_size_object(*p++, 0); } } else { Eterm *head = (Eterm *)hashmap_val(t); Eterm hdr = *head; Uint sz; + sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); sum += 1 + sz + header_arity(hdr); head += 1 + header_arity(hdr); while(sz-- > 0) { - sum += my_size_object(head[sz]); + sum += my_size_object(head[sz], 1); } } break; @@ -5322,42 +5329,50 @@ static Uint my_size_object(Eterm t) return sum; } -static Eterm my_copy_struct(Eterm t, Eterm **hp, ErlOffHeap* off_heap) +static Eterm my_copy_struct(Eterm t, Eterm **hp, ErlOffHeap* off_heap, + int is_hashmap_node) { Eterm ret = NIL, a, b; Eterm *p; Uint sz; switch (t & _TAG_PRIMARY_MASK) { case TAG_PRIMARY_LIST: - a = my_copy_struct(CAR(list_val(t)), hp, off_heap); - b = my_copy_struct(CDR(list_val(t)), hp, off_heap); + a = my_copy_struct(CAR(list_val(t)), hp, off_heap, 0); + b = my_copy_struct(CDR(list_val(t)), hp, off_heap, 0); ret = CONS(*hp, a, b); *hp += 2; break; case TAG_PRIMARY_BOXED: if (is_tuple(t)) { - if (tuple_val(t)[0] == make_arityval(1) && - is_tuple(a = tuple_val(t)[1])) { - Uint i,n; - Eterm *savep = *hp; - ret = make_tuple(savep); - p = tuple_val(a); - n = arityval(p[0]); - *hp += n + 1; - *savep++ = make_arityval(n); - for(i = 1; i <= n; ++i) - *savep++ = my_copy_struct(p[i], hp, off_heap); + Eterm* tpl = tuple_val(t); + Uint i,n; + Eterm *savep; + + if (is_hashmap_node) { + /* hashmap collision node, no matchspec syntax here */ + } + else if (tpl[0] == make_arityval(1) && is_tuple(tpl[1])) { + /* A {{...}} expression */ + tpl = tuple_val(tpl[1]); } - else if (tuple_val(t)[0] == make_arityval(2) && - tuple_val(t)[1] == am_const) { + else if (tpl[0] == make_arityval(2) && tpl[1] == am_const) { /* A {const, XXX} expression */ - b = tuple_val(t)[2]; + b = tpl[2]; sz = size_object(b); ret = copy_struct(b,sz,hp,off_heap); + break; } else { erts_exit(ERTS_ERROR_EXIT, "Trying to constant-copy non constant expression " "0x%bex in (d)ets:match compilation.", t); } + savep = *hp; + ret = make_tuple(savep); + n = arityval(tpl[0]); + *hp += n + 1; + *savep++ = tpl[0]; + for(i = 1; i <= n; ++i) + *savep++ = my_copy_struct(tpl[i], hp, off_heap, 0); + } else if (is_map(t)) { if (is_flatmap(t)) { Uint i,n; @@ -5375,7 +5390,7 @@ static Eterm my_copy_struct(Eterm t, Eterm **hp, ErlOffHeap* off_heap) *hp += n + 1; *savep++ = make_arityval(n); for(i = 1; i <= n; ++i) - *savep++ = my_copy_struct(p[i], hp, off_heap); + *savep++ = my_copy_struct(p[i], hp, off_heap, 0); savep = *hp; ret = make_flatmap(savep); @@ -5387,7 +5402,7 @@ static Eterm my_copy_struct(Eterm t, Eterm **hp, ErlOffHeap* off_heap) *savep++ = keys; p += 3; /* hdr + size + keys words */ for (i = 0; i < n; i++) - *savep++ = my_copy_struct(p[i], hp, off_heap); + *savep++ = my_copy_struct(p[i], hp, off_heap, 0); erts_usort_flatmap((flatmap_t*)flatmap_val(ret)); } else { Eterm *head = hashmap_val(t); @@ -5404,7 +5419,7 @@ static Eterm my_copy_struct(Eterm t, Eterm **hp, ErlOffHeap* off_heap) *savep++ = *head++; /* map size */ for (int i = 0; i < sz; i++) { - *savep++ = my_copy_struct(head[i],hp,off_heap); + *savep++ = my_copy_struct(head[i],hp,off_heap, 1); } } } else { diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index c4ddee1436..5cd867bb36 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -94,8 +94,8 @@ static Uint hashmap_subtree_size(Eterm node); static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node, Eterm *value); static Eterm flatmap_from_validated_list(Process *p, Eterm list, Eterm fill_value, Uint size); static Eterm hashmap_from_unsorted_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int reject_dupkeys, ErtsAlcType_t temp_memory_allocator); -static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int is_root, ErtsAlcType_t temp_memory_allocator); -static Eterm hashmap_from_chunked_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, Uint size, int is_root, ErtsAlcType_t temp_memory_allocator); +static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, ErtsAlcType_t temp_memory_allocator); +static Eterm hashmap_from_chunked_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, Uint size, ErtsAlcType_t temp_memory_allocator); static Eterm hashmap_info(Process *p, Eterm node); static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]); static int hxnodecmp(const void* a, const void* b); @@ -111,8 +111,7 @@ static int hxnodecmpkey(const void* a, const void* b); #define maskval(V,L) (((V) >> ((7 - (L))*4)) & 0xf) #define DBG_PRINT(X) /*erts_printf X*/ -#define HALLOC_EXTRA_HASHMAP_FROM_CHUNKED_ARRAY 200 -#define HALLOC_EXTRA HALLOC_EXTRA_HASHMAP_FROM_CHUNKED_ARRAY +#define HALLOC_EXTRA 200 /* ******************************* * ** Yielding C Fun (YCF) Note ** * ******************************* @@ -134,7 +133,6 @@ static int hxnodecmpkey(const void* a, const void* b); #include "erl_map.ycf.h" #endif #define NOT_YCF_YIELDING_VERSION 1 -#undef HALLOC_EXTRA #define YCF_CONSUME_REDS(X) while(0){} void erts_init_map(void) { @@ -270,6 +268,7 @@ BIF_RETTYPE map_get_2(BIF_ALIST_2) { * means that the code has to follow some restrictions. See note about * YCF near the top of the file for more information. */ + #ifdef INCLUDE_YCF_TRANSFORMED_ONLY_FUNCTIONS static BIF_RETTYPE maps_from_keys_2_helper(Process* p, Eterm* bif_args) { Eterm list = bif_args[0]; @@ -486,14 +485,11 @@ static Eterm hashmap_from_validated_list(Process *p, #ifdef NOT_YCF_YIELDING_VERSION /* Macro to make YCF ignore declarations */ #define YCF_IGNORE(X) X - YCF_IGNORE(Eterm tmp[2];) YCF_IGNORE(ErtsHeapFactory factory_instance;) #undef YCF_IGNORE factory = &factory_instance; #else - Eterm *tmp; factory = YCF_STACK_ALLOC(sizeof(ErtsHeapFactory)); - tmp = YCF_STACK_ALLOC(2 * sizeof(Eterm)); #endif ASSERT(size > 0); @@ -513,7 +509,7 @@ static Eterm hashmap_from_validated_list(Process *p, key = kv[1]; value = kv[2]; } - hx = hashmap_restore_hash(tmp,0,key); + hx = hashmap_restore_hash(0,key); swizzle32(sw,hx); hxns[ix].hx = sw; hxns[ix].val = CONS(hp, key, value); hp += 2; @@ -768,7 +764,7 @@ static Eterm hashmap_from_unsorted_array(ErtsHeapFactory* factory, if (hxns[ix].hx == hxns[ix+1].hx) { /* find region of equal hash values */ - jx = ix + 1; + jx = ix + 2; while(jx < n && hxns[ix].hx == hxns[jx].hx) { jx++; } /* find all correct keys from region * (last in list but now hash sorted so we check highest id instead) */ @@ -811,7 +807,8 @@ static Eterm hashmap_from_unsorted_array(ErtsHeapFactory* factory, if (cx > 1) { /* recursive decompose array */ - res = hashmap_from_sorted_unique_array(factory, hxns, cx, 0, temp_memory_allocator); + res = hashmap_from_sorted_unique_array(factory, hxns, cx, + temp_memory_allocator); } else { Eterm *hp; @@ -838,52 +835,49 @@ static Eterm hashmap_from_unsorted_array(ErtsHeapFactory* factory, * YCF near the top of the file for more information. */ static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory* factory, - hxnode_t *hxns, Uint n, int lvl, + hxnode_t *hxns, Uint n, ErtsAlcType_t temp_memory_allocator) { Eterm res = NIL; - Uint i; Uint ix; - Uint jx; Uint elems; - Uint32 sw; - Uint32 hx; - Eterm val; hxnode_t *tmp = NULL; - Eterm th[2]; - ASSERT(lvl < 32); + ix = 0; elems = 1; while (ix < n - 1) { if (hxns[ix].hx == hxns[ix+1].hx) { - jx = ix + 1; - while (jx < n && hxns[ix].hx == hxns[jx].hx) { jx++; } - tmp = (hxnode_t *)erts_alloc(temp_memory_allocator, ((jx - ix)) * sizeof(hxnode_t)); - - for(i = 0; i < jx - ix; i++) { - val = hxns[i + ix].val; - hx = hashmap_restore_hash(th, lvl + 8, CAR(list_val(val))); - swizzle32(sw,hx); - tmp[i].hx = sw; - tmp[i].val = val; - tmp[i].i = i; - tmp[i].skip = 1; - } + Uint n_colliders; + Eterm* hp; + Eterm collision_node; + Uint jx = ix + 2; + Uint i; + + while (jx < n && hxns[ix].hx == hxns[jx].hx) + jx++; + + n_colliders = jx - ix; + hp = erts_produce_heap(factory, HAMT_COLLISION_NODE_SZ(n_colliders), + HALLOC_EXTRA); + collision_node = make_tuple(hp); + + *hp++ = MAP_HEADER_HAMT_COLLISION_NODE(n_colliders); + for (i = 0; i < n_colliders; i++) { + *hp++ = hxns[ix + i].val; + ASSERT(i == 0 + || CMP_TERM(CAR(list_val(hxns[ix+i-1].val)), + CAR(list_val(hxns[ix+i].val))) < 0); + } - erts_qsort(tmp, jx - ix, sizeof(hxnode_t), hxnodecmp); + hxns[ix].val = collision_node; + hxns[ix].skip = n_colliders; + ix = jx; - hxns[ix].skip = jx - ix; - hxns[ix].val = - hashmap_from_sorted_unique_array(factory, tmp, jx - ix, lvl + 8, temp_memory_allocator); - erts_free(temp_memory_allocator, (void *) tmp); - /* Memory management depend on the statement below */ - tmp = NULL; - ix = jx; - if (ix < n) { elems++; } - continue; + if (ix < n) { elems++; } + continue; } - hxns[ix].skip = 1; - elems++; - ix++; + hxns[ix].skip = 1; + elems++; + ix++; } YCF_SPECIAL_CODE_START(ON_DESTROY_STATE); { @@ -894,14 +888,13 @@ static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory* factory, } } YCF_SPECIAL_CODE_END(); - res = hashmap_from_chunked_array(factory, hxns, elems, n, !lvl, temp_memory_allocator); + res = hashmap_from_chunked_array(factory, hxns, elems, n, temp_memory_allocator); ERTS_FACTORY_HOLE_CHECK(factory); return res; } -#define HALLOC_EXTRA HALLOC_EXTRA_HASHMAP_FROM_CHUNKED_ARRAY /* **Important Note** * * A yielding version of this function is generated with YCF. This @@ -909,7 +902,7 @@ static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory* factory, * YCF near the top of the file for more information. */ static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory, hxnode_t *hxns, Uint n, - Uint size, int is_root, + Uint size, ErtsAlcType_t temp_memory_allocator) { Uint ix; Uint d; @@ -961,16 +954,11 @@ static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory, hxnode_t *hxns } slot = maskval(v,0); - hp = erts_produce_heap(factory, (is_root ? 3 : 2), 0); + hp = erts_produce_heap(factory, 3, 0); - if (is_root) { - hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(1 << slot); - hp[1] = size; - hp[2] = res; - } else { - hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << slot); - hp[1] = res; - } + hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(1 << slot); + hp[1] = size; + hp[2] = res; return make_hashmap(hp); } @@ -1132,15 +1120,11 @@ static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory, hxnode_t *hxns bp = 1 << slot; hdr |= bp; sz = hashmap_bitcount(hdr); - hp = erts_produce_heap(factory, sz + /* hdr + item */ (is_root ? 2 : 1), 0); + hp = erts_produce_heap(factory, sz + /* hdr + item */ 2, 0); nhp = hp; - if (is_root) { - *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_HEAD_ARRAY : MAP_HEADER_HAMT_HEAD_BITMAP(hdr); - *hp++ = size; - } else { - *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hdr); - } + *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_HEAD_ARRAY : MAP_HEADER_HAMT_HEAD_BITMAP(hdr); + *hp++ = size; *hp++ = res; sz--; while (sz--) { *hp++ = ESTACK_POP(stack); } @@ -1152,7 +1136,6 @@ static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory, hxnode_t *hxns ERTS_FACTORY_HOLE_CHECK(factory); return res; } -#undef HALLOC_EXTRA static int hxnodecmpkey(const void *va, const void *vb) { const hxnode_t *a = (const hxnode_t*) va; @@ -1481,9 +1464,57 @@ BIF_RETTYPE maps_merge_trap_1(BIF_ALIST_1) { (HashmapMergeContext*) ERTS_MAGIC_BIN_DATA(ctx_bin)); } -#define HALLOC_EXTRA 200 #define MAP_MERGE_LOOP_FACTOR 8 +static Eterm merge_collision_node(Process* p, + Eterm* srcA, Uint szA, + Eterm* srcB, Uint szB, + Uint* map_sizep) +{ + Eterm *hp; + Eterm *hdr_ptr; + Eterm *hp_end; + Uint arity; + + ERTS_ASSERT(szA >= 1 && szB >= 1); + arity = szA + szB; + hp = HAlloc(p, HAMT_COLLISION_NODE_SZ(arity)); + hp_end = hp + HAMT_COLLISION_NODE_SZ(arity); + hdr_ptr = hp++; + + while (szA && szB) { + Eterm keyA = CAR(list_val(*srcA)); + Eterm keyB = CAR(list_val(*srcB)); + const Sint key_cmp = CMP_TERM(keyA, keyB); + + if (key_cmp < 0) { + *hp++ = *srcA++; + szA--; + } + else { + *hp++ = *srcB++; + szB--; + if (key_cmp == 0) { + srcA++; + szA--; + arity--; + (*map_sizep)--; + } + } + } + ASSERT(arity >= 2); + + for ( ; szA; szA--) + *hp++ = *srcA++; + for ( ; szB; szB--) + *hp++ = *srcB++; + + HRelease(p, hp_end, hp); + *hdr_ptr = make_arityval(arity); + return make_tuple(hdr_ptr); +} + + static BIF_RETTYPE hashmap_merge(Process *p, Eterm map_A, Eterm map_B, int swap_args, HashmapMergeContext* ctx) { #define PSTACK_TYPE struct HashmapMergePStackType @@ -1497,8 +1528,7 @@ static BIF_RETTYPE hashmap_merge(Process *p, Eterm map_A, Eterm map_B, Eterm trap_ret; Sint initial_reds = (Sint) (ERTS_BIF_REDS_LEFT(p) * MAP_MERGE_LOOP_FACTOR); Sint reds = initial_reds; - DeclareTmpHeap(th,2,p); - UseTmpHeap(2,p); + Uint coll_szA = 0, coll_szB = 0; /* * Strategy: Do depth-first traversal of both trees (at the same time) @@ -1558,8 +1588,13 @@ recurse: goto merge_nodes; } } - hx = hashmap_restore_hash(th, ctx->lvl, keyA); - sp->abm = 1 << hashmap_index(hx); + if (ctx->lvl < HAMT_MAX_LEVEL) { + hx = hashmap_restore_hash(ctx->lvl, keyA); + sp->abm = 1 << hashmap_index(hx); + } + else { + coll_szA = 1; + } /* keep srcA pointing at the leaf */ } else { /* A is NODE */ @@ -1568,25 +1603,35 @@ recurse: ASSERT(is_header(hdrA)); switch (hdrA & _HEADER_MAP_SUBTAG_MASK) { case HAMT_SUBTAG_HEAD_ARRAY: { + ASSERT(ctx->lvl < HAMT_MAX_LEVEL); sp->srcA++; sp->abm = 0xffff; break; } case HAMT_SUBTAG_HEAD_BITMAP: sp->srcA++; case HAMT_SUBTAG_NODE_BITMAP: { + ASSERT(ctx->lvl < HAMT_MAX_LEVEL); sp->abm = MAP_HEADER_VAL(hdrA); break; } - default: - erts_exit(ERTS_ABORT_EXIT, "bad header %ld\r\n", hdrA); + default: /* collision node */ + ERTS_ASSERT(is_arity_value(hdrA)); + ASSERT(ctx->lvl == HAMT_MAX_LEVEL); + coll_szA = arityval(hdrA); + ASSERT(coll_szA >= 2); } } if (is_list(sp->nodeB)) { /* B is LEAF */ Eterm keyB = CAR(list_val(sp->nodeB)); - hx = hashmap_restore_hash(th, ctx->lvl, keyB); - sp->bbm = 1 << hashmap_index(hx); + if (ctx->lvl < HAMT_MAX_LEVEL) { + hx = hashmap_restore_hash(ctx->lvl, keyB); + sp->bbm = 1 << hashmap_index(hx); + } + else { + coll_szB = 1; + } /* keep srcB pointing at the leaf */ } else { /* B is NODE */ @@ -1595,17 +1640,22 @@ recurse: ASSERT(is_header(hdrB)); switch (hdrB & _HEADER_MAP_SUBTAG_MASK) { case HAMT_SUBTAG_HEAD_ARRAY: { + ASSERT(ctx->lvl < HAMT_MAX_LEVEL); sp->srcB++; sp->bbm = 0xffff; break; } case HAMT_SUBTAG_HEAD_BITMAP: sp->srcB++; case HAMT_SUBTAG_NODE_BITMAP: { + ASSERT(ctx->lvl < HAMT_MAX_LEVEL); sp->bbm = MAP_HEADER_VAL(hdrB); break; } - default: - erts_exit(ERTS_ABORT_EXIT, "bad header %ld\r\n", hdrB); + default: /* collision node */ + ERTS_ASSERT(is_arity_value(hdrB)); + ASSERT(ctx->lvl == HAMT_MAX_LEVEL); + coll_szB = arityval(hdrB); + ASSERT(coll_szB >= 2); } } } @@ -1629,13 +1679,22 @@ merge_nodes: sp->srcA++; sp->srcB++; } - } else { /* Start build a node */ + } + else if (ctx->lvl < HAMT_MAX_LEVEL) { /* Start build a node */ sp->ix = 0; sp->rbm = sp->abm | sp->bbm; ASSERT(!(sp->rbm == 0 && ctx->lvl > 0)); } + else { + res = merge_collision_node(p, sp->srcA, coll_szA, + sp->srcB, coll_szB, &ctx->size); + sp->mix = 3; + coll_szA = coll_szB = 0; + continue; + } if (--reds <= 0) { + ASSERT(!coll_szA && !coll_szB); goto trap; } resume_from_trap: @@ -1779,24 +1838,14 @@ static int hash_cmp(Uint32 ha, Uint32 hb) int hashmap_key_hash_cmp(Eterm* ap, Eterm* bp) { - unsigned int lvl = 0; - DeclareTmpHeapNoproc(th,2); - UseTmpHeapNoproc(2); - if (ap && bp) { + Uint32 ha, hb; ASSERT(CMP_TERM(CAR(ap), CAR(bp)) != 0); - for (;;) { - Uint32 ha = hashmap_restore_hash(th, lvl, CAR(ap)); - Uint32 hb = hashmap_restore_hash(th, lvl, CAR(bp)); - int cmp = hash_cmp(ha, hb); - if (cmp) { - UnUseTmpHeapNoproc(2); - return cmp; - } - lvl += 8; - } + ha = hashmap_make_hash(CAR(ap)); + hb = hashmap_make_hash(CAR(bp)); + return hash_cmp(ha, hb); } - UnUseTmpHeapNoproc(2); + ASSERT(ap || bp); return ap ? -1 : 1; } @@ -2229,7 +2278,9 @@ Uint hashmap_node_size(Eterm hdr, Eterm **nodep) ASSERT(sz < 17); break; default: - erts_exit(ERTS_ABORT_EXIT, "bad header"); + ERTS_ASSERT(is_arity_value(hdr)); + sz = arityval(hdr); + break; } return sz; } @@ -2323,11 +2374,9 @@ Eterm* hashmap_iterator_prev(ErtsWStack* s) { const Eterm * erts_hashmap_get(Uint32 hx, Eterm key, Eterm node) { - Eterm *ptr, hdr, *res; + Eterm *ptr, hdr; Uint ix, lvl = 0; Uint32 hval,bp; - DeclareTmpHeapNoproc(th,2); - UseTmpHeapNoproc(2); ASSERT(is_boxed(node)); ptr = boxed_val(node); @@ -2336,15 +2385,16 @@ erts_hashmap_get(Uint32 hx, Eterm key, Eterm node) ASSERT(is_hashmap_header_head(hdr)); ptr++; - for (;;) { + do { + ASSERT(lvl == 0 || is_hashmap_header_node(hdr)); + hval = MAP_HEADER_VAL(hdr); ix = hashmap_index(hx); if (hval != 0xffff) { bp = 1 << ix; if (!(bp & hval)) { /* not occupied */ - res = NULL; - break; + return NULL; } ix = hashmap_bitcount(hval & (bp - 1)); } @@ -2352,21 +2402,26 @@ erts_hashmap_get(Uint32 hx, Eterm key, Eterm node) if (is_list(node)) { /* LEAF NODE [K|V] */ ptr = list_val(node); - res = EQ(CAR(ptr), key) ? &(CDR(ptr)) : NULL; - break; + return EQ(CAR(ptr), key) ? &(CDR(ptr)) : NULL; } - hx = hashmap_shift_hash(th,hx,lvl,key); + hx = hashmap_shift_hash(hx,lvl,key); ASSERT(is_boxed(node)); ptr = boxed_val(node); hdr = *ptr; ASSERT(is_header(hdr)); - ASSERT(!is_hashmap_header_head(hdr)); - } + } while (!is_arity_value(hdr)); - UnUseTmpHeapNoproc(2); - return res; + /* collision node */ + ix = arityval(hdr); + ASSERT(ix > 1); + do { + Eterm* kv = list_val(*(++ptr)); + if (EQ(CAR(kv), key)) + return &(CDR(kv)); + } while (--ix > 0); + return NULL; } Eterm erts_hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, @@ -2380,6 +2435,8 @@ Eterm erts_hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, /* We are putting a new value (under a new or existing key) */ hp = HAlloc(p, size); res = erts_hashmap_insert_up(hp, key, value, upsz, &stack); + ASSERT(hashmap_val(res) + 2 + hashmap_bitcount(MAP_HEADER_VAL(*hashmap_val(res))) + == hp + size); } else { /* We are putting the same key-value */ @@ -2403,7 +2460,6 @@ int erts_hashmap_insert_down(Uint32 hx, Eterm key, Eterm value, Eterm node, Uint Uint32 ix, cix, bp, hval, chx; Uint slot, lvl = 0, clvl; Uint size = 0, n = 0; - Eterm th[2]; *update_size = 1; @@ -2432,7 +2488,7 @@ int erts_hashmap_insert_down(Uint32 hx, Eterm key, Eterm value, Eterm node, Uint switch(hdr & _HEADER_MAP_SUBTAG_MASK) { case HAMT_SUBTAG_HEAD_ARRAY: ix = hashmap_index(hx); - hx = hashmap_shift_hash(th,hx,lvl,key); + hx = hashmap_shift_hash(hx,lvl,key); size += HAMT_HEAD_ARRAY_SZ; ESTACK_PUSH2(*sp, ix, node); node = ptr[ix+2]; @@ -2459,7 +2515,7 @@ int erts_hashmap_insert_down(Uint32 hx, Eterm key, Eterm value, Eterm node, Uint goto unroll; } - hx = hashmap_shift_hash(th,hx,lvl,key); + hx = hashmap_shift_hash(hx,lvl,key); node = ptr[slot+1]; ASSERT(HAMT_NODE_BITMAP_SZ(n) <= 17); size += HAMT_NODE_BITMAP_SZ(n); @@ -2476,7 +2532,7 @@ int erts_hashmap_insert_down(Uint32 hx, Eterm key, Eterm value, Eterm node, Uint /* occupied */ if (bp & hval) { - hx = hashmap_shift_hash(th,hx,lvl,key); + hx = hashmap_shift_hash(hx,lvl,key); node = ptr[slot+2]; ASSERT(HAMT_HEAD_BITMAP_SZ(n) <= 18); size += HAMT_HEAD_BITMAP_SZ(n); @@ -2488,9 +2544,34 @@ int erts_hashmap_insert_down(Uint32 hx, Eterm key, Eterm value, Eterm node, Uint } size += HAMT_HEAD_BITMAP_SZ(n+1); goto unroll; - default: - erts_exit(ERTS_ERROR_EXIT, "bad header tag %ld\r\n", hdr & _HEADER_MAP_SUBTAG_MASK); - break; + default: + ERTS_ASSERT(is_arity_value(hdr)); + n = arityval(hdr); + ASSERT(n >= 2); + for (slot = 0; slot < n; slot++) { + Eterm* kv = list_val(ptr[1+slot]); + Sint c; + ckey = CAR(kv); + c = CMP_TERM(key, ckey); + if (c == 0) { + if (CDR(ptr) == value) { + *sz = 0; + return 1; + } + *update_size = 0; + size += HAMT_COLLISION_NODE_SZ(n); + ESTACK_PUSH3(*sp, slot, 0, node); + goto unroll; + } + if (c < 0) + break; + } + if (is_update) { + return 0; + } + size += HAMT_COLLISION_NODE_SZ(n+1); + ESTACK_PUSH3(*sp, slot, 1, node); + goto unroll; } break; default: @@ -2499,21 +2580,25 @@ int erts_hashmap_insert_down(Uint32 hx, Eterm key, Eterm value, Eterm node, Uint } } insert_subnodes: - clvl = lvl; - chx = hashmap_restore_hash(th,clvl,ckey); - size += HAMT_NODE_BITMAP_SZ(2); - ix = hashmap_index(hx); - cix = hashmap_index(chx); - - while (cix == ix) { - ESTACK_PUSH4(*sp, 0, 1 << ix, 0, MAP_HEADER_HAMT_NODE_BITMAP(0)); - size += HAMT_NODE_BITMAP_SZ(1); - hx = hashmap_shift_hash(th,hx,lvl,key); - chx = hashmap_shift_hash(th,chx,clvl,ckey); - ix = hashmap_index(hx); - cix = hashmap_index(chx); - } - ESTACK_PUSH3(*sp, cix, ix, node); + if (lvl < HAMT_MAX_LEVEL) { + clvl = lvl; + chx = hashmap_restore_hash(clvl,ckey); + do { + ix = hashmap_index(hx); + cix = hashmap_index(chx); + if (cix != ix) { + size += HAMT_NODE_BITMAP_SZ(2); + ESTACK_PUSH4(*sp, cix, ix, 0, node); + goto unroll; + } + ESTACK_PUSH4(*sp, 0, 1 << ix, 0, MAP_HEADER_HAMT_NODE_BITMAP(0)); + size += HAMT_NODE_BITMAP_SZ(1); + hx = hashmap_shift_hash(hx,lvl,key); + chx = hashmap_shift_hash(chx,clvl,ckey); + } while (lvl < HAMT_MAX_LEVEL); + } + size += HAMT_COLLISION_NODE_SZ(2); + ESTACK_PUSH2(*sp, 1, node); unroll: *sz = size + /* res cons */ 2; @@ -2527,17 +2612,29 @@ Eterm erts_hashmap_insert_up(Eterm *hp, Eterm key, Eterm value, Eterm *nhp = NULL; Uint32 ix, cix, bp, hval; Uint slot, n; - /* Needed for halfword */ - DeclareTmpHeapNoproc(fake,1); - UseTmpHeapNoproc(1); + Eterm fake; res = CONS(hp, key, value); hp += 2; do { node = ESTACK_POP(*sp); switch(primary_tag(node)) { - case TAG_PRIMARY_LIST: - ix = (Uint32) ESTACK_POP(*sp); + case TAG_PRIMARY_LIST: { + const int is_collision_node = (int) ESTACK_POP(*sp); + if (is_collision_node) { + nhp = hp; + *hp++ = MAP_HEADER_HAMT_COLLISION_NODE(2); + if (CMP_TERM(key, CAR(list_val(node))) < 0){ + *hp++ = res; + *hp++ = node; + } else { + *hp++ = node; + *hp++ = res; + } + res = make_hashmap(nhp); + break; + } + ix = (Uint32)ESTACK_POP(*sp); cix = (Uint32) ESTACK_POP(*sp); nhp = hp; @@ -2551,10 +2648,11 @@ Eterm erts_hashmap_insert_up(Eterm *hp, Eterm key, Eterm value, } res = make_hashmap(nhp); break; + } case TAG_PRIMARY_HEADER: /* subnodes, fake it */ - *fake = node; - node = make_boxed(fake); + fake = node; + node = make_boxed(&fake); case TAG_PRIMARY_BOXED: ptr = boxed_val(node); hdr = *ptr; @@ -2607,9 +2705,27 @@ Eterm erts_hashmap_insert_up(Eterm *hp, Eterm key, Eterm value, } res = make_hashmap(nhp); break; - default: - erts_exit(ERTS_ERROR_EXIT, "bad header tag %x\r\n", hdr & _HEADER_MAP_SUBTAG_MASK); - break; + default: { + int is_insert; + ERTS_ASSERT(is_arity_value(hdr)); + n = arityval(hdr); + ASSERT(n >= 2); + is_insert = (int) ESTACK_POP(*sp); + slot = (Uint) ESTACK_POP(*sp); + nhp = hp; + n += is_insert; + *hp++ = MAP_HEADER_HAMT_COLLISION_NODE(n); ptr++; + ix = 0; + while (ix++ < slot) + *hp++ = *ptr++; + *hp++ = res; + if (!is_insert) + ptr++; + while (ix++ < n) + *hp++ = *ptr++; + res = make_hashmap(nhp); + break; + } } break; default: @@ -2719,8 +2835,6 @@ static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Uint slot, lvl = 0; Uint size = 0, n = 0; DECLARE_ESTACK(stack); - DeclareTmpHeapNoproc(th,2); - UseTmpHeapNoproc(2); for (;;) { switch(primary_tag(node)) { @@ -2741,7 +2855,7 @@ static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, switch(hdr & _HEADER_MAP_SUBTAG_MASK) { case HAMT_SUBTAG_HEAD_ARRAY: ix = hashmap_index(hx); - hx = hashmap_shift_hash(th,hx,lvl,key); + hx = hashmap_shift_hash(hx,lvl,key); size += HAMT_HEAD_ARRAY_SZ; ESTACK_PUSH2(stack, ix, node); node = ptr[ix+2]; @@ -2764,7 +2878,7 @@ static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, ESTACK_PUSH4(stack, n, bp, slot, node); - hx = hashmap_shift_hash(th,hx,lvl,key); + hx = hashmap_shift_hash(hx,lvl,key); node = ptr[slot+1]; ASSERT(HAMT_NODE_BITMAP_SZ(n) <= 17); size += HAMT_NODE_BITMAP_SZ(n); @@ -2781,7 +2895,7 @@ static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, /* occupied */ if (bp & hval) { - hx = hashmap_shift_hash(th,hx,lvl,key); + hx = hashmap_shift_hash(hx,lvl,key); node = ptr[slot+2]; ASSERT(HAMT_HEAD_BITMAP_SZ(n) <= 18); size += HAMT_HEAD_BITMAP_SZ(n); @@ -2790,9 +2904,22 @@ static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, /* not occupied */ res = THE_NON_VALUE; goto not_found; - default: - erts_exit(ERTS_ERROR_EXIT, "bad header tag %ld\r\n", hdr & _HEADER_MAP_SUBTAG_MASK); - break; + default: /* collision node */ + ERTS_ASSERT(is_arity_value(hdr)); + n = arityval(hdr); + ASSERT(n >= 2); + for (slot = 0; slot < n; slot++) { + Eterm* kv = list_val(ptr[1+slot]); + if (EQ(key, CAR(kv))) { + if (value) + *value = CDR(kv); + ESTACK_PUSH2(stack, slot, node); + size += HAMT_COLLISION_NODE_SZ(n); + goto unroll; + } + } + res = THE_NON_VALUE; + goto not_found; } break; default: @@ -2974,8 +3101,25 @@ unroll: } res = make_hashmap(nhp); break; - default: - erts_exit(ERTS_ERROR_EXIT, "bad header tag %x\r\n", hdr & _HEADER_MAP_SUBTAG_MASK); + default: /* collision node */ + ERTS_ASSERT(is_arity_value(hdr)); + n = arityval(hdr); + ASSERT(n >= 2); + slot = (Uint) ESTACK_POP(stack); + ASSERT(slot < n); + if (n > 2) { /* Shrink collision node */ + nhp = hp; + *hp++ = MAP_HEADER_HAMT_COLLISION_NODE(n-1); ptr++; + n -= slot + 1; + while (slot--) { *hp++ = *ptr++; } + ptr++; + while(n--) { *hp++ = *ptr++; } + res = make_hashmap(nhp); + } + else { /* Collapse collision node */ + ASSERT(res == THE_NON_VALUE); + res = ptr[1 + (1-slot)]; + } break; } } while(!ESTACK_ISEMPTY(stack)); @@ -3243,8 +3387,10 @@ BIF_RETTYPE erts_internal_map_hashmap_children_1(BIF_ALIST_1) { sz = 16; ptr += 2; break; - default: - erts_exit(ERTS_ERROR_EXIT, "bad header\r\n"); + default: /* collision node */ + ERTS_ASSERT(is_arity_value(hdr)); + sz = arityval(hdr); + ASSERT(sz >= 2); break; } ASSERT(sz < 17); @@ -3266,15 +3412,17 @@ static Eterm hashmap_info(Process *p, Eterm node) { DECL_AM(leafs); DECL_AM(bitmaps); DECL_AM(arrays); - Uint nleaf=0, nbitmap=0, narray=0; - Uint bitmap_usage[16], leaf_usage[16]; - Uint lvl = 0, clvl; + DECL_AM(collisions); + Uint nleaf=0, nbitmap=0, narray=0, ncollision = 0; + Uint bitmap_usage[16]; + Uint collision_usage[16]; + Uint leaf_usage[HAMT_MAX_LEVEL + 2]; + Uint max_depth = 0, clvl; DECLARE_ESTACK(stack); - for (sz = 0; sz < 16; sz++) { - bitmap_usage[sz] = 0; - leaf_usage[sz] = 0; - } + sys_memzero(bitmap_usage, sizeof(bitmap_usage)); + sys_memzero(collision_usage, sizeof(collision_usage)); + sys_memzero(leaf_usage, sizeof(leaf_usage)); ptr = boxed_val(node); ESTACK_PUSH(stack, 0); @@ -3282,8 +3430,6 @@ static Eterm hashmap_info(Process *p, Eterm node) { do { node = ESTACK_POP(stack); clvl = ESTACK_POP(stack); - if (lvl < clvl) - lvl = clvl; switch(primary_tag(node)) { case TAG_PRIMARY_LIST: nleaf++; @@ -3299,45 +3445,49 @@ static Eterm hashmap_info(Process *p, Eterm node) { sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); ASSERT(sz < 17); bitmap_usage[sz-1] += 1; - while(sz--) { - ESTACK_PUSH(stack, clvl + 1); - ESTACK_PUSH(stack, ptr[sz+1]); - } break; case HAMT_SUBTAG_HEAD_BITMAP: nbitmap++; sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); bitmap_usage[sz-1] += 1; - while(sz--) { - ESTACK_PUSH(stack, clvl + 1); - ESTACK_PUSH(stack, ptr[sz+2]); - } + ptr++; break; case HAMT_SUBTAG_HEAD_ARRAY: narray++; sz = 16; - while(sz--) { - ESTACK_PUSH(stack, clvl + 1); - ESTACK_PUSH(stack, ptr[sz+2]); - } - break; - default: - erts_exit(ERTS_ERROR_EXIT, "bad header\r\n"); + ptr++; break; + default: /* collision node */ + ERTS_ASSERT(is_arity_value(hdr)); + ncollision++; + sz = arityval(hdr); + ASSERT(sz >= 2); + collision_usage[(sz > 16 ? 16 : sz) - 1] += 1; + break; } + ASSERT(sz >= 1); + clvl++; + ASSERT(clvl <= HAMT_MAX_LEVEL+1); + if (max_depth < clvl) + max_depth = clvl; + while(sz--) { + ESTACK_PUSH(stack, clvl); + ESTACK_PUSH(stack, ptr[sz+1]); + } } } while(!ESTACK_ISEMPTY(stack)); /* size */ sz = 0; - hashmap_bld_tuple_uint(NULL,&sz,16,leaf_usage); - hashmap_bld_tuple_uint(NULL,&sz,16,bitmap_usage); + hashmap_bld_tuple_uint(NULL, &sz, HAMT_MAX_LEVEL+2, leaf_usage); + hashmap_bld_tuple_uint(NULL, &sz, 16, bitmap_usage); + hashmap_bld_tuple_uint(NULL, &sz, 16, collision_usage); /* alloc */ - hp = HAlloc(p, 2+3 + 3*(2+4) + sz); + hp = HAlloc(p, 2+3 + 4*(2+4) + sz); - info = hashmap_bld_tuple_uint(&hp,NULL,16,leaf_usage); + info = hashmap_bld_tuple_uint(&hp, NULL, HAMT_MAX_LEVEL+2, leaf_usage); tup = TUPLE3(hp, AM_leafs, make_small(nleaf),info); hp += 4; res = CONS(hp, tup, res); hp += 2; @@ -3345,10 +3495,14 @@ static Eterm hashmap_info(Process *p, Eterm node) { tup = TUPLE3(hp, AM_bitmaps, make_small(nbitmap), info); hp += 4; res = CONS(hp, tup, res); hp += 2; + info = hashmap_bld_tuple_uint(&hp, NULL, 16, collision_usage); + tup = TUPLE3(hp, AM_collisions, make_small(ncollision), info); hp += 4; + res = CONS(hp, tup, res); hp += 2; + tup = TUPLE3(hp, AM_arrays, make_small(narray),NIL); hp += 4; res = CONS(hp, tup, res); hp += 2; - tup = TUPLE2(hp, AM_depth, make_small(lvl)); hp += 3; + tup = TUPLE2(hp, AM_depth, make_small(max_depth)); hp += 3; res = CONS(hp, tup, res); hp += 2; DESTROY_ESTACK(stack); @@ -3376,12 +3530,16 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]) * Since each hashmap node can only be up to 16 elements * large we use 4 bits per level in the path. * - * So a Path with value 0x110 will first get the 0:th + * So a Path with value 0x210 will first get the 0:th * slot in the head node, and then the 1:st slot in the - * resulting node and then finally the 1:st slot in the + * resulting node and then finally the 2:st slot in the * node beneath. If that slot is not a leaf, then the path * continues down the 0:th slot until it finds a leaf. * + * Collision nodes may (theoretically and in debug) have more + * than 16 elements. To not complicate the 4-bit path format + * we avoid yielding in collision nodes. + * * Once the leaf has been found, the return value is created * by traversing the tree using the the stack that was built * when searching for the first leaf to return. @@ -3470,7 +3628,12 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { Uint path_length = 0; Uint *path_rest = NULL; int i, elems, orig_elems; - Eterm node = map, res, *patch_ptr = NULL, *hp; + Eterm node = map, res, *patch_ptr = NULL; + Eterm *hp = NULL; + Eterm *hp_end; + Eterm *ptr; + Uint sz, words_per_elem; + Uint idx; /* A stack WSTACK is used when traversing the hashmap. * It contains: node, idx, sz, ptr @@ -3528,61 +3691,29 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { BIF_ERROR(BIF_P, BADARG); } - if (type == iterator) { - /* - * Iterator uses the format {K1, V1, {K2, V2, {K3, V3, [Path | Map]}}}, - * so each element is 4 words large. - * To make iteration order independent of input reductions - * the KV-pairs are here built in DESTRUCTIVE non-reverse order. - */ - hp = HAlloc(BIF_P, 4 * elems); - } else { - /* - * List used the format [Path, Map, {K3,V3}, {K2,V2}, {K1,V1} | BIF_ARG_3], - * so each element is 2+3 words large. - * To make list order independent of input reductions - * the KV-pairs are here built in FUNCTIONAL reverse order - * as this is how the list as a whole is constructed. - */ - hp = HAlloc(BIF_P, (2 + 3) * elems); - } - - orig_elems = elems; - /* First we look for the leaf to start at using the path given. While doing so, we push each map node and the index onto the stack to use later. */ for (i = 1; ; i++) { - Eterm *ptr = hashmap_val(node), - hdr = *ptr++; - Uint sz; + Eterm hdr; + + ptr = hashmap_val(node); + hdr = *ptr++; sz = hashmap_node_size(hdr, &ptr); - if (PATH_ELEM(curr_path) >= sz) + idx = PATH_ELEM(curr_path); + if (idx >= sz) goto badarg; - WSTACK_PUSH4(stack, node, PATH_ELEM(curr_path)+1, sz, (UWord)ptr); - - /* We have found a leaf, return it and the next X elements */ - if (is_list(ptr[PATH_ELEM(curr_path)])) { - Eterm *lst = list_val(ptr[PATH_ELEM(curr_path)]); - if (type == iterator) { - res = make_tuple(hp); - hp[0] = make_arityval(3); - hp[1] = CAR(lst); - hp[2] = CDR(lst); - patch_ptr = &hp[3]; - hp += 4; - } else { - Eterm tup = TUPLE2(hp, CAR(lst), CDR(lst)); hp += 3; - res = CONS(hp, tup, BIF_ARG_3); hp += 2; - } - elems--; + if (is_list(ptr[idx])) { + /* We have found a leaf, return it and the next X elements */ break; } - node = ptr[PATH_ELEM(curr_path)]; + WSTACK_PUSH4(stack, node, idx+1, sz, (UWord)ptr); + + node = ptr[idx]; curr_path >>= PATH_ELEM_SIZE; @@ -3600,12 +3731,50 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { } } + if (type == iterator) { + /* + * Iterator uses the format {K1, V1, {K2, V2, {K3, V3, [Path | Map]}}}, + * so each element is 4 words large. + * To make iteration order independent of input reductions + * the KV-pairs are here built in DESTRUCTIVE non-reverse order. + */ + words_per_elem = 4; + patch_ptr = &res; + } else { + /* + * List used the format [Path, Map, {K3,V3}, {K2,V2}, {K1,V1} | BIF_ARG_3], + * so each element is 2+3 words large. + * To make list order independent of input reductions + * the KV-pairs are here built in FUNCTIONAL reverse order + * as this is how the list as a whole is constructed. + */ + words_per_elem = 2 + 3; + res = BIF_ARG_3; + } + hp = HAlloc(BIF_P, words_per_elem * elems); + hp_end = hp + words_per_elem * elems; + + orig_elems = elems; + /* We traverse the hashmap and return at most `elems` elements */ while(1) { - Eterm *ptr = (Eterm*)WSTACK_POP(stack); - Uint sz = (Uint)WSTACK_POP(stack); - Uint idx = (Uint)WSTACK_POP(stack); - Eterm node = (Eterm)WSTACK_POP(stack); + + if (idx == 0) { + if (elems < sz && is_arity_value(*hashmap_val(node))) { + /* + * This is a collision node! + * Make sure 'elems' is large enough not to yield in the + * middle of it. Collision nodes may be larger than 16 + * and that would complicate the 4-bit path format. + */ + elems = sz; + HRelease(BIF_P, hp_end, hp); + hp = HAlloc(BIF_P, words_per_elem * elems); + hp_end = hp + words_per_elem * elems; + } + } + else + ASSERT(!is_arity_value(*hashmap_val(node))); while (idx < sz && elems != 0 && is_list(ptr[idx])) { Eterm *lst = list_val(ptr[idx]); @@ -3624,6 +3793,8 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { idx++; } + ASSERT(idx == sz || !is_arity_value(*hashmap_val(node))); + if (elems == 0) { if (idx < sz) { /* There are more elements in this node to explore */ @@ -3642,26 +3813,29 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { } } break; - } else { - if (idx < sz) { - Eterm hdr; - /* Push next idx in current node */ - WSTACK_PUSH4(stack, node, idx+1, sz, (UWord)ptr); - - /* Push first idx in child node */ - node = ptr[idx]; - ptr = hashmap_val(ptr[idx]); - hdr = *ptr++; - sz = hashmap_node_size(hdr, &ptr); - WSTACK_PUSH4(stack, node, 0, sz, (UWord)ptr); - } } - - /* There are no more element in the hashmap */ - if (WSTACK_ISEMPTY(stack)) { + else if (idx < sz) { + Eterm hdr; + /* Push next idx in current node */ + WSTACK_PUSH4(stack, node, idx+1, sz, (UWord)ptr); + + /* Continue with first idx in child node */ + node = ptr[idx]; + ptr = hashmap_val(ptr[idx]); + hdr = *ptr++; + sz = hashmap_node_size(hdr, &ptr); + idx = 0; + } + else if (!WSTACK_ISEMPTY(stack)) { + ptr = (Eterm*)WSTACK_POP(stack); + sz = (Uint)WSTACK_POP(stack); + idx = (Uint)WSTACK_POP(stack); + node = (Eterm)WSTACK_POP(stack); + } + else { + /* There are no more element in the hashmap */ break; } - } if (!WSTACK_ISEMPTY(stack)) { @@ -3720,24 +3894,16 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { res = CONS(hp, path, res); hp += 2; } } else { - if (type == iterator) { + if (type == iterator) *patch_ptr = am_none; - HRelease(BIF_P, hp + 4 * elems, hp); - } else { - HRelease(BIF_P, hp + (2+3) * elems, hp); - } + HRelease(BIF_P, hp_end, hp); } BIF_P->fcalls -= 4 * (orig_elems - elems); DESTROY_WSTACK(stack); BIF_RET(res); badarg: - if (type == iterator) { - HRelease(BIF_P, hp + 4 * elems, hp); - } else { - HRelease(BIF_P, hp + (2+3) * elems, hp); - } - BIF_P->fcalls -= 4 * (orig_elems - elems); + ASSERT(hp == NULL); DESTROY_WSTACK(stack); BIF_ERROR(BIF_P, BADARG); } diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h index 9f070ea33e..9ecacb8aa0 100644 --- a/erts/emulator/beam/erl_map.h +++ b/erts/emulator/beam/erl_map.h @@ -55,14 +55,16 @@ typedef struct flatmap_s { /* the head-node is a bitmap or array with an untagged size */ - #define hashmap_size(x) (((hashmap_head_t*) hashmap_val(x))->size) -#define hashmap_make_hash(Key) make_internal_hash(Key, 0) +#define hashmap_make_hash(Key) make_map_hash(Key) + +#define hashmap_restore_hash(Lvl, Key) \ + (ASSERT(Lvl < 8), \ + hashmap_make_hash(Key) >> (4*(Lvl))) -#define hashmap_restore_hash(Heap,Lvl,Key) \ - (((Lvl) < 8) ? hashmap_make_hash(Key) >> (4*(Lvl)) : hashmap_make_hash(CONS(Heap, make_small((Lvl)>>3), (Key))) >> (4*((Lvl) & 7))) -#define hashmap_shift_hash(Heap,Hx,Lvl,Key) \ - (((++(Lvl)) & 7) ? (Hx) >> 4 : hashmap_make_hash(CONS(Heap, make_small((Lvl)>>3), Key))) +#define hashmap_shift_hash(Hx, Lvl, Key) \ + (++(Lvl), ASSERT(Lvl <= HAMT_MAX_LEVEL), /* we allow one level too much */\ + (Hx) >> 4) /* erl_term.h stuff */ #define flatmap_get_values(x) (((Eterm *)(x)) + sizeof(flatmap_t)/sizeof(Eterm)) @@ -143,7 +145,8 @@ typedef struct hashmap_head_s { /* erl_map.h stuff */ -#define is_hashmap_header_head(x) ((MAP_HEADER_TYPE(x) & (0x2))) +#define is_hashmap_header_head(x) (MAP_HEADER_TYPE(x) & (0x2)) +#define is_hashmap_header_node(x) (MAP_HEADER_TYPE(x) == 1) #define MAKE_MAP_HEADER(Type,Arity,Val) \ (_make_header(((((Uint16)(Val)) << MAP_HEADER_ARITY_SZ) | (Arity)) << MAP_HEADER_TAG_SZ | (Type) , _TAG_HEADER_MAP)) @@ -160,12 +163,21 @@ typedef struct hashmap_head_s { #define MAP_HEADER_HAMT_NODE_BITMAP(Bmp) \ MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_NODE_BITMAP,0x0,Bmp) +#define MAP_HEADER_HAMT_COLLISION_NODE(Arity) make_arityval(Arity) + #define MAP_HEADER_FLATMAP_SZ (sizeof(flatmap_t) / sizeof(Eterm)) #define HAMT_NODE_ARRAY_SZ (17) #define HAMT_HEAD_ARRAY_SZ (18) #define HAMT_NODE_BITMAP_SZ(n) (1 + n) #define HAMT_HEAD_BITMAP_SZ(n) (2 + n) +#define HAMT_COLLISION_NODE_SZ(n) (1 + n) +/* + * Collision nodes are used when all hash bits have been exhausted. + * They are normal tuples of arity 2 or larger. The elements of a collision + * node tuple contain key-value cons cells like the other nodes, + * but they are sorted in map-key order. + */ /* 2 bits maps tag + 4 bits subtag + 2 ignore bits */ #define _HEADER_MAP_SUBTAG_MASK (0xfc) @@ -179,11 +191,17 @@ typedef struct hashmap_head_s { #define hashmap_index(hash) (((Uint32)hash) & 0xf) +#define HAMT_MAX_LEVEL 8 + /* hashmap heap size: [one cons cell + one list term in parent node] per key [one header + one boxed term in parent node] per inner node [one header + one size word] for root node Observed average number of nodes per key is about 0.35. + + Amendment: This size estimation does not take collision nodes into account. + It should be good enough though, as collision nodes are rare + and only make the size smaller compared to unlimited HAMT depth. */ #define HASHMAP_WORDS_PER_KEY 3 #define HASHMAP_WORDS_PER_NODE 2 diff --git a/erts/emulator/beam/erl_term.h b/erts/emulator/beam/erl_term.h index 490fe1f1d1..c23876aa5d 100644 --- a/erts/emulator/beam/erl_term.h +++ b/erts/emulator/beam/erl_term.h @@ -319,7 +319,7 @@ _ET_DECLARE_CHECKED(Uint,header_arity,Eterm) #define is_sane_arity_value(x) ((((x) & _TAG_HEADER_MASK) == _TAG_HEADER_ARITYVAL) && \ (((x) >> _HEADER_ARITY_OFFS) <= MAX_ARITYVAL)) #define is_not_arity_value(x) (!is_arity_value((x))) -#define _unchecked_arityval(x) _unchecked_header_arity((x)) +#define _unchecked_arityval(x) ((x) >> _HEADER_ARITY_OFFS) _ET_DECLARE_CHECKED(Uint,arityval,Eterm) #define arityval(x) _ET_APPLY(arityval,(x)) diff --git a/erts/emulator/beam/erl_utils.h b/erts/emulator/beam/erl_utils.h index f87773ddca..a4624783df 100644 --- a/erts/emulator/beam/erl_utils.h +++ b/erts/emulator/beam/erl_utils.h @@ -71,8 +71,15 @@ Sint erts_list_length(Eterm); int erts_is_builtin(Eterm, Eterm, int); Uint32 make_hash2(Eterm); Uint32 trapping_make_hash2(Eterm, Eterm*, struct process*); +#ifdef DEBUG +# define DBG_HASHMAP_COLLISION_BONANZA +#endif +#ifdef DBG_HASHMAP_COLLISION_BONANZA +Uint32 erts_dbg_hashmap_collision_bonanza(Uint32 hash, Eterm key); +#endif Uint32 make_hash(Eterm); Uint32 make_internal_hash(Eterm, Uint32 salt); +Uint32 make_map_hash(Eterm key); void erts_save_emu_args(int argc, char **argv); Eterm erts_get_emu_args(struct process *c_p); diff --git a/erts/emulator/beam/external.c b/erts/emulator/beam/external.c index 1c79586f3d..697b9c0b8c 100644 --- a/erts/emulator/beam/external.c +++ b/erts/emulator/beam/external.c @@ -3036,7 +3036,6 @@ dec_pid(ErtsDistExternal *edep, ErtsHeapFactory* factory, const byte* ep, #define ENC_BIN_COPY ((Eterm) 3) #define ENC_MAP_PAIR ((Eterm) 4) #define ENC_HASHMAP_NODE ((Eterm) 5) -#define ENC_STORE_MAP_ELEMENT ((Eterm) 6) #define ENC_START_SORTING_MAP ((Eterm) 7) #define ENC_CONTINUE_SORTING_MAP ((Eterm) 8) #define ENC_PUSH_SORTED_MAP ((Eterm) 9) @@ -3232,18 +3231,32 @@ enc_term_int(TTBEncodeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, byte* ep, case ENC_HASHMAP_NODE: if (is_list(obj)) { /* leaf node [K|V] */ ptr = list_val(obj); + if (dflags & DFLAG_DETERMINISTIC) { + *next_map_element++ = CAR(ptr); + *next_map_element++ = CDR(ptr); + goto outer_loop; + } WSTACK_PUSH2(s, ENC_TERM, CDR(ptr)); obj = CAR(ptr); } - break; - case ENC_STORE_MAP_ELEMENT: /* option `deterministic` */ - if (is_list(obj)) { /* leaf node [K|V] */ - ptr = list_val(obj); - *next_map_element++ = CAR(ptr); - *next_map_element++ = CDR(ptr); + else if (is_tuple(obj)) { /* collision node */ + Uint tpl_sz; + ptr = tuple_val(obj); + tpl_sz = arityval(*ptr); + ASSERT(tpl_sz >= 2); + ptr++; + WSTACK_RESERVE(s, tpl_sz * 2); + while(tpl_sz--) { + ASSERT(is_list(*ptr)); + WSTACK_FAST_PUSH(s, ENC_HASHMAP_NODE); + WSTACK_FAST_PUSH(s, *ptr++); + } goto outer_loop; - } - break; + } + else + ASSERT((*boxed_val(obj) & _HEADER_MAP_SUBTAG_MASK) + == HAMT_SUBTAG_NODE_BITMAP); + break; case ENC_START_SORTING_MAP: /* option `deterministic` */ { long num_reductions = r; @@ -3528,7 +3541,6 @@ enc_term_int(TTBEncodeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, byte* ep, } else { Eterm hdr; Uint node_sz; - Eterm node_processor; ptr = boxed_val(obj); hdr = *ptr; ASSERT(is_header(hdr)); @@ -3569,17 +3581,14 @@ enc_term_int(TTBEncodeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, byte* ep, node_sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); ASSERT(node_sz < 17); break; - default: - erts_exit(ERTS_ERROR_EXIT, "bad header\r\n"); - } - + default: + erts_exit(ERTS_ERROR_EXIT, "bad header\r\n"); + } ptr++; - node_processor = (dflags & DFLAG_DETERMINISTIC) ? - ENC_STORE_MAP_ELEMENT : ENC_HASHMAP_NODE; WSTACK_RESERVE(s, node_sz*2); while(node_sz--) { - WSTACK_FAST_PUSH(s, node_processor); - WSTACK_FAST_PUSH(s, *ptr++); + WSTACK_FAST_PUSH(s, ENC_HASHMAP_NODE); + WSTACK_FAST_PUSH(s, *ptr++); } } break; @@ -5365,8 +5374,8 @@ encode_size_struct_int(TTBSizeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, node_sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); ASSERT(node_sz < 17); break; - default: - erts_exit(ERTS_ERROR_EXIT, "bad header\r\n"); + default: + erts_exit(ERTS_ERROR_EXIT, "bad header\r\n"); } ptr++; diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c index 9cd4a57b85..9881eb4a78 100644 --- a/erts/emulator/beam/utils.c +++ b/erts/emulator/beam/utils.c @@ -1616,15 +1616,12 @@ make_hash2_helper(Eterm term_param, const int can_trap, Eterm* state_mref_write_ * We therefore calculate context independent hashes for all . * key-value pairs and then xor them together. */ - ESTACK_PUSH(s, hash_xor_pairs); - ESTACK_PUSH(s, hash); - ESTACK_PUSH(s, HASH_MAP_TAIL); + ESTACK_PUSH3(s, hash_xor_pairs, hash, HASH_MAP_TAIL); hash = 0; hash_xor_pairs = 0; for (ctx.i = ctx.size - 1; ctx.i >= 0; ctx.i--) { - ESTACK_PUSH(s, HASH_MAP_PAIR); - ESTACK_PUSH(s, ctx.vs[ctx.i]); - ESTACK_PUSH(s, ctx.ks[ctx.i]); + ESTACK_PUSH3(s, HASH_MAP_PAIR, + ctx.vs[ctx.i], ctx.ks[ctx.i]); TRAP_LOCATION(hamt_subtag_head_flatmap); } goto hash2_common; @@ -1636,9 +1633,7 @@ make_hash2_helper(Eterm term_param, const int can_trap, Eterm* state_mref_write_ UINT32_HASH(size, HCONST_16); if (size == 0) goto hash2_common; - ESTACK_PUSH(s, hash_xor_pairs); - ESTACK_PUSH(s, hash); - ESTACK_PUSH(s, HASH_MAP_TAIL); + ESTACK_PUSH3(s, hash_xor_pairs, hash, HASH_MAP_TAIL); hash = 0; hash_xor_pairs = 0; } @@ -1656,13 +1651,22 @@ make_hash2_helper(Eterm term_param, const int can_trap, Eterm* state_mref_write_ while (ctx.i) { if (is_list(*ctx.ptr)) { Eterm* cons = list_val(*ctx.ptr); - ESTACK_PUSH(s, HASH_MAP_PAIR); - ESTACK_PUSH(s, CDR(cons)); - ESTACK_PUSH(s, CAR(cons)); + ESTACK_PUSH3(s, HASH_MAP_PAIR, CDR(cons), CAR(cons)); } else { ASSERT(is_boxed(*ctx.ptr)); - ESTACK_PUSH(s, *ctx.ptr); + if (is_tuple(*ctx.ptr)) { /* collision node */ + Eterm *coll_ptr = tuple_val(*ctx.ptr); + Uint n = arityval(*coll_ptr); + ASSERT(n >= 2); + coll_ptr++; + for (; n; n--, coll_ptr++) { + Eterm* cons = list_val(*coll_ptr); + ESTACK_PUSH3(s, HASH_MAP_PAIR, CDR(cons), CAR(cons)); + } + } + else + ESTACK_PUSH(s, *ctx.ptr); } ctx.i--; ctx.ptr++; TRAP_LOCATION(map_subtag); @@ -2047,6 +2051,45 @@ trapping_make_hash2(Eterm term, Eterm* state_mref_write_back, Process* p) return make_hash2_helper(term, 1, state_mref_write_back, p); } +#ifdef DBG_HASHMAP_COLLISION_BONANZA +Uint32 erts_dbg_hashmap_collision_bonanza(Uint32 hash, Eterm key) +{ +/*{ + static Uint32 hashvec[7] = { + 0x02345678, + 0x12345678, + 0xe2345678, + 0xf2345678, + 0x12abcdef, + 0x13abcdef, + 0xcafebabe + }; + hash = hashvec[hash % (sizeof(hashvec) / sizeof(hashvec[0]))]; + }*/ + const Uint32 bad_hash = (hash & 0x12482481) * 1442968193; + const Uint32 bad_bits = hash % 67; + if (bad_bits < 32) { + /* Mix in a number of high good bits to get "randomly" close + to the collision nodes */ + const Uint32 bad_mask = (1 << bad_bits) - 1; + return (hash & ~bad_mask) | (bad_hash & bad_mask); + } + return bad_hash; +} +#endif + +/* Term hash function for maps, with a separate depth parameter */ +Uint32 make_map_hash(Eterm key) { + Uint32 hash = 0; + + hash = make_internal_hash(key, hash); + +#ifdef DBG_HASHMAP_COLLISION_BONANZA + hash = erts_dbg_hashmap_collision_bonanza(hash, key); +#endif + return hash; +} + /* Term hash function for internal use. * * Limitation #1: Is not "portable" in any way between different VM instances. @@ -2057,12 +2100,10 @@ trapping_make_hash2(Eterm term, Eterm* state_mref_write_back, Process* p) * with a new ErlNode struct, externals from that node will hash different than * before. * - * One IMPORTANT property must hold (for hamt). - * EVERY BIT of the term that is significant for equality (see EQ) - * MUST BE USED AS INPUT FOR THE HASH. Two different terms must always have a - * chance of hashing different when salted. - * - * This is why we cannot use cached hash values for atoms for example. + * The property "EVERY BIT of the term that is significant for equality + * MUST BE USED AS INPUT FOR THE HASH" is nice but no longer crucial for the + * hashmap implementation that now uses collision nodes at the bottom of + * the HAMT when all hash bits are exhausted. * */ @@ -2208,6 +2249,8 @@ make_internal_hash(Eterm term, Uint32 salt) } else { ASSERT(is_boxed(*ptr)); + /* no special treatment of collision nodes needed, + hash them as the tuples they are */ ESTACK_PUSH(s, *ptr); } i--; ptr++; @@ -3073,8 +3116,8 @@ tailrecur_ne: sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); ASSERT(sz > 0 && sz < 17); break; - default: - erts_exit(ERTS_ERROR_EXIT, "Unknown hashmap subsubtag\n"); + default: + erts_exit(ERTS_ERROR_EXIT, "bad header"); } goto term_array; } @@ -3437,6 +3480,11 @@ tailrecur_ne: A minimal key can only be candidate as tie-breaker if we have passed that hash value in the other tree (which means the key did not exist in the other tree). + + Collision node amendment: + The leafs in collision nodes are sorted in map-key order. + If keys are different but hashes are equal we advance the + one lagging behind key-wise. */ sp = PSTACK_PUSH(hmap_stack); @@ -3835,12 +3883,19 @@ pop_next: sp = PSTACK_TOP(hmap_stack); if (j) { /* Key diff found, enter phase 2 */ - if (hashmap_key_hash_cmp(sp->ap, sp->bp) < 0) { + int hash_cmp = hashmap_key_hash_cmp(sp->ap, sp->bp); + if (hash_cmp == 0) { + /* Hash collision. Collision nodes are sorted by map key + * order, so we advance the one with the lesser key */ + hash_cmp = j; + } + if (hash_cmp < 0) { sp->min_key = CAR(sp->ap); sp->cmp_res = -1; sp->ap = hashmap_iterator_next(&stack); } else { + ASSERT(hash_cmp > 0); sp->min_key = CAR(sp->bp); sp->cmp_res = 1; sp->bp = hashmap_iterator_next(&b_stack); @@ -3890,7 +3945,7 @@ pop_next: sp->bp = hashmap_iterator_next(&b_stack); if (!sp->ap) { /* end of maps with identical keys */ - ASSERT(!sp->bp); + ASSERT(!sp->bp); /* as we assume indentical map sizes */ j = sp->cmp_res; exact = sp->was_exact; (void) PSTACK_POP(hmap_stack); @@ -3925,14 +3980,21 @@ pop_next: /* fall through */ case_HASHMAP_PHASE2_NEXT_STEP: if (sp->ap || sp->bp) { - if (hashmap_key_hash_cmp(sp->ap, sp->bp) < 0) { + int hash_cmp = hashmap_key_hash_cmp(sp->ap, sp->bp); + if (hash_cmp == 0) { + /* Hash collision. Collision nodes are sorted by map key + * order, so we advance the one with the lesser key */ + hash_cmp = j; + } + if (hash_cmp < 0) { ASSERT(sp->ap); a = CAR(sp->ap); b = sp->min_key; ASSERT(exact); WSTACK_PUSH(stack, OP_WORD(HASHMAP_PHASE2_IS_MIN_KEY_A)); } - else { /* hash_cmp > 0 */ + else { + ASSERT(hash_cmp > 0); ASSERT(sp->bp); a = CAR(sp->bp); b = sp->min_key; diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl index 5707a8e56c..9399303f54 100644 --- a/erts/emulator/test/map_SUITE.erl +++ b/erts/emulator/test/map_SUITE.erl @@ -256,6 +256,8 @@ t_build_and_match_literals_large(Config) when is_list(Config) -> 60 = map_size(M0), 60 = maps:size(M0), + 60 = apply(erlang, id(map_size), [M0]), + 60 = apply(maps, id(size), [M0]), % with repeating M1 = id(#{ 10=>a0,20=>b0,30=>"c0","40"=>"d0",<<"50">>=>"e0",{["00"]}=>"10", @@ -292,6 +294,8 @@ t_build_and_match_literals_large(Config) when is_list(Config) -> 60 = map_size(M1), 60 = maps:size(M1), + 60 = apply(erlang, id(map_size), [M1]), + 60 = apply(maps, id(size), [M1]), % with floats @@ -345,6 +349,8 @@ t_build_and_match_literals_large(Config) when is_list(Config) -> 90 = map_size(M2), 90 = maps:size(M2), + 90 = apply(erlang, id(map_size), [M2]), + 90 = apply(maps, id(size), [M2]), % with bignums M3 = id(#{ 10=>a0,20=>b0,30=>"c0","40"=>"d0",<<"50">>=>"e0",{["00"]}=>"10", @@ -408,6 +414,8 @@ t_build_and_match_literals_large(Config) when is_list(Config) -> 98 = map_size(M3), 98 = maps:size(M3), + 98 = apply(erlang, id(map_size), [M3]), + 98 = apply(maps, id(size), [M3]), %% with maps @@ -528,6 +536,8 @@ t_build_and_match_literals_large(Config) when is_list(Config) -> 95 = map_size(M4), 95 = maps:size(M4), + 95 = apply(erlang, id(map_size), [M4]), + 95 = apply(maps, id(size), [M4]), % call for value @@ -625,6 +635,8 @@ t_build_and_match_literals_large(Config) when is_list(Config) -> 95 = map_size(M5), 95 = maps:size(M5), + 95 = apply(erlang, id(map_size), [M5]), + 95 = apply(maps, id(size), [M5]), %% remember @@ -2046,6 +2058,10 @@ t_bif_map_merge(Config) when is_list(Config) -> {'EXIT',{{badmap,T},[{maps,merge,_,_}|_]}} = (catch maps:merge(T, #{})), {'EXIT',{{badmap,T},[{maps,merge,_,_}|_]}} = + (catch maps:merge(M11, T)), + {'EXIT',{{badmap,T},[{maps,merge,_,_}|_]}} = + (catch maps:merge(T, M11)), + {'EXIT',{{badmap,T},[{maps,merge,_,_}|_]}} = (catch maps:merge(T, T)) end), ok. @@ -2279,6 +2295,16 @@ t_bif_erlang_phash2() -> 70249457 = erlang:phash2(M0), % 118679416 59617982 = erlang:phash2(M1), % 51612236 70249457 = erlang:phash2(M2), % 118679416 + + M1000 = maps:from_list([{K,K} || K <- lists:seq(1,1000)]), + 66609305 = erlang:phash2(M1000), + + Mnested1 = #{flatmap => M0, M0 => flatmap, hashmap => M1000, M1000 => hashmap}, + 113689339 = erlang:phash2(Mnested1), + + Mnested2 = maps:merge(Mnested1, M1000), + 29167443 = erlang:phash2(Mnested2), + ok. t_bif_erlang_phash() -> @@ -2299,6 +2325,16 @@ t_bif_erlang_phash() -> 2620391445 = erlang:phash(M0,Sz), % 3590546636 1670235874 = erlang:phash(M1,Sz), % 4066388227 2620391445 = erlang:phash(M2,Sz), % 3590546636 + + M1000 = maps:from_list([{K,K} || K <- lists:seq(1,1000)]), + 1945662653 = erlang:phash(M1000, Sz), + + Mnested1 = #{flatmap => M0, M0 => flatmap, hashmap => M1000, M1000 => hashmap}, + 113694495 = erlang:phash(Mnested1, Sz), + + Mnested2 = maps:merge(Mnested1, M1000), + 431825783 = erlang:phash(Mnested2, Sz), + ok. t_map_encode_decode(Config) when is_list(Config) -> @@ -2774,25 +2810,31 @@ t_maps_without(_Config) -> %% Verify that the the number of nodes in hashmaps %% of different types and sizes does not deviate too %% much from the theoretical model. +%% For debug with DBG_HASHMAP_COLLISION_BONANZA the test will expect +%% the hashmaps to NOT be well balanced. t_hashmap_balance(_Config) -> + erts_debug:set_internal_state(available_internal_state, true), + ExpectBalance = not erts_debug:get_internal_state(hashmap_collision_bonanza), + hashmap_balance(ExpectBalance), + erts_debug:set_internal_state(available_internal_state, false), + ok. + +hashmap_balance(EB) -> io:format("Integer keys\n", []), - hashmap_balance(fun(I) -> I end), + hashmap_balance(fun(I) -> I end, EB), io:format("Float keys\n", []), - hashmap_balance(fun(I) -> float(I) end), + hashmap_balance(fun(I) -> float(I) end, EB), io:format("String keys\n", []), - hashmap_balance(fun(I) -> integer_to_list(I) end), + hashmap_balance(fun(I) -> integer_to_list(I) end, EB), io:format("Binary (big) keys\n", []), - hashmap_balance(fun(I) -> <<I:16/big>> end), + hashmap_balance(fun(I) -> <<I:16/big>> end, EB), io:format("Binary (little) keys\n", []), - hashmap_balance(fun(I) -> <<I:16/little>> end), + hashmap_balance(fun(I) -> <<I:16/little>> end, EB), io:format("Atom keys\n", []), - erts_debug:set_internal_state(available_internal_state, true), - hashmap_balance(fun(I) -> erts_debug:get_internal_state({atom,I}) end), - erts_debug:set_internal_state(available_internal_state, false), - + hashmap_balance(fun(I) -> erts_debug:get_internal_state({atom,I}) end, EB), ok. -hashmap_balance(KeyFun) -> +hashmap_balance(KeyFun, ExpectBalance) -> %% For uniformly distributed hash values, the average number of nodes N %% in a hashmap varies between 0.3*K and 0.4*K where K is number of keys. %% The standard deviation of N is about sqrt(K)/3. @@ -2836,9 +2878,10 @@ hashmap_balance(KeyFun) -> erts_debug:flat_size(MaxMap)]) end, - true = (MaxDiff < 6), % The probability of this line failing is about 0.000000001 - % for a uniform hash. I've set the probability this "high" for now - % to detect flaws in our make_internal_hash. + %% The probability of this line failing is about 0.000000001 + %% for a uniform hash. I've set the probability this "high" for now + %% to detect flaws in our make_internal_hash. + ExpectBalance = (MaxDiff < 6), ok. hashmap_nodes(M) -> @@ -2847,6 +2890,7 @@ hashmap_nodes(M) -> case element(1,Tpl) of bitmaps -> Acc + element(2,Tpl); arrays -> Acc + element(2,Tpl); + collisions -> Acc + element(2,Tpl); _ -> Acc end end, |