summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--erts/emulator/beam/erl_map.c65
-rw-r--r--erts/emulator/test/map_SUITE.erl41
-rw-r--r--system/doc/efficiency_guide/maps.xml15
3 files changed, 90 insertions, 31 deletions
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index 7009a7f105..e7452f4e8c 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -1334,34 +1334,31 @@ BIF_RETTYPE maps_merge_2(BIF_ALIST_2) {
BIF_ERROR(BIF_P, BADMAP);
}
-static Eterm flatmap_merge(Process *p, Eterm nodeA, Eterm nodeB) {
+static Eterm flatmap_merge(Process *p, Eterm map1, Eterm map2) {
Eterm *hp,*thp;
- Eterm tup;
Eterm *ks,*vs,*ks1,*vs1,*ks2,*vs2;
flatmap_t *mp1,*mp2,*mp_new;
Uint n,n1,n2,i1,i2,need,unused_size=0;
Sint c = 0;
- mp1 = (flatmap_t*)flatmap_val(nodeA);
- mp2 = (flatmap_t*)flatmap_val(nodeB);
+ mp1 = (flatmap_t*)flatmap_val(map1);
+ mp2 = (flatmap_t*)flatmap_val(map2);
n1 = flatmap_get_size(mp1);
n2 = flatmap_get_size(mp2);
- if (n1 == 0) return nodeB;
- if (n2 == 0) return nodeA;
+ if (n1 == 0) return map2;
+ if (n2 == 0) return map1;
need = MAP_HEADER_FLATMAP_SZ + 1 + 2 * (n1 + n2);
hp = HAlloc(p, need);
- thp = hp;
- tup = make_tuple(thp);
- ks = hp + 1; hp += 1 + n1 + n2;
mp_new = (flatmap_t*)hp; hp += MAP_HEADER_FLATMAP_SZ;
vs = hp; hp += n1 + n2;
+ thp = hp;
+ ks = hp + 1; hp += 1 + n1 + n2;
mp_new->thing_word = MAP_HEADER_FLATMAP;
- mp_new->size = 0;
- mp_new->keys = tup;
+ mp_new->keys = make_tuple(thp);
i1 = 0; i2 = 0;
ks1 = flatmap_get_keys(mp1);
@@ -1401,20 +1398,42 @@ static Eterm flatmap_merge(Process *p, Eterm nodeA, Eterm nodeB) {
i2++;
}
- if (unused_size) {
- /* the key tuple is embedded in the heap, write a bignum to clear it.
- *
- * release values as normal since they are on the top of the heap
- * size = n1 + n1 - unused_size
- */
-
- *ks = make_pos_bignum_header(unused_size - 1);
- HRelease(p, vs + unused_size, vs);
- }
-
n = n1 + n2 - unused_size;
- *thp = make_arityval(n);
mp_new->size = n;
+ *thp = make_arityval(n);
+
+ if (unused_size ) {
+ Eterm* hp_release;
+
+ if (n == n2) {
+ /* Reuse entire map2 */
+ if (n == n1
+ && erts_is_literal(mp1->keys, boxed_val(mp1->keys))
+ && !erts_is_literal(mp2->keys, boxed_val(mp2->keys))) {
+ /*
+ * We want map2, but map1 has a nice literal key tuple.
+ * Solution: MUTATE HEAP to get both.
+ */
+ ASSERT(eq(mp1->keys, mp2->keys));
+ mp2->keys = mp1->keys;
+ }
+ HRelease(p, hp, (Eterm *)mp_new);
+ return map2;
+ }
+ else if (n == n1) {
+ /* Reuse key tuple of map1 */
+ mp_new->keys = mp1->keys;
+ /* Release key tuple and unused values */
+ hp_release = thp - unused_size;
+ }
+ else {
+ /* Unused values are embedded in the heap, write bignum to clear them */
+ *vs = make_pos_bignum_header(unused_size - 1);
+ /* Release unused keys */
+ hp_release = ks;
+ }
+ HRelease(p, hp, hp_release);
+ }
/* Reshape map to a hashmap if the map exceeds the limit */
diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl
index e64311c2e5..030ad5ee13 100644
--- a/erts/emulator/test/map_SUITE.erl
+++ b/erts/emulator/test/map_SUITE.erl
@@ -2135,12 +2135,7 @@ t_bif_map_merge(Config) when is_list(Config) ->
M0 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>,
4 => number, 18446744073709551629 => wat},
-
- #{ "hi" := "hello", int := 3, <<"key">> := <<"value">>,
- 4 := number, 18446744073709551629 := wat} = maps:merge(#{}, M0),
-
- #{ "hi" := "hello", int := 3, <<"key">> := <<"value">>,
- 4 := number, 18446744073709551629 := wat} = maps:merge(M0, #{}),
+ merge_with_empty(M0),
M1 = #{ "hi" => "hello again", float => 3.3, {1,2} => "tuple", 4 => integer },
@@ -2155,6 +2150,7 @@ t_bif_map_merge(Config) when is_list(Config) ->
Is = lists:seq(1,N),
M2 = maps:from_list([{I,I}||I<-Is]),
150000 = maps:size(M2),
+ merge_with_empty(M2),
M3 = maps:from_list([{<<I:32>>,I}||I<-Is]),
150000 = maps:size(M3),
M4 = maps:merge(M2,M3),
@@ -2193,6 +2189,30 @@ t_bif_map_merge(Config) when is_list(Config) ->
M11 = maps:merge(M9,M10),
ok = check_keys_exist(Ks1 ++ Ks2, M11),
+ %% Verify map and/or key tuple reuse
+
+ MS = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>},
+ merge_with_empty(MS),
+ MS_keys = erts_internal:map_to_tuple_keys(MS),
+
+ %% key tuple reuse
+ MS_a = maps:merge(MS, #{int => 4}),
+ true = erts_debug:same(erts_internal:map_to_tuple_keys(MS_a), MS_keys),
+ %% map reuse
+ MS_b = maps:merge(#{int => 4}, MS),
+ true = erts_debug:same(MS_b, MS),
+
+ %% mutated map reuse with literal key tuple
+ MS_c = maps:put(int, 4, maps:remove(int, MS)),
+ false = erts_debug:same(erts_internal:map_to_tuple_keys(MS_c), MS_keys),
+ MS_cc = maps:merge(MS, MS_c),
+ true = erts_debug:same(MS_cc, MS_c),
+ %% not only do we reuse MS_c, it has mutated to use the literal keys of MS
+ true = erts_debug:same(erts_internal:map_to_tuple_keys(MS_c), MS_keys),
+
+ MS_d = maps:merge(MS_c, MS),
+ true = erts_debug:same(MS_d, MS),
+
%% error case
do_badmap(fun(T) ->
{'EXIT',{{badmap,T},[{maps,merge,_,_}|_]}} =
@@ -2204,6 +2224,15 @@ t_bif_map_merge(Config) when is_list(Config) ->
end),
ok.
+merge_with_empty(M0) ->
+ M0_1 = maps:merge(#{}, M0),
+ M0 = M0_1,
+ true = erts_debug:same(M0, M0_1),
+
+ M0_2 = maps:merge(M0, #{}),
+ M0 = M0_2,
+ true = erts_debug:same(M0, M0_2),
+ ok.
t_bif_map_put(Config) when is_list(Config) ->
M0 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>,
diff --git a/system/doc/efficiency_guide/maps.xml b/system/doc/efficiency_guide/maps.xml
index 1cbfa6786d..b5264d5a17 100644
--- a/system/doc/efficiency_guide/maps.xml
+++ b/system/doc/efficiency_guide/maps.xml
@@ -37,6 +37,7 @@
finally the functions in the <seeerl
marker="stdlib:maps">maps</seeerl> module.</p>
+ <marker id="terminology"/>
<p>Terminology used in this chapter:</p>
<list type="bulleted">
<item>A map with at most 32 elements will informally be called a
@@ -589,7 +590,17 @@ new() ->
<section>
<title>maps:merge/2</title>
<p><seemfa marker="stdlib:maps#merge/2">maps:merge/2</seemfa>
- is implemented in C.</p>
+ is implemented in C. For <seeguide marker="#terminology">small
+ maps</seeguide>, the key tuple may be shared with any of the argument
+ maps if that argument map contains all the keys. Literal key tuples are
+ prefered if possible.</p>
+ <change>
+ <p>
+ The sharing of key tuples by <c>maps:merge/2</c> was introduced in
+ OTP @OTP-18503@. Older versions always contructed a new key tuple on
+ the callers heap.
+ </p>
+ </change>
</section>
<section>
@@ -669,7 +680,7 @@ new() ->
<p>If the keys are constants known at compile-time, using the
map update syntax with the <c>:=</c> operator is more
efficient than multiple calls to <c>maps:update/3</c>,
- especially for small maps.</p>
+ especially for <seeguide marker="#terminology">small maps</seeguide>.</p>
</section>
<section>
View Lorry Controller Status