Do not allocate a new map when the value is the same

This patch optimizes map operations to not allocate new maps
when the key is being replaced by the exact same value in memory.

Imagine this very common idiom:

    Map#{key := compute_new_value(Value, Condition)}

where:

    compute_new_x(X, true) -> X + 1;
    compute_new_x(X, false) -> X;

In many cases, we are not changing the value in `Key`, however
the code prior to this patch would still allocate a new array
for the map values. This optimization changes this.

The cost of optimization is minimum, as in the worst case scenario
it only adds a pointer comparison and boolean check. The major benefit
is reducing the GC pressure by avoiding allocating data.

Next we list the operations we have changed alongside the benchmark
results. The benchmarks basically create a map and perform the same
operations, roughly 20000 times, once replacing the key with the same
value, and another with a different value.

* Map#{Key := Value}

For a map with 4 keys, replacing the fourth key 20000 times went from
718us to 539us.

For a map with 8 keys, replacing the fourth key 20000 times went from
976us to 555us.

* maps:update/3

For a map with 4 keys, replacing the fourth key 20000 times went from
673us to 575us.

For a map with 8 keys, replacing the fourth key 20000 times went from
827us to 585us.

* maps:put/3

For a map with 4 keys, replacing the fourth key 20000 times went from
763us to 553us.

For a map with 8 keys, replacing the fourth key 20000 times went from
788us to 561us.

Note that we have ported some optimizations found in maps:update/3
to maps:put/3 while creating this patch.

2 files changed, 46 insertions, 27 deletions

diff --git a/erts/emulator/beam/beam_emu.c b/erts/emulator/beam/beam_emu.c
index ab5920a67e..aa61a2d7f9 100644
--- a/erts/emulator/beam/beam_emu.c
+++ b/erts/emulator/beam/beam_emu.c
@@ -3061,12 +3061,14 @@ erts_gc_update_map_exact(Process* p, Eterm* reg, Uint live, Uint n, Eterm* new_p
     Uint need;
     flatmap_t *old_mp, *mp;
     Eterm res;
+    Eterm* old_hp;
     Eterm* hp;
     Eterm* E;
     Eterm* old_keys;
     Eterm* old_vals;
     Eterm new_key;
     Eterm map;
+    int changed = 0;
 
     n /= 2;		/* Number of values to be updated */
     ASSERT(n > 0);
@@ -3133,6 +3135,7 @@ erts_gc_update_map_exact(Process* p, Eterm* reg, Uint live, Uint n, Eterm* new_p
      * Update map, keeping the old key tuple.
      */
 
+    old_hp = p->htop;
     hp = p->htop;
     E = p->stop;
 
@@ -3155,20 +3158,26 @@ erts_gc_update_map_exact(Process* p, Eterm* reg, Uint live, Uint n, Eterm* new_p
 	    /* Not same keys */
 	    *hp++ = *old_vals;
 	} else {
-	    GET_TERM(new_p[1], *hp);
-	    hp++;
-	    n--;
+            GET_TERM(new_p[1], *hp);
+            if(*hp != *old_vals) changed = 1;
+            hp++;
+            n--;
 	    if (n == 0) {
-		/*
-		 * All updates done. Copy remaining values
-		 * and return the result.
-		 */
-		for (i++, old_vals++; i < num_old; i++) {
-		    *hp++ = *old_vals++;
-		}
-		ASSERT(hp == p->htop + need);
-		p->htop = hp;
-		return res;
+                /*
+                * All updates done. Copy remaining values
+                * if any changed or return the original one.
+                */
+                if(changed) {
+		    for (i++, old_vals++; i < num_old; i++) {
+		        *hp++ = *old_vals++;
+		    }
+		    ASSERT(hp == p->htop + need);
+		    p->htop = hp;
+		    return res;
+                } else {
+                    p->htop = old_hp;
+                    return map;
+                }
 	    } else {
 		new_p += 2;
 		GET_TERM(*new_p, new_key);
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index 4a1fe4470e..3d6c9eb43f 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -1688,11 +1688,16 @@ int erts_maps_update(Process *p, Eterm key, Eterm value, Eterm map, Eterm *res)
 	return 0;
 
 found_key:
-	*hp++ = value;
-	vs++;
-	if (++i < n)
-	    sys_memcpy(hp, vs, (n - i)*sizeof(Eterm));
-	*res = make_flatmap(shp);
+        if(*vs == value) {
+            HRelease(p, shp + MAP_HEADER_FLATMAP_SZ + n, shp);
+            *res = map;
+        } else {
+	    *hp++ = value;
+	    vs++;
+	    if (++i < n)
+	       sys_memcpy(hp, vs, (n - i)*sizeof(Eterm));
+	    *res = make_flatmap(shp);
+        }
 	return 1;
     }
 
@@ -1748,9 +1753,7 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) {
 	if (is_immed(key)) {
 	    for( i = 0; i < n; i ++) {
 		if (ks[i] == key) {
-		    *hp++ = value;
-		    vs++;
-		    c = 1;
+                    goto found_key;
 		} else {
 		    *hp++ = *vs++;
 		}
@@ -1758,18 +1761,13 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) {
 	} else {
 	    for( i = 0; i < n; i ++) {
 		if (EQ(ks[i], key)) {
-		    *hp++ = value;
-		    vs++;
-		    c = 1;
+		    goto found_key;
 		} else {
 		    *hp++ = *vs++;
 		}
 	    }
 	}
 
-	if (c)
-	    return res;
-
 	/* the map will grow */
 
 	if (n >= MAP_SMALL_MAP_LIMIT) {
@@ -1824,6 +1822,18 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) {
 	 */
 	*shp = make_pos_bignum_header(0);
 	return res;
+
+found_key:
+        if(*vs == value) {
+            HRelease(p, shp + MAP_HEADER_FLATMAP_SZ + n, shp);
+            return map;
+        } else {
+            *hp++ = value;
+            vs++;
+            if (++i < n)
+               sys_memcpy(hp, vs, (n - i)*sizeof(Eterm));
+            return res;
+        }
     }
     ASSERT(is_hashmap(map));