From 245aa4ed9b41aa601784598b0b3286d29b6d0085 Mon Sep 17 00:00:00 2001 From: Michal Muskala Date: Sat, 1 Jul 2017 17:19:52 +0200 Subject: Introduce new_small_map_lit op Take advantage of the fact that small maps have a tuple for keys. When new map is constructed and all keys are literals, we can construct the entire keys tuple as a literal. This should reduce the memory of maps created with literal keys almost by half, since they all can share the same keys tuple. --- erts/emulator/beam/beam_debug.c | 21 ++++++++ erts/emulator/beam/beam_emu.c | 50 +++++++++++++++++++ erts/emulator/beam/beam_load.c | 105 ++++++++++++++++++++++++++++++++++++++++ erts/emulator/beam/ops.tab | 4 ++ 4 files changed, 180 insertions(+) (limited to 'erts/emulator/beam') diff --git a/erts/emulator/beam/beam_debug.c b/erts/emulator/beam/beam_debug.c index a2060c80de..74e6ab8bc5 100644 --- a/erts/emulator/beam/beam_debug.c +++ b/erts/emulator/beam/beam_debug.c @@ -718,6 +718,27 @@ print_op(fmtfn_t to, void *to_arg, int op, int size, BeamInstr* addr) } } break; + case op_i_new_small_map_lit_dIq: + { + Eterm *tp = tuple_val(unpacked[-1]); + int n = arityval(*tp); + + while (n > 0) { + switch (loader_tag(ap[0])) { + case LOADER_X_REG: + erts_print(to, to_arg, " x(%d)", loader_x_reg_index(ap[0])); + break; + case LOADER_Y_REG: + erts_print(to, to_arg, " x(%d)", loader_y_reg_index(ap[0])); + break; + default: + erts_print(to, to_arg, " %T", (Eterm) ap[0]); + break; + } + ap++, size++, n--; + } + } + break; case op_i_get_map_elements_fsI: { int n = unpacked[-1]; diff --git a/erts/emulator/beam/beam_emu.c b/erts/emulator/beam/beam_emu.c index 27d19d2504..039ce3fa24 100644 --- a/erts/emulator/beam/beam_emu.c +++ b/erts/emulator/beam/beam_emu.c @@ -1080,6 +1080,7 @@ static BeamInstr* apply_fun(Process* p, Eterm fun, static Eterm new_fun(Process* p, Eterm* reg, ErlFunEntry* fe, int num_free) NOINLINE; static Eterm new_map(Process* p, Eterm* reg, BeamInstr* I) NOINLINE; +static Eterm new_small_map_lit(Process* p, Eterm* reg, Uint* n_exp, BeamInstr* I) NOINLINE; static Eterm update_map_assoc(Process* p, Eterm* reg, Eterm map, BeamInstr* I) NOINLINE; static Eterm update_map_exact(Process* p, Eterm* reg, @@ -2461,6 +2462,17 @@ void process_main(Eterm * x_reg_array, FloatDef* f_reg_array) Next(3+Arg(2)); } + OpCase(i_new_small_map_lit_dIq): { + Eterm res; + Uint n; + + HEAVY_SWAPOUT; + res = new_small_map_lit(c_p, reg, &n, I-1); + HEAVY_SWAPIN; + StoreResult(res, Arg(0)); + Next(3+n); + } + #define PUT_TERM_REG(term, desc) \ do { \ switch (loader_tag(desc)) { \ @@ -7034,6 +7046,44 @@ new_map(Process* p, Eterm* reg, BeamInstr* I) return make_flatmap(mp); } +static Eterm +new_small_map_lit(Process* p, Eterm* reg, Uint* n_exp, BeamInstr* I) +{ + Eterm* keys = tuple_val(Arg(3)); + Uint n = arityval(*keys); + Uint need = n + 1 /* hdr */ + 1 /*size*/ + 1 /* ptr */ + 1 /* arity */; + Uint i; + BeamInstr *ptr; + flatmap_t *mp; + Eterm *mhp; + Eterm *E; + + *n_exp = n; + ptr = &Arg(4); + + ASSERT(n <= MAP_SMALL_MAP_LIMIT); + + if (HeapWordsLeft(p) < need) { + erts_garbage_collect(p, need, reg, Arg(2)); + } + + mhp = p->htop; + E = p->stop; + + mp = (flatmap_t *)mhp; mhp += MAP_HEADER_FLATMAP_SZ; + mp->thing_word = MAP_HEADER_FLATMAP; + mp->size = n; + mp->keys = Arg(3); + + for (i = 0; i < n; i++) { + GET_TERM(*ptr++, *mhp++); + } + + p->htop = mhp; + + return make_flatmap(mp); +} + static Eterm update_map_assoc(Process* p, Eterm* reg, Eterm map, BeamInstr* I) { diff --git a/erts/emulator/beam/beam_load.c b/erts/emulator/beam/beam_load.c index 23258dbe9c..71637cf4d6 100644 --- a/erts/emulator/beam/beam_load.c +++ b/erts/emulator/beam/beam_load.c @@ -537,6 +537,7 @@ static int get_tag_and_value(LoaderState* stp, Uint len_code, static int new_label(LoaderState* stp); static void new_literal_patch(LoaderState* stp, int pos); static void new_string_patch(LoaderState* stp, int pos); +static int find_literal(LoaderState* stp, Eterm needle, Uint *idx); static Uint new_literal(LoaderState* stp, Eterm** hpp, Uint heap_size); static int genopargcompare(GenOpArg* a, GenOpArg* b); static Eterm get_module_info(Process* p, ErtsCodeIndex code_ix, @@ -4221,6 +4222,92 @@ literal_is_map(LoaderState* stp, GenOpArg Lit) return is_map(term); } +/* + * Predicate to test whether all of the given new small map keys are literals + */ +static int +is_small_map_literal_keys(LoaderState* stp, GenOpArg Size, GenOpArg* Rest) +{ + if (Size.val > MAP_SMALL_MAP_LIMIT) { + return 0; + } + + /* + * Operations with non-literals have always only one key. + */ + if (Size.val != 2) { + return 1; + } + + switch (Rest[0].type) { + case TAG_a: + case TAG_i: + case TAG_n: + case TAG_q: + return 1; + default: + return 0; + } +} + +static GenOp* +gen_new_small_map_lit(LoaderState* stp, GenOpArg Dst, GenOpArg Live, + GenOpArg Size, GenOpArg* Rest) +{ + unsigned size = Size.val; + Uint lit; + unsigned i; + GenOp* op; + GenOpArg* dst; + Eterm* hp; + Eterm* tmp; + Eterm* thp; + Eterm keys; + + NEW_GENOP(stp, op); + GENOP_ARITY(op, 3 + size/2); + op->next = NULL; + op->op = genop_i_new_small_map_lit_3; + + tmp = thp = erts_alloc(ERTS_ALC_T_LOADER_TMP, (1 + size/2) * sizeof(*tmp)); + keys = make_tuple(thp); + *thp++ = make_arityval(size/2); + + dst = op->a+3; + + for (i = 0; i < size; i += 2) { + switch (Rest[i].type) { + case TAG_a: + *thp++ = Rest[i].val; + ASSERT(is_atom(Rest[i].val)); + break; + case TAG_i: + *thp++ = make_small(Rest[i].val); + break; + case TAG_n: + *thp++ = NIL; + break; + case TAG_q: + *thp++ = stp->literals[Rest[i].val].term; + break; + } + *dst++ = Rest[i + 1]; + } + + if (!find_literal(stp, keys, &lit)) { + lit = new_literal(stp, &hp, 1 + size/2); + sys_memcpy(hp, tmp, (1 + size/2) * sizeof(*tmp)); + } + erts_free(ERTS_ALC_T_LOADER_TMP, tmp); + + op->a[0] = Dst; + op->a[1] = Live; + op->a[2].type = TAG_q; + op->a[2].val = lit; + + return op; +} + /* * Predicate to test whether the given literal is an empty map. */ @@ -5509,6 +5596,24 @@ new_literal(LoaderState* stp, Eterm** hpp, Uint heap_size) return stp->num_literals++; } +static int +find_literal(LoaderState* stp, Eterm needle, Uint *idx) +{ + int i; + + /* + * The search is done backwards since the most recent literals + * allocated by the loader itself will be placed at the end + */ + for (i = stp->num_literals - 1; i >= 0; i--) { + if (EQ(needle, stp->literals[i].term)) { + *idx = (Uint) i; + return 1; + } + } + return 0; +} + Eterm erts_module_info_0(Process* p, Eterm module) { diff --git a/erts/emulator/beam/ops.tab b/erts/emulator/beam/ops.tab index 4ce86ce949..ed856b760b 100644 --- a/erts/emulator/beam/ops.tab +++ b/erts/emulator/beam/ops.tab @@ -1425,7 +1425,11 @@ sorted_put_map_exact F Src=s Dst Live Size Rest=* => \ sorted_put_map_exact F Src Dst Live Size Rest=* => \ move Src x | update_map_exact F x Dst Live Size Rest +new_map Dst Live Size Rest=* | is_small_map_literal_keys(Size, Rest) => \ + gen_new_small_map_lit(Dst, Live, 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_exact j s d I I -- cgit v1.2.3