erts: Simplify map hashing

Cherry-picked: 5b0cf37de9d69a63a49dac1171ad4e5f1e616cf3

4 files changed, 39 insertions, 38 deletions

diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index c4ddee1436..34c4189fe9 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -486,14 +486,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 +510,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;
@@ -849,7 +846,6 @@ static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory* factory,
     Uint32 hx;
     Eterm val;
     hxnode_t *tmp = NULL;
-    Eterm th[2];
     ASSERT(lvl < 32);
     ix = 0;
     elems = 1;
@@ -861,7 +857,7 @@ static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory* factory,
 
 	    for(i = 0; i < jx - ix; i++) {
 		val = hxns[i + ix].val;
-		hx  = hashmap_restore_hash(th, lvl + 8, CAR(list_val(val)));
+		hx  = hashmap_restore_hash(lvl + 8, CAR(list_val(val)));
 		swizzle32(sw,hx);
 		tmp[i].hx   = sw;
 		tmp[i].val  = val;
@@ -1497,8 +1493,6 @@ 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);
 
     /*
      * Strategy: Do depth-first traversal of both trees (at the same time)
@@ -1558,7 +1552,7 @@ recurse:
                     goto merge_nodes;
                 }
             }
-            hx = hashmap_restore_hash(th, ctx->lvl, keyA);
+            hx = hashmap_restore_hash(ctx->lvl, keyA);
             sp->abm = 1 << hashmap_index(hx);
             /* keep srcA pointing at the leaf */
         }
@@ -1585,7 +1579,7 @@ recurse:
         if (is_list(sp->nodeB)) { /* B is LEAF */
             Eterm keyB = CAR(list_val(sp->nodeB));
 
-            hx = hashmap_restore_hash(th, ctx->lvl, keyB);
+            hx = hashmap_restore_hash(ctx->lvl, keyB);
             sp->bbm = 1 << hashmap_index(hx);
             /* keep srcB pointing at the leaf */
         }
@@ -1780,23 +1774,20 @@ 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) {
 	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));
+	    Uint32 ha = hashmap_restore_hash(lvl, CAR(ap));
+	    Uint32 hb = hashmap_restore_hash(lvl, CAR(bp));
 	    int cmp = hash_cmp(ha, hb);
 	    if (cmp) {
-                UnUseTmpHeapNoproc(2);
 		return cmp;
             }
 	    lvl += 8;
 	}
     }
-    UnUseTmpHeapNoproc(2);
+
     return ap ? -1 : 1;
 }
 
@@ -2326,8 +2317,6 @@ erts_hashmap_get(Uint32 hx, Eterm key, Eterm node)
     Eterm *ptr, hdr, *res;
     Uint ix, lvl = 0;
     Uint32 hval,bp;
-    DeclareTmpHeapNoproc(th,2);
-    UseTmpHeapNoproc(2);
 
     ASSERT(is_boxed(node));
     ptr = boxed_val(node);
@@ -2356,7 +2345,7 @@ erts_hashmap_get(Uint32 hx, Eterm key, Eterm node)
             break;
         }
 
-        hx = hashmap_shift_hash(th,hx,lvl,key);
+        hx = hashmap_shift_hash(hx,lvl,key);
 
         ASSERT(is_boxed(node));
         ptr = boxed_val(node);
@@ -2365,7 +2354,6 @@ erts_hashmap_get(Uint32 hx, Eterm key, Eterm node)
         ASSERT(!is_hashmap_header_head(hdr));
     }
 
-    UnUseTmpHeapNoproc(2);
     return res;
 }
 
@@ -2403,7 +2391,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 +2419,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 +2446,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 +2463,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);
@@ -2500,7 +2487,7 @@ 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);
+    chx   = hashmap_restore_hash(clvl,ckey);
     size += HAMT_NODE_BITMAP_SZ(2);
     ix    = hashmap_index(hx);
     cix   = hashmap_index(chx);
@@ -2508,8 +2495,8 @@ insert_subnodes:
     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);
+	hx    = hashmap_shift_hash(hx,lvl,key);
+	chx   = hashmap_shift_hash(chx,clvl,ckey);
 	ix    = hashmap_index(hx);
 	cix   = hashmap_index(chx);
     }
@@ -2719,8 +2706,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 +2726,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 +2749,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 +2766,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);
diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h
index 9f070ea33e..b451bad7e1 100644
--- a/erts/emulator/beam/erl_map.h
+++ b/erts/emulator/beam/erl_map.h
@@ -55,14 +55,18 @@ 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, 0)
+
+#define hashmap_restore_hash(Lvl, Key)                                        \
+    (((Lvl) < 8) ?                                                            \
+     hashmap_make_hash(Key) >> (4*(Lvl)) :                                    \
+     make_map_hash(Key, ((Lvl) >> 3)) >> (4 * ((Lvl) & 7)))
 
-#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)) & 7) ?                                                        \
+     (Hx) >> 4 :                                                              \
+     make_map_hash(Key, ((Lvl) >> 3)))
 
 /* erl_term.h stuff */
 #define flatmap_get_values(x)        (((Eterm *)(x)) + sizeof(flatmap_t)/sizeof(Eterm))
diff --git a/erts/emulator/beam/erl_utils.h b/erts/emulator/beam/erl_utils.h
index f87773ddca..070d6aef48 100644
--- a/erts/emulator/beam/erl_utils.h
+++ b/erts/emulator/beam/erl_utils.h
@@ -73,6 +73,7 @@ Uint32 make_hash2(Eterm);
 Uint32 trapping_make_hash2(Eterm, Eterm*, struct process*);
 Uint32 make_hash(Eterm);
 Uint32 make_internal_hash(Eterm, Uint32 salt);
+Uint32 make_map_hash(Eterm key, int level);
 
 void erts_save_emu_args(int argc, char **argv);
 Eterm erts_get_emu_args(struct process *c_p);
diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c
index 80d92c5602..bf8b91e374 100644
--- a/erts/emulator/beam/utils.c
+++ b/erts/emulator/beam/utils.c
@@ -2047,6 +2047,17 @@ trapping_make_hash2(Eterm term, Eterm* state_mref_write_back, Process* p)
     return make_hash2_helper(term, 1, state_mref_write_back, p);
 }
 
+/* Term hash function for maps, with a separate depth parameter */
+Uint32 make_map_hash(Eterm key, int depth) {
+    Uint32 hash = 0;
+
+    if (depth > 0) {
+        UINT32_HASH_2(depth, 1, HCONST_22);
+    }
+
+    return make_internal_hash(key, hash);
+}
+
 /* Term hash function for internal use.
  *
  * Limitation #1: Is not "portable" in any way between different VM instances.