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.

4 files changed, 180 insertions, 0 deletions

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)) {			\
@@ -7035,6 +7047,44 @@ new_map(Process* p, Eterm* reg, BeamInstr* I)
 }
 
 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)
 {
     Uint n;
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,
@@ -4222,6 +4223,92 @@ literal_is_map(LoaderState* stp, GenOpArg Lit)
 }
 
 /*
+ * 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