From f3c7a82d45db4c8d9a9f3579726719360384da50 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Wed, 21 Jan 2015 14:17:41 +0100 Subject: First non-recursive version of hashmap:merge/2 --- erts/emulator/beam/erl_hashmap.c | 180 +++++++++++++++++++++++++-------------- 1 file changed, 116 insertions(+), 64 deletions(-) (limited to 'erts/emulator/beam') diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c index 74f27fb3ac..bdcb479c30 100644 --- a/erts/emulator/beam/erl_hashmap.c +++ b/erts/emulator/beam/erl_hashmap.c @@ -70,7 +70,7 @@ static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node); 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_merge(Process *p, Eterm nodeA, Eterm nodeB, Uint lvl, Uint *sizep, int keepA); +static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB); static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]); /* hashmap:new/0 */ @@ -196,10 +196,7 @@ BIF_RETTYPE hashmap_values_1(BIF_ALIST_1) { BIF_RETTYPE hashmap_merge_2(BIF_ALIST_2) { if (is_hashmap(BIF_ARG_1) && is_hashmap(BIF_ARG_2)) { - hashmap_head_t* a = (hashmap_head_t*) hashmap_val(BIF_ARG_1); - hashmap_head_t* b = (hashmap_head_t*) hashmap_val(BIF_ARG_2); - Uint size = a->size + b->size; - BIF_RET(hashmap_merge(BIF_P, BIF_ARG_1, BIF_ARG_2, 0, &size, 0)); + BIF_RET(hashmap_merge(BIF_P, BIF_ARG_1, BIF_ARG_2)); } BIF_ERROR(BIF_P, BADARG); } @@ -797,15 +794,46 @@ static Eterm hashmap_to_list(Process *p, Eterm node) { #define HALLOC_EXTRA 200 -static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB, - Uint lvl, Uint *sizep, int keepA) { +#if defined(VALGRIND) || defined(GO_SUPER_FAST) +# define UNDEF(V,I) +#else +# define UNDEF(V,I) V=I +#endif + +static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB) { + struct { + Eterm *ptrA, *ptrB; + Uint32 abm, bbm, rbm; + Uint ix; + int keepA; + Eterm array[16]; + }stack[16]; Eterm *hp, *nhp; Eterm *ptrA, *ptrB; - Eterm array[16]; Eterm hdrA, hdrB; Eterm th[2]; Uint32 ahx, bhx, abm, bbm, rbm, bit; Uint ix; + Uint size; + int keepA = 0; + unsigned lvl = 0; + Eterm res = THE_NON_VALUE; + + UNDEF(abm,0); + UNDEF(bbm,0); + + /* + * Strategy: Do depth-first traversal of both trees (at the same time) + * and merge each pair of nodes. + */ + + { + hashmap_head_t* a = (hashmap_head_t*) hashmap_val(nodeA); + hashmap_head_t* b = (hashmap_head_t*) hashmap_val(nodeB); + size = a->size + b->size; + } + +recurse: if (primary_tag(nodeA) == TAG_PRIMARY_BOXED && primary_tag(nodeB) == TAG_PRIMARY_LIST) { @@ -817,40 +845,27 @@ static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB, } switch (primary_tag(nodeA)) { - case TAG_PRIMARY_LIST: { /* LEAF NODE [K|V] */ + case TAG_PRIMARY_LIST: { ptrA = list_val(nodeA); switch (primary_tag(nodeB)) { - case TAG_PRIMARY_LIST: { /* LEAF NODE [K|V] */ + case TAG_PRIMARY_LIST: { /* LEAF + LEAF */ ptrB = list_val(nodeB); if (EQ(CAR(ptrA), CAR(ptrB))) { - --(*sizep); - return keepA ? nodeA : nodeB; - } - ahx = hashmap_restore_hash(th, lvl, CAR(ptrA)); - bhx = hashmap_restore_hash(th, lvl, CAR(ptrB)); - abm = 1 << hashmap_index(ahx); - bbm = 1 << hashmap_index(bhx); - - if (abm != bbm) { - hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(2), HALLOC_EXTRA); - hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(abm | bbm); - if (abm < bbm) { - hp[1] = CAR(ptrA); - hp[2] = CAR(ptrB); - } else { - hp[1] = CAR(ptrB); - hp[2] = CAR(ptrA); - } - } - else { - hp = HAllocX(p, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA); - hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(abm); - hp[1] = hashmap_merge(p, nodeA, nodeB, lvl+1, sizep, keepA); + --size; + res = keepA ? nodeA : nodeB; + } else { + ahx = hashmap_restore_hash(th, lvl, CAR(ptrA)); + bhx = hashmap_restore_hash(th, lvl, CAR(ptrB)); + abm = 1 << hashmap_index(ahx); + bbm = 1 << hashmap_index(bhx); + + ptrA = &nodeA; + ptrB = &nodeB; } - return make_hashmap(hp); + break; } - case TAG_PRIMARY_BOXED: { + case TAG_PRIMARY_BOXED: { /* LEAF + NODE */ ptrB = boxed_val(nodeB); ASSERT(is_header(*ptrB)); hdrB = *ptrB++; @@ -884,7 +899,7 @@ static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB, } break; } - case TAG_PRIMARY_BOXED: { + case TAG_PRIMARY_BOXED: { /* NODE + NODE */ ptrA = boxed_val(nodeA); hdrA = *ptrA; ASSERT(is_header(hdrA)); @@ -974,39 +989,76 @@ static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB, erl_exit(1, "bad primary tag %ld\r\n", nodeA); } - ix = 0; - rbm = abm | bbm; - ASSERT(rbm != 0); - do { - Uint32 next = rbm & (rbm-1); - bit = rbm ^ next; - rbm = next; - if (abm & bit) { - if (bbm & bit) { - array[ix++] = hashmap_merge(p, *ptrA++, *ptrB++, lvl+1, sizep, keepA); + for (;;) { + if (is_value(res)) { /* We have a complete (sub-)tree or leaf */ + if (lvl == 0) + return res; + + /* Pop from stack and continue build parent node */ + lvl--; + abm = stack[lvl].abm; + bbm = stack[lvl].bbm; + rbm = stack[lvl].rbm; + ix = stack[lvl].ix; + stack[lvl].array[ix++] = res; + res = THE_NON_VALUE; + if (rbm) { + ptrA = stack[lvl].ptrA; + ptrB = stack[lvl].ptrB; + keepA = stack[lvl].keepA; + } + } else { /* Start build a node */ + ix = 0; + rbm = abm | bbm; + ASSERT(!(rbm == 0 && lvl > 0)); + } + + while (rbm) { + Uint32 next = rbm & (rbm-1); + bit = rbm ^ next; + rbm = next; + if (abm & bit) { + if (bbm & bit) { + /* Bit clash. Push and resolve by recursive merge */ + if (rbm) { + stack[lvl].ptrA = ptrA + 1; + stack[lvl].ptrB = ptrB + 1; + stack[lvl].keepA = keepA; + } + stack[lvl].abm = abm; + stack[lvl].bbm = bbm; + stack[lvl].rbm = rbm; + stack[lvl].ix = ix; + nodeA = *ptrA; + nodeB = *ptrB; + lvl++; + goto recurse; + } else { + stack[lvl].array[ix++] = *ptrA++; + } } else { - array[ix++] = *ptrA++; + ASSERT(bbm & bit); + stack[lvl].array[ix++] = *ptrB++; } + } + + if (lvl == 0) { + nhp = HAllocX(p, HAMT_HEAD_BITMAP_SZ(ix), HALLOC_EXTRA); + hp = nhp; + *hp++ = (ix == 16) ? MAP_HEADER_HAMT_HEAD_ARRAY + : MAP_HEADER_HAMT_HEAD_BITMAP(abm | bbm); + *hp++ = size; } else { - ASSERT(bbm & bit); - array[ix++] = *ptrB++; + nhp = HAllocX(p, HAMT_NODE_BITMAP_SZ(ix), HALLOC_EXTRA); + hp = nhp; + *hp++ = (ix == 16) ? make_arityval(16) + : MAP_HEADER_HAMT_NODE_BITMAP(abm | bbm); } - }while (rbm); - - if (lvl == 0) { - nhp = HAllocX(p, HAMT_HEAD_BITMAP_SZ(ix), HALLOC_EXTRA); - hp = nhp; - *hp++ = (ix == 16) ? MAP_HEADER_HAMT_HEAD_ARRAY - : MAP_HEADER_HAMT_HEAD_BITMAP(abm | bbm); - *hp++ = *sizep; - } else { - nhp = HAllocX(p, HAMT_NODE_BITMAP_SZ(ix), HALLOC_EXTRA); - hp = nhp; - *hp++ = (ix == 16) ? make_arityval(16) - : MAP_HEADER_HAMT_NODE_BITMAP(abm | bbm); + memcpy(hp, stack[lvl].array, ix * sizeof(Eterm)); + res = make_boxed(nhp); } - memcpy(hp, array, ix * sizeof(Eterm)); - return make_boxed(nhp); + + return res; } typedef void hashmap_doer(Eterm*, void*); -- cgit v1.2.3