erts: Move hashmap:from_list/1 to maps

5 files changed, 454 insertions, 486 deletions

diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab
index 320cd39da8..7e92e58cab 100644
--- a/erts/emulator/beam/bif.tab
+++ b/erts/emulator/beam/bif.tab
@@ -616,7 +616,6 @@ bif erlang:get_keys/0
 
 # Hash Array Mappped Trie
 bif hashmap:info/1
-bif hashmap:from_list/1
 bif hashmap:new/0
 bif hashmap:merge/2
 
diff --git a/erts/emulator/beam/erl_hashmap.c b/erts/emulator/beam/erl_hashmap.c
index 9b16a5a88f..06012950e1 100644
--- a/erts/emulator/beam/erl_hashmap.c
+++ b/erts/emulator/beam/erl_hashmap.c
@@ -61,22 +61,8 @@ static char *format_binary(Uint64 x, char *b) {
 #endif
 
 
-/* for hashmap_from_list/1 */
-typedef struct {
-    Uint32 hx;
-    Uint32 skip;
-    Uint i;
-    Eterm  val;
-} hxnode_t;
-
-static Eterm hashmap_from_list(Process *p, Eterm node);
 static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB);
 static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]);
-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 int hxnodecmp(hxnode_t* a, hxnode_t* b);
-static int hxnodecmpkey(hxnode_t* a, hxnode_t* b);
 
 /* hashmap:new/0 */
 
