aboutsummaryrefslogtreecommitdiffstats
path: root/erts
diff options
context:
space:
mode:
authorBjörn-Egil Dahlberg <[email protected]>2015-03-03 09:35:10 +0100
committerBjörn-Egil Dahlberg <[email protected]>2015-03-12 19:15:30 +0100
commiteb6f1d4923899fcb29a5d3c312f14489e7846a37 (patch)
tree9f9c18d9f3ba7fb7c3596044bd0ce9bb7ef63b58 /erts
parentf316f5f718a9e60ed8dc394a6a0a1cb15147dd2a (diff)
downloadotp-eb6f1d4923899fcb29a5d3c312f14489e7846a37.tar.gz
otp-eb6f1d4923899fcb29a5d3c312f14489e7846a37.tar.bz2
otp-eb6f1d4923899fcb29a5d3c312f14489e7846a37.zip
erts: Ensure maps becomes hashmaps in maps:merge/2
Maps should become hashmaps when merged size exceeds small limit size.
Diffstat (limited to 'erts')
-rw-r--r--erts/emulator/beam/erl_map.c49
1 files changed, 42 insertions, 7 deletions
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index 4ad33f98a7..1703f86b0e 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -830,12 +830,14 @@ BIF_RETTYPE maps_merge_2(BIF_ALIST_2) {
if (is_map(BIF_ARG_2)) {
BIF_RET(map_merge(BIF_P, BIF_ARG_1, BIF_ARG_2));
} else if (is_hashmap(BIF_ARG_2)) {
+ /* Will always become a tree */
BIF_RET(map_merge_mixed(BIF_P, BIF_ARG_1, BIF_ARG_2, 0));
}
} else if (is_hashmap(BIF_ARG_1)) {
if (is_hashmap(BIF_ARG_2)) {
BIF_RET(hashmap_merge(BIF_P, BIF_ARG_1, BIF_ARG_2));
} else if (is_map(BIF_ARG_2)) {
+ /* Will always become a tree */
BIF_RET(map_merge_mixed(BIF_P, BIF_ARG_2, BIF_ARG_1, 1));
}
}
@@ -847,7 +849,7 @@ static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB) {
Eterm tup;
Eterm *ks,*vs,*ks1,*vs1,*ks2,*vs2;
map_t *mp1,*mp2,*mp_new;
- Uint n1,n2,i1,i2,need,unused_size=0;
+ Uint n,n1,n2,i1,i2,need,unused_size=0;
int c = 0;
mp1 = (map_t*)map_val(nodeA);
@@ -876,13 +878,13 @@ static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB) {
while(i1 < n1 && i2 < n2) {
c = CMP_TERM(ks1[i1],ks2[i2]);
- if ( c == 0) {
+ if (c == 0) {
/* use righthand side arguments map value,
* but advance both maps */
*ks++ = ks2[i2];
*vs++ = vs2[i2];
i1++, i2++, unused_size++;
- } else if ( c < 0) {
+ } else if (c < 0) {
*ks++ = ks1[i1];
*vs++ = vs1[i1];
i1++;
@@ -917,8 +919,42 @@ static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB) {
HRelease(p, vs + unused_size, vs);
}
- mp_new->size = n1 + n2 - unused_size;
- *thp = make_arityval(n1 + n2 - unused_size);
+ n = n1 + n2 - unused_size;
+ *thp = make_arityval(n);
+
+ /* Reshape map to a hashmap if the map exceeds the limit */
+
+ if (n > MAP_SMALL_MAP_LIMIT) {
+ Uint32 hx,sw;
+ Uint i;
+ Eterm res;
+ hxnode_t *hxns;
+
+ ks = map_get_keys(mp_new);
+ vs = map_get_values(mp_new);
+
+ hp = HAlloc(p, 2 * n);
+
+ hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP,n * sizeof(hxnode_t));
+
+ for (i = 0; i < n; i++) {
+ hx = hashmap_make_hash(ks[i]);
+ swizzle32(sw,hx);
+ hxns[i].hx = sw;
+ hxns[i].val = CONS(hp, ks[i], vs[i]); hp += 2;
+ hxns[i].skip = 1;
+ hxns[i].i = i;
+ }
+
+ res = hashmap_from_unsorted_array(p, hxns, n);
+
+ erts_free(ERTS_ALC_T_TMP, (void *) hxns);
+ ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
+
+ return res;
+ }
+
+ mp_new->size = n;
return make_map(mp_new);
}
@@ -929,7 +965,6 @@ static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args)
Uint n, i;
hxnode_t *hxns;
Uint32 sw, hx;
- Eterm tmp[2];
/* convert flat to tree */
@@ -947,7 +982,7 @@ static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args)
hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, n * sizeof(hxnode_t));
for (i = 0; i < n; i++) {
- hx = hashmap_restore_hash(tmp,0,ks[i]);
+ hx = hashmap_make_hash(ks[i]);
swizzle32(sw,hx);
hxns[i].hx = sw;
hxns[i].val = CONS(hp, ks[i], vs[i]); hp += 2;