Merge branch 'lukas/stdlib/maps_iterators/OTP-14012'

* lukas/stdlib/maps_iterators/OTP-14012:
  erts: Limit size of first iterator for hashmaps
  Update primary bootstrap
  Update preloaded modules
  erts: Remove erts_internal:maps_to_list/2
  stdlib: Make io_lib and io_lib_pretty use maps iterator
  erts: Implement batching maps:iterator
  erts: Implement maps path iterator
  erts: Implement map iterator using a stack
  stdlib: Introduce maps iterator API

Conflicts:
	bootstrap/lib/stdlib/ebin/io_lib.beam
	bootstrap/lib/stdlib/ebin/io_lib_pretty.beam
	erts/emulator/beam/bif.tab
	erts/preloaded/ebin/erlang.beam
	erts/preloaded/ebin/erts_internal.beam
	erts/preloaded/ebin/zlib.beam

35 files changed, 699 insertions, 239 deletions

diff --git a/bootstrap/lib/compiler/ebin/compiler.appup b/bootstrap/lib/compiler/ebin/compiler.appup
index 277b35faa8..2973178217 100644
--- a/bootstrap/lib/compiler/ebin/compiler.appup
+++ b/bootstrap/lib/compiler/ebin/compiler.appup
@@ -16,7 +16,7 @@
 %% limitations under the License.
 %%
 %% %CopyrightEnd%
-{"7.1.1",
+{"7.1.3",
  [{<<".*">>,[{restart_application, compiler}]}],
  [{<<".*">>,[{restart_application, compiler}]}]
 }.
diff --git a/bootstrap/lib/kernel/ebin/dist_util.beam b/bootstrap/lib/kernel/ebin/dist_util.beam
index fd4e4fb5de..27bda597d5 100644
--- a/bootstrap/lib/kernel/ebin/dist_util.beam
+++ b/bootstrap/lib/kernel/ebin/dist_util.beam
diff --git a/bootstrap/lib/kernel/ebin/net_kernel.beam b/bootstrap/lib/kernel/ebin/net_kernel.beam
index 3d59085f05..f4dd56e87e 100644
--- a/bootstrap/lib/kernel/ebin/net_kernel.beam
+++ b/bootstrap/lib/kernel/ebin/net_kernel.beam
diff --git a/bootstrap/lib/stdlib/ebin/io_lib.beam b/bootstrap/lib/stdlib/ebin/io_lib.beam
index 3884967cba..5942331d8d 100644
--- a/bootstrap/lib/stdlib/ebin/io_lib.beam
+++ b/bootstrap/lib/stdlib/ebin/io_lib.beam
diff --git a/bootstrap/lib/stdlib/ebin/io_lib_pretty.beam b/bootstrap/lib/stdlib/ebin/io_lib_pretty.beam
index 183e5b6278..ffda8dcb5b 100644
--- a/bootstrap/lib/stdlib/ebin/io_lib_pretty.beam
+++ b/bootstrap/lib/stdlib/ebin/io_lib_pretty.beam
diff --git a/bootstrap/lib/stdlib/ebin/maps.beam b/bootstrap/lib/stdlib/ebin/maps.beam
index f07f4f922d..50678db509 100644
--- a/bootstrap/lib/stdlib/ebin/maps.beam
+++ b/bootstrap/lib/stdlib/ebin/maps.beam
diff --git a/bootstrap/lib/stdlib/ebin/supervisor.beam b/bootstrap/lib/stdlib/ebin/supervisor.beam
index f7f11b9b26..bd80784a4b 100644
--- a/bootstrap/lib/stdlib/ebin/supervisor.beam
+++ b/bootstrap/lib/stdlib/ebin/supervisor.beam
diff --git a/erts/emulator/beam/atom.names b/erts/emulator/beam/atom.names
index 75a70c3716..cef633bd93 100644
--- a/erts/emulator/beam/atom.names
+++ b/erts/emulator/beam/atom.names
@@ -348,6 +348,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 f739f414de..1bd4acbf95 100644
--- a/erts/emulator/beam/bif.tab
+++ b/erts/emulator/beam/bif.tab
@@ -627,7 +627,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
@@ -682,12 +681,10 @@ bif math:floor/1
 bif math:ceil/1
 bif math:fmod/2
 bif os:set_signal/2
-bif erts_internal:maps_to_list/2
 
 #
 # New in 20.1
 #
-
 bif erlang:iolist_to_iovec/1
 
 #
@@ -696,4 +693,4 @@ bif erlang:iolist_to_iovec/1
 
 bif erts_internal:new_connection/1
 bif erts_internal:abort_connection/2
-
+bif erts_internal:map_next/3
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index f0c54e05f7..8047a9567f 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -91,7 +91,6 @@ static BIF_RETTYPE hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB, int swap_
 static Export hashmap_merge_trap_export;
 static BIF_RETTYPE maps_merge_trap_1(BIF_ALIST_1);
 static Uint hashmap_subtree_size(Eterm node);
-static Eterm hashmap_to_list(Process *p, Eterm map, Sint n);
 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, Eterm *value);