@@ -101,13 +87,6 @@ BIF_RETTYPE hashmap_new_0(BIF_ALIST_0) {
 
 /* hashmap:from_list/1 */
 
-BIF_RETTYPE hashmap_from_list_1(BIF_ALIST_1) {
-    if (is_list(BIF_ARG_1) || is_nil(BIF_ARG_1)) {
-	return hashmap_from_list(BIF_P, BIF_ARG_1);
-    }
-
-    BIF_ERROR(BIF_P, BADARG);
-}
 /* hashmap:get/2 */
 
 /* hashmap:find/2 */
@@ -134,435 +113,11 @@ BIF_RETTYPE hashmap_merge_2(BIF_ALIST_2) {
 /* impl. */
 
 
-#define swizzle32(D,S) \
-    do { \
-	(D) = ((S) & 0x0000000f) << 28 | ((S) & 0x000000f0) << 20  \
-	    | ((S) & 0x00000f00) << 12 | ((S) & 0x0000f000) << 4   \
-	    | ((S) & 0x000f0000) >> 4  | ((S) & 0x00f00000) >> 12  \
-	    | ((S) & 0x0f000000) >> 20 | ((S) & 0xf0000000) >> 28; \
-    } while(0)
-
-
-static Eterm hashmap_from_list(Process *p, Eterm list) {
-    Eterm *kv, res, item = list;
-    Eterm *hp;
-    Eterm tmp[2];
-    Uint32 sw, hx;
-    Uint ix = 0, n = 0;
-    hxnode_t *hxns;
-
-    /* Calculate size and check validity */
-
-    if (is_nil(list)) {
-	hp    = HAlloc(p, HAMT_HEAD_EMPTY_SZ);
-	hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(0);
-	hp[1] = 0;
-	return make_hashmap(hp);
-    }
-
-    while(is_list(item)) {
-	res = CAR(list_val(item));
-	if (is_not_tuple(res))
-	    goto error;
-
-	kv = tuple_val(res);
-	if (*kv != make_arityval(2))
-	    goto error;
-
-	n++;
-	item = CDR(list_val(item));
-    }
-
-    if (is_not_nil(item))
-	goto error;
-
-    hp = HAlloc(p, (2 * n));
-
-    /* create tmp hx values and leaf ptrs */
-    hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, n * sizeof(hxnode_t));
-    item = list;
-
-    while(is_list(item)) {
-	res = CAR(list_val(item));
-	kv  = tuple_val(res);
-	hx  = hashmap_restore_hash(tmp,0,kv[1]);
-	swizzle32(sw,hx);
-	hxns[ix].hx   = sw;
-	hxns[ix].val  = CONS(hp, kv[1], kv[2]); hp += 2;
-	hxns[ix].skip = 1; /* will be reassigned in from_array */
-	hxns[ix].i    = ix;
-	ix++;
-	item = CDR(list_val(item));
-    }
-
-    ASSERT(n > 0);
-
-    res = hashmap_from_unsorted_array(p, hxns, n);
-
-    erts_free(ERTS_ALC_T_TMP, (void *) hxns);
-    ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
-
-    BIF_RET(res);
-error:
-    BIF_ERROR(p, BADARG);
-}
-
-Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n) {
-    Eterm tmp[2];
-    Uint32 sw, hx;
-    Uint ix;
-    hxnode_t *hxns;
-    Eterm res;
-
-    /* create tmp hx values and leaf ptrs */
-    hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, n * sizeof(hxnode_t));
-
-    for (ix = 0; ix < n; ix++) {
-	hx  = hashmap_restore_hash(tmp,0,CAR(list_val(leafs[ix])));
-	swizzle32(sw,hx);
-	hxns[ix].hx   = sw;
-	hxns[ix].val  = leafs[ix];
-	hxns[ix].skip = 1;
-	hxns[ix].i    = ix;
-    }
-
-    res = hashmap_from_unsorted_array(p, hxns, n);
-
-    erts_free(ERTS_ALC_T_TMP, (void *) hxns);
-    ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
-
-    return res;
-}
-
-static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n) {
-    Uint jx = 0, ix = 0, lx, cx;
-    Eterm res;
-
-    /* sort and compact array (remove non-unique entries) */
-    qsort(hxns, n, sizeof(hxnode_t), (int (*)(const void *, const void *)) hxnodecmp);
-
-    ix = 0, cx = 0;
-    while(ix < n - 1) {
-	if (hxns[ix].hx == hxns[ix+1].hx) {
-
-	    /* find region of equal hash values */
-	    jx = ix + 1;
-	    while(jx < n && hxns[ix].hx == hxns[jx].hx) { jx++; }
-	    /* find all correct keys from region
-	     * (last in list but now hash sorted so we check highest id instead) */
-
-	    /* resort with keys instead of hash value within region */
-	    
-	    qsort(&hxns[ix], jx - ix, sizeof(hxnode_t),
-		    (int (*)(const void *, const void *)) hxnodecmpkey);
-
-	    while(ix < jx) {
-		lx = ix;
-		while(ix < jx && EQ(CAR(list_val(hxns[ix].val)), CAR(list_val(hxns[lx].val)))) {
-		    if (hxns[ix].i > hxns[lx].i) {
-			lx = ix;
-		    }
-		    ix++;
-		}
-		hxns[cx].hx  = hxns[lx].hx;
-		hxns[cx].val = hxns[lx].val;
-		cx++;
-	    }
-	    ix = jx;
-	    continue;
-	}
-	if (ix > cx) {
-	    hxns[cx].hx  = hxns[ix].hx;
-	    hxns[cx].val = hxns[ix].val;
-	}
-	cx++;
-	ix++;
-    }
-
-    if (ix < n) {
-	hxns[cx].hx  = hxns[ix].hx;
-	hxns[cx].val = hxns[ix].val;
-	cx++;
-    }
-
-    if (cx > 1) {
-	/* recursive decompose array */
-	res = hashmap_from_sorted_unique_array(p, hxns, cx, 0);
-    } else {
-	Eterm *hp;
-	 /* hash value has been swizzled, need to drag it down to get the
-	 * correct slot. */
-	hp    = HAlloc(p, HAMT_HEAD_BITMAP_SZ(1));
-	hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(1 << ((hxns[0].hx >> 0x1c) & 0xf));
-	hp[1] = 1;
-	hp[2] = hxns[0].val;
-	res   = make_hashmap(hp);
-    }
-
-    return res;
-}
-
-static Eterm hashmap_from_sorted_unique_array(Process *p, hxnode_t *hxns, Uint n, int lvl) {
-    Eterm res = NIL;
-    Uint i,ix,jx,elems;
-    Uint32 sw, hx;
-    Eterm val;
-    Eterm th[2];
-    hxnode_t *tmp;
-
-    ASSERT(lvl < 32);
-    ix = 0;
-    elems = 1;
-    while (ix < n - 1) {
-	if (hxns[ix].hx == hxns[ix+1].hx) {
-	    jx = ix + 1;
-	    while (jx < n && hxns[ix].hx == hxns[jx].hx) { jx++; }
-	    tmp = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, ((jx - ix)) * sizeof(hxnode_t));
-
-	    for(i = 0; i < jx - ix; i++) {
-		val = hxns[i + ix].val;
-		hx  = hashmap_restore_hash(th, lvl + 8, CAR(list_val(val)));
-		swizzle32(sw,hx);
-		tmp[i].hx   = sw;
-		tmp[i].val  = val;
-		tmp[i].i    = i;
-		tmp[i].skip = 1;
-	    }
-
-	    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);
-	    erts_free(ERTS_ALC_T_TMP, (void *) tmp);
-	    ix = jx;
-	    if (ix < n) { elems++; }
-	    continue;
-	}
-	hxns[ix].skip = 1;
-	elems++;
-	ix++;
-    }
-
-    res = hashmap_from_chunked_array(p, hxns, elems, !lvl);
-
-    ERTS_HOLE_CHECK(p);
-
-    return res;
-}
-
-#define maskval(V,L)      (((V) >> ((7 - (L))*4)) & 0xf)
-#define cdepth(V1,V2)     (hashmap_clz((V1) ^ (V2)) >> 2)
-
 /* n must be > 1
  * hash values in hxns has to be unique
  */
 
 #define HALLOC_EXTRA 200
