First stab at binary_to_term for hamt

with over estimation of heap size.

6 files changed, 189 insertions, 78 deletions

diff --git a/erts/emulator/beam/beam_emu.c b/erts/emulator/beam/beam_emu.c
index 15591c3cad..4f57037507 100644
--- a/erts/emulator/beam/beam_emu.c
+++ b/erts/emulator/beam/beam_emu.c
@@ -6556,6 +6556,7 @@ new_map(Process* p, Eterm* reg, BeamInstr* I)
     Eterm *E;
     BeamInstr *ptr;
     map_t *mp;
+    ErtsHeapFactory factory;
 
     ptr = &Arg(4);
 
@@ -6575,7 +6576,8 @@ new_map(Process* p, Eterm* reg, BeamInstr* I)
 
 	p->htop = mhp;
 
-	return erts_hashmap_from_array(p, thp, n/2);
+        factory.p = p;
+	return erts_hashmap_from_array(&factory, thp, n/2);
     }
 
     if (HeapWordsLeft(p) < need) {
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index 0cf1c0e59d..eacdd0b6c3 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -87,9 +87,9 @@ static Eterm hashmap_values(Process *p, Eterm map);
 static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node);
 static Eterm map_from_validated_list(Process *p, Eterm list, Uint size);
 static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size);
-static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n);
-static Eterm hashmap_from_sorted_unique_array(Process *p, hxnode_t *hxns, Uint n, int is_root);
-static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int is_root);
+static Eterm hashmap_from_unsorted_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n);
+static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int is_root);
+static Eterm hashmap_from_chunked_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int is_root);
 static Eterm hashmap_info(Process *p, Eterm node);
 static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]);
 static int hxnodecmp(hxnode_t* a, hxnode_t* b);
@@ -396,6 +396,7 @@ static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) {
     Uint32 sw, hx;
     Uint ix = 0;
     hxnode_t *hxns;
+    ErtsHeapFactory factory;
 
     ASSERT(size > 0);
 
@@ -417,7 +418,8 @@ static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) {
 	item = CDR(list_val(item));
     }
 
-    res = hashmap_from_unsorted_array(p, hxns, size);
+    factory.p = p;
+    res = hashmap_from_unsorted_array(&factory, hxns, size);
 
     erts_free(ERTS_ALC_T_TMP, (void *) hxns);
     ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
@@ -460,7 +462,7 @@ static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) {
     return res;
 }
 
-Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n) {
+Eterm erts_hashmap_from_array(ErtsHeapFactory* factory, Eterm *leafs, Uint n) {
     Uint32 sw, hx;
     Uint ix;
     hxnode_t *hxns;
@@ -479,10 +481,9 @@ Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n) {
 	leafs += 2;
     }
 
-    res = hashmap_from_unsorted_array(p, hxns, n);
+    res = hashmap_from_unsorted_array(factory, hxns, n);
 
     erts_free(ERTS_ALC_T_TMP, (void *) hxns);
-    ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
 
     return res;
 }