@@ -139,80 +138,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.
- * Never document it.
- * Never encourage its usage.
- *
- * A negative value in ARG 2 means the entire map.
- */
-
-BIF_RETTYPE erts_internal_maps_to_list_2(BIF_ALIST_2) {
-    Sint m;
-    if (term_to_Sint(BIF_ARG_2, &m)) {
-        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);
-
-            if (m >= 0) {
-                n = m < n ? m : n;
-            }
-
-            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, m);
-        }
-        BIF_P->fvalue = BIF_ARG_1;
-        BIF_ERROR(BIF_P, BADMAP);
-    }
-    BIF_ERROR(BIF_P, BADARG);
-}
-
-
 /* maps:find/2
  * return value if key *matches* a key in the map
  */
@@ -1962,45 +1887,31 @@ BIF_RETTYPE maps_values_1(BIF_ALIST_1) {
     BIF_ERROR(BIF_P, BADMAP);
 }
 
-static Eterm hashmap_to_list(Process *p, Eterm node, Sint m) {
-    DECLARE_WSTACK(stack);
-    Eterm *hp, *kv;
-    Eterm tup, res = NIL;
-    Uint n = hashmap_size(node);
-
-    if (m >= 0) {
-        n = m < n ? m : n;
-    }
-
-    hp  = HAlloc(p, n * (2 + 3));
-    hashmap_iterator_init(&stack, node, 0);
-    while (n--) {
-        kv  = hashmap_iterator_next(&stack);
-        ASSERT(kv != NULL);
-	tup = TUPLE2(hp, CAR(kv), CDR(kv));
-	hp += 3;
-	res = CONS(hp, tup, res);
-	hp += 2;
-    }
-    DESTROY_WSTACK(stack);
-    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 +1935,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 +1972,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,6 +2946,363 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[])
 }
 
 