-static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int is_root) {
-    Uint ix, d, dn, dc, slot, elems;
-    Uint32 v, vp, vn, hdr;
-    Uint bp, sz;
-    DECLARE_ESTACK(stack);
-    Eterm res = NIL, *hp = NULL, *nhp;
-
-    ASSERT(n > 1);
-
-    /* push initial nodes on the stack,
-     * this is the starting depth */
-
-    ix = 0;
-    d  = 0;
-    vp = hxns[ix].hx;
-    v  = hxns[ix + hxns[ix].skip].hx;
-
-    ASSERT(vp > v);
-    slot = maskval(vp,d);
-
-    while(slot == maskval(v,d)) {
-	ESTACK_PUSH(stack, 1 << slot);
-	d++;
-	slot = maskval(vp,d);
-    }
-
-    res = hxns[ix].val;
-
-    if (hxns[ix].skip > 1) {
-	dc = 7;
-	/* build collision nodes */
-	while (dc > d) {
-	    hp    = HAllocX(p, 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);
-	    dc--;
-	}
-    }
-
-    ESTACK_PUSH(stack, res);
-    ESTACK_PUSH(stack, 1 << slot);
-
-    /* all of the other nodes .. */
-    elems = n - 2; /* remove first and last elements */
-    while(elems--) {
-	hdr = ESTACK_POP(stack);
-	ix  = ix + hxns[ix].skip;
-
-	/* determine if node or subtree should be built by looking
-	 * at the next value. */
-
-	vn = hxns[ix + hxns[ix].skip].hx;
-	dn = cdepth(v,vn);
-	ASSERT(v > vn);
-
-	res = hxns[ix].val;
-
-	if (hxns[ix].skip > 1) {
-	    int wat = (d > dn) ? d : dn;
-	    dc = 7;
-	    /* build collision nodes */
-	    while (dc > wat) {
-		hp    = HAllocX(p, 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);
-		dc--;
-	    }
-	}
-
-	/* next depth is higher (implies collision) */
-	if (d < dn) {
-	    /* hdr is the popped one initially */
-	    while(d < dn) {
-		slot = maskval(v, d);
-		bp   = 1 << slot;
-		ESTACK_PUSH(stack, hdr | bp);
-		d++;
-		hdr = 0; /* clear hdr for all other collisions */
-	    }
-
-	    slot = maskval(v, d);
-	    bp   = 1 << slot;
-	    /* no more collisions */
-	    ESTACK_PUSH(stack,res);
-	    ESTACK_PUSH(stack,bp);
-	} else if (d == dn) {
-	    /* no collisions at all */
-	    slot = maskval(v, d);
-	    bp   = 1 << slot;
-	    ESTACK_PUSH(stack,res);
-	    ESTACK_PUSH(stack,hdr | bp);
-	} else {
-	    /* dn < n, we have a drop and we are done
-	     * build nodes and subtree */
-	    while (dn != d) {
-		slot  = maskval(v, d);
-		bp    = 1 << slot;
-		/* OR bitposition before sz calculation to handle
-		 * redundant collisions */
-		hdr  |= bp;
-		sz    = hashmap_bitcount(hdr);
-		hp    = HAllocX(p, 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--;
-		while (sz--) { *hp++ = ESTACK_POP(stack); }
-		ASSERT((hp - nhp) < 18);
-		res = make_hashmap(nhp);
-
-		/* we need to pop the next hdr and push if we don't need it */
-
-		hdr = ESTACK_POP(stack);
-		d--;
-	    }
-	    ESTACK_PUSH(stack, res);
-	    ESTACK_PUSH(stack, hdr);
-	}
-
-	vp = v;
-	v  = vn;
-	d  = dn;
-	ERTS_HOLE_CHECK(p);
-    }
-
-    /* v and vp are reused from above */
-    dn  = cdepth(vp,v);
-    ix  = ix + hxns[ix].skip;
-    res = hxns[ix].val;
-
-    if (hxns[ix].skip > 1) {
-	dc = 7;
-	/* build collision nodes */
-	while (dc > dn) {
-	    hp    = HAllocX(p, 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);
-	    dc--;
-	}
-    }
-
-    hdr = ESTACK_POP(stack);
-    /* pop remaining subtree if any */
-    while (dn) {
-	slot  = maskval(v, dn);
-	bp    = 1 << slot;
-	/* OR bitposition before sz calculation to handle
-	 * redundant collisions */
-	hdr  |= bp;
-	sz    = hashmap_bitcount(hdr);
-	hp    = HAllocX(p, 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--;
-
-	while (sz--) { *hp++ = ESTACK_POP(stack); }
-	res = make_hashmap(nhp);
-	hdr = ESTACK_POP(stack);
-	dn--;
-    }
-
-    /* and finally the root .. */
-
-    slot  = maskval(v, dn);
-    bp    = 1 << slot;
-    hdr  |= bp;
-    sz    = hashmap_bitcount(hdr);
-    hp    = HAlloc(p, sz + /* hdr + item */ (is_root ? 2 : 1));
-    nhp   = hp;
-
-    if (is_root) {
-	*hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_HEAD_ARRAY : MAP_HEADER_HAMT_HEAD_BITMAP(hdr);
-	*hp++ = n;
-    } else {
-	*hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_NODE_ARRAY : MAP_HEADER_HAMT_NODE_BITMAP(hdr);
-    }
-
-    *hp++ = res; sz--;
-    while (sz--) { *hp++ = ESTACK_POP(stack); }
-
-    res = make_hashmap(nhp);
-
-    ASSERT(ESTACK_COUNT(stack) == 0);
-    DESTROY_ESTACK(stack);
-    ERTS_HOLE_CHECK(p);
-    return res;
-}
-#undef HALLOC_EXTRA
-
-static int hxnodecmpkey(hxnode_t *a, hxnode_t *b) {
-    return CMP_TERM(CAR(list_val(a->val)), CAR(list_val(b->val)));
-}
-
-static int hxnodecmp(hxnode_t *a, hxnode_t *b) {
-    if (a->hx < b->hx)
-	return 1;
-    else if (a->hx == b->hx)
-	return 0;
-    else
-	return -1;
-}
-
-#define HALLOC_EXTRA 200
 
 static Eterm hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB) {
 #define PSTACK_TYPE struct HashmapMergePStackType
@@ -938,30 +493,3 @@ BIF_RETTYPE hashmap_info_1(BIF_ALIST_1) {
     }
     BIF_ERROR(BIF_P, BADARG);
 }
-
-/* implementation of builtin emulations */
-
-#if !defined(__GNUC__)
-/* Count leading zeros emulation */
-Uint32 hashmap_clz(Uint32 x) {
-    Uint32 y;
-    int n = 32;
-    y = x >>16;  if (y != 0) {n = n -16;  x = y;}
-    y = x >> 8;  if (y != 0) {n = n - 8;  x = y;}
-    y = x >> 4;  if (y != 0) {n = n - 4;  x = y;}
-    y = x >> 2;  if (y != 0) {n = n - 2;  x = y;}
-    y = x >> 1;  if (y != 0) return n - 2;
-    return n - x;
-}
-const Uint32 SK5 = 0x55555555, SK3 = 0x33333333;
-const Uint32 SKF0 = 0xF0F0F0F, SKFF = 0xFF00FF;
-
-/* CTPOP emulation */
-Uint32 hashmap_bitcount(Uint32 x) {
-    x -= ((x >> 1  ) & SK5);
-    x  =  (x & SK3 ) + ((x >> 2 ) & SK3 );
-    x  =  (x & SKF0) + ((x >> 4 ) & SKF0);
-    x +=   x >> 8;
-    return (x + (x >> 16)) & 0x3F;
-}
-#endif
diff --git a/erts/emulator/beam/erl_hashmap.h b/erts/emulator/beam/erl_hashmap.h
index 5a9aa05f61..7ac33b34b0 100644
--- a/erts/emulator/beam/erl_hashmap.h
+++ b/erts/emulator/beam/erl_hashmap.h
@@ -24,20 +24,10 @@
 #include "sys.h"
 #include "erl_term.h"
 
-Eterm erts_hashmap_get(Eterm key, Eterm map);
 int hashmap_key_hash_cmp(Eterm* ap, Eterm* bp);
-Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n);
 
 /* HASH */
 
