Merge PR-4656 from josevalim/jv-large-map-opt OTP-17310

Do not allocate large map when value is the same

3 files changed, 33 insertions, 18 deletions

diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index 9b1762e299..4f9d9ce287 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -2370,39 +2370,53 @@ Eterm erts_hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value,
     Uint size, upsz;
     Eterm *hp, res = THE_NON_VALUE;
     DECLARE_ESTACK(stack);
-    if (erts_hashmap_insert_down(hx, key, map, &size, &upsz, &stack, is_update)) {
-	hp  = HAlloc(p, size);
-	res = erts_hashmap_insert_up(hp, key, value, &upsz, &stack);
+    if (erts_hashmap_insert_down(hx, key, value, map, &size, &upsz, &stack,
+                                 is_update)) {
+        if (size) {
+            /* 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);
+	}
+        else {
+            /* We are putting the same key-value */
+            res = map;
+        }
+    }
+    else {
+        /* We are updating and the key does not exist */
+        ASSERT(is_update);
     }
-    DESTROY_ESTACK(stack);
 
+    DESTROY_ESTACK(stack);
     return res;
 }
 
 
-int erts_hashmap_insert_down(Uint32 hx, Eterm key, Eterm node, Uint *sz,
+int erts_hashmap_insert_down(Uint32 hx, Eterm key, Eterm value, Eterm node, Uint *sz,
 			     Uint *update_size, ErtsEStack *sp, int is_update) {
     Eterm *ptr;
     Eterm hdr, ckey;
     Uint32 ix, cix, bp, hval, chx;
     Uint slot, lvl = 0, clvl;
     Uint size = 0, n = 0;
-    DeclareTmpHeapNoproc(th,2);
+    Eterm th[2];
 
     *update_size = 1;
 
-    UseTmpHeapNoproc(2);
     for (;;) {
 	switch(primary_tag(node)) {
 	    case TAG_PRIMARY_LIST: /* LEAF NODE [K|V] */
 		ptr  = list_val(node);
 		ckey = CAR(ptr);
 		if (EQ(ckey, key)) {
+		    if (CDR(ptr) == value) {
+                        *sz = 0; /* same value, same map, no heap needed */
+                        return 1;
+                    }
 		    *update_size = 0;
 		    goto unroll;
 		}
 		if (is_update) {
-                    UnUseTmpHeapNoproc(2);
 		    return 0;
 		}
 		goto insert_subnodes;
@@ -2435,7 +2449,6 @@ int erts_hashmap_insert_down(Uint32 hx, Eterm key, Eterm node, Uint *sz,
 
                         if (!(bp & hval)) { /* not occupied */
                             if (is_update) {
-				UnUseTmpHeapNoproc(2);
                                 return 0;
                             }
                             size += HAMT_NODE_BITMAP_SZ(n+1);
@@ -2467,7 +2480,6 @@ int erts_hashmap_insert_down(Uint32 hx, Eterm key, Eterm node, Uint *sz,
 			}
 			/* not occupied */
 			if (is_update) {
-                            UnUseTmpHeapNoproc(2);
 			    return 0;
 			}
 			size += HAMT_HEAD_BITMAP_SZ(n+1);
@@ -2501,12 +2513,11 @@ insert_subnodes:
 
 unroll:
     *sz = size + /* res cons */ 2;
-    UnUseTmpHeapNoproc(2);
     return 1;
 }
 
 Eterm erts_hashmap_insert_up(Eterm *hp, Eterm key, Eterm value,
-			     Uint *update_size, ErtsEStack *sp) {
+			     Uint update_size, ErtsEStack *sp) {
     Eterm node, *ptr, hdr;
     Eterm res;
     Eterm *nhp = NULL;
@@ -2551,7 +2562,7 @@ Eterm erts_hashmap_insert_up(Eterm *hp, Eterm key, Eterm value,
 			nhp   = hp;
 			n     = HAMT_HEAD_ARRAY_SZ - 2;
 			*hp++ = MAP_HEADER_HAMT_HEAD_ARRAY; ptr++;
-			*hp++ = (*ptr++) + *update_size;
+			*hp++ = (*ptr++) + update_size;
 			while(n--) { *hp++ = *ptr++; }
 			nhp[slot+2] = res;
 			res = make_hashmap(nhp);
@@ -2579,7 +2590,7 @@ Eterm erts_hashmap_insert_up(Eterm *hp, Eterm key, Eterm value,
 			hval  = MAP_HEADER_VAL(hdr);
 			nhp   = hp;
 			*hp++ = MAP_HEADER_HAMT_HEAD_BITMAP(hval | bp); ptr++;
-			*hp++ = (*ptr++) + *update_size;
+			*hp++ = (*ptr++) + update_size;
 
 			n -= slot;
 			while(slot--) { *hp++ = *ptr++; }
diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h
index 718d400e22..980cf246c4 100644
--- a/erts/emulator/beam/erl_map.h
+++ b/erts/emulator/beam/erl_map.h
@@ -85,10 +85,10 @@ int    erts_maps_take(Process *p, Eterm key, Eterm map, Eterm *res, Eterm *value
 
 Eterm  erts_hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value,
 			   Eterm node, int is_update);
-int    erts_hashmap_insert_down(Uint32 hx, Eterm key, Eterm node, Uint *sz,
+int    erts_hashmap_insert_down(Uint32 hx, Eterm key, Eterm value, Eterm node, Uint *sz,
 			        Uint *upsz, struct ErtsEStack_ *sp, int is_update);
 Eterm  erts_hashmap_insert_up(Eterm *hp, Eterm key, Eterm value,
-			      Uint *upsz, struct ErtsEStack_ *sp);
+			      Uint upsz, struct ErtsEStack_ *sp);
 
 int    erts_validate_and_sort_flatmap(flatmap_t* map);
 void   hashmap_iterator_init(struct ErtsWStack_* s, Eterm node, int reverse);
diff --git a/lib/stdlib/test/maps_SUITE.erl b/lib/stdlib/test/maps_SUITE.erl
index 4159ea6c3b..4860e39b70 100644
--- a/lib/stdlib/test/maps_SUITE.erl
+++ b/lib/stdlib/test/maps_SUITE.erl
@@ -495,8 +495,12 @@ iter_kv(I) ->
 
 t_put_opt(Config) when is_list(Config) ->
     Value = id(#{complex => map}),
-    Map = id(#{a => Value}),
-    true = erts_debug:same(maps:put(a, Value, Map), Map),
+    Small = id(#{a => Value}),
+    true = erts_debug:same(maps:put(a, Value, Small), Small),
+
+    LargeBase = maps:from_list([{I,I}||I<-lists:seq(1,200)]),
+    Large = LargeBase#{a => Value},
+    true = erts_debug:same(maps:put(a, Value, Large), Large),
     ok.
 
 t_merge_opt(Config) when is_list(Config) ->