@@ -493,6 +494,7 @@ Eterm erts_hashmap_from_ks_and_vs_extra(Process *p, Eterm *ks, Eterm *vs, Uint n
     Uint32 sw, hx;
     Uint i,sz;
     hxnode_t *hxns;
+    ErtsHeapFactory factory;
     Eterm *hp, res;
 
     sz = (key == THE_NON_VALUE) ? n : (n + 1);
@@ -520,7 +522,8 @@ Eterm erts_hashmap_from_ks_and_vs_extra(Process *p, Eterm *ks, Eterm *vs, Uint n
 	hxns[i].i    = i;
     }
 
-    res = hashmap_from_unsorted_array(p, hxns, sz);
+    factory.p = p;
+    res = hashmap_from_unsorted_array(&factory, hxns, sz);
 
     erts_free(ERTS_ALC_T_TMP, (void *) hxns);
     ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
@@ -528,13 +531,14 @@ Eterm erts_hashmap_from_ks_and_vs_extra(Process *p, Eterm *ks, Eterm *vs, Uint n
     return res;
 }
 
-static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n) {
+static Eterm hashmap_from_unsorted_array(ErtsHeapFactory* factory,
+                                         hxnode_t *hxns, Uint n) {
     Uint jx = 0, ix = 0, lx, cx;
     Eterm res;
 
     if (n == 0) {
 	Eterm *hp;
-	hp = HAlloc(p, 2);
+	hp = erts_produce_heap(factory, 2, 0);
 	hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(0);
 	hp[1] = 0;
 
@@ -590,7 +594,7 @@ static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n) {
 
     if (cx > 1) {
 	/* recursive decompose array */
-	res = hashmap_from_sorted_unique_array(p, hxns, cx, 0);
+	res = hashmap_from_sorted_unique_array(factory, hxns, cx, 0);
     } else {
 	Eterm *hp;
 
@@ -600,7 +604,7 @@ static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n) {
 	 * hash value has been swizzled, need to drag it down to get the
 	 * correct slot. */
 
-	hp    = HAlloc(p, HAMT_HEAD_BITMAP_SZ(1));
+	hp    = erts_produce_heap(factory, HAMT_HEAD_BITMAP_SZ(1), 0);
 	hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(1 << ((hxns[0].hx >> 0x1c) & 0xf));
 	hp[1] = 1;
 	hp[2] = hxns[0].val;
@@ -610,7 +614,8 @@ static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n) {
     return res;
 }
 
-static Eterm hashmap_from_sorted_unique_array(Process *p, hxnode_t *hxns, Uint n, int lvl) {
+static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory* factory,
+                                              hxnode_t *hxns, Uint n, int lvl) {
     Eterm res = NIL;
     Uint i,ix,jx,elems;
     Uint32 sw, hx;
@@ -640,7 +645,7 @@ static Eterm hashmap_from_sorted_unique_array(Process *p, hxnode_t *hxns, Uint n
 	    qsort(tmp, jx - ix, sizeof(hxnode_t), (int (*)(const void *, const void *)) hxnodecmp);
 
 	    hxns[ix].skip = jx - ix;
-	    hxns[ix].val  = hashmap_from_sorted_unique_array(p, tmp, jx - ix, lvl + 8);
+	    hxns[ix].val  = hashmap_from_sorted_unique_array(factory, tmp, jx - ix, lvl + 8);
 	    erts_free(ERTS_ALC_T_TMP, (void *) tmp);
 	    ix = jx;
 	    if (ix < n) { elems++; }
@@ -651,15 +656,16 @@ static Eterm hashmap_from_sorted_unique_array(Process *p, hxnode_t *hxns, Uint n
 	ix++;
     }
 
-    res = hashmap_from_chunked_array(p, hxns, elems, !lvl);
+    res = hashmap_from_chunked_array(factory, hxns, elems, !lvl);
 
-    ERTS_HOLE_CHECK(p);
+    ERTS_FACTORY_HOLE_CHECK(factory);
 
     return res;
 }
 
 #define HALLOC_EXTRA 200
-static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int is_root) {
+static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory,
+                                        hxnode_t *hxns, Uint n, int is_root) {
     Uint ix, d, dn, dc, slot, elems;
     Uint32 v, vp, vn, hdr;
     Uint bp, sz;
@@ -691,7 +697,7 @@ static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int
 	dc = 7;
 	/* build collision nodes */
 	while (dc > d) {
-	    hp    = HAllocX(p, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA);
+	    hp    = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA);
 	    hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << maskval(vp,dc));
 	    hp[1] = res;
 	    res   = make_hashmap(hp);
@@ -722,7 +728,7 @@ static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int
 	    dc = 7;
 	    /* build collision nodes */
 	    while (dc > wat) {
-		hp    = HAllocX(p, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA);
+		hp    = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA);
 		hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << maskval(v,dc));
 		hp[1] = res;
 		res   = make_hashmap(hp);
@@ -762,7 +768,7 @@ static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int
 		 * redundant collisions */
 		hdr  |= bp;
 		sz    = hashmap_bitcount(hdr);
-		hp    = HAllocX(p, HAMT_NODE_BITMAP_SZ(sz), HALLOC_EXTRA);
+		hp    = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(sz), HALLOC_EXTRA);
 		nhp   = hp;
 		*hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_NODE_ARRAY : MAP_HEADER_HAMT_NODE_BITMAP(hdr);
 		*hp++ = res; sz--;
@@ -782,7 +788,7 @@ static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int
 	vp = v;
 	v  = vn;
 	d  = dn;
-	ERTS_HOLE_CHECK(p);
+	ERTS_FACTORY_HOLE_CHECK(factory);
     }
 
     /* v and vp are reused from above */
