erts: Implement batching maps:iterator

This iterator implementation fetches multiple elements to
iterate over in one call to erts_internal:maps_next instead
of one at a time. This means that the memory usage will go
up for the iterator as we are buffering elements, but the
usage is still bounded.

In this implementation the max memory usage is 1000 words.

Using this approach makes the iterator as fast as using
maps:to_list, so maps:iterator/2 has been removed.

11 files changed, 282 insertions, 343 deletions

diff --git a/bootstrap/lib/stdlib/ebin/maps.beam b/bootstrap/lib/stdlib/ebin/maps.beam
index f07f4f922d..6820b81db5 100644
--- a/bootstrap/lib/stdlib/ebin/maps.beam
+++ b/bootstrap/lib/stdlib/ebin/maps.beam
diff --git a/erts/emulator/beam/atom.names b/erts/emulator/beam/atom.names
index fc55b687d4..42a6991c6e 100644
--- a/erts/emulator/beam/atom.names
+++ b/erts/emulator/beam/atom.names
@@ -352,6 +352,7 @@ atom instruction_counts
 atom invalid
 atom is_constant
 atom is_seq_trace
+atom iterator
 atom io
 atom keypos
 atom kill
diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab
index f2c8331850..b7b66e2ee7 100644
--- a/erts/emulator/beam/bif.tab
+++ b/erts/emulator/beam/bif.tab
@@ -629,7 +629,6 @@ bif re:inspect/2
 
 ubif erlang:is_map/1
 gcbif erlang:map_size/1
-bif maps:to_list/1
 bif maps:find/2
 bif maps:get/2
 bif maps:from_list/1
@@ -695,4 +694,4 @@ bif erlang:iolist_to_iovec/1
 # New in 21.0
 #
 
-bif erts_internal:map_next/2
+bif erts_internal:map_next/3
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index a5fda7b86d..135053dd18 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -139,35 +139,6 @@ BIF_RETTYPE map_size_1(BIF_ALIST_1) {
     BIF_ERROR(BIF_P, BADMAP);
 }
 
-/* maps:to_list/1 */
-
-BIF_RETTYPE maps_to_list_1(BIF_ALIST_1) {
-    if (is_flatmap(BIF_ARG_1)) {
-	Uint n;
-	Eterm* hp;
-	Eterm *ks,*vs, res, tup;
-	flatmap_t *mp = (flatmap_t*)flatmap_val(BIF_ARG_1);
-
-	ks  = flatmap_get_keys(mp);
-	vs  = flatmap_get_values(mp);
-	n   = flatmap_get_size(mp);
-	hp  = HAlloc(BIF_P, (2 + 3) * n);
-	res = NIL;
-
-	while(n--) {
-	    tup = TUPLE2(hp, ks[n], vs[n]); hp += 3;
-	    res = CONS(hp, tup, res); hp += 2;
-	}
-
-	BIF_RET(res);
-    } else if (is_hashmap(BIF_ARG_1)) {
-	return hashmap_to_list(BIF_P, BIF_ARG_1, -1);
-    }
-
-    BIF_P->fvalue = BIF_ARG_1;
-    BIF_ERROR(BIF_P, BADMAP);
-}
-
 /* erts_internal:maps_to_list/2
  *
  * This function should be removed once iterators are in place.
@@ -1986,21 +1957,31 @@ static Eterm hashmap_to_list(Process *p, Eterm node, Sint m) {
     return res;
 }
 
-void hashmap_iterator_init(ErtsWStack* s, Eterm node, int reverse) {
-    Eterm hdr = *hashmap_val(node);
+static ERTS_INLINE
+Uint hashmap_node_size(Eterm hdr, Eterm **nodep)
+{
     Uint sz;
 
     switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
     case HAMT_SUBTAG_HEAD_ARRAY:
 	sz = 16;
+        if (nodep) ++*nodep;
 	break;
     case HAMT_SUBTAG_HEAD_BITMAP:
+        if (nodep) ++*nodep;
     case HAMT_SUBTAG_NODE_BITMAP:
         sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
+        ASSERT(sz < 17);
 	break;
     default:
 	erts_exit(ERTS_ABORT_EXIT, "bad header");
     }
+    return sz;
+}
+
+void hashmap_iterator_init(ErtsWStack* s, Eterm node, int reverse) {
+    Eterm hdr = *hashmap_val(node);
+    Uint sz = hashmap_node_size(hdr, NULL);
 
     WSTACK_PUSH3((*s), (UWord)THE_NON_VALUE,  /* end marker */
 		 (UWord)(!reverse ? 0 : sz+1),
@@ -2024,20 +2005,7 @@ Eterm* hashmap_iterator_next(ErtsWStack* s) {
 	    ptr = boxed_val(node);
 	    hdr = *ptr;
 	    ASSERT(is_header(hdr));
-	    switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
-	    case HAMT_SUBTAG_HEAD_ARRAY:
-		ptr++;
-		sz = 16;
-		break;
-	    case HAMT_SUBTAG_HEAD_BITMAP:
-		ptr++;
-	    case HAMT_SUBTAG_NODE_BITMAP:
-		sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
-		ASSERT(sz < 17);
-		break;
-	    default:
-		erts_exit(ERTS_ABORT_EXIT, "bad header");
-	    }
+            sz = hashmap_node_size(hdr, &ptr);
 
 	    idx++;
 