-#if defined(__GNUC__)
-#define hashmap_clz(x)       ((Uint32) __builtin_clz((unsigned int)(x)))
-#define hashmap_bitcount(x)  ((Uint32) __builtin_popcount((unsigned int) (x)))
-#else
-Uint32 hashmap_clz(Uint32 x);
-Uint32 hashmap_bitcount(Uint32 x);
-#endif
-
 /* hamt nodes v2.0
  * 
  * node :: leaf | array | bitmap
@@ -49,8 +39,6 @@ typedef struct hashmap_head_s {
     Eterm items[1];
 } hashmap_head_t;
 
-
-
 /* thing_word tagscheme
  * Need two bits for map subtags
  *
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index 5e5e567642..7281353af5 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -63,6 +63,14 @@
  * - erts_internal:map_to_tuple_keys/1
  */
 
+/* for hashmap_from_list/1 */
+typedef struct {
+    Uint32 hx;
+    Uint32 skip;
+    Uint i;
+    Eterm  val;
+} hxnode_t;
+
 static const Eterm *hashmap_get(Uint32 hx, Eterm key, Eterm node);
 static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, Eterm node, int is_update);
 static Eterm hashmap_to_list(Process *p, Eterm map);
@@ -70,6 +78,12 @@ static Eterm hashmap_keys(Process *p, Eterm map);
 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 int hxnodecmp(hxnode_t* a, hxnode_t* b);