@@ -794,7 +800,7 @@ static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int
 	dc = 7;
 	/* build collision nodes */
 	while (dc > dn) {
-	    hp    = HAllocX(p, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA);
+	    hp    = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA);
 	    hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << maskval(v,dc));
 	    hp[1] = res;
 	    res   = make_hashmap(hp);
@@ -811,7 +817,7 @@ static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int
 	 * redundant collisions */
 	hdr  |= bp;
 	sz    = hashmap_bitcount(hdr);
-	hp    = HAllocX(p, HAMT_NODE_BITMAP_SZ(sz), HALLOC_EXTRA);
+	hp    = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(sz), HALLOC_EXTRA);
 	nhp   = hp;
 	*hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_NODE_ARRAY : MAP_HEADER_HAMT_NODE_BITMAP(hdr);
 	*hp++ = res; sz--;
@@ -828,7 +834,7 @@ static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int
     bp    = 1 << slot;
     hdr  |= bp;
     sz    = hashmap_bitcount(hdr);
-    hp    = HAlloc(p, sz + /* hdr + item */ (is_root ? 2 : 1));
+    hp    = erts_produce_heap(factory, sz + /* hdr + item */ (is_root ? 2 : 1), 0);
     nhp   = hp;
 
     if (is_root) {
@@ -845,7 +851,7 @@ static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int
 
     ASSERT(ESTACK_COUNT(stack) == 0);
     DESTROY_ESTACK(stack);
-    ERTS_HOLE_CHECK(p);
+    ERTS_FACTORY_HOLE_CHECK(factory);
     return res;
 }
 #undef HALLOC_EXTRA
@@ -1005,6 +1011,7 @@ static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB) {
 	Uint i;
 	Eterm res;
 	hxnode_t *hxns;
+        ErtsHeapFactory factory;
 
 	ks = map_get_keys(mp_new);
 	vs = map_get_values(mp_new);
@@ -1022,7 +1029,8 @@ static Eterm map_merge(Process *p, Eterm nodeA, Eterm nodeB) {
 	    hxns[i].i    = i;
 	}
 
-	res = hashmap_from_unsorted_array(p, hxns, n);
+        factory.p = p;
+	res = hashmap_from_unsorted_array(&factory, hxns, n);
 
 	erts_free(ERTS_ALC_T_TMP, (void *) hxns);
 	ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
@@ -1041,6 +1049,7 @@ static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args)
     Uint n, i;
     hxnode_t *hxns;
     Uint32 sw, hx;
+    ErtsHeapFactory factory;
 
     /* convert flat to tree */
 
@@ -1066,7 +1075,8 @@ static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args)
 	hxns[i].i    = i;
     }
 
-    res = hashmap_from_unsorted_array(p, hxns, n);
+    factory.p = p;
+    res = hashmap_from_unsorted_array(&factory, hxns, n);
 
     erts_free(ERTS_ALC_T_TMP, (void *) hxns);
     ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