+/**
+ * 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
+ * large we use 4 bits per level in the path.
+ *
+ * So a Path with value 0x110 will first get the 0:th
+ * 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.
+ *
+ * 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
+#define PATH_ELEM_MASK 0xf
+#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_3(BIF_ALIST_3) {
+
+    Eterm path, map;
+    enum { iterator, list } type;
+
+    path = BIF_ARG_1;
+    map  = BIF_ARG_2;
+
+    if (!is_map(map))
+        BIF_ERROR(BIF_P, BADARG);
+
+    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)) {
+        Uint n;
+	Eterm *ks,*vs, res, *hp;
+	flatmap_t *mp = (flatmap_t*)flatmap_val(map);
+
+	ks  = flatmap_get_keys(mp);
+	vs  = flatmap_get_values(mp);
+	n   = flatmap_get_size(mp);
+
+        if (!is_small(BIF_ARG_1) || n < unsigned_val(BIF_ARG_1))
+            BIF_ERROR(BIF_P, BADARG);
+
+        if (type == iterator) {
+            hp  = HAlloc(BIF_P, 4 * n);
+            res = am_none;
+
+            while(n--) {
+                res = TUPLE3(hp, ks[n], vs[n], res); hp += 4;
+            }
+        } else {
+            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, elems, orig_elems;
+        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));
+
+/* 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.
+ *
+ * Also, when the path is 0 (i.e. for the first call) we limit the number of
+ * elements to MAP_SMALL_MAP_LIMIT in order to not use a huge amount of heap
+ * when only the first X associations in the hashmap was needed.
+ */
+#if defined(DEBUG)
+#define FCALLS_ELEMS(BIF_P) ((BIF_P->fcalls / 4) & 0xF)
+#else
+#define FCALLS_ELEMS(BIF_P) (BIF_P->fcalls / 4)
+#endif
+
+        if (MAX(FCALLS_ELEMS(BIF_P), 1) < hashmap_size(map))
+            elems = MAX(FCALLS_ELEMS(BIF_P), 1);
+        else
+            elems = hashmap_size(map);
+
+#undef FCALLS_ELEMS
+
+        if (is_small(path)) {
+            curr_path = unsigned_val(path);
+
+            if (curr_path == 0 && elems > MAP_SMALL_MAP_LIMIT) {
+                elems = MAP_SMALL_MAP_LIMIT;
+            }
+        } else if (is_big(path)) {
+            Eterm *big = big_val(path);
+            if (bignum_header_is_neg(*big))
+                BIF_ERROR(BIF_P, BADARG);
+            path_length = BIG_ARITY(big) - 1;
+            curr_path = BIG_DIGIT(big,  0);
+            path_rest = BIG_V(big) + 1;
+        } else {
+            BIF_ERROR(BIF_P, BADARG);
+        }
+
+        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 * elems);
+            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) * elems);
+            res = BIF_ARG_3;
+        }
+
+        orig_elems = elems;
+
+        /* 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 to use later. */
+        for (i = 1; ; i++) {
+            Eterm *ptr = hashmap_val(node),
+                hdr = *ptr++;
+            Uint sz;
+
+            sz = hashmap_node_size(hdr, &ptr);
+
+            if (PATH_ELEM(curr_path) >= sz)
+                goto badarg;
+
+            WSTACK_PUSH4(stack, node, PATH_ELEM(curr_path)+1, sz, (UWord)ptr);
+
+            /* We have found a leaf, return it and the next X elements */
+            if (is_list(ptr[PATH_ELEM(curr_path)])) {
+                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;
+            }
+
+            node = ptr[PATH_ELEM(curr_path)];
+
+            curr_path >>= PATH_ELEM_SIZE;
+
+            if (i == PATH_ELEMS_PER_DIGIT) {
+                /* Switch to next bignum word if available,
+                   otherwise just follow 0 path */
+                i = 0;
+                if (path_length) {
+                    curr_path = *path_rest;
+                    path_length--;
+                    path_rest++;
+                } else {
+                    curr_path = 0;
+                }
+            }
+        }
+
+        /* 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);
+
+            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 (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);
+                }
+            }
+
+            /* There are no more element in the hashmap */
+            if (WSTACK_ISEMPTY(stack)) {
+                break;
+            }
+
+        }
+
+        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) {
+                /* We need multiple ErtsDigit's to represent the path */
+                int big_size = BIG_NEED_FOR_BITS(depth * PATH_ELEM_SIZE);
+                hp = HAlloc(BIF_P, big_size);
+                hp[0] = make_pos_bignum_header(big_size - BIG_NEED_SIZE(0));
+                path_digits = hp + big_size - 1;
+            }
+
+
+            /* Pop the stack to create the complete path to the next leaf */
+            while(!WSTACK_ISEMPTY(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;
+                }
+
+                curr_path <<= PATH_ELEM_SIZE;
+                curr_path |= idx;
+            }
+
+            if (path_digits) {
+                path_digits[0] = curr_path;
+                path = make_big(hp);
+            } else {
+                /* 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 * (orig_elems - 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 * (orig_elems - elems);
+        DESTROY_WSTACK(stack);
+        BIF_ERROR(BIF_P, BADARG);
+    }
+}
+
 /* implementation of builtin emulations */
 
 #if !ERTS_AT_LEAST_GCC_VSN__(3, 4, 0)
diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h
index c3ccf80b85..718d400e22 100644
--- a/erts/emulator/beam/erl_map.h
+++ b/erts/emulator/beam/erl_map.h
@@ -64,7 +64,6 @@ typedef struct flatmap_s {
 #define hashmap_shift_hash(Heap,Hx,Lvl,Key) \
     (((++(Lvl)) & 7) ? (Hx) >> 4 : hashmap_make_hash(CONS(Heap, make_small((Lvl)>>3), Key)))
 
-
 /* erl_term.h stuff */
 #define flatmap_get_values(x)        (((Eterm *)(x)) + sizeof(flatmap_t)/sizeof(Eterm))
 #define flatmap_get_keys(x)          (((Eterm *)tuple_val(((flatmap_t *)(x))->keys)) + 1)
diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl
index 02f3c89318..c9e971af8a 100644
--- a/erts/emulator/test/map_SUITE.erl
+++ b/erts/emulator/test/map_SUITE.erl
@@ -52,7 +52,7 @@
          t_bif_map_values/1,
          t_bif_map_to_list/1,
          t_bif_map_from_list/1,
-         t_bif_erts_internal_maps_to_list/1,
+         t_bif_map_next/1,
 
          %% erlang
          t_erlang_hash/1,
@@ -119,7 +119,7 @@ all() -> [t_build_and_match_literals, t_build_and_match_literals_large,
           t_bif_map_update,
           t_bif_map_values,
           t_bif_map_to_list, t_bif_map_from_list,
-          t_bif_erts_internal_maps_to_list,
+          t_bif_map_next,
 
           %% erlang
           t_erlang_hash, t_map_encode_decode,
@@ -2364,41 +2364,71 @@ 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),
+t_bif_map_next(Config) when is_list(Config) ->
 
-    %% 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(<<>>))),
+    erts_debug:set_internal_state(available_internal_state, true),
+
+    try
+
+        none = maps:next(maps:iterator(id(#{}))),
+
+        verify_iterator(#{}),
+        verify_iterator(#{a => 1, b => 2, c => 3}),
+
+        %% Use fatmap in order to test iterating in very deep maps
+        FM = fatmap(43),
+        verify_iterator(FM),
+
+        {'EXIT', {{badmap,[{a,b},b]},_}} = (catch maps:iterator(id([{a,b},b]))),
+        {'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([-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
+            erts_debug:set_internal_state(available_internal_state, false)
+    end.
+
+verify_iterator(Map) ->
+    KVs = t_fold(fun(K, V, A) -> [{K, V} | A] end, [], Map),
+
+    %% Verify that KVs created by iterating Map is of
+    %% correct size and contains all elements
+    true = length(KVs) == maps:size(Map),
+    [maps:get(K, Map) || {K, _} <- KVs],
     ok.
 
+
+t_fold(Fun, Init, Map) ->
+    t_fold_1(Fun, Init, maps:iterator(Map)).
+
+t_fold_1(Fun, Acc, Iter) ->
+    case maps:next(Iter) of
+        {K, V, NextIter} ->
+            t_fold_1(Fun, Fun(K,V,Acc), NextIter);
+        none ->
+            Acc
+    end.
+
 t_bif_build_and_check(Config) when is_list(Config) ->
     ok = check_build_and_remove(750,[fun(K) -> [K,K] end,
 				     fun(K) -> [float(K),K] end,
diff --git a/erts/preloaded/ebin/erl_prim_loader.beam b/erts/preloaded/ebin/erl_prim_loader.beam
index af6facb5f2..198032c18d 100644
--- a/erts/preloaded/ebin/erl_prim_loader.beam
+++ b/erts/preloaded/ebin/erl_prim_loader.beam
diff --git a/erts/preloaded/ebin/erl_tracer.beam b/erts/preloaded/ebin/erl_tracer.beam
index 7ca25803be..7754d64a6b 100644
--- a/erts/preloaded/ebin/erl_tracer.beam
+++ b/erts/preloaded/ebin/erl_tracer.beam
diff --git a/erts/preloaded/ebin/erlang.beam b/erts/preloaded/ebin/erlang.beam
index 01ed412562..7ee47ee023 100644
--- a/erts/preloaded/ebin/erlang.beam
+++ b/erts/preloaded/ebin/erlang.beam
diff --git a/erts/preloaded/ebin/erts_code_purger.beam b/erts/preloaded/ebin/erts_code_purger.beam
index b7c061d9a0..655e1d2e06 100644
--- a/erts/preloaded/ebin/erts_code_purger.beam
+++ b/erts/preloaded/ebin/erts_code_purger.beam
diff --git a/erts/preloaded/ebin/erts_dirty_process_code_checker.beam b/erts/preloaded/ebin/erts_dirty_process_code_checker.beam
index 6467b1c016..2a4cb53d3e 100644
--- a/erts/preloaded/ebin/erts_dirty_process_code_checker.beam
+++ b/erts/preloaded/ebin/erts_dirty_process_code_checker.beam
diff --git a/erts/preloaded/ebin/erts_internal.beam b/erts/preloaded/ebin/erts_internal.beam
index cb8e6b6d69..f8871c63eb 100644
--- a/erts/preloaded/ebin/erts_internal.beam
+++ b/erts/preloaded/ebin/erts_internal.beam
diff --git a/erts/preloaded/ebin/erts_literal_area_collector.beam b/erts/preloaded/ebin/erts_literal_area_collector.beam
index fbd3249d70..bb2676a9e8 100644
--- a/erts/preloaded/ebin/erts_literal_area_collector.beam
+++ b/erts/preloaded/ebin/erts_literal_area_collector.beam
diff --git a/erts/preloaded/ebin/init.beam b/erts/preloaded/ebin/init.beam
index 1c8d0e626a..fb4fc67148 100644
--- a/erts/preloaded/ebin/init.beam
+++ b/erts/preloaded/ebin/init.beam
diff --git a/erts/preloaded/ebin/otp_ring0.beam b/erts/preloaded/ebin/otp_ring0.beam
index 73a017d981..6a03451ad5 100644
--- a/erts/preloaded/ebin/otp_ring0.beam
+++ b/erts/preloaded/ebin/otp_ring0.beam
diff --git a/erts/preloaded/ebin/prim_eval.beam b/erts/preloaded/ebin/prim_eval.beam
index 7e46b79671..17c59708e7 100644
--- a/erts/preloaded/ebin/prim_eval.beam
+++ b/erts/preloaded/ebin/prim_eval.beam
diff --git a/erts/preloaded/ebin/prim_file.beam b/erts/preloaded/ebin/prim_file.beam
index 32755d5c28..eb326ac4b6 100644
--- a/erts/preloaded/ebin/prim_file.beam
+++ b/erts/preloaded/ebin/prim_file.beam
diff --git a/erts/preloaded/ebin/prim_inet.beam b/erts/preloaded/ebin/prim_inet.beam
index c03415c758..32b104ae95 100644
--- a/erts/preloaded/ebin/prim_inet.beam
+++ b/erts/preloaded/ebin/prim_inet.beam
diff --git a/erts/preloaded/ebin/prim_zip.beam b/erts/preloaded/ebin/prim_zip.beam
index 77d0d2edb0..1ec6870178 100644
--- a/erts/preloaded/ebin/prim_zip.beam
+++ b/erts/preloaded/ebin/prim_zip.beam
diff --git a/erts/preloaded/ebin/zlib.beam b/erts/preloaded/ebin/zlib.beam
index 4ad5f37434..7a5f4d7527 100644
--- a/erts/preloaded/ebin/zlib.beam
+++ b/erts/preloaded/ebin/zlib.beam
diff --git a/erts/preloaded/src/erts_internal.erl b/erts/preloaded/src/erts_internal.erl
index 1f5c88c4b9..ffa9217c4d 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/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]).
 
@@ -370,20 +370,23 @@ term_type(_T) ->
 map_hashmap_children(_M) ->
     erlang:nif_error(undefined).
 
+%% return the next assoc in the iterator and a new iterator
+-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, _A) ->
+    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(),
-    N :: integer(),
-    Pairs :: list().
-
-maps_to_list(_M, _N) ->
-    erlang:nif_error(undefined).
-
 %% erlang:demonitor(Ref, [flush]) traps to
 %% erts_internal:flush_monitor_messages(Ref, Res) when
 %% it needs to flush monitor messages.
diff --git a/lib/dialyzer/test/small_SUITE_data/results/maps_sum b/lib/dialyzer/test/small_SUITE_data/results/maps_sum
index bd192bdb93..b29ac77d88 100644
--- a/lib/dialyzer/test/small_SUITE_data/results/maps_sum
+++ b/lib/dialyzer/test/small_SUITE_data/results/maps_sum
@@ -1,4 +1,4 @@
 
-maps_sum.erl:15: Invalid type specification for function maps_sum:wrong1/1. The success typing is (map()) -> any()
+maps_sum.erl:15: Invalid type specification for function maps_sum:wrong1/1. The success typing is (maps:iterator() | map()) -> any()
 maps_sum.erl:26: Function wrong2/1 has no local return
 maps_sum.erl:27: The call lists:foldl(fun((_,_,_) -> any()),0,Data::any()) will never return since it differs in the 1st argument from the success typing arguments: (fun((_,_) -> any()),any(),[any()])
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 8c7270816b..987d92989d 100644
--- a/lib/stdlib/doc/src/maps.xml
+++ b/lib/stdlib/doc/src/maps.xml
@@ -33,16 +33,31 @@
     <p>This module contains functions for maps processing.</p>
   </description>
 
+  <datatypes>
+    <datatype>
+      <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>.</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
+          <seealso marker="#map-2"><c>maps:map/2</c></seealso>.</p>
+      </desc>
+    </datatype>
+  </datatypes>
+
   <funcs>
     <func>
       <name name="filter" arity="2"/>
       <fsummary>Select pairs that satisfy a predicate.</fsummary>
       <desc>
-        <p>Returns a map <c><anno>Map2</anno></c> for which predicate
-          <c><anno>Pred</anno></c> holds true in <c><anno>Map1</anno></c>.</p>
+        <p>Returns a map <c><anno>Map</anno></c> for which predicate
+          <c><anno>Pred</anno></c> holds true in <c><anno>MapOrIter</anno></c>.</p>
         <p>The call fails with a <c>{badmap,Map}</c> exception if
-          <c><anno>Map1</anno></c> is not a map, or with <c>badarg</c> if
-          <c><anno>Pred</anno></c> is not a function of arity 2.</p>
+          <c><anno>MapOrIter</anno></c> is not a map or valid iterator,
+          or with <c>badarg</c> if <c><anno>Pred</anno></c> is not a
+          function of arity 2.</p>
         <p><em>Example:</em></p>
         <code type="none">
 > M = #{a => 2, b => 3, c=> 4, "a" => 1, "b" => 2, "c" => 4},
@@ -76,12 +91,16 @@
       <fsummary></fsummary>
       <desc>
         <p>Calls <c>F(K, V, AccIn)</c> for every <c><anno>K</anno></c> to value
-          <c><anno>V</anno></c> association in <c><anno>Map</anno></c> in
+          <c><anno>V</anno></c> association in <c><anno>MapOrIter</anno></c> in
           any order. Function <c>fun F/3</c> must return a new
           accumulator, which is passed to the next successive call.
           This function returns the final value of the accumulator. The initial
           accumulator value <c><anno>Init</anno></c> is returned if the map is
           empty.</p>
+        <p>The call fails with a <c>{badmap,Map}</c> exception if
+          <c><anno>MapOrIter</anno></c> is not a map or valid iterator,
+          or with <c>badarg</c> if <c><anno>Fun</anno></c> is not a
+          function of arity 3.</p>
         <p><em>Example:</em></p>
         <code type="none">
 > Fun = fun(K,V,AccIn) when is_list(K) -> AccIn + V end,
@@ -169,6 +188,32 @@ false</code>
     </func>
 
     <func>
+      <name name="iterator" arity="1"/>
+      <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 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>
+        <code type="none">
+> M = #{ a => 1, b => 2 }.
+#{a => 1,b => 2}
+> I = maps:iterator(M).
+[{a,1},{b,2}]
+> {K1, V1, I2} = maps:next(I).
+{a,1,[{b,2}]}
+> {K2, V2, I3} = maps:next(I2).
+{b,2,[]}
+> maps:next(I3).
+none</code>
+      </desc>
+    </func>
+
+    <func>
       <name name="keys" arity="1"/>
       <fsummary></fsummary>
       <desc>
@@ -188,12 +233,16 @@ false</code>
       <name name="map" arity="2"/>
       <fsummary></fsummary>
       <desc>
-        <p>Produces a new map <c><anno>Map2</anno></c> by calling function
+        <p>Produces a new map <c><anno>Map</anno></c> by calling function
           <c>fun F(K, V1)</c> for every <c><anno>K</anno></c> to value
-          <c><anno>V1</anno></c> association in <c><anno>Map1</anno></c> in
+          <c><anno>V1</anno></c> association in <c><anno>MapOrIter</anno></c> in
           any order. Function <c>fun F/2</c> must return value
           <c><anno>V2</anno></c> to be associated with key <c><anno>K</anno></c>
-          for the new map <c><anno>Map2</anno></c>.</p>
+          for the new map <c><anno>Map</anno></c>.</p>
+        <p>The call fails with a <c>{badmap,Map}</c> exception if
+          <c><anno>MapOrIter</anno></c> is not a map or valid iterator,
+          or with <c>badarg</c> if <c><anno>Fun</anno></c> is not a
+          function of arity 2.</p>
         <p><em>Example:</em></p>
         <code type="none">
 > Fun = fun(K,V1) when is_list(K) -> V1*2 end,
@@ -234,6 +283,35 @@ false</code>
     </func>
 
     <func>
+      <name name="next" arity="1"/>
+      <fsummary>Get the next key and value from an iterator.</fsummary>
+      <desc>
+        <p>Returns the next key-value association in
+          <c><anno>Iterator</anno></c> and a new iterator for the
+          remaining associations in the iterator.
+        </p>
+        <p>
+          If there are no more associations in the iterator,
+          <c>none</c> is returned.
+        </p>
+        <p><em>Example:</em></p>
+        <code type="none">
+> Map = #{a => 1, b => 2, c => 3}.
+#{a => 1,b => 2,c => 3}
+> Iter = maps:iterator(Map).
+[{a,1},{b,2},{c,3}]
+> {_, _, Iter1} = maps:next(Iter).
+{a,1,[{b,2},{c,3}]}
+> {_, _, Iter2} = maps:next(Iter1).
+{b,2,[{c,3}]}
+> {_, _, Iter3} = maps:next(Iter2).
+{c,3,[]}
+> maps:next(Iter3).
+none</code>
+      </desc>
+    </func>
+
+    <func>
       <name name="put" arity="3"/>
       <fsummary></fsummary>
       <desc>
diff --git a/lib/stdlib/src/io_lib.erl b/lib/stdlib/src/io_lib.erl
index 9d447418f8..3c8430b820 100644
--- a/lib/stdlib/src/io_lib.erl
+++ b/lib/stdlib/src/io_lib.erl
@@ -963,7 +963,18 @@ limit_tail(Other, D) ->
 %% maps:from_list() creates a map with the same internal ordering of
 %% the selected associations as in Map.
 limit_map(Map, D) ->
-    maps:from_list(erts_internal:maps_to_list(Map, D)).
+    limit_map(maps:iterator(Map), D, []).
+
+limit_map(_I, 0, Acc) ->
+    maps:from_list(Acc);
+limit_map(I, D, Acc) ->
+    case maps:next(I) of
+        {K, V, NextI} ->
+            limit_map(NextI, D-1, [{K,V} | Acc]);
+        none ->
+            maps:from_list(Acc)
+    end.
+
 %%     maps:from_list(limit_map_body(erts_internal:maps_to_list(Map, D), D)).
 
 %% limit_map_body(_, 0) -> [{'...', '...'}];
diff --git a/lib/stdlib/src/io_lib_pretty.erl b/lib/stdlib/src/io_lib_pretty.erl
index 505613b80e..89e1931d2d 100644
--- a/lib/stdlib/src/io_lib_pretty.erl
+++ b/lib/stdlib/src/io_lib_pretty.erl
@@ -478,9 +478,19 @@ print_length(Term, _D, _RF, _Enc, _Str) ->
 print_length_map(_Map, 1, _RF, _Enc, _Str) ->
     {"#{...}", 6};
 print_length_map(Map, D, RF, Enc, Str) when is_map(Map) ->
-    Pairs = print_length_map_pairs(erts_internal:maps_to_list(Map, D), D, RF, Enc, Str),
+    Pairs = print_length_map_pairs(limit_map(maps:iterator(Map), D, []), D, RF, Enc, Str),
     {{map, Pairs}, list_length(Pairs, 3)}.
 
+limit_map(_I, 0, Acc) ->
+    Acc;
+limit_map(I, D, Acc) ->
+    case maps:next(I) of
+        {K, V, NextI} ->
+            limit_map(NextI, D-1, [{K,V} | Acc]);
+        none ->
+            Acc
+    end.
+
 print_length_map_pairs([], _D, _RF, _Enc, _Str) ->
     [];
 print_length_map_pairs(_Pairs, 1, _RF, _Enc, _Str) ->
diff --git a/lib/stdlib/src/maps.erl b/lib/stdlib/src/maps.erl
index 5dafdb282a..a13f340709 100644
--- a/lib/stdlib/src/maps.erl
+++ b/lib/stdlib/src/maps.erl
@@ -23,7 +23,8 @@
 -export([get/3, filter/2,fold/3,
          map/2, size/1,
          update_with/3, update_with/4,
-         without/2, with/2]).
+         without/2, with/2,
+         iterator/1, next/1]).
 
 %% BIFs
 -export([get/2, find/2, from_list/1,
@@ -31,6 +32,15 @@
          new/0, put/3, remove/2, take/2,
          to_list/1, update/3, values/1]).
 
+-opaque iterator() :: {term(), term(), iterator()}
+                      | none | nonempty_improper_list(integer(),map()).
+
+-export_type([iterator/0]).
+
+-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
     Key :: term(),
@@ -39,7 +49,6 @@
 
 get(_,_) -> erlang:nif_error(undef).
 
-
 -spec find(Key,Map) -> {ok, Value} | error when
     Key :: term(),
     Map :: map(),
@@ -114,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
@@ -192,47 +207,80 @@ get(Key,Map,Default) ->
     erlang:error({badmap,Map},[Key,Map,Default]).
 
 
--spec filter(Pred,Map1) -> Map2 when
+-spec filter(Pred,MapOrIter) -> Map when
       Pred :: fun((Key, Value) -> boolean()),
       Key  :: term(),
       Value :: term(),
-      Map1 :: map(),
-      Map2 :: map().
+      MapOrIter :: map() | iterator(),
+      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) ->
     erlang:error(error_type(Map),[Pred,Map]).
 
-
--spec fold(Fun,Init,Map) -> Acc when
+filter_1(Pred, Iter) ->
+    case next(Iter) of
+        {K, V, NextIter} ->
+            case Pred(K,V) of
+                true ->
+                    [{K,V} | filter_1(Pred, NextIter)];
+                false ->
+                    filter_1(Pred, NextIter)
+            end;
+        none ->
+            []
+    end.
+
+-spec fold(Fun,Init,MapOrIter) -> Acc when
     Fun :: fun((K, V, AccIn) -> AccOut),
     Init :: term(),
     Acc :: term(),
     AccIn :: term(),
     AccOut :: term(),
-    Map :: map(),
+    MapOrIter :: map() | iterator(),
     K :: term(),
     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) ->
     erlang:error(error_type(Map),[Fun,Init,Map]).
 
--spec map(Fun,Map1) -> Map2 when
+fold_1(Fun, Acc, Iter) ->
+    case next(Iter) of
+        {K, V, NextIter} ->
+            fold_1(Fun, Fun(K,V,Acc), NextIter);
+        none ->
+            Acc
+    end.
+
+-spec map(Fun,MapOrIter) -> Map when
     Fun :: fun((K, V1) -> V2),
-    Map1 :: map(),
-    Map2 :: map(),
+    MapOrIter :: map() | iterator(),
+    Map :: map(),
     K :: term(),
     V1 :: term(),
     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) ->
     erlang:error(error_type(Map),[Fun,Map]).
 