@@ -2074,20 +2042,7 @@ Eterm* hashmap_iterator_prev(ErtsWStack* s) {
 	    ptr = boxed_val(node);
 	    hdr = *ptr;
 	    ASSERT(is_header(hdr));
-	    switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
-	    case HAMT_SUBTAG_HEAD_ARRAY:
-		ptr++;
-		sz = 16;
-		break;
-	    case HAMT_SUBTAG_HEAD_BITMAP:
-		ptr++;
-	    case HAMT_SUBTAG_NODE_BITMAP:
-		sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
-		ASSERT(sz < 17);
-		break;
-	    default:
-		erts_exit(ERTS_ERROR_EXIT, "bad header");
-	    }
+            sz = hashmap_node_size(hdr, &ptr);
 
             if (idx > sz)
 		idx = sz;
@@ -3061,15 +3016,7 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[])
 }
 
 
-/*
- * The iterator work in about the same way for both
- * flat- and hash-maps. It consists of a Path, Map
- * term where Path describes where to find the
- * term to get.
- *
- * In flatmap Path is just the index of the element
- * in the flatmap array.
- *
+/**
  * In hashmap the Path is a bit pattern that describes
  * which slot we should traverse in each hashmap node.
  * Since each hashmap node can only be up to 16 elements
@@ -3079,17 +3026,35 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[])
  * slot in the head node, and then the 1:st slot in the
  * resulting node and then finally the 1:st slot in the
  * node beneath. If that slot is not a leaf, then the path
- * continues down the 0:th slot until it finds a leaf and
- * returns that leaf.
+ * continues down the 0:th slot until it finds a leaf.
  *
- * Once the leaf has been found, the Path to the next leaf
- * is built using a stack that was created while traversing
- * the tree down.
+ * Once the leaf has been found, the return value is created
+ * by traversing the tree using the the stack that was built
+ * when searching for the first leaf to return.
  *
  * The index can become a bignum, which complicates the code
  * a bit. However it should be very rare that this happens
  * even on a 32bit system as you would need a tree of depth
  * 7 or more.
+ *
+ * If the number of elements remaining in the map is greater
+ * than how many we want to return, we build a new Path, using
+ * the stack, that points to the next leaf.
+ *
+ * The third argument to this function controls how the data
+ * is returned.
+ *
+ * iterator: The key-value associations are to be used by
+ *           maps:iterator. The return has this format:
+ *             {K1,V1,{K2,V2,none | [Path | Map]}}
+ *           this makes the maps:next function very simple
+ *           and performant.
+ *
+ * list(): The key-value associations are to be used by
+ *         maps:to_list. The return has this format:
+ *             [Path, Map | [{K1,V1},{K2,V2} | BIF_ARG_3]]
+ *                 or if no more associations remain
+ *             [{K1,V1},{K2,V2} | BIF_ARG_3]
  */
 
 #define PATH_ELEM_SIZE 4
@@ -3097,10 +3062,24 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[])
 #define PATH_ELEM(PATH) ((PATH) & PATH_ELEM_MASK)
 #define PATH_ELEMS_PER_DIGIT (sizeof(ErtsDigit) * 8 / PATH_ELEM_SIZE)
 
-BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) {
+/* How many elements we return in one call depends on the number of reductions
+   that the process has left to run. In debug we return fewer elements to test
+   the Path implementation better. */
+#if defined(DEBUG)
+#define FCALLS_ELEMS(BIF_P) ((BIF_P->fcalls / 4) & 0xF)
+#else
+#define FCALLS_ELEMS(BIF_P) (BIF_P->fcalls / 4)
+#endif
+
+#define NUM_ELEMS_TO_RETURN(BIF_P, map)                   \
+    ((MAX(FCALLS_ELEMS(BIF_P), 1) < hashmap_size(map)) ?  \
+     MAX(FCALLS_ELEMS(BIF_P), 1) : hashmap_size(map))
 
-    Eterm *hp = NULL, *lst,
-        iter, path, map, k, v;
+
+BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) {
+
+    Eterm path, map;
+    enum { iterator, list } type;
 
     path = BIF_ARG_1;
     map  = BIF_ARG_2;
@@ -3108,41 +3087,65 @@ BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) {
     if (!is_map(map))
         BIF_ERROR(BIF_P, BADARG);
 
-    if (path == am_none)
-        BIF_RET(am_none);
+    if (BIF_ARG_3 == am_iterator) {
+        type = iterator;
+    } else if (is_nil(BIF_ARG_3) || is_list(BIF_ARG_3)) {
+        type = list;
+    } else {
+        BIF_ERROR(BIF_P, BADARG);
+    }
 
     if (is_flatmap(map)) {
-        flatmap_t *mp = (flatmap_t *)flatmap_val(map);
-        Uint idx, sz = flatmap_get_size(mp);
-
-        if (is_not_small(path))
-            BIF_ERROR(BIF_P, BADARG);
+        Uint n;
+	Eterm *ks,*vs, res, *hp;
+	flatmap_t *mp = (flatmap_t*)flatmap_val(map);
 
-        idx = unsigned_val(path);
+	ks  = flatmap_get_keys(mp);
+	vs  = flatmap_get_values(mp);
+	n   = flatmap_get_size(mp);
 
-        if (sz == 0) {
-            if (idx == 0)
-                BIF_RET(am_none);
-            else
-                BIF_ERROR(BIF_P, BADARG);
-        }
+        if (!is_small(BIF_ARG_1) || n < unsigned_val(BIF_ARG_1))
+            BIF_ERROR(BIF_P, BADARG);
 
-        k = flatmap_get_keys(mp)[idx];
-        v = flatmap_get_values(mp)[idx];
+        if (type == iterator) {
+            hp  = HAlloc(BIF_P, 4 * n);
+            res = am_none;
 
-        if (idx + 1 < sz) {
-            path = make_small(idx + 1);
-        } else if (idx < sz) {
-            path = am_none;
+            while(n--) {
+                res = TUPLE3(hp, ks[n], vs[n], res); hp += 4;
+            }
         } else {
-            BIF_ERROR(BIF_P, BADARG);
+            hp  = HAlloc(BIF_P, (2 + 3) * n);
+            res = BIF_ARG_3;
+
+            while(n--) {
+                Eterm tup = TUPLE2(hp, ks[n], vs[n]); hp += 3;
+                res = CONS(hp, tup, res); hp += 2;
+            }
         }
+
+	BIF_RET(res);
     } else {
         Uint curr_path;
         Uint path_length = 0;
         Uint *path_rest = NULL;
-        int i;
-        Eterm node = map;
+        int i, elems = NUM_ELEMS_TO_RETURN(BIF_P, map);
+        Eterm node = map, res, *path_ptr = NULL, *hp;
+
+        /* A stack WSTACK is used when traversing the hashmap.
+         * It contains: node, idx, sz, ptr
+         *
+         * `node` is not really needed, but it is very nice to
+         * have when debugging.
+         *
+         * `idx` always points to the next un-explored entry in
+         * a node. If there are no more un-explored entries,
+         * `idx` is equal to `sz`.
+         *
+         * `sz` is the number of elements in the node.
+         *
+         * `ptr` is a pointer to where the elements of the node begins.
+         */
         DECLARE_WSTACK(stack);
 
         ASSERT(is_hashmap(node));
@@ -3152,7 +3155,7 @@ BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) {
         } else if (is_big(path)) {
             Eterm *big = big_val(path);
             if (bignum_header_is_neg(*big))
-                BIF_ERROR(BIF_P, BADARG);
+                goto badarg;
             path_length = BIG_ARITY(big) - 1;
             curr_path = BIG_DIGIT(big,  0);
             path_rest = BIG_V(big) + 1;
@@ -3160,42 +3163,45 @@ BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) {
             BIF_ERROR(BIF_P, BADARG);
         }
 
-        /* First we look for the K and V to return using the
+        if (type == iterator) {
+            /* iterator uses the format {K, V, {K, V, {K, V, [Path | Map]}}},
+             * so each element is 4 words large */
+            hp = HAlloc(BIF_P, 4 * NUM_ELEMS_TO_RETURN(BIF_P, map));
+            res = am_none;
+        } else {
+            /* list used the format [Path, Map, {K,V}, {K,V} | BIF_ARG_3],
+             * so each element is 2+3 words large */
+            hp = HAlloc(BIF_P, (2 + 3) * NUM_ELEMS_TO_RETURN(BIF_P, map));
+            res = BIF_ARG_3;
+        }
+
+        /* First we look for the leaf to start at using the
            path given. While doing so, we push each map node
-           and the index onto the stack so use later when
-           building the next index. */
+           and the index onto the stack to use later. */
         for (i = 1; ; i++) {
             Eterm *ptr = hashmap_val(node),
-                hdr = *ptr;
+                hdr = *ptr++;
             Uint sz;
 
-            ptr++;
-
-            switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
-	    case HAMT_SUBTAG_HEAD_ARRAY:
-		ptr++;
-		sz = 16;
-		break;
-	    case HAMT_SUBTAG_HEAD_BITMAP:
-		ptr++;
-	    case HAMT_SUBTAG_NODE_BITMAP:
-		sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
-		ASSERT(sz < 17);
-		break;
-            default:
-		erts_exit(ERTS_ABORT_EXIT, "bad header");
-	    }
+            sz = hashmap_node_size(hdr, &ptr);
 
             if (PATH_ELEM(curr_path) >= sz)
-                BIF_ERROR(BIF_P, BADARG);
+                goto badarg;
 
-            WSTACK_PUSH2(stack, node, PATH_ELEM(curr_path));
+            WSTACK_PUSH4(stack, node, PATH_ELEM(curr_path)+1, sz, (UWord)ptr);
 
-            /* We have found a leaf, return it and calculate the path to next */
+            /* We have found a leaf, return it and the next X elements */
             if (is_list(ptr[PATH_ELEM(curr_path)])) {
-                lst = list_val(ptr[PATH_ELEM(curr_path)]);
-                k = CAR(lst);
-                v = CDR(lst);
+                Eterm *lst = list_val(ptr[PATH_ELEM(curr_path)]);
+                if (type == iterator) {
+                    res = TUPLE3(hp, CAR(lst), CDR(lst), res); hp += 4;
+                    /* Note where we should patch the Iterator is needed */
+                    path_ptr = hp-1;
+                } else {
+                    Eterm tup = TUPLE2(hp, CAR(lst), CDR(lst)); hp += 3;
+                    res = CONS(hp, tup, res); hp += 2;
+                }
+                elems--;
                 break;
             }
 
@@ -3217,48 +3223,70 @@ BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) {
             }
         }
 
