aboutsummaryrefslogtreecommitdiffstats
path: root/erts
diff options
context:
space:
mode:
authorJose Valim & Michal Muskala <[email protected]>2018-07-25 17:33:30 +0200
committerJosé Valim <[email protected]>2018-07-25 17:39:44 +0200
commit6007bf0f822014e0bbd0cef675848d18ae99b69e (patch)
tree0faaf057a69927bce5974658f1c6e1a56dc923f8 /erts
parentfc12f6935028bf03a46892fc833aaa117d2cbc9e (diff)
downloadotp-6007bf0f822014e0bbd0cef675848d18ae99b69e.tar.gz
otp-6007bf0f822014e0bbd0cef675848d18ae99b69e.tar.bz2
otp-6007bf0f822014e0bbd0cef675848d18ae99b69e.zip
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.
Diffstat (limited to 'erts')
-rw-r--r--erts/emulator/beam/beam_emu.c35
-rw-r--r--erts/emulator/beam/erl_map.c38
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));