+map_1(Fun, Iter) ->
+    case next(Iter) of
+        {K, V, NextIter} ->
+            [{K, Fun(K, V)} | map_1(Fun, NextIter)];
+        none ->
+            []
+    end.
 
 -spec size(Map) -> non_neg_integer() when
     Map :: map().
@@ -242,6 +290,26 @@ size(Map) when is_map(Map) ->
 size(Val) ->
     erlang:error({badmap,Val},[Val]).
 
+-spec iterator(Map) -> Iterator when
+      Map :: map(),
+      Iterator :: iterator().
+
+iterator(M) when is_map(M) -> [0 | M];
+iterator(M) -> erlang:error({badmap, M}, [M]).
+
+-spec next(Iterator) -> {Key, Value, NextIterator} | 'none' when
+      Iterator :: iterator(),
+      Key :: term(),
+      Value :: term(),
+      NextIterator :: iterator().
+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]).
 
 -spec without(Ks,Map1) -> Map2 when
     Ks :: [K],
@@ -250,11 +318,10 @@ size(Val) ->
     K :: term().
 
 without(Ks,M) when is_list(Ks), is_map(M) ->
-    lists:foldl(fun(K, M1) -> ?MODULE:remove(K, M1) end, M, Ks);
+    lists:foldl(fun(K, M1) -> maps:remove(K, M1) end, M, Ks);
 without(Ks,M) ->
     erlang:error(error_type(M),[Ks,M]).
 
