From 17bb6bfa8d435300ee2205f1e0c20b0c6b50591a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 15 Aug 2017 13:34:45 +0200 Subject: Slightly optimize updating of maps The instruction put_map_assoc/5 (used for updating a map) has a failure operand, but it can't actually fail provided that its "map" argument is a map. The following code: M#{key=>value}. will be compiled to: {test,is_map,{f,3},[{x,0}]}. {line,[...]}. {put_map_assoc,{f,0},{x,0},{x,0},1,{list,[{atom,key},{atom,value}]}}. return. {label,3}. %% Code that produces a 'badmap' exception follows. Because of the is_map instruction, {x,0} always contains a map when the put_map_assoc instruction is executed. Therefore we can remove the failure operand. That will save one word, and also eliminate two tests at run-time. The only problem is that the compiler in OTP 17 did not emit a is_map instruction before the put_map_assoc instruction. Therefore, we must add an instruction that tests for a map if the code was compiled with the OTP 17 compiler. Unfortunately, there is no safe and relatively easy way to known that the OTP 17 compiler was used, so we will check whether a compiler before OTP 20 was used. OTP 20 introduced a new chunk type for atoms, which is trivial to check. --- erts/emulator/beam/beam_debug.c | 2 +- erts/emulator/beam/beam_emu.c | 15 +++---- erts/emulator/beam/beam_load.c | 14 +++++++ erts/emulator/beam/macros.tab | 5 +++ erts/emulator/beam/map_instrs.tab | 27 +++++-------- erts/emulator/beam/ops.tab | 49 ++++++++++++++++++----- erts/emulator/test/map_SUITE_data/badmap_17.beam | Bin 592 -> 1192 bytes erts/emulator/test/map_SUITE_data/badmap_17.erl | 36 ++++++++++++++++- 8 files changed, 109 insertions(+), 39 deletions(-) diff --git a/erts/emulator/beam/beam_debug.c b/erts/emulator/beam/beam_debug.c index fa912e52e9..afe87288ce 100644 --- a/erts/emulator/beam/beam_debug.c +++ b/erts/emulator/beam/beam_debug.c @@ -697,7 +697,7 @@ print_op(fmtfn_t to, void *to_arg, int op, int size, BeamInstr* addr) case op_i_put_tuple_xI: case op_i_put_tuple_yI: case op_new_map_dII: - case op_update_map_assoc_jsdII: + case op_update_map_assoc_sdII: case op_update_map_exact_jsdII: { int n = unpacked[-1]; diff --git a/erts/emulator/beam/beam_emu.c b/erts/emulator/beam/beam_emu.c index ff3c725bbc..e5935f5f02 100644 --- a/erts/emulator/beam/beam_emu.c +++ b/erts/emulator/beam/beam_emu.c @@ -2849,19 +2849,14 @@ update_map_assoc(Process* p, Eterm* reg, Eterm map, BeamInstr* I) Eterm new_key; Eterm* kp; - new_p = &Arg(5); - num_updates = Arg(4) / 2; + new_p = &Arg(4); + num_updates = Arg(3) / 2; if (is_not_flatmap(map)) { Uint32 hx; Eterm val; - /* apparently the compiler does not emit is_map instructions, - * bad compiler */ - - if (is_not_hashmap(map)) - return THE_NON_VALUE; - + ASSERT(is_hashmap(map)); res = map; E = p->stop; while(num_updates--) { @@ -2885,7 +2880,7 @@ update_map_assoc(Process* p, Eterm* reg, Eterm map, BeamInstr* I) */ if (num_old == 0) { - return new_map(p, reg, I+1); + return new_map(p, reg, I); } /* @@ -2895,7 +2890,7 @@ update_map_assoc(Process* p, Eterm* reg, Eterm map, BeamInstr* I) need = 2*(num_old+num_updates) + 1 + MAP_HEADER_FLATMAP_SZ; if (HeapWordsLeft(p) < need) { - Uint live = Arg(3); + Uint live = Arg(2); reg[live] = map; erts_garbage_collect(p, need, reg, live+1); map = reg[live]; diff --git a/erts/emulator/beam/beam_load.c b/erts/emulator/beam/beam_load.c index d38e71f489..dcd312f54f 100644 --- a/erts/emulator/beam/beam_load.c +++ b/erts/emulator/beam/beam_load.c @@ -306,6 +306,7 @@ typedef struct LoaderState { int on_load; /* Index in the code for the on_load function * (or 0 if there is no on_load function) */ + int otp_20_or_higher; /* Compiled with OTP 20 or higher */ /* * Atom table. @@ -739,6 +740,13 @@ erts_prepare_loading(Binary* magic, Process *c_p, Eterm group_leader, } } + /* + * Find out whether the code was compiled with OTP 20 + * or higher. + */ + + stp->otp_20_or_higher = stp->chunks[UTF8_ATOM_CHUNK].size > 0; + /* * Load the code chunk. */ @@ -2731,6 +2739,12 @@ load_code(LoaderState* stp) #define never(St) 0 +static int +compiled_with_otp_20_or_higher(LoaderState* stp) +{ + return stp->otp_20_or_higher; +} + /* * Predicate that tests whether a jump table can be used. */ diff --git a/erts/emulator/beam/macros.tab b/erts/emulator/beam/macros.tab index 57015fac31..41dc761e90 100644 --- a/erts/emulator/beam/macros.tab +++ b/erts/emulator/beam/macros.tab @@ -92,6 +92,11 @@ NEXT(Addr) { Goto(*I); } +FAIL_BODY() { + //| -no_prefetch + goto find_func_info; +} + FAIL_HEAD_OR_BODY(Fail) { //| -no_prefetch if ($Fail) { diff --git a/erts/emulator/beam/map_instrs.tab b/erts/emulator/beam/map_instrs.tab index 7f9346d029..30c3d7743f 100644 --- a/erts/emulator/beam/map_instrs.tab +++ b/erts/emulator/beam/map_instrs.tab @@ -19,10 +19,12 @@ // %CopyrightEnd% // -BADMAP(Fail, Map) { - c_p->freason = BADMAP; - c_p->fvalue = $Map; - $FAIL_HEAD_OR_BODY($Fail); +ensure_map(Map) { + if (is_not_map($Map)) { + c_p->freason = BADMAP; + c_p->fvalue = $Map; + $FAIL_BODY(); + } } new_map(Dst, Live, N) { @@ -123,7 +125,7 @@ i_get_map_elements(Fail, Src, N) { } } -update_map_assoc(Fail, Src, Dst, Live, N) { +update_map_assoc(Src, Dst, Live, N) { Eterm res; Eterm map; @@ -131,17 +133,10 @@ update_map_assoc(Fail, Src, Dst, Live, N) { HEAVY_SWAPOUT; res = update_map_assoc(c_p, reg, map, I); HEAVY_SWAPIN; - if (is_value(res)) { - $REFRESH_GEN_DEST(); - $Dst = res; - $NEXT($NEXT_INSTRUCTION+$N); - } else { - /* - * This can only happen if the code was compiled - * with the compiler in OTP 17. - */ - $BADMAP($Fail, map); - } + ASSERT(is_value(res)); + $REFRESH_GEN_DEST(); + $Dst = res; + $NEXT($NEXT_INSTRUCTION+$N); } update_map_exact(Fail, Src, Dst, Live, N) { diff --git a/erts/emulator/beam/ops.tab b/erts/emulator/beam/ops.tab index fdc4506351..92e67bb470 100644 --- a/erts/emulator/beam/ops.tab +++ b/erts/emulator/beam/ops.tab @@ -1299,23 +1299,52 @@ apply I apply_last I P # -# Map instructions in R17. +# Handle compatibility with OTP 17 here. # -sorted_put_map_assoc/5 -put_map_assoc F Map Dst Live Size Rest=* | map_key_sort(Size, Rest) => \ - sorted_put_map_assoc F Map Dst Live Size Rest +i_put_map_assoc/4 + +# We KNOW that in OTP 20 (actually OTP 18 and higher), a put_map_assoc instruction +# is always preceded by an is_map test. That means that put_map_assoc can never +# fail and does not need any failure label. + +put_map_assoc Fail Map Dst Live Size Rest=* | compiled_with_otp_20_or_higher() => \ + i_put_map_assoc Map Dst Live Size Rest + +# Translate the put_map_assoc instruction if the module was compiled by a compiler +# before 20. This is only necessary if the OTP 17 compiler was used, but we +# have no safe and relatively easy way to know whether OTP 18/19 was used. + +put_map_assoc Fail=p Map Dst Live Size Rest=* => \ + ensure_map Map | i_put_map_assoc Map Dst Live Size Rest +put_map_assoc Fail=f Map Dst Live Size Rest=* => \ + is_map Fail Map | i_put_map_assoc Map Dst Live Size Rest + +ensure_map Lit=q | literal_is_map(Lit) => +ensure_map Src=cqy => move Src x | ensure_map x + +%cold +ensure_map x +%hot + +# +# Map instructions. First introduced in R17. +# + +sorted_put_map_assoc/4 +i_put_map_assoc Map Dst Live Size Rest=* | map_key_sort(Size, Rest) => \ + sorted_put_map_assoc Map Dst Live Size Rest sorted_put_map_exact/5 put_map_exact F Map Dst Live Size Rest=* | map_key_sort(Size, Rest) => \ sorted_put_map_exact F Map Dst Live Size Rest -sorted_put_map_assoc j Map Dst Live Size Rest=* | is_empty_map(Map) => \ +sorted_put_map_assoc Map Dst Live Size Rest=* | is_empty_map(Map) => \ new_map Dst Live Size Rest -sorted_put_map_assoc F Src=s Dst Live Size Rest=* => \ - update_map_assoc F Src Dst Live Size Rest -sorted_put_map_assoc F Src Dst Live Size Rest=* => \ - move Src x | update_map_assoc F x Dst Live Size Rest +sorted_put_map_assoc Src=s Dst Live Size Rest=* => \ + update_map_assoc Src Dst Live Size Rest +sorted_put_map_assoc Src Dst Live Size Rest=* => \ + move Src x | update_map_assoc x Dst Live Size Rest sorted_put_map_exact F Src=s Dst Live Size Rest=* => \ update_map_exact F Src Dst Live Size Rest @@ -1327,7 +1356,7 @@ new_map Dst Live Size Rest=* | is_small_map_literal_keys(Size, Rest) => \ new_map d I I i_new_small_map_lit d I q -update_map_assoc j s d I I +update_map_assoc s d I I update_map_exact j s d I I is_map Fail Lit=q | literal_is_map(Lit) => diff --git a/erts/emulator/test/map_SUITE_data/badmap_17.beam b/erts/emulator/test/map_SUITE_data/badmap_17.beam index 277fc34b94..6f79bb8c2c 100644 Binary files a/erts/emulator/test/map_SUITE_data/badmap_17.beam and b/erts/emulator/test/map_SUITE_data/badmap_17.beam differ diff --git a/erts/emulator/test/map_SUITE_data/badmap_17.erl b/erts/emulator/test/map_SUITE_data/badmap_17.erl index 0ec65e0e33..887fc2e5e3 100644 --- a/erts/emulator/test/map_SUITE_data/badmap_17.erl +++ b/erts/emulator/test/map_SUITE_data/badmap_17.erl @@ -1,7 +1,7 @@ -module(badmap_17). -export([update/1]). -%% Compile this source file with OTP 17. +%% Compile this source file with OTP 17.0. update(Map) -> try @@ -17,10 +17,42 @@ update(Map) -> catch error:{badmap,Map} -> ok - end. + end, + try + update_3(Map), + error(update_did_not_fail) + catch + error:{badmap,Map} -> + ok + end, + ok = update_4(Map), + ok = update_5(Map), + ok. update_1(M) -> M#{a=>42}. update_2(M) -> M#{a:=42}. + +update_3(M) -> + id(M), + M#{a=>42}. + +update_4(M) when M#{a=>b} =:= M -> + did_not_fail; +update_4(_) -> + ok. + +update_5(M) -> + id(M), + case id(true) of + true when M#{a=>b} =:= M -> + did_not_fail; + true -> + ok + end. + +id(I) -> + I. + -- cgit v1.2.3