-        /* We pop the stack until we come to the next leaf to return */
-        while (1) {
+        /* We traverse the hashmap and return at most `elems` elements */
+        while(1) {
+            Eterm *ptr = (Eterm*)WSTACK_POP(stack);
+            Uint sz = (Uint)WSTACK_POP(stack);
             Uint idx = (Uint)WSTACK_POP(stack);
             Eterm node = (Eterm)WSTACK_POP(stack);
-            Eterm *ptr = hashmap_val(node),
-                hdr = *ptr;
-            Uint sz;
 
-            ptr++;
-
-            switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
-	    case HAMT_SUBTAG_HEAD_ARRAY:
-		ptr++;
-		sz = 16;
-		break;
-	    case HAMT_SUBTAG_HEAD_BITMAP:
-		ptr++;
-	    case HAMT_SUBTAG_NODE_BITMAP:
-		sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
-		ASSERT(sz < 17);
-		break;
-            default:
-		erts_exit(ERTS_ABORT_EXIT, "bad header");
-	    }
+            while (idx < sz && elems != 0 && is_list(ptr[idx])) {
+                Eterm *lst = list_val(ptr[idx]);
+                if (type == iterator) {
+                    res = TUPLE3(hp, CAR(lst), CDR(lst), res); hp += 4;
+                } else {
+                    Eterm tup = TUPLE2(hp, CAR(lst), CDR(lst)); hp += 3;
+                    res = CONS(hp, tup, res); hp += 2;
+                }
+                elems--;
+                idx++;
+            }
 
-            if (idx + 1 < sz) {
-                curr_path = idx + 1;
+            if (elems == 0) {
+                if (idx < sz) {
+                    /* There are more elements in this node to explore */
+                    WSTACK_PUSH4(stack, node, idx+1, sz, (UWord)ptr);
+                } else {
+                    /* pop stack to find the next value */
+                    while (!WSTACK_ISEMPTY(stack)) {
+                        Eterm *ptr = (Eterm*)WSTACK_POP(stack);
+                        Uint sz = (Uint)WSTACK_POP(stack);
+                        Uint idx = (Uint)WSTACK_POP(stack);
+                        Eterm node = (Eterm)WSTACK_POP(stack);
+                        if (idx < sz) {
+                            WSTACK_PUSH4(stack, node, idx+1, sz, (UWord)ptr);
+                            break;
+                        }
+                    }
+                }
                 break;
+            } else {
+                if (idx < sz) {
+                    Eterm hdr;
+                    /* Push next idx in current node */
+                    WSTACK_PUSH4(stack, node, idx+1, sz, (UWord)ptr);
+
+                    /* Push first idx in child node */
+                    node = ptr[idx];
+                    ptr = hashmap_val(ptr[idx]);
+                    hdr = *ptr++;
+                    sz = hashmap_node_size(hdr, &ptr);
+                    WSTACK_PUSH4(stack, node, 0, sz, (UWord)ptr);
+                }
             }
 
-            /* We have reached the end of the iteration */
+            /* There are no more element in the hashmap */
             if (WSTACK_ISEMPTY(stack)) {
-                path = am_none;
                 break;
             }
 
         }
 
-        if (path != am_none) {
-            Uint depth = WSTACK_COUNT(stack) / 2 + 1;
+        if (!WSTACK_ISEMPTY(stack)) {
+            Uint depth = WSTACK_COUNT(stack) / 4 + 1;
             /* +1 because we already have the first element in curr_path */
             Eterm *path_digits = NULL;
+            Uint curr_path = 0;
 
             /* If the path cannot fit in a small, we allocate a bignum */
             if (depth >= PATH_ELEMS_PER_DIGIT) {
@@ -3269,13 +3297,21 @@ BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) {
                 path_digits = hp + big_size - 1;
             }
 
+
             /* Pop the stack to create the complete path to the next leaf */
             while(!WSTACK_ISEMPTY(stack)) {
-                Uint idx = (Uint)WSTACK_POP(stack);
+                Uint idx;
+
+                (void)WSTACK_POP(stack);
+                (void)WSTACK_POP(stack);
+                idx = (Uint)WSTACK_POP(stack)-1;
+                /* idx - 1 because idx in the stack is pointing to
+                   the next element to fetch. */
                 (void)WSTACK_POP(stack);
 
                 depth--;
                 if (depth % PATH_ELEMS_PER_DIGIT == 0) {
+                    /* Switch to next bignum element */
                     path_digits[0] = curr_path;
                     path_digits--;
                     curr_path = 0;
@@ -3292,15 +3328,36 @@ BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) {
                 /* The Uint could be too large for a small */
                 path = erts_make_integer(curr_path, BIF_P);
             }
+
+            if (type == iterator) {
+                hp = HAlloc(BIF_P, 2);
+                *path_ptr = CONS(hp, path, map); hp += 2;
+            } else {
+                hp = HAlloc(BIF_P, 4);
+                res = CONS(hp, map, res); hp += 2;
+                res = CONS(hp, path, res); hp += 2;
+            }
+        } else {
+            if (type == iterator) {
+                HRelease(BIF_P, hp + 4 * elems, hp);
+            } else {
+                HRelease(BIF_P, hp + (2+3) * elems, hp);
+            }
         }
+        BIF_P->fcalls -= 4 * (NUM_ELEMS_TO_RETURN(BIF_P, map) - elems);
+        DESTROY_WSTACK(stack);
+        BIF_RET(res);
 
+    badarg:
+        if (type == iterator) {
+            HRelease(BIF_P, hp + 4 * elems, hp);
+        } else {
+            HRelease(BIF_P, hp + (2+3) * elems, hp);
+        }
+        BIF_P->fcalls -= 4 * (NUM_ELEMS_TO_RETURN(BIF_P, map) - elems);
         DESTROY_WSTACK(stack);
+        BIF_ERROR(BIF_P, BADARG);
     }
-
-    hp = HAlloc(BIF_P, 4 + 3 /* 3-tuple + 2-tuple */);
-    iter = TUPLE2(hp, path, map);
-    hp += 3;
-    BIF_RET(TUPLE3(hp, k, v, iter));
 }
 
 /* implementation of builtin emulations */
diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl
index 3cf071b590..1e70d31b16 100644
--- a/erts/emulator/test/map_SUITE.erl
+++ b/erts/emulator/test/map_SUITE.erl
@@ -2366,41 +2366,6 @@ t_bif_map_from_list(Config) when is_list(Config) ->
     {'EXIT', {badarg,_}} = (catch maps:from_list(id(42))),
     ok.
 
-t_bif_erts_internal_maps_to_list(Config) when is_list(Config) ->
-    %% small maps
-    [] = erts_internal:maps_to_list(#{},-1),
-    [] = erts_internal:maps_to_list(#{},-2),
-    [] = erts_internal:maps_to_list(#{},10),
-    [{a,1},{b,2}] = lists:sort(erts_internal:maps_to_list(#{a=>1,b=>2}, 2)),
-    [{a,1},{b,2}] = lists:sort(erts_internal:maps_to_list(#{a=>1,b=>2}, -1)),
-    [{_,_}] = erts_internal:maps_to_list(#{a=>1,b=>2}, 1),
-    [{a,1},{b,2},{c,3}] = lists:sort(erts_internal:maps_to_list(#{c=>3,a=>1,b=>2},-2)),
-    [{a,1},{b,2},{c,3}] = lists:sort(erts_internal:maps_to_list(#{c=>3,a=>1,b=>2},3)),
-    [{a,1},{b,2},{c,3}] = lists:sort(erts_internal:maps_to_list(#{c=>3,a=>1,b=>2},5)),
-    [{_,_},{_,_}] = erts_internal:maps_to_list(#{c=>3,a=>1,b=>2},2),
-    [{_,_}] = erts_internal:maps_to_list(#{c=>3,a=>1,b=>2},1),
-    [] = erts_internal:maps_to_list(#{c=>3,a=>1,b=>2},0),
-
-    %% big maps
-    M = maps:from_list([{I,ok}||I <- lists:seq(1,500)]),
-    [] = erts_internal:maps_to_list(M,0),
-    [{_,_}] = erts_internal:maps_to_list(M,1),
-    [{_,_},{_,_}] = erts_internal:maps_to_list(M,2),
-    Ls1 = erts_internal:maps_to_list(M,10),
-    10 = length(Ls1),
-    Ls2 = erts_internal:maps_to_list(M,20),
-    20 = length(Ls2),
-    Ls3 = erts_internal:maps_to_list(M,120),
-    120 = length(Ls3),
-    Ls4 = erts_internal:maps_to_list(M,-1),
-    500 = length(Ls4),
-
-    %% error cases
-    {'EXIT', {{badmap,[{a,b},b]},_}} = (catch erts_internal:maps_to_list(id([{a,b},b]),id(1))),
-    {'EXIT', {badarg,_}} = (catch erts_internal:maps_to_list(id(#{}),id(a))),
-    {'EXIT', {badarg,_}} = (catch erts_internal:maps_to_list(id(#{1=>2}),id(<<>>))),
-    ok.
-
 t_bif_map_next(Config) when is_list(Config) ->
 
     erts_debug:set_internal_state(available_internal_state, true),
@@ -2420,9 +2385,25 @@ t_bif_map_next(Config) when is_list(Config) ->
         {'EXIT', {badarg,_}} = (catch maps:next(id(a))),
         {'EXIT', {badarg,_}} = (catch maps:next(id([a|FM]))),
         {'EXIT', {badarg,_}} = (catch maps:next(id([1|#{}]))),
-        {'EXIT', {badarg,_}} = (catch maps:next(id([16#FFFFFFF|FM]))),
-        {'EXIT', {badarg,_}} = (catch maps:next(id([16#F0F0F0F|FM]))),
-        {'EXIT', {badarg,_}} = (catch maps:next(id([16#1234567890ABCDEF|FM]))),
+        {'EXIT', {badarg,_}} = (catch maps:next(id([-1|#{}]))),
+        {'EXIT', {badarg,_}} = (catch maps:next(id([-1|FM]))),
+        {'EXIT', {badarg,_}} = (catch maps:next(id([16#FFFFFFFFFFFFFFFF|FM]))),
+        {'EXIT', {badarg,_}} = (catch maps:next(id([-16#FFFFFFFFFFFFFFFF|FM]))),
+
+        %% This us a whitebox test that the error code works correctly.
+        %% It uses a path for a tree of depth 4 and tries to do next on
+        %% each of those paths.
+        (fun F(0) -> ok;
+             F(N) ->
+                 try maps:next([N|FM]) of
+                     none ->
+                         F(N-1);
+                     {_K,_V,_I} ->
+                         F(N-1)
+                 catch error:badarg ->
+                         F(N-1)
+                 end
+         end)(16#FFFF),
 
         ok
     after
diff --git a/erts/preloaded/ebin/erts_internal.beam b/erts/preloaded/ebin/erts_internal.beam
index 015508d326..3257c68897 100644
--- a/erts/preloaded/ebin/erts_internal.beam
+++ b/erts/preloaded/ebin/erts_internal.beam
diff --git a/erts/preloaded/src/erts_internal.erl b/erts/preloaded/src/erts_internal.erl
index 46bdeaad30..efff76f1fa 100644
--- a/erts/preloaded/src/erts_internal.erl
+++ b/erts/preloaded/src/erts_internal.erl
@@ -32,7 +32,7 @@
 -export([await_port_send_result/3]).
 -export([cmp_term/2]).
 -export([map_to_tuple_keys/1, term_type/1, map_hashmap_children/1,
-         maps_to_list/2, map_next/2]).
+         maps_to_list/2, map_next/3]).
 -export([open_port/2, port_command/3, port_connect/2, port_close/1,
 	 port_control/3, port_call/3, port_info/1, port_info/2]).
 
@@ -367,11 +367,6 @@ term_type(_T) ->
 map_hashmap_children(_M) ->
     erlang:nif_error(undefined).
 
--spec erts_internal:flush_monitor_messages(Ref, Multi, Res) -> term() when
-      Ref :: reference(),
-      Multi :: boolean(),
-      Res :: term().
-
 %% return a list of key value pairs, at most of length N
 -spec maps_to_list(M,N) -> Pairs when
     M :: map(),
@@ -382,16 +377,22 @@ maps_to_list(_M, _N) ->
     erlang:nif_error(undefined).
 
 %% return the next assoc in the iterator and a new iterator
--spec map_next(I, M) -> {K,V,NI} when
+-spec map_next(I, M, A) -> {K,V,NI} | list() when
       I :: non_neg_integer(),
       M :: map(),
       K :: term(),
       V :: term(),
+      A :: iterator | list(),
       NI :: maps:iterator().
 
-map_next(_I, _M) ->
+map_next(_I, _M, _A) ->
     erlang:nif_error(undefined).
 
+-spec erts_internal:flush_monitor_messages(Ref, Multi, Res) -> term() when
+      Ref :: reference(),
+      Multi :: boolean(),
+      Res :: term().
+
 %% erlang:demonitor(Ref, [flush]) traps to
 %% erts_internal:flush_monitor_messages(Ref, Res) when
 %% it needs to flush monitor messages.
diff --git a/lib/hipe/cerl/erl_bif_types.erl b/lib/hipe/cerl/erl_bif_types.erl
index a3a936322a..462a1f9dcd 100644
--- a/lib/hipe/cerl/erl_bif_types.erl
+++ b/lib/hipe/cerl/erl_bif_types.erl
@@ -1701,24 +1701,6 @@ type(maps, size, 1, Xs, Opaques) ->
 		 t_from_range(LowerBound, UpperBound)
 	     end
 	 end, Opaques);
-type(maps, to_list, 1, Xs, Opaques) ->
-  strict(maps, to_list, 1, Xs,
-	 fun ([Map]) ->
-	     DefK = t_map_def_key(Map, Opaques),
-	     DefV = t_map_def_val(Map, Opaques),
-	     Pairs = t_map_entries(Map, Opaques),
-	     EType = lists:foldl(
-		       fun({K,_,V},EType0) ->
-			   case t_is_none(V) of
-			     true -> t_subtract(EType0, t_tuple([K,t_any()]));
-			     false -> t_sup(EType0, t_tuple([K,V]))
-			   end
-		       end, t_tuple([DefK, DefV]), Pairs),
-	     case t_is_none(EType) of
-	       true -> t_nil();
-	       false -> t_list(EType)
-	     end
-	 end, Opaques);
 type(maps, update, 3, Xs, Opaques) ->
   strict(maps, update, 3, Xs,
 	 fun ([Key, Value, Map]) ->
@@ -2648,8 +2630,6 @@ arg_types(maps, put, 3) ->
   [t_any(), t_any(), t_map()];
 arg_types(maps, size, 1) ->
   [t_map()];
-arg_types(maps, to_list, 1) ->
-  [t_map()];
 arg_types(maps, update, 3) ->
   [t_any(), t_any(), t_map()];
 arg_types(M, F, A) when is_atom(M), is_atom(F),
diff --git a/lib/stdlib/doc/src/maps.xml b/lib/stdlib/doc/src/maps.xml
index a3afbf8e7f..987d92989d 100644
--- a/lib/stdlib/doc/src/maps.xml
+++ b/lib/stdlib/doc/src/maps.xml
@@ -38,8 +38,7 @@
       <name name="iterator"/>
       <desc>
         <p>An iterator representing the key value associations in a map.</p>
-        <p>Created using <seealso marker="#iterator-1"><c>maps:iterator/1</c></seealso>
-        and <seealso marker="#iterator-2"><c>maps:iterator/2</c></seealso>.</p>
+        <p>Created using <seealso marker="#iterator-1"><c>maps:iterator/1</c></seealso>.</p>
         <p>Consumed by <seealso marker="#next-1"><c>maps:next/1</c></seealso>,
           <seealso marker="#filter-2"><c>maps:filter/2</c></seealso>,
           <seealso marker="#fold-3"><c>maps:fold/3</c></seealso> and
@@ -194,9 +193,9 @@ false</code>
       <desc>
         <p>Returns a map iterator <c><anno>Iterator</anno></c> that can
           be used by <seealso marker="#next-1"><c>maps:next/1</c></seealso>
-          to traverse the keys and values in a map. This call is equivalent
-          to calling <seealso marker="#iterator-2"><c>maps:iterator/2</c></seealso>
-          with an empty map as the options.</p>
+          to traverse the key-value associations in a map. When iterating
+          over a map, the memory usage is guaranteed to be bounded no matter
+          the size of the map.</p>
         <p>The call fails with a <c>{badmap,Map}</c> exception if
           <c><anno>Map</anno></c> is not a map.</p>
         <p><em>Example:</em></p>
@@ -215,49 +214,6 @@ none</code>
     </func>
 
     <func>
-      <name name="iterator" arity="2"/>
-      <fsummary>Create a map iterator.</fsummary>
-      <desc>
-        <p>Returns a map iterator <c><anno>Iterator</anno></c> that can
-          be used by <seealso marker="#next-1"><c>maps:next/1</c></seealso>
-          to traverse the keys and values in a map. The iterator will behave
-          according to the given <c><anno>Opts</anno></c>.</p>
-        <taglist>
-          <tag>optimize</tag>
-          <item>
-            Configures whether the iterator should be optimized for <c>speed</c>
-            or for <c>memory</c> consumption. Default is <c>speed</c>.
-          </item>
-          <tag>ordered</tag>
-          <item>
-            Configures whether the iterator should return the key value
-            associations ordered on the keys according to erlang term order
-            or not. The default is <c>false</c>.
-          </item>
-        </taglist>
-        <p>Both options can be configured at the same time.</p>
-        <p>The call fails with a <c>{badmap,Map}</c> exception if
-          <c><anno>Map</anno></c> is not a map.</p>
-        <p><em>Example:</em></p>
-        <code type="none">
-> M = maps:from_list([{I,I} || I &lt;- lists:seq(1,50)]).
-#{45 => 45,6 => 6,2 => 2,49 => 49,41 => 41,33 => 33,42 => 42,
-  43 => 43,10 => 10,9 => 9,19 => 19,14 => 14,5 => 5,18 => 18,
-  31 => 31,22 => 22,29 => 29,21 => 21,27 => 27,24 => 24,
-  47 => 47,40 => 40,30 => 30,23 => 23,28 => 28,46 => 46,
-  16 => 16,38 => 38,4 => 4,...}
-> MemoryIter = maps:iterator(M, #{ optimize => memory }), ok.
-ok
-> {K1, V1, _} = maps:next(MemoryIter), {K1, V1}.
-{46,46}
-> OrderedIter = maps:iterator(M, #{ ordered => true, optimize => memory }), ok.
-ok
-> {K2, V2, _} = maps:next(OrderedIter), {K2, V2}.
-{1,1}</code>
-      </desc>
-    </func>
-
-    <func>
       <name name="keys" arity="1"/>
       <fsummary></fsummary>
       <desc>
diff --git a/lib/stdlib/src/maps.erl b/lib/stdlib/src/maps.erl
index 2f2dd41979..a13f340709 100644
--- a/lib/stdlib/src/maps.erl
+++ b/lib/stdlib/src/maps.erl
@@ -24,7 +24,7 @@
          map/2, size/1,
          update_with/3, update_with/4,
          without/2, with/2,
-         iterator/1, iterator/2, next/1]).
+         iterator/1, next/1]).
 
 %% BIFs
 -export([get/2, find/2, from_list/1,
@@ -32,12 +32,14 @@
          new/0, put/3, remove/2, take/2,
          to_list/1, update/3, values/1]).
 
--opaque iterator() :: {non_neg_integer() | none | list(term()), map()}
-                    | list({term(), term()}).
+-opaque iterator() :: {term(), term(), iterator()}
+                      | none | nonempty_improper_list(integer(),map()).
 
 -export_type([iterator/0]).
 
--define(IS_ITERATOR(I), (is_list(I) orelse (is_map(element(2,I) andalso (is_list(element(1,I) orelse is_integer(element(1,I)))))))).
+-dialyzer({no_improper_lists, iterator/1}).
+
+-define(IS_ITERATOR(I), is_tuple(I) andalso tuple_size(I) == 3; I == none; is_integer(hd(I)) andalso is_map(tl(I))).
 
 %% Shadowed by erl_bif_types: maps:get/2
 -spec get(Key,Map) -> Value when
@@ -121,14 +123,20 @@ remove(_,_) -> erlang:nif_error(undef).
 
 take(_,_) -> erlang:nif_error(undef).
 
-%% Shadowed by erl_bif_types: maps:to_list/1
 -spec to_list(Map) -> [{Key,Value}] when
     Map :: map(),
     Key :: term(),
     Value :: term().
 
-to_list(_) -> erlang:nif_error(undef).
+to_list(Map) when is_map(Map) ->
+    to_list_internal(erts_internal:map_next(0, Map, []));
+to_list(Map) ->
+    erlang:error({badmap,Map},[Map]).
 
+to_list_internal([Iter, Map | Acc]) when is_integer(Iter) ->
+    to_list_internal(erts_internal:map_next(Iter, Map, Acc));
+to_list_internal(Acc) ->
+    Acc.
 
 %% Shadowed by erl_bif_types: maps:update/3
 -spec update(Key,Value,Map1) -> Map2 when
@@ -207,7 +215,7 @@ get(Key,Map,Default) ->
       Map :: map().
 
 filter(Pred,Map) when is_function(Pred,2), is_map(Map) ->
-    maps:from_list([{K,V}||{K,V}<-maps:to_list(Map),Pred(K,V)]);
+    maps:from_list(filter_1(Pred, iterator(Map)));
 filter(Pred,Iterator) when is_function(Pred,2), ?IS_ITERATOR(Iterator) ->
     maps:from_list(filter_1(Pred, Iterator));
 filter(Pred,Map) ->
@@ -237,7 +245,7 @@ filter_1(Pred, Iter) ->
     V :: term().
 
 fold(Fun,Init,Map) when is_function(Fun,3), is_map(Map) ->
-    lists:foldl(fun({K,V},A) -> Fun(K,V,A) end,Init,maps:to_list(Map));
+    fold_1(Fun,Init,iterator(Map));
 fold(Fun,Init,Iterator) when is_function(Fun,3), ?IS_ITERATOR(Iterator) ->
     fold_1(Fun,Init,Iterator);
 fold(Fun,Init,Map) ->
@@ -260,7 +268,7 @@ fold_1(Fun, Acc, Iter) ->
     V2 :: term().
 
 map(Fun,Map) when is_function(Fun, 2), is_map(Map) ->
-    maps:from_list([{K,Fun(K,V)}||{K,V}<-maps:to_list(Map)]);
+    maps:from_list(map_1(Fun, iterator(Map)));
 map(Fun,Iterator) when is_function(Fun, 2), ?IS_ITERATOR(Iterator) ->
     maps:from_list(map_1(Fun, Iterator));
 map(Fun,Map) ->
@@ -286,42 +294,19 @@ size(Val) ->
       Map :: map(),
       Iterator :: iterator().
 
-iterator(M) when is_map(M) -> iterator(M, #{});
+iterator(M) when is_map(M) -> [0 | M];
 iterator(M) -> erlang:error({badmap, M}, [M]).
 
--spec iterator(Map, Opts) -> Iterator when
-      Map :: map(),
-      Opts :: #{ ordered => boolean(), optimize => speed | memory },
-      Iterator :: iterator().
-iterator(M, Opts) when is_map(M), is_map(Opts) ->
-    case maps:merge(default_iterator_opts(), Opts) of
-        #{ ordered := true, optimize := speed} -> lists:sort(maps:to_list(M));
-        #{ ordered := false, optimize := speed} -> maps:to_list(M);
-        #{ ordered := true, optimize := memory} -> {lists:sort(maps:keys(M)), M};
-        #{ ordered := false, optimize := memory} -> {0, M}
-    end;
-iterator(M, Opts) when is_map(M) ->
-    erlang:error({badmap, M}, [M, Opts]);
-iterator(M, Opts) ->
-    erlang:error(error_type(M), [M, Opts]).
-
-default_iterator_opts() ->
-    #{ ordered => false, optimize => speed }.
-
 -spec next(Iterator) -> {Key, Value, NextIterator} | 'none' when
       Iterator :: iterator(),
       Key :: term(),
       Value :: term(),
       NextIterator :: iterator().
-next([{K, V} | T]) ->
-    {K, V, T};
-next([]) ->
-    none;
-next({I, M}) when is_map(M), is_integer(I) orelse is_atom(I) ->
-    erts_internal:map_next(I, M);
-next({[K | T], M}) when is_map(M) ->
-    {K, maps:get(K, M), {T, M}};
-next({[], M}) when is_map(M) ->
+next({K, V, I}) ->
+    {K, V, I};
+next([Path | Map]) when is_integer(Path), is_map(Map) ->
+    erts_internal:map_next(Path, Map, iterator);
+next(none) ->
     none;
 next(Iter) ->
     erlang:error(badarg, [Iter]).
diff --git a/lib/stdlib/test/maps_SUITE.erl b/lib/stdlib/test/maps_SUITE.erl
index 0021dd0657..a75751b31d 100644
--- a/lib/stdlib/test/maps_SUITE.erl
+++ b/lib/stdlib/test/maps_SUITE.erl
@@ -30,7 +30,7 @@
 -export([t_update_with_3/1, t_update_with_4/1,
          t_get_3/1, t_filter_2/1,
          t_fold_3/1,t_map_2/1,t_size_1/1,
-         t_iterator_1/1, t_iterator_2/1,
+         t_iterator_1/1,
          t_with_2/1,t_without_2/1]).
 
 %%-define(badmap(V,F,Args), {'EXIT', {{badmap,V}, [{maps,F,Args,_}|_]}}).
@@ -48,7 +48,7 @@ all() ->
     [t_update_with_3,t_update_with_4,
      t_get_3,t_filter_2,
      t_fold_3,t_map_2,t_size_1,
-     t_iterator_1, t_iterator_2,
+     t_iterator_1,
      t_with_2,t_without_2].
 
 t_update_with_3(Config) when is_list(Config) ->
@@ -179,40 +179,19 @@ t_iterator_1(Config) when is_list(Config) ->
 
     %% Large map test
 
-    Vs = lists:seq(1,200),
-    M2 = maps:from_list([{{k,I},I}||I<-Vs]),
+    Vs2 = lists:seq(1,200),
+    M2 = maps:from_list([{{k,I},I}||I<-Vs2]),
     KVList2 = lists:sort(iter_kv(maps:iterator(M2))),
     KVList2 = lists:sort(maps:to_list(M2)),
-    ok.
 
-t_iterator_2(Config) when is_list(Config) ->
-
-    Vs = lists:seq(1,200),
-    Maps = [#{ a => 1, b => 2 }, maps:from_list([{{k,I},I}||I<-Vs])],
-    Optimize = [speed, memory],
-    Ordered = [true, false],
-
-    [test_iterator(Map, Opt, Ord) || Map <- Maps,
-                                     Opt <- Optimize,
-                                     Ord <- Ordered],
+    %% Larger map test
 
+    Vs3 = lists:seq(1,10000),
+    M3 = maps:from_list([{{k,I},I}||I<-Vs3]),
+    KVList3 = lists:sort(iter_kv(maps:iterator(M3))),
+    KVList3 = lists:sort(maps:to_list(M3)),
     ok.
 
-test_iterator(Map, Opt, Ord) ->
-    Opts = #{ optimize => Opt, ordered => Ord },
-    test_iterator_1(maps:iterator(Map, Opts), Map, Opts).
-
-test_iterator_1(Iter, OrigMap, Opts) ->
-    erlang:display(Opts),
-    KVs = iter_kv(Iter),
-    case Opts of
-        #{ ordered := true } ->
-            KVs = lists:sort(maps:to_list(OrigMap));
-        #{ ordered := false } ->
-            OrderedKVs = lists:sort(KVs),
-            OrderedKVs = lists:sort(maps:to_list(OrigMap))
-    end.
-
 iter_kv(I) ->
     case maps:next(I) of
         none ->