-
 -spec with(Ks, Map1) -> Map2 when
     Ks :: [K],
     Map1 :: map(),
@@ -263,17 +330,17 @@ without(Ks,M) ->
 
 with(Ks,Map1) when is_list(Ks), is_map(Map1) ->
     Fun = fun(K, List) ->
-      case ?MODULE:find(K, Map1) of
-          {ok, V} ->
-              [{K, V} | List];
-          error ->
-              List
-      end
-    end,
-    ?MODULE:from_list(lists:foldl(Fun, [], Ks));
+                  case maps:find(K, Map1) of
+                      {ok, V} ->
+                          [{K, V} | List];
+                      error ->
+                          List
+                  end
+          end,
+    maps:from_list(lists:foldl(Fun, [], Ks));
 with(Ks,M) ->
     erlang:error(error_type(M),[Ks,M]).
 
 
-error_type(M) when is_map(M) -> badarg;
+error_type(M) when is_map(M); ?IS_ITERATOR(M) -> badarg;
 error_type(V) -> {badmap, V}.
diff --git a/lib/stdlib/test/io_SUITE.erl b/lib/stdlib/test/io_SUITE.erl
index e2c73371cd..13929bdbb6 100644
--- a/lib/stdlib/test/io_SUITE.erl
+++ b/lib/stdlib/test/io_SUITE.erl
@@ -2138,8 +2138,8 @@ otp_14175(_Config) ->
     "#{}" = p(#{}, 1),
     "#{...}" = p(#{a => 1}, 1),
     "#{#{} => a}" = p(#{#{} => a}, 2),
-    "#{a => 1,...}" = p(#{a => 1, b => 2}, 2),
-    "#{a => 1,b => 2}" = p(#{a => 1, b => 2}, -1),
+    mt("#{a => 1,...}", p(#{a => 1, b => 2}, 2)),
+    mt("#{a => 1,b => 2}", p(#{a => 1, b => 2}, -1)),
 
     M = #{kaaaaaaaaaaaaaaaaaaa => v1,kbbbbbbbbbbbbbbbbbbb => v2,
           kccccccccccccccccccc => v3,kddddddddddddddddddd => v4,
diff --git a/lib/stdlib/test/maps_SUITE.erl b/lib/stdlib/test/maps_SUITE.erl
index 42e669a799..a75751b31d 100644
--- a/lib/stdlib/test/maps_SUITE.erl
+++ b/lib/stdlib/test/maps_SUITE.erl
@@ -30,6 +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_with_2/1,t_without_2/1]).
 
 %%-define(badmap(V,F,Args), {'EXIT', {{badmap,V}, [{maps,F,Args,_}|_]}}).
@@ -47,6 +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_with_2,t_without_2].
 
 t_update_with_3(Config) when is_list(Config) ->
@@ -127,6 +129,8 @@ t_filter_2(Config) when is_list(Config) ->
     Pred2 = fun(K,V) -> is_list(K) andalso (V rem 2) =:= 0 end,
     #{a := 2,c := 4} = maps:filter(Pred1,M),
     #{"b" := 2,"c" := 4} = maps:filter(Pred2,M),
+    #{a := 2,c := 4} = maps:filter(Pred1,maps:iterator(M)),
+    #{"b" := 2,"c" := 4} = maps:filter(Pred2,maps:iterator(M)),
     %% error case
     ?badmap(a,filter,[_,a]) = (catch maps:filter(fun(_,_) -> ok end,id(a))),
     ?badarg(filter,[<<>>,#{}]) = (catch maps:filter(id(<<>>),#{})),
@@ -139,6 +143,8 @@ t_fold_3(Config) when is_list(Config) ->
     Tot0 = lists:sum(Vs),
     Tot1 = maps:fold(fun({k,_},V,A) -> A + V end, 0, M0),
     true = Tot0 =:= Tot1,
+    Tot2 = maps:fold(fun({k,_},V,A) -> A + V end, 0, maps:iterator(M0)),
+    true = Tot0 =:= Tot2,
 
     %% error case
     ?badmap(a,fold,[_,0,a]) = (catch maps:fold(fun(_,_,_) -> ok end,0,id(a))),
@@ -151,12 +157,48 @@ t_map_2(Config) when is_list(Config) ->
     #{ {k,1} := 1, {k,200} := 200} = M0,
     M1 = maps:map(fun({k,_},V) -> V + 42 end, M0),
     #{ {k,1} := 43, {k,200} := 242} = M1,
+    M2 = maps:map(fun({k,_},V) -> V + 42 end, maps:iterator(M0)),
+    #{ {k,1} := 43, {k,200} := 242} = M2,
 
     %% error case
     ?badmap(a,map,[_,a]) = (catch maps:map(fun(_,_) -> ok end, id(a))),
     ?badarg(map,[<<>>,#{}]) = (catch maps:map(id(<<>>),#{})),
     ok.
 
+t_iterator_1(Config) when is_list(Config) ->
+
+    %% Small map test
+    M0 = #{ a => 1, b => 2 },
+    I0 = maps:iterator(M0),
+    {K1,V1,I1} = maps:next(I0),
+    {K2,V2,I2} = maps:next(I1),
+    none = maps:next(I2),
+
+    KVList = lists:sort([{K1,V1},{K2,V2}]),
+    KVList = lists:sort(maps:to_list(M0)),
+
+    %% Large map test
+
+    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)),
+
+    %% 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.
+
+iter_kv(I) ->
+    case maps:next(I) of
+        none ->
+            [];
+        {K,V,NI} ->
+            [{K,V} | iter_kv(NI)]
+    end.
 
 t_size_1(Config) when is_list(Config) ->
       0 = maps:size(#{}),