First non-recursive version of hashmap:merge/2

1 files changed, 116 insertions, 64 deletions

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*);