+static int hxnodecmpkey(hxnode_t* a, hxnode_t* b);
 
 /* erlang:map_size/1
  * the corresponding instruction is implemented in:
@@ -250,7 +264,11 @@ BIF_RETTYPE maps_from_list_1(BIF_ALIST_1) {
 	if (is_not_nil(item))
 	    goto error;
 
-	BIF_RET(map_from_validated_list(BIF_P, BIF_ARG_1, size));
+	if (size > MAP_SMALL_MAP_LIMIT) {
+	    BIF_RET(hashmap_from_validated_list(BIF_P, BIF_ARG_1, size));
+	} else {
+	    BIF_RET(map_from_validated_list(BIF_P, BIF_ARG_1, size));
+	}
     }
 
 error:
@@ -349,6 +367,401 @@ static Eterm map_from_validated_list(Process *p, Eterm list, Uint size) {
     return res;
 }
 
+#define swizzle32(D,S) \
+    do { \
+	(D) = ((S) & 0x0000000f) << 28 | ((S) & 0x000000f0) << 20  \
+	    | ((S) & 0x00000f00) << 12 | ((S) & 0x0000f000) << 4   \
+	    | ((S) & 0x000f0000) >> 4  | ((S) & 0x00f00000) >> 12  \
+	    | ((S) & 0x0f000000) >> 20 | ((S) & 0xf0000000) >> 28; \
+    } while(0)
+
+#define maskval(V,L)      (((V) >> ((7 - (L))*4)) & 0xf)
+#define cdepth(V1,V2)     (hashmap_clz((V1) ^ (V2)) >> 2)
+
+static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) {
+    Eterm item = list;
+    Eterm *hp;
+    Eterm *kv, res;
+    Eterm tmp[2];
+    Uint32 sw, hx;
+    Uint ix = 0;
+    hxnode_t *hxns;
+
+    ASSERT(size > 0);
+
+    hp = HAlloc(p, (2 * size));
+
+    /* create tmp hx values and leaf ptrs */
+    hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, size * sizeof(hxnode_t));
+
+    while(is_list(item)) {
+	res = CAR(list_val(item));
+	kv  = tuple_val(res);
+	hx  = hashmap_restore_hash(tmp,0,kv[1]);
+	swizzle32(sw,hx);
+	hxns[ix].hx   = sw;
+	hxns[ix].val  = CONS(hp, kv[1], kv[2]); hp += 2;
+	hxns[ix].skip = 1; /* will be reassigned in from_array */
+	hxns[ix].i    = ix;
+	ix++;
+	item = CDR(list_val(item));
+    }
+
+    res = hashmap_from_unsorted_array(p, hxns, size);
+
+    erts_free(ERTS_ALC_T_TMP, (void *) hxns);
+    ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
+
+    return res;
+}
+
+Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n) {
+    Eterm tmp[2];
+    Uint32 sw, hx;
+    Uint ix;
+    hxnode_t *hxns;
+    Eterm res;
+
+    /* create tmp hx values and leaf ptrs */
+    hxns = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, n * sizeof(hxnode_t));
+
+    for (ix = 0; ix < n; ix++) {
+	hx  = hashmap_restore_hash(tmp,0,CAR(list_val(leafs[ix])));
+	swizzle32(sw,hx);
+	hxns[ix].hx   = sw;
+	hxns[ix].val  = leafs[ix];
+	hxns[ix].skip = 1;
+	hxns[ix].i    = ix;
+    }
+
+    res = hashmap_from_unsorted_array(p, hxns, n);
+
+    erts_free(ERTS_ALC_T_TMP, (void *) hxns);
+    ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
+
+    return res;
+}
+
+static Eterm hashmap_from_unsorted_array(Process *p, hxnode_t *hxns, Uint n) {
+    Uint jx = 0, ix = 0, lx, cx;
+    Eterm res;
+
+    /* sort and compact array (remove non-unique entries) */
+    qsort(hxns, n, sizeof(hxnode_t), (int (*)(const void *, const void *)) hxnodecmp);
+
+    ix = 0, cx = 0;
+    while(ix < n - 1) {
+	if (hxns[ix].hx == hxns[ix+1].hx) {
+
+	    /* find region of equal hash values */
+	    jx = ix + 1;
+	    while(jx < n && hxns[ix].hx == hxns[jx].hx) { jx++; }
+	    /* find all correct keys from region
+	     * (last in list but now hash sorted so we check highest id instead) */
+
+	    /* resort with keys instead of hash value within region */
+
+	    qsort(&hxns[ix], jx - ix, sizeof(hxnode_t),
+		    (int (*)(const void *, const void *)) hxnodecmpkey);
+
+	    while(ix < jx) {
+		lx = ix;
+		while(ix < jx && EQ(CAR(list_val(hxns[ix].val)), CAR(list_val(hxns[lx].val)))) {
+		    if (hxns[ix].i > hxns[lx].i) {
+			lx = ix;
+		    }
+		    ix++;
+		}
+		hxns[cx].hx  = hxns[lx].hx;
+		hxns[cx].val = hxns[lx].val;
+		cx++;
+	    }
+	    ix = jx;
+	    continue;
+	}
+	if (ix > cx) {
+	    hxns[cx].hx  = hxns[ix].hx;
+	    hxns[cx].val = hxns[ix].val;
+	}
+	cx++;
+	ix++;
+    }
+
+    if (ix < n) {
+	hxns[cx].hx  = hxns[ix].hx;
+	hxns[cx].val = hxns[ix].val;
+	cx++;
+    }
+
+    if (cx > 1) {
+	/* recursive decompose array */
+	res = hashmap_from_sorted_unique_array(p, hxns, cx, 0);
+    } else {
+	Eterm *hp;
+	 /* hash value has been swizzled, need to drag it down to get the
+	 * correct slot. */
+	hp    = HAlloc(p, HAMT_HEAD_BITMAP_SZ(1));
+	hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(1 << ((hxns[0].hx >> 0x1c) & 0xf));
+	hp[1] = 1;
+	hp[2] = hxns[0].val;
+	res   = make_hashmap(hp);
+    }
+
+    return res;
+}
+
+static Eterm hashmap_from_sorted_unique_array(Process *p, hxnode_t *hxns, Uint n, int lvl) {
+    Eterm res = NIL;
+    Uint i,ix,jx,elems;
+    Uint32 sw, hx;
+    Eterm val;
+    Eterm th[2];
+    hxnode_t *tmp;
+
+    ASSERT(lvl < 32);
+    ix = 0;
+    elems = 1;
+    while (ix < n - 1) {
+	if (hxns[ix].hx == hxns[ix+1].hx) {
+	    jx = ix + 1;
+	    while (jx < n && hxns[ix].hx == hxns[jx].hx) { jx++; }
+	    tmp = (hxnode_t *)erts_alloc(ERTS_ALC_T_TMP, ((jx - ix)) * sizeof(hxnode_t));
+
+	    for(i = 0; i < jx - ix; i++) {
+		val = hxns[i + ix].val;
+		hx  = hashmap_restore_hash(th, lvl + 8, CAR(list_val(val)));
+		swizzle32(sw,hx);
+		tmp[i].hx   = sw;
+		tmp[i].val  = val;
+		tmp[i].i    = i;
+		tmp[i].skip = 1;
+	    }
+
+	    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);
+	    erts_free(ERTS_ALC_T_TMP, (void *) tmp);
+	    ix = jx;
+	    if (ix < n) { elems++; }
+	    continue;
+	}
+	hxns[ix].skip = 1;
+	elems++;
+	ix++;
+    }
+
+    res = hashmap_from_chunked_array(p, hxns, elems, !lvl);
+
+    ERTS_HOLE_CHECK(p);
+
+    return res;
+}
+
+#define HALLOC_EXTRA 200
+static Eterm hashmap_from_chunked_array(Process *p, hxnode_t *hxns, Uint n, int is_root) {
+    Uint ix, d, dn, dc, slot, elems;
+    Uint32 v, vp, vn, hdr;
+    Uint bp, sz;
+    DECLARE_ESTACK(stack);
+    Eterm res = NIL, *hp = NULL, *nhp;
+
+    ASSERT(n > 1);
+
+    /* push initial nodes on the stack,
+     * this is the starting depth */
+
+    ix = 0;
+    d  = 0;
+    vp = hxns[ix].hx;
+    v  = hxns[ix + hxns[ix].skip].hx;
+
+    ASSERT(vp > v);
+    slot = maskval(vp,d);
+
+    while(slot == maskval(v,d)) {
+	ESTACK_PUSH(stack, 1 << slot);
+	d++;
+	slot = maskval(vp,d);
+    }
+
+    res = hxns[ix].val;
+
+    if (hxns[ix].skip > 1) {
+	dc = 7;
+	/* build collision nodes */
+	while (dc > d) {
+	    hp    = HAllocX(p, 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);
+	    dc--;
+	}
+    }
+
+    ESTACK_PUSH(stack, res);
+    ESTACK_PUSH(stack, 1 << slot);
+
+    /* all of the other nodes .. */
+    elems = n - 2; /* remove first and last elements */
+    while(elems--) {
+	hdr = ESTACK_POP(stack);
+	ix  = ix + hxns[ix].skip;
+
+	/* determine if node or subtree should be built by looking
+	 * at the next value. */
+
+	vn = hxns[ix + hxns[ix].skip].hx;
+	dn = cdepth(v,vn);
+	ASSERT(v > vn);
+
+	res = hxns[ix].val;
+
+	if (hxns[ix].skip > 1) {
+	    int wat = (d > dn) ? d : dn;
+	    dc = 7;
+	    /* build collision nodes */
+	    while (dc > wat) {
+		hp    = HAllocX(p, 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);
+		dc--;
+	    }
+	}
+
+	/* next depth is higher (implies collision) */
+	if (d < dn) {
+	    /* hdr is the popped one initially */
+	    while(d < dn) {
+		slot = maskval(v, d);
+		bp   = 1 << slot;
+		ESTACK_PUSH(stack, hdr | bp);
+		d++;
+		hdr = 0; /* clear hdr for all other collisions */
+	    }
+
+	    slot = maskval(v, d);
+	    bp   = 1 << slot;
+	    /* no more collisions */
+	    ESTACK_PUSH(stack,res);
+	    ESTACK_PUSH(stack,bp);
+	} else if (d == dn) {
+	    /* no collisions at all */
+	    slot = maskval(v, d);
+	    bp   = 1 << slot;
+	    ESTACK_PUSH(stack,res);
+	    ESTACK_PUSH(stack,hdr | bp);
+	} else {
+	    /* dn < n, we have a drop and we are done
+	     * build nodes and subtree */
+	    while (dn != d) {
+		slot  = maskval(v, d);
+		bp    = 1 << slot;
+		/* OR bitposition before sz calculation to handle
+		 * redundant collisions */
+		hdr  |= bp;
+		sz    = hashmap_bitcount(hdr);
+		hp    = HAllocX(p, 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--;
+		while (sz--) { *hp++ = ESTACK_POP(stack); }
+		ASSERT((hp - nhp) < 18);
+		res = make_hashmap(nhp);
+
+		/* we need to pop the next hdr and push if we don't need it */
+
+		hdr = ESTACK_POP(stack);
+		d--;
+	    }
+	    ESTACK_PUSH(stack, res);
+	    ESTACK_PUSH(stack, hdr);
+	}
+
+	vp = v;
+	v  = vn;
+	d  = dn;
+	ERTS_HOLE_CHECK(p);
+    }
+
+    /* v and vp are reused from above */
+    dn  = cdepth(vp,v);
+    ix  = ix + hxns[ix].skip;
+    res = hxns[ix].val;
+
+    if (hxns[ix].skip > 1) {
+	dc = 7;
+	/* build collision nodes */
+	while (dc > dn) {
+	    hp    = HAllocX(p, 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);
+	    dc--;
+	}
+    }
+
+    hdr = ESTACK_POP(stack);
+    /* pop remaining subtree if any */
+    while (dn) {
+	slot  = maskval(v, dn);
+	bp    = 1 << slot;
+	/* OR bitposition before sz calculation to handle
+	 * redundant collisions */
+	hdr  |= bp;
+	sz    = hashmap_bitcount(hdr);
+	hp    = HAllocX(p, 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--;
+
+	while (sz--) { *hp++ = ESTACK_POP(stack); }
+	res = make_hashmap(nhp);
+	hdr = ESTACK_POP(stack);
+	dn--;
+    }
+
+    /* and finally the root .. */
+
+    slot  = maskval(v, dn);
+    bp    = 1 << slot;
+    hdr  |= bp;
+    sz    = hashmap_bitcount(hdr);
+    hp    = HAlloc(p, sz + /* hdr + item */ (is_root ? 2 : 1));
+    nhp   = hp;
+
+    if (is_root) {
+	*hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_HEAD_ARRAY : MAP_HEADER_HAMT_HEAD_BITMAP(hdr);
+	*hp++ = n;
+    } else {
+	*hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_NODE_ARRAY : MAP_HEADER_HAMT_NODE_BITMAP(hdr);
+    }
+
+    *hp++ = res; sz--;
+    while (sz--) { *hp++ = ESTACK_POP(stack); }
+
+    res = make_hashmap(nhp);
+
+    ASSERT(ESTACK_COUNT(stack) == 0);
+    DESTROY_ESTACK(stack);
+    ERTS_HOLE_CHECK(p);
+    return res;
+}
+#undef HALLOC_EXTRA
+
+static int hxnodecmpkey(hxnode_t *a, hxnode_t *b) {
+    return CMP_TERM(CAR(list_val(a->val)), CAR(list_val(b->val)));
+}
+
+static int hxnodecmp(hxnode_t *a, hxnode_t *b) {
+    if (a->hx < b->hx)
+	return 1;
+    else if (a->hx == b->hx)
+	return 0;
+    else
+	return -1;
+}
 
 /* maps:is_key/2
  */
@@ -1593,3 +2006,30 @@ BIF_RETTYPE erts_internal_map_to_tuple_keys_1(BIF_ALIST_1) {
     }
     BIF_ERROR(BIF_P, BADARG);
 }
+
+/* implementation of builtin emulations */
+
+#if !defined(__GNUC__)
+/* Count leading zeros emulation */
+Uint32 hashmap_clz(Uint32 x) {
+    Uint32 y;
+    int n = 32;
+    y = x >>16;  if (y != 0) {n = n -16;  x = y;}
+    y = x >> 8;  if (y != 0) {n = n - 8;  x = y;}
+    y = x >> 4;  if (y != 0) {n = n - 4;  x = y;}
+    y = x >> 2;  if (y != 0) {n = n - 2;  x = y;}
+    y = x >> 1;  if (y != 0) return n - 2;
+    return n - x;
+}
+const Uint32 SK5 = 0x55555555, SK3 = 0x33333333;
+const Uint32 SKF0 = 0xF0F0F0F, SKFF = 0xFF00FF;
+
+/* CTPOP emulation */
+Uint32 hashmap_bitcount(Uint32 x) {
+    x -= ((x >> 1  ) & SK5);
+    x  =  (x & SK3 ) + ((x >> 2 ) & SK3 );
+    x  =  (x & SKF0) + ((x >> 4 ) & SKF0);
+    x +=   x >> 8;
+    return (x + (x >> 16)) & 0x3F;
+}
+#endif
diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h
index 48bc316e3b..428cfe9b63 100644
--- a/erts/emulator/beam/erl_map.h
+++ b/erts/emulator/beam/erl_map.h
@@ -22,6 +22,16 @@
 #define __ERL_MAP_H__
 
 #include "sys.h"
+
+/* instrinsic wrappers */
+#if defined(__GNUC__)
+#define hashmap_clz(x)       ((Uint32) __builtin_clz((unsigned int)(x)))
+#define hashmap_bitcount(x)  ((Uint32) __builtin_popcount((unsigned int) (x)))
+#else
+Uint32 hashmap_clz(Uint32 x);
+Uint32 hashmap_bitcount(Uint32 x);
+#endif
+
 /* MAP */
 
 typedef struct map_s {
@@ -70,6 +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_HEADER             _make_header(1,_TAG_HEADER_MAP)
 #define MAP_HEADER_SIZE        (sizeof(map_t) / sizeof(Eterm))
 
@@ -80,6 +91,8 @@ int   erts_maps_remove(Process *p, Eterm key, Eterm map, Eterm *res);
 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);
+Eterm erts_hashmap_get(Eterm key, Eterm map);
+Eterm erts_hashmap_from_array(Process *p, Eterm *leafs, Uint n);
 
 #if HALFWORD_HEAP
 const Eterm *