From 12bf6b0c82762744506e153720076524401c8512 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Mon, 23 Mar 2015 17:07:45 +0100 Subject: erts: Rename to flatmap_from_validated_list from map_to_validated_list --- erts/emulator/beam/erl_map.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'erts/emulator/beam') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index bcbda65da0..26233a98c6 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -85,7 +85,7 @@ static Eterm hashmap_to_list(Process *p, Eterm map); static Eterm hashmap_keys(Process *p, Eterm map); static Eterm hashmap_values(Process *p, Eterm map); static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node); -static Eterm map_from_validated_list(Process *p, Eterm list, Uint size); +static Eterm flatmap_from_validated_list(Process *p, Eterm list, Uint size); static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size); static Eterm hashmap_from_unsorted_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int reject_dupkeys); static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int is_root); @@ -277,7 +277,7 @@ BIF_RETTYPE maps_from_list_1(BIF_ALIST_1) { if (size > MAP_SMALL_MAP_LIMIT) { BIF_RET(hashmap_from_validated_list(BIF_P, BIF_ARG_1, size)); } else { - BIF_RET(map_from_validated_list(BIF_P, BIF_ARG_1, size)); + BIF_RET(flatmap_from_validated_list(BIF_P, BIF_ARG_1, size)); } } @@ -286,7 +286,7 @@ error: BIF_ERROR(BIF_P, BADARG); } -static Eterm map_from_validated_list(Process *p, Eterm list, Uint size) { +static Eterm flatmap_from_validated_list(Process *p, Eterm list, Uint size) { Eterm *kv, item = list; Eterm *hp, *thp,*vs, *ks, keys, res; flatmap_t *mp; -- cgit v1.2.3 From 1f23b603f022c7345dd573bf917926a575ae030d Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 24 Mar 2015 20:01:11 +0100 Subject: erts: Fix bug in binary_to_term for hamt when yielding Must save hamt_list in context. --- erts/emulator/beam/external.c | 1 + 1 file changed, 1 insertion(+) (limited to 'erts/emulator/beam') diff --git a/erts/emulator/beam/external.c b/erts/emulator/beam/external.c index 82c60840e5..c99b60ed09 100644 --- a/erts/emulator/beam/external.c +++ b/erts/emulator/beam/external.c @@ -3878,6 +3878,7 @@ dec_term_atom_common: ctx->u.dc.next = next; ctx->u.dc.hp = hp; ctx->u.dc.maps_list = maps_list; + ctx->u.dc.hamt_list = hamt_list; ctx->reds = 0; return NULL; } -- cgit v1.2.3 From db54eaa94562b49c81b677948a8e9139ebdb010e Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 24 Mar 2015 15:27:11 +0100 Subject: erts: Remove HAMT_SUBTAG_NODE_ARRAY This will also fix a bug in term_to_binary treating full nodes as tuples and emiting LIST_EXT for leafs. --- erts/emulator/beam/erl_map.c | 88 ++++++------------------------------------- erts/emulator/beam/erl_map.h | 6 --- erts/emulator/beam/external.c | 6 +-- erts/emulator/beam/utils.c | 5 +-- 4 files changed, 15 insertions(+), 90 deletions(-) (limited to 'erts/emulator/beam') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 26233a98c6..ef806c2cfa 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -775,7 +775,7 @@ static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory, sz = hashmap_bitcount(hdr); hp = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(sz), HALLOC_EXTRA); nhp = hp; - *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_NODE_ARRAY : MAP_HEADER_HAMT_NODE_BITMAP(hdr); + *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hdr); *hp++ = res; sz--; while (sz--) { *hp++ = ESTACK_POP(stack); } ASSERT((hp - nhp) < 18); @@ -824,7 +824,7 @@ static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory, sz = hashmap_bitcount(hdr); hp = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(sz), HALLOC_EXTRA); nhp = hp; - *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_NODE_ARRAY : MAP_HEADER_HAMT_NODE_BITMAP(hdr); + *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hdr); *hp++ = res; sz--; while (sz--) { *hp++ = ESTACK_POP(stack); } @@ -846,7 +846,7 @@ static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory, *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_HEAD_ARRAY : MAP_HEADER_HAMT_HEAD_BITMAP(hdr); *hp++ = n; } else { - *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_NODE_ARRAY : MAP_HEADER_HAMT_NODE_BITMAP(hdr); + *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hdr); } *hp++ = res; sz--; @@ -1163,8 +1163,8 @@ recurse: sp->abm = 1 << hashmap_index(ahx); sp->srcA = &nodeA; switch(hdrB & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_HEAD_ARRAY: sp->srcB++; - case HAMT_SUBTAG_NODE_ARRAY: + case HAMT_SUBTAG_HEAD_ARRAY: + sp->srcB++; sp->bbm = 0xffff; break; @@ -1189,16 +1189,16 @@ recurse: hdrA = *sp->srcA++; ASSERT(is_header(hdrA)); switch (hdrA & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_HEAD_ARRAY: sp->srcA++; - case HAMT_SUBTAG_NODE_ARRAY: { + case HAMT_SUBTAG_HEAD_ARRAY: { + sp->srcA++; ASSERT(primary_tag(nodeB) == TAG_PRIMARY_BOXED); sp->abm = 0xffff; sp->srcB = boxed_val(nodeB); hdrB = *sp->srcB++; ASSERT(is_header(hdrB)); switch (hdrB & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_HEAD_ARRAY: sp->srcB++; - case HAMT_SUBTAG_NODE_ARRAY: + case HAMT_SUBTAG_HEAD_ARRAY: + sp->srcB++; sp->bbm = 0xffff; break; case HAMT_SUBTAG_HEAD_BITMAP: sp->srcB++; @@ -1218,8 +1218,8 @@ recurse: hdrB = *sp->srcB++; ASSERT(is_header(hdrB)); switch (hdrB & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_HEAD_ARRAY: sp->srcB++; - case HAMT_SUBTAG_NODE_ARRAY: + case HAMT_SUBTAG_HEAD_ARRAY: + sp->srcB++; sp->bbm = 0xffff; break; case HAMT_SUBTAG_HEAD_BITMAP: sp->srcB++; @@ -1296,8 +1296,7 @@ recurse: } else { nhp = HAllocX(p, HAMT_NODE_BITMAP_SZ(sp->ix), HALLOC_EXTRA); hp = nhp; - *hp++ = (sp->ix == 16 ? make_arityval(16) - : MAP_HEADER_HAMT_NODE_BITMAP(sp->abm | sp->bbm)); + *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(sp->abm | sp->bbm); } memcpy(hp, sp->array, sp->ix * sizeof(Eterm)); res = make_boxed(nhp); @@ -1748,7 +1747,6 @@ Eterm* hashmap_iterator_next(ErtsWStack* s) { switch(hdr & _HEADER_MAP_SUBTAG_MASK) { case HAMT_SUBTAG_HEAD_ARRAY: ptr++; - case HAMT_SUBTAG_NODE_ARRAY: sz = 16; break; case HAMT_SUBTAG_HEAD_BITMAP: @@ -1799,7 +1797,6 @@ Eterm* hashmap_iterator_prev(ErtsWStack* s) { switch(hdr & _HEADER_MAP_SUBTAG_MASK) { case HAMT_SUBTAG_HEAD_ARRAY: ptr++; - case HAMT_SUBTAG_NODE_ARRAY: sz = 16; break; case HAMT_SUBTAG_HEAD_BITMAP: @@ -1862,11 +1859,6 @@ erts_hashmap_get(Uint32 hx, Eterm key, Eterm node) ASSERT(is_header(hdr)); switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_NODE_ARRAY: - ix = hashmap_index(hx); - hx = hashmap_shift_hash(th,hx,lvl,key); - node = ptr[ix+1]; - break; case HAMT_SUBTAG_HEAD_ARRAY: ix = hashmap_index(hx); hx = hashmap_shift_hash(th,hx,lvl,key); @@ -1964,13 +1956,6 @@ int erts_hashmap_insert_down(Uint32 hx, Eterm key, Eterm node, Uint *sz, ASSERT(is_header(hdr)); switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_NODE_ARRAY: - ix = hashmap_index(hx); - hx = hashmap_shift_hash(th,hx,lvl,key); - size += HAMT_NODE_ARRAY_SZ; - ESTACK_PUSH2(*sp, ix, node); - node = ptr[ix+1]; - break; case HAMT_SUBTAG_HEAD_ARRAY: ix = hashmap_index(hx); hx = hashmap_shift_hash(th,hx,lvl,key); @@ -2100,14 +2085,6 @@ Eterm erts_hashmap_insert_up(Eterm *hp, Eterm key, Eterm value, ASSERT(is_header(hdr)); switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_NODE_ARRAY: - slot = (Uint) ESTACK_POP(*sp); - nhp = hp; - n = HAMT_NODE_ARRAY_SZ; - while(n--) { *hp++ = *ptr++; } - nhp[slot+1] = res; - res = make_hashmap(nhp); - break; case HAMT_SUBTAG_HEAD_ARRAY: slot = (Uint) ESTACK_POP(*sp); nhp = hp; @@ -2132,9 +2109,6 @@ Eterm erts_hashmap_insert_up(Eterm *hp, Eterm key, Eterm value, if (hval & bp) { ptr++; n--; } while(n--) { *hp++ = *ptr++; } - if ((hval | bp) == 0xffff) { - *nhp = make_arityval(16); - } res = make_hashmap(nhp); break; case HAMT_SUBTAG_HEAD_BITMAP: @@ -2230,13 +2204,6 @@ static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm map) { ASSERT(is_header(hdr)); switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_NODE_ARRAY: - ix = hashmap_index(hx); - hx = hashmap_shift_hash(th,hx,lvl,key); - size += HAMT_NODE_ARRAY_SZ; - ESTACK_PUSH2(stack, ix, node); - node = ptr[ix+1]; - break; case HAMT_SUBTAG_HEAD_ARRAY: ix = hashmap_index(hx); hx = hashmap_shift_hash(th,hx,lvl,key); @@ -2351,24 +2318,6 @@ unroll: ASSERT(is_header(hdr)); switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_NODE_ARRAY: - ix = (Uint) ESTACK_POP(stack); - nhp = hp; - if (res == THE_NON_VALUE) { - *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(0xffff ^ (1 << ix)); ptr++; - n = 16; - n -= ix; - while(ix--) { *hp++ = *ptr++; } - ptr++; n--; - while(n--) { *hp++ = *ptr++; } - res = make_hashmap(nhp); - } else { - n = HAMT_NODE_ARRAY_SZ; - while(n--) { *hp++ = *ptr++; } - nhp[ix+1] = res; - res = make_hashmap(nhp); - } - break; case HAMT_SUBTAG_HEAD_ARRAY: ix = (Uint) ESTACK_POP(stack); nhp = hp; @@ -2610,7 +2559,6 @@ BIF_RETTYPE erts_internal_map_type_1(BIF_ALIST_1) { case HAMT_SUBTAG_HEAD_ARRAY: case HAMT_SUBTAG_HEAD_BITMAP: BIF_RET(AM_hashmap); - case HAMT_SUBTAG_NODE_ARRAY: case HAMT_SUBTAG_NODE_BITMAP: BIF_RET(AM_hashmap_node); default: @@ -2637,10 +2585,6 @@ BIF_RETTYPE erts_internal_map_hashmap_children_1(BIF_ALIST_1) { ASSERT(is_header(hdr)); switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_NODE_ARRAY: - sz = 16; - ptr += 1; - break; case HAMT_SUBTAG_NODE_BITMAP: sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); ptr += 1; @@ -2703,14 +2647,6 @@ static Eterm hashmap_info(Process *p, Eterm node) { hdr = *ptr; ASSERT(is_header(hdr)); switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_NODE_ARRAY: - narray++; - sz = 16; - while(sz--) { - ESTACK_PUSH(stack, clvl + 1); - ESTACK_PUSH(stack, ptr[sz+1]); - } - break; case HAMT_SUBTAG_NODE_BITMAP: nbitmap++; sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h index 1333a734a8..9fc1a72b68 100644 --- a/erts/emulator/beam/erl_map.h +++ b/erts/emulator/beam/erl_map.h @@ -178,21 +178,15 @@ typedef struct hashmap_head_s { #define MAP_HEADER_HAMT_HEAD_BITMAP(Bmp) \ MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_HEAD_BITMAP,0x1,Bmp) -#define MAP_HEADER_HAMT_NODE_ARRAY \ - make_arityval(16) - #define MAP_HEADER_HAMT_NODE_BITMAP(Bmp) \ MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_NODE_BITMAP,0x0,Bmp) #define HAMT_HEAD_EMPTY_SZ (2) -#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 _HEADER_MAP_SUBTAG_MASK (0xfc) /* 2 bits maps tag + 4 bits subtag + 2 ignore bits */ -/* SUBTAG_NODE_ARRAY is in fact a tuple with 16 elements */ -#define HAMT_SUBTAG_NODE_ARRAY (((16 << _HEADER_ARITY_OFFS) | ARITYVAL_SUBTAG) & _HEADER_MAP_SUBTAG_MASK) #define HAMT_SUBTAG_NODE_BITMAP ((MAP_HEADER_TAG_HAMT_NODE_BITMAP << _HEADER_ARITY_OFFS) | HASHMAP_SUBTAG) #define HAMT_SUBTAG_HEAD_ARRAY ((MAP_HEADER_TAG_HAMT_HEAD_ARRAY << _HEADER_ARITY_OFFS) | HASHMAP_SUBTAG) #define HAMT_SUBTAG_HEAD_BITMAP ((MAP_HEADER_TAG_HAMT_HEAD_BITMAP << _HEADER_ARITY_OFFS) | HASHMAP_SUBTAG) diff --git a/erts/emulator/beam/external.c b/erts/emulator/beam/external.c index c99b60ed09..b0b232f185 100644 --- a/erts/emulator/beam/external.c +++ b/erts/emulator/beam/external.c @@ -2633,8 +2633,6 @@ enc_term_int(TTBEncodeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, byte* ep, *ep++ = MAP_EXT; ptr++; put_int32(*ptr, ep); ep += 4; - /*fall through*/ - case HAMT_SUBTAG_NODE_ARRAY: node_sz = 16; break; case HAMT_SUBTAG_HEAD_BITMAP: @@ -4172,8 +4170,8 @@ encode_size_struct_int(TTBSizeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, hdr = *ptr; ASSERT(is_header(hdr)); switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_HEAD_ARRAY: ptr++; - case HAMT_SUBTAG_NODE_ARRAY: + case HAMT_SUBTAG_HEAD_ARRAY: + ptr++; node_sz = 16; break; case HAMT_SUBTAG_HEAD_BITMAP: ptr++; diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c index 3549e18538..d98251addc 100644 --- a/erts/emulator/beam/utils.c +++ b/erts/emulator/beam/utils.c @@ -1321,7 +1321,6 @@ make_hash2(Eterm term) } switch (hdr & _HEADER_MAP_SUBTAG_MASK) { case HAMT_SUBTAG_HEAD_ARRAY: - case HAMT_SUBTAG_NODE_ARRAY: i = 16; break; case HAMT_SUBTAG_HEAD_BITMAP: @@ -1724,7 +1723,6 @@ make_internal_hash(Eterm term) } switch (hdr & _HEADER_MAP_SUBTAG_MASK) { case HAMT_SUBTAG_HEAD_ARRAY: - case HAMT_SUBTAG_NODE_ARRAY: i = 16; break; case HAMT_SUBTAG_HEAD_BITMAP: @@ -2797,14 +2795,13 @@ tailrecur_ne: switch (hdr & _HEADER_MAP_SUBTAG_MASK) { case HAMT_SUBTAG_HEAD_ARRAY: aa++; bb++; - case HAMT_SUBTAG_NODE_ARRAY: sz = 16; break; case HAMT_SUBTAG_HEAD_BITMAP: aa++; bb++; case HAMT_SUBTAG_NODE_BITMAP: sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); - ASSERT(sz > 0 && sz < 16); + ASSERT(sz > 0 && sz < 17); break; default: erl_exit(1, "Unknown hashmap subsubtag\n"); -- cgit v1.2.3 From 8d31ecea8b68ef6e16d7d77c0160e36f078b98de Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 24 Mar 2015 15:03:46 +0100 Subject: erts: Optimize hashmap_get --- erts/emulator/beam/erl_map.c | 96 +++++++++++++++++--------------------------- 1 file changed, 36 insertions(+), 60 deletions(-) (limited to 'erts/emulator/beam') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index ef806c2cfa..3852366876 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -1837,75 +1837,51 @@ erts_hashmap_get_rel(Uint32 hx, Eterm key, Eterm node, Eterm *map_base) erts_hashmap_get(Uint32 hx, Eterm key, Eterm node) #endif { - Eterm *ptr, hdr; - Uint ix,slot, lvl = 0; + Eterm *ptr, hdr, *res; + Uint ix, lvl = 0; Uint32 hval,bp; DeclareTmpHeapNoproc(th,2); UseTmpHeapNoproc(2); + ASSERT(is_boxed(node)); + ptr = boxed_val(node); + hdr = *ptr; + ASSERT(is_header(hdr)); + ASSERT(is_hashmap_header_head(hdr)); + ptr++; + for (;;) { - switch(primary_tag(node)) { - case TAG_PRIMARY_LIST: /* LEAF NODE [K|V] */ - ptr = list_val(node); - UnUseTmpHeapNoproc(2); - - if (eq_rel(CAR(ptr), map_base, key, NULL)) { - return &(CDR(ptr)); - } - return NULL; - case TAG_PRIMARY_BOXED: - ptr = boxed_val(node); - hdr = *ptr; - ASSERT(is_header(hdr)); - - switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_HEAD_ARRAY: - ix = hashmap_index(hx); - hx = hashmap_shift_hash(th,hx,lvl,key); - node = ptr[ix+2]; - break; - case HAMT_SUBTAG_NODE_BITMAP: - hval = MAP_HEADER_VAL(hdr); - ix = hashmap_index(hx); - bp = 1 << ix; - slot = hashmap_bitcount(hval & (bp - 1)); - - /* occupied */ - if (bp & hval) { - hx = hashmap_shift_hash(th,hx,lvl,key); - node = ptr[slot+1]; - break; - } - /* not occupied */ - UnUseTmpHeapNoproc(2); - return NULL; - case HAMT_SUBTAG_HEAD_BITMAP: - hval = MAP_HEADER_VAL(hdr); - ix = hashmap_index(hx); - bp = 1 << ix; - slot = hashmap_bitcount(hval & (bp - 1)); - - /* occupied */ - if (bp & hval) { - hx = hashmap_shift_hash(th,hx,lvl,key); - node = ptr[slot+2]; - break; - } - /* not occupied */ - UnUseTmpHeapNoproc(2); - return NULL; - default: - erl_exit(1, "bad header tag %ld\r\n", hdr & _HEADER_MAP_SUBTAG_MASK); - break; - } - break; - default: - erl_exit(1, "bad primary tag %p\r\n", node); + hval = MAP_HEADER_VAL(hdr); + ix = hashmap_index(hx); + if (hval != 0xffff) { + bp = 1 << ix; + if (!(bp & hval)) { + /* not occupied */ + res = NULL; break; + } + ix = hashmap_bitcount(hval & (bp - 1)); + } + node = ptr[ix+1]; + + if (is_list(node)) { /* LEAF NODE [K|V] */ + ptr = list_val(node); + + res = eq_rel(CAR(ptr), map_base, key, NULL) ? &(CDR(ptr)) : NULL; + break; } + + hx = hashmap_shift_hash(th,hx,lvl,key); + + ASSERT(is_boxed(node)); + ptr = boxed_val(node); + hdr = *ptr; + ASSERT(is_header(hdr)); + ASSERT(!is_hashmap_header_head(hdr)); } + UnUseTmpHeapNoproc(2); - return NULL; + return res; } Eterm erts_hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, -- cgit v1.2.3