@@ -1576,7 +1586,7 @@ Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) {
 
 	/* the map will grow */
 
-	if (n > MAP_SMALL_MAP_LIMIT) {
+	if (n >= MAP_SMALL_MAP_LIMIT) {
 	    HRelease(p, shp + MAP_HEADER_SIZE + n, shp);
 	    ks = map_get_keys(mp);
 	    vs = map_get_values(mp);
diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h
index d1e227183f..35dbed86a9 100644
--- a/erts/emulator/beam/erl_map.h
+++ b/erts/emulator/beam/erl_map.h
@@ -80,7 +80,7 @@ typedef struct map_s {
 #define map_get_keys(x)        (((Eterm *)tuple_val(((map_t *)(x))->keys)) + 1)
 #define map_get_size(x)        (((map_t*)(x))->size)
 
-#define MAP_SMALL_MAP_LIMIT    (32)
+#define MAP_SMALL_MAP_LIMIT    (2) /*SVERK (32) */
 #define MAP_HEADER             _make_header(1,_TAG_HEADER_MAP)
 #define MAP_HEADER_SIZE        (sizeof(map_t) / sizeof(Eterm))
 
@@ -102,7 +102,7 @@ int    erts_validate_and_sort_map(map_t* map);
 void   hashmap_iterator_init(struct ErtsWStack_* s, Eterm node);
 Eterm* hashmap_iterator_next(struct ErtsWStack_* s);
 int    hashmap_key_hash_cmp(Eterm* ap, Eterm* bp);
-Eterm  erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n);
+Eterm  erts_hashmap_from_array(ErtsHeapFactory*, Eterm *leafs, Uint n);
 const  Eterm *erts_hashmap_get(Uint32 hx, Eterm key, Eterm map);
 
 #define erts_hashmap_from_ks_and_vs(P, KS, VS, N) \
diff --git a/erts/emulator/beam/erl_message.c b/erts/emulator/beam/erl_message.c
index 8870fac7d9..e4cbd8477d 100644
--- a/erts/emulator/beam/erl_message.c
+++ b/erts/emulator/beam/erl_message.c
@@ -1146,3 +1146,16 @@ erts_deliver_exit_message(Eterm from, Process *to, ErtsProcLocks *to_locksp,
     }
 }
 
+Eterm* erts_produce_heap(ErtsHeapFactory* factory, Uint need, Uint xtra)
+{
+    Eterm* res;
+    if (factory->p) {
+        res = HAllocX(factory->p, need, xtra);
+    } else {
+        res = factory->hp;
+        factory->hp += need;
+        ASSERT(factory->hp <= factory->hp_end);
+    }
+    return res;
+}
+
diff --git a/erts/emulator/beam/erl_message.h b/erts/emulator/beam/erl_message.h
index 0f3bb8d281..ece75a5ee4 100644
--- a/erts/emulator/beam/erl_message.h
+++ b/erts/emulator/beam/erl_message.h
@@ -68,6 +68,23 @@ struct erl_heap_fragment {
     Eterm mem[1];		/* Data */
 };
 
+typedef struct {
+    Process* p;
+    Eterm* hp;
+    Eterm* hp_end;
+    /* more to come... */
+} ErtsHeapFactory;
+
+Eterm* erts_produce_heap(ErtsHeapFactory*, Uint need, Uint xtra);
+#ifdef CHECK_FOR_HOLES
+# define ERTS_FACTORY_HOLE_CHECK(f) do {    \
+        if ((f)->p) erts_check_for_holes((f)->p); \
+    } while (0)
+#else
+# define ERTS_FACTORY_HOLE_CHECK(p)
+#endif
+
+
 typedef struct erl_mesg {
     struct erl_mesg* next;	/* Next message */
     union {
diff --git a/erts/emulator/beam/external.c b/erts/emulator/beam/external.c
index af8db4c265..0e012e9eec 100644
--- a/erts/emulator/beam/external.c
+++ b/erts/emulator/beam/external.c
@@ -1182,7 +1182,8 @@ typedef struct {
     Eterm* hp_end;
     int remaining_n;
     char* remaining_bytes;
-    Eterm* maps_head;
+    Eterm* maps_list;
+    struct dec_term_hamt_placeholder* hamt_list;
 } B2TDecodeContext;
 
 typedef struct {
@@ -1508,7 +1509,8 @@ static BIF_RETTYPE binary_to_term_int(Process* p, Uint32 flags, Eterm bin, Binar
             ctx->u.dc.hp_start = HAlloc(p, ctx->heap_size);
             ctx->u.dc.hp       = ctx->u.dc.hp_start;
             ctx->u.dc.hp_end   = ctx->u.dc.hp_start + ctx->heap_size;
-	    ctx->u.dc.maps_head = NULL;
+	    ctx->u.dc.maps_list = NULL;
+	    ctx->u.dc.hamt_list = NULL;
             ctx->state = B2TDecode;
             /*fall through*/
 	case B2TDecode:
@@ -2938,9 +2940,21 @@ undo_offheap_in_area(ErlOffHeap* off_heap, Eterm* start, Eterm* end)
 #endif /* DEBUG */
 }
 
+struct dec_term_hamt_placeholder
+{
+    struct dec_term_hamt_placeholder* next;
+    Eterm* objp; /* write result here */
+    Uint size;   /* nr of leafs */
+    Eterm* leaf_array;
+
+    Eterm _heap_capacity_[1];
+};
+
+#define DEC_TERM_HAMT_PLACEHOLDER_SIZE(SZ) \
+    (offsetof(struct dec_term_hamt_placeholder, _heap_capacity_) + (SZ))
 
 /* Decode term from external format into *objp.
-** On failure return NULL and (R13B04) *hpp will be unchanged.
+** On failure return NULL and *hpp will be unchanged.
 */
 static byte*
 dec_term(ErtsDistExternal *edep, Eterm** hpp, byte* ep, ErlOffHeap* off_heap,
@@ -2950,7 +2964,8 @@ dec_term(ErtsDistExternal *edep, Eterm** hpp, byte* ep, ErlOffHeap* off_heap,
     int n;
     ErtsAtomEncoding char_enc;
     register Eterm* hp;        /* Please don't take the address of hp */
-    Eterm *maps_head;   /* for validation of maps */
+    Eterm *maps_list;   /* for preprocessing of small maps */
+    struct dec_term_hamt_placeholder* hamt_list;   /* for preprocessing of big maps */
     Eterm* next;
     SWord reds;
 
@@ -2960,7 +2975,8 @@ dec_term(ErtsDistExternal *edep, Eterm** hpp, byte* ep, ErlOffHeap* off_heap,
         next     = ctx->u.dc.next;
         ep       = ctx->u.dc.ep;
         hpp      = &ctx->u.dc.hp;
-	maps_head = ctx->u.dc.maps_head;
+	maps_list = ctx->u.dc.maps_list;
+        hamt_list = ctx->u.dc.hamt_list;
 
         if (ctx->state != B2TDecode) {
             int n_limit = reds;
@@ -3041,7 +3057,8 @@ dec_term(ErtsDistExternal *edep, Eterm** hpp, byte* ep, ErlOffHeap* off_heap,
         reds = ERTS_SWORD_MAX;
         next = objp;
         *next = (Eterm) (UWord) NULL;
-	maps_head = NULL;
+	maps_list = NULL;
+        hamt_list = NULL;
     }
     hp = *hpp;
 
@@ -3577,46 +3594,68 @@ dec_term_atom_common:
 	    break;
 	case MAP_EXT:
 	    {
-		map_t *mp;
 		Uint32 size,n;
 		Eterm *kptr,*vptr;
 		Eterm keys;
 
 		size = get_int32(ep); ep += 4;
 
-		keys  = make_tuple(hp);
-		*hp++ = make_arityval(size);
-		hp   += size;
-		kptr = hp - 1;
-
-		mp    = (map_t*)hp;
-		hp   += MAP_HEADER_SIZE;
-		hp   += size;
-		vptr = hp - 1;
-
-		/* kptr, last word for keys
-		 * vptr, last word for values
-		 */
-
-		/*
-		 * Use thing_word to link through decoded maps.
-		 * The list of maps is for later validation.
-		 */
-
-		mp->thing_word = (Eterm) COMPRESS_POINTER(maps_head);
-		maps_head      = (Eterm *) mp;
-
-		mp->size       = size;
-		mp->keys       = keys;
-		*objp          = make_map(mp);
-
-		for (n = size; n; n--) {
-		    *vptr = (Eterm) COMPRESS_POINTER(next);
-		    *kptr = (Eterm) COMPRESS_POINTER(vptr);
-		    next  = kptr;
-		    vptr--;
-		    kptr--;
-		}
+                if (size <= MAP_SMALL_MAP_LIMIT) {
+                    map_t *mp;
+
+                    keys  = make_tuple(hp);
+                    *hp++ = make_arityval(size);
+                    hp   += size;
+                    kptr = hp - 1;
+
+                    mp    = (map_t*)hp;
+                    hp   += MAP_HEADER_SIZE;
+                    hp   += size;
+                    vptr = hp - 1;
+
+                    /* kptr, last word for keys
+                     * vptr, last word for values
+                     */
+
+                    /*
+                     * Use thing_word to link through decoded maps.
+                     * The list of maps is for later validation.
+                     */
+
+                    mp->thing_word = (Eterm) COMPRESS_POINTER(maps_list);
+                    maps_list      = (Eterm *) mp;
+
+                    mp->size       = size;
+                    mp->keys       = keys;
+                    *objp          = make_map(mp);
+
+                    for (n = size; n; n--) {
+                        *vptr = (Eterm) COMPRESS_POINTER(next);
+                        *kptr = (Eterm) COMPRESS_POINTER(vptr);
+                        next  = kptr;
+                        vptr--;
+                        kptr--;
+                    }
+                }
+                else {  /* Make hamt */
+                    struct dec_term_hamt_placeholder* holder =
+                        (struct dec_term_hamt_placeholder*) hp;
+
+                    holder->next = hamt_list;
+                    hamt_list    = holder;
+                    holder->objp = objp;
+                    holder->size = size;
+
+                    hp += DEC_TERM_HAMT_PLACEHOLDER_SIZE(size);
+                    holder->leaf_array = hp;
+
+                    for (n = size; n; n--) {
+                        CDR(hp) = (Eterm) COMPRESS_POINTER(next);
+                        CAR(hp) = (Eterm) COMPRESS_POINTER(&CDR(hp));
+                        next = &CAR(hp);
+                        hp += 2;
+                    }
+                }
 	    }
 	    break;
 	case NEW_FUN_EXT:
@@ -3837,7 +3876,7 @@ dec_term_atom_common:
                     ctx->u.dc.ep = ep;
                     ctx->u.dc.next = next;
                     ctx->u.dc.hp = hp;
-		    ctx->u.dc.maps_head = maps_head;
+		    ctx->u.dc.maps_list = maps_list;
                     ctx->reds = 0;
                     return NULL;
                 }
@@ -3852,12 +3891,38 @@ dec_term_atom_common:
      * - done here for when we know it is complete.
      */
 
-    while (maps_head) {
-	next  = (Eterm *)(EXPAND_POINTER(*maps_head));
-	*maps_head = MAP_HEADER;
-	if (!erts_validate_and_sort_map((map_t*)maps_head))
+    while (maps_list) {
+	next  = (Eterm *)(EXPAND_POINTER(*maps_list));
+	*maps_list = MAP_HEADER;
+	if (!erts_validate_and_sort_map((map_t*)maps_list))
 	    goto error;
-	maps_head  = next;
+	maps_list  = next;
+    }
+
+    while (hamt_list) {
+        ErtsHeapFactory factory;
+        int residue;
+
+        factory.p = NULL;
+        factory.hp = (Eterm*) hamt_list;
+        factory.hp_end = hamt_list->leaf_array;
+
+        next  = (Eterm *) hamt_list->next;
+        objp = hamt_list->objp;
+
+	/*SVERK Make it reject duplicate keys */
+        *objp = erts_hashmap_from_array(&factory,
+                                        hamt_list->leaf_array,
+                                        hamt_list->size);
+        if (is_non_value(*objp))
+            goto error;
+
+        residue = factory.hp_end - factory.hp;
+        if (residue) {
+            ASSERT(residue > 0);
+            *factory.hp = make_pos_bignum_header(residue-1);
+        }
+        hamt_list = (struct dec_term_hamt_placeholder*) next;
     }
 
     if (ctx) {
@@ -4420,7 +4485,11 @@ init_done:
 	    n = get_int32(ep);
 	    ep += 4;
 	    ADDTERMS(2*n);
-	    heap_size += 3 + n + 1 + n;
+            if (n <= MAP_SMALL_MAP_LIMIT) {
+                heap_size += 3 + n + 1 + n;
+            } else {
+                heap_size += DEC_TERM_HAMT_PLACEHOLDER_SIZE(n) + 2*n;
+            }
 	    break;
 	case STRING_EXT:
 	    CHKSIZE(2);