From d945d6f1c71d5442a25e4be60f84fc49ae8b6b4e Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Tue, 19 Sep 2017 12:01:09 +0200 Subject: stdlib: Introduce maps iterator API --- lib/stdlib/src/maps.erl | 76 ++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 62 insertions(+), 14 deletions(-) diff --git a/lib/stdlib/src/maps.erl b/lib/stdlib/src/maps.erl index 5dafdb282a..7ed32a3988 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,10 @@ new/0, put/3, remove/2, take/2, to_list/1, update/3, values/1]). +-opaque iterator() :: [{term(), term()}]. + +-export_type([iterator/0]). + %% Shadowed by erl_bif_types: maps:get/2 -spec get(Key,Map) -> Value when Key :: term(), @@ -200,10 +205,22 @@ get(Key,Map,Default) -> Map2 :: 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,Map) -> erlang:error(error_type(Map),[Pred,Map]). +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,Map) -> Acc when Fun :: fun((K, V, AccIn) -> AccOut), @@ -216,10 +233,18 @@ filter(Pred,Map) -> 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,Map) -> erlang:error(error_type(Map),[Fun,Init,Map]). +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,Map1) -> Map2 when Fun :: fun((K, V1) -> V2), Map1 :: map(), @@ -229,10 +254,17 @@ fold(Fun,Init,Map) -> 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,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 +274,23 @@ size(Map) when is_map(Map) -> size(Val) -> erlang:error({badmap,Val},[Val]). +-spec iterator(Map) -> Iterator when + Map :: map(), + Iterator :: iterator(). + +iterator(Map) when is_map(Map) -> + maps:to_list(Map); +iterator(M) -> + erlang:error(error_type(M),[M]). + +-spec next(Iterator) -> {K,V,NextIterator} | 'none' when + Iterator :: iterator(), + K :: term(), + V :: term(), + NextIterator :: iterator(). +next([]) -> none; +next([{K, V} | I]) -> + {K, V, I}. -spec without(Ks,Map1) -> Map2 when Ks :: [K], @@ -250,11 +299,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,14 +311,14 @@ 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]). -- cgit v1.2.3 From 513a322941d208d9dcdc4c39db2966ae4c707fe7 Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Tue, 19 Sep 2017 14:37:59 +0200 Subject: erts: Implement map iterator using a stack This version does not work great as the subtrees created are not proper hash maps. Also it is not all that performant as the extra allocations to keep the stack there is expensive. --- erts/emulator/beam/bif.tab | 1 + erts/emulator/beam/erl_map.c | 72 ++++++++++++++++++++++++++++++++++++++++++-- erts/emulator/beam/erl_map.h | 3 +- lib/stdlib/src/maps.erl | 13 ++++++-- 4 files changed, 84 insertions(+), 5 deletions(-) diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab index f7b4451890..4ee5af14bc 100644 --- a/erts/emulator/beam/bif.tab +++ b/erts/emulator/beam/bif.tab @@ -691,3 +691,4 @@ bif erts_internal:maps_to_list/2 # bif erlang:iolist_to_iovec/1 +bif erts_internal:map_get_index/2 \ No newline at end of file diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index f0c54e05f7..37fcedbc6d 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -90,7 +90,6 @@ static BIF_RETTYPE hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB, int swap_ struct HashmapMergeContext_*); 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); @@ -1519,7 +1518,7 @@ trap: /* Yield */ return trap_ret; } -static Uint hashmap_subtree_size(Eterm node) { +Uint hashmap_subtree_size(Eterm node) { DECLARE_WSTACK(stack); Uint size = 0; @@ -3060,6 +3059,75 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]) return res; } +static Uint32 +index_to_hash(Sint idx, Uint32 hval) +{ + Uint32 new_hval = 1; + while (1) { + if (hval & 0x1) { + idx--; + if (!idx) break; + } + new_hval = new_hval << 1; + hval = hval >> 1; + } + return new_hval; +} + +BIF_RETTYPE erts_internal_map_get_index_2(BIF_ALIST_2) { + Sint idx; + Uint32 hval, sz; + Eterm *ptr, hdr; + + if (!is_hashmap(BIF_ARG_2) || is_not_small(BIF_ARG_1)) + BIF_ERROR(BIF_P, BADARG); + + idx = signed_val(BIF_ARG_1); + + if (idx < 1 || idx > 17) + BIF_ERROR(BIF_P, BADARG); + + ASSERT(is_boxed(BIF_ARG_2)); + + ptr = boxed_val(BIF_ARG_2); +again: + hdr = *ptr; + + switch(hdr & _HEADER_MAP_SUBTAG_MASK) { + case HAMT_SUBTAG_HEAD_ARRAY: + ptr++; + sz = 16; + hval = 0xffff; + break; + case HAMT_SUBTAG_HEAD_BITMAP: + ptr++; + if (ptr[0] == -1) { + ptr = boxed_val(ptr[1]); + goto again; + } + case HAMT_SUBTAG_NODE_BITMAP: + hval = MAP_HEADER_VAL(hdr); + sz = hashmap_bitcount(hval); + ASSERT(sz < 17); + break; + default: + erts_exit(ERTS_ABORT_EXIT, "bad header"); + } + + if (idx <= sz) { + if (is_list(ptr[idx])) + return ptr[idx]; + else { + Eterm *hp = HAlloc(BIF_P, HAMT_HEAD_BITMAP_SZ(1)); + hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(index_to_hash(idx, hval)); + hp[1] = -1; + hp[2] = ptr[idx]; + return make_hashmap(hp); + } + } else { + return am_none; + } +} /* implementation of builtin emulations */ diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h index c3ccf80b85..d910e98398 100644 --- a/erts/emulator/beam/erl_map.h +++ b/erts/emulator/beam/erl_map.h @@ -56,7 +56,7 @@ typedef struct flatmap_s { /* the head-node is a bitmap or array with an untagged size */ -#define hashmap_size(x) (((hashmap_head_t*) hashmap_val(x))->size) +#define hashmap_size(x) (((hashmap_head_t*) hashmap_val(x))->size == -1 ? hashmap_subtree_size(x) : ((hashmap_head_t*) hashmap_val(x))->size) #define hashmap_make_hash(Key) make_internal_hash(Key, 0) #define hashmap_restore_hash(Heap,Lvl,Key) \ @@ -106,6 +106,7 @@ Eterm erts_hashmap_from_ks_and_vs_extra(ErtsHeapFactory *factory, Eterm *ks, Eterm *vs, Uint n, Eterm k, Eterm v); +Uint hashmap_subtree_size(Eterm node); const Eterm *erts_maps_get(Eterm key, Eterm map); const Eterm *erts_hashmap_get(Uint32 hx, Eterm key, Eterm map); diff --git a/lib/stdlib/src/maps.erl b/lib/stdlib/src/maps.erl index 7ed32a3988..0da12cf8e2 100644 --- a/lib/stdlib/src/maps.erl +++ b/lib/stdlib/src/maps.erl @@ -32,7 +32,7 @@ new/0, put/3, remove/2, take/2, to_list/1, update/3, values/1]). --opaque iterator() :: [{term(), term()}]. +-opaque iterator() :: [{term(), term()}] | [[pos_integer() | map()]]. -export_type([iterator/0]). @@ -279,7 +279,10 @@ size(Val) -> Iterator :: iterator(). iterator(Map) when is_map(Map) -> - maps:to_list(Map); + case maps:size(Map) < 42 of + true -> maps:to_list(Map); + false -> [[1 | Map]] + end; iterator(M) -> erlang:error(error_type(M),[M]). @@ -289,6 +292,12 @@ iterator(M) -> V :: term(), NextIterator :: iterator(). next([]) -> none; +next([[Index | Map] | St]) -> + case erts_internal:map_get_index(Index, Map) of + SubMap when is_map(SubMap) -> next([[1 | SubMap], [Index+1|Map] | St]); + [K|V] -> {K,V,[[Index+1 | Map] | St]}; + none -> next(St) + end; next([{K, V} | I]) -> {K, V, I}. -- cgit v1.2.3 From 0149a73d15df1f80cb46752ec3829f48c38dd230 Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Thu, 21 Sep 2017 09:20:30 +0200 Subject: erts: Implement maps path iterator --- erts/emulator/beam/bif.tab | 8 +- erts/emulator/beam/erl_map.c | 288 +++++++++++++++++---- erts/emulator/beam/erl_map.h | 4 +- erts/emulator/test/map_SUITE.erl | 51 ++++ erts/preloaded/ebin/erts_internal.beam | Bin 11872 -> 12100 bytes erts/preloaded/src/erts_internal.erl | 13 +- .../test/small_SUITE_data/results/maps_sum | 2 +- lib/stdlib/doc/src/maps.xml | 138 +++++++++- lib/stdlib/src/maps.erl | 91 ++++--- lib/stdlib/test/maps_SUITE.erl | 63 +++++ 10 files changed, 553 insertions(+), 105 deletions(-) diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab index 4ee5af14bc..f2c8331850 100644 --- a/erts/emulator/beam/bif.tab +++ b/erts/emulator/beam/bif.tab @@ -689,6 +689,10 @@ bif erts_internal:maps_to_list/2 # # New in 20.1 # - bif erlang:iolist_to_iovec/1 -bif erts_internal:map_get_index/2 \ No newline at end of file + +# +# New in 21.0 +# + +bif erts_internal:map_next/2 diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 37fcedbc6d..a5fda7b86d 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -90,6 +90,7 @@ static BIF_RETTYPE hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB, int swap_ struct HashmapMergeContext_*); 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); @@ -1518,7 +1519,7 @@ trap: /* Yield */ return trap_ret; } -Uint hashmap_subtree_size(Eterm node) { +static Uint hashmap_subtree_size(Eterm node) { DECLARE_WSTACK(stack); Uint size = 0; @@ -3059,74 +3060,247 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]) return res; } -static Uint32 -index_to_hash(Sint idx, Uint32 hval) -{ - Uint32 new_hval = 1; - while (1) { - if (hval & 0x1) { - idx--; - if (!idx) break; - } - new_hval = new_hval << 1; - hval = hval >> 1; - } - return new_hval; -} -BIF_RETTYPE erts_internal_map_get_index_2(BIF_ALIST_2) { - Sint idx; - Uint32 hval, sz; - Eterm *ptr, hdr; +/* + * 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 + * 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 and + * returns that 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. + * + * 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 (!is_hashmap(BIF_ARG_2) || is_not_small(BIF_ARG_1)) - BIF_ERROR(BIF_P, BADARG); +#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) - idx = signed_val(BIF_ARG_1); +BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) { - if (idx < 1 || idx > 17) + Eterm *hp = NULL, *lst, + iter, path, map, k, v; + + path = BIF_ARG_1; + map = BIF_ARG_2; + + if (!is_map(map)) BIF_ERROR(BIF_P, BADARG); - ASSERT(is_boxed(BIF_ARG_2)); + if (path == am_none) + BIF_RET(am_none); - ptr = boxed_val(BIF_ARG_2); -again: - hdr = *ptr; + if (is_flatmap(map)) { + flatmap_t *mp = (flatmap_t *)flatmap_val(map); + Uint idx, sz = flatmap_get_size(mp); - switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_HEAD_ARRAY: - ptr++; - sz = 16; - hval = 0xffff; - break; - case HAMT_SUBTAG_HEAD_BITMAP: - ptr++; - if (ptr[0] == -1) { - ptr = boxed_val(ptr[1]); - goto again; + if (is_not_small(path)) + BIF_ERROR(BIF_P, BADARG); + + idx = unsigned_val(path); + + if (sz == 0) { + if (idx == 0) + BIF_RET(am_none); + else + BIF_ERROR(BIF_P, BADARG); } - case HAMT_SUBTAG_NODE_BITMAP: - hval = MAP_HEADER_VAL(hdr); - sz = hashmap_bitcount(hval); - ASSERT(sz < 17); - break; - default: - erts_exit(ERTS_ABORT_EXIT, "bad header"); - } - - if (idx <= sz) { - if (is_list(ptr[idx])) - return ptr[idx]; - else { - Eterm *hp = HAlloc(BIF_P, HAMT_HEAD_BITMAP_SZ(1)); - hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(index_to_hash(idx, hval)); - hp[1] = -1; - hp[2] = ptr[idx]; - return make_hashmap(hp); + + k = flatmap_get_keys(mp)[idx]; + v = flatmap_get_values(mp)[idx]; + + if (idx + 1 < sz) { + path = make_small(idx + 1); + } else if (idx < sz) { + path = am_none; + } else { + BIF_ERROR(BIF_P, BADARG); } } else { - return am_none; + Uint curr_path; + Uint path_length = 0; + Uint *path_rest = NULL; + int i; + Eterm node = map; + DECLARE_WSTACK(stack); + + ASSERT(is_hashmap(node)); + + if (is_small(path)) { + curr_path = unsigned_val(path); + } 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); + } + + /* First we look for the K and V to return 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. */ + for (i = 1; ; i++) { + 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"); + } + + if (PATH_ELEM(curr_path) >= sz) + BIF_ERROR(BIF_P, BADARG); + + WSTACK_PUSH2(stack, node, PATH_ELEM(curr_path)); + + /* We have found a leaf, return it and calculate the path to next */ + if (is_list(ptr[PATH_ELEM(curr_path)])) { + lst = list_val(ptr[PATH_ELEM(curr_path)]); + k = CAR(lst); + v = CDR(lst); + 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 pop the stack until we come to the next leaf to return */ + while (1) { + 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"); + } + + if (idx + 1 < sz) { + curr_path = idx + 1; + break; + } + + /* We have reached the end of the iteration */ + if (WSTACK_ISEMPTY(stack)) { + path = am_none; + break; + } + + } + + if (path != am_none) { + Uint depth = WSTACK_COUNT(stack) / 2 + 1; + /* +1 because we already have the first element in curr_path */ + Eterm *path_digits = NULL; + + /* 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 = (Uint)WSTACK_POP(stack); + (void)WSTACK_POP(stack); + + depth--; + if (depth % PATH_ELEMS_PER_DIGIT == 0) { + 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); + } + } + + DESTROY_WSTACK(stack); } + + 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/beam/erl_map.h b/erts/emulator/beam/erl_map.h index d910e98398..718d400e22 100644 --- a/erts/emulator/beam/erl_map.h +++ b/erts/emulator/beam/erl_map.h @@ -56,7 +56,7 @@ typedef struct flatmap_s { /* the head-node is a bitmap or array with an untagged size */ -#define hashmap_size(x) (((hashmap_head_t*) hashmap_val(x))->size == -1 ? hashmap_subtree_size(x) : ((hashmap_head_t*) hashmap_val(x))->size) +#define hashmap_size(x) (((hashmap_head_t*) hashmap_val(x))->size) #define hashmap_make_hash(Key) make_internal_hash(Key, 0) #define hashmap_restore_hash(Heap,Lvl,Key) \ @@ -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) @@ -106,7 +105,6 @@ Eterm erts_hashmap_from_ks_and_vs_extra(ErtsHeapFactory *factory, Eterm *ks, Eterm *vs, Uint n, Eterm k, Eterm v); -Uint hashmap_subtree_size(Eterm node); const Eterm *erts_maps_get(Eterm key, Eterm map); const Eterm *erts_hashmap_get(Uint32 hx, Eterm key, Eterm map); diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl index 02f3c89318..3cf071b590 100644 --- a/erts/emulator/test/map_SUITE.erl +++ b/erts/emulator/test/map_SUITE.erl @@ -53,6 +53,7 @@ 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, @@ -120,6 +121,7 @@ all() -> [t_build_and_match_literals, t_build_and_match_literals_large, 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, @@ -2399,6 +2401,55 @@ t_bif_erts_internal_maps_to_list(Config) when is_list(Config) -> {'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), + + 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([16#FFFFFFF|FM]))), + {'EXIT', {badarg,_}} = (catch maps:next(id([16#F0F0F0F|FM]))), + {'EXIT', {badarg,_}} = (catch maps:next(id([16#1234567890ABCDEF|FM]))), + + 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/erts_internal.beam b/erts/preloaded/ebin/erts_internal.beam index 5416826f19..015508d326 100644 Binary files a/erts/preloaded/ebin/erts_internal.beam and b/erts/preloaded/ebin/erts_internal.beam differ diff --git a/erts/preloaded/src/erts_internal.erl b/erts/preloaded/src/erts_internal.erl index bb1824ecd4..46bdeaad30 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]). + maps_to_list/2, map_next/2]). -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]). @@ -381,6 +381,17 @@ map_hashmap_children(_M) -> 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 + I :: non_neg_integer(), + M :: map(), + K :: term(), + V :: term(), + NI :: maps:iterator(). + +map_next(_I, _M) -> + 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/stdlib/doc/src/maps.xml b/lib/stdlib/doc/src/maps.xml index 8c7270816b..a3afbf8e7f 100644 --- a/lib/stdlib/doc/src/maps.xml +++ b/lib/stdlib/doc/src/maps.xml @@ -33,16 +33,32 @@

This module contains functions for maps processing.

+ + + + +

An iterator representing the key value associations in a map.

+

Created using maps:iterator/1 + and maps:iterator/2.

+

Consumed by maps:next/1, + maps:filter/2, + maps:fold/3 and + maps:map/2.

+ + + + Select pairs that satisfy a predicate. -

Returns a map Map2 for which predicate - Pred holds true in Map1.

+

Returns a map Map for which predicate + Pred holds true in MapOrIter.

The call fails with a {badmap,Map} exception if - Map1 is not a map, or with badarg if - Pred is not a function of arity 2.

+ MapOrIter is not a map or valid iterator, + or with badarg if Pred is not a + function of arity 2.

Example:

> M = #{a => 2, b => 3, c=> 4, "a" => 1, "b" => 2, "c" => 4}, @@ -76,12 +92,16 @@

Calls F(K, V, AccIn) for every K to value - V association in Map in + V association in MapOrIter in any order. Function fun F/3 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 Init is returned if the map is empty.

+

The call fails with a {badmap,Map} exception if + MapOrIter is not a map or valid iterator, + or with badarg if Fun is not a + function of arity 3.

Example:

> Fun = fun(K,V,AccIn) when is_list(K) -> AccIn + V end, @@ -168,6 +188,75 @@ false + + + Create a map iterator. + +

Returns a map iterator Iterator that can + be used by maps:next/1 + to traverse the keys and values in a map. This call is equivalent + to calling maps:iterator/2 + with an empty map as the options.

+

The call fails with a {badmap,Map} exception if + Map is not a map.

+

Example:

+ +> 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 + + + + + + Create a map iterator. + +

Returns a map iterator Iterator that can + be used by maps:next/1 + to traverse the keys and values in a map. The iterator will behave + according to the given Opts.

+ + optimize + + Configures whether the iterator should be optimized for speed + or for memory consumption. Default is speed. + + ordered + + Configures whether the iterator should return the key value + associations ordered on the keys according to erlang term order + or not. The default is false. + + +

Both options can be configured at the same time.

+

The call fails with a {badmap,Map} exception if + Map is not a map.

+

Example:

+ +> M = maps:from_list([{I,I} || I <- 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} + + + @@ -188,12 +277,16 @@ false -

Produces a new map Map2 by calling function +

Produces a new map Map by calling function fun F(K, V1) for every K to value - V1 association in Map1 in + V1 association in MapOrIter in any order. Function fun F/2 must return value V2 to be associated with key K - for the new map Map2.

+ for the new map Map.

+

The call fails with a {badmap,Map} exception if + MapOrIter is not a map or valid iterator, + or with badarg if Fun is not a + function of arity 2.

Example:

> Fun = fun(K,V1) when is_list(K) -> V1*2 end, @@ -233,6 +326,35 @@ false + + + Get the next key and value from an iterator. + +

Returns the next key-value association in + Iterator and a new iterator for the + remaining associations in the iterator. +

+

+ If there are no more associations in the iterator, + none is returned. +

+

Example:

+ +> 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 + + + diff --git a/lib/stdlib/src/maps.erl b/lib/stdlib/src/maps.erl index 0da12cf8e2..2f2dd41979 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, next/1]). + iterator/1, iterator/2, next/1]). %% BIFs -export([get/2, find/2, from_list/1, @@ -32,10 +32,13 @@ new/0, put/3, remove/2, take/2, to_list/1, update/3, values/1]). --opaque iterator() :: [{term(), term()}] | [[pos_integer() | map()]]. +-opaque iterator() :: {non_neg_integer() | none | list(term()), map()} + | list({term(), term()}). -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)))))))). + %% Shadowed by erl_bif_types: maps:get/2 -spec get(Key,Map) -> Value when Key :: term(), @@ -44,7 +47,6 @@ get(_,_) -> erlang:nif_error(undef). - -spec find(Key,Map) -> {ok, Value} | error when Key :: term(), Map :: map(), @@ -197,15 +199,17 @@ 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(filter_1(Pred, iterator(Map))); + maps:from_list([{K,V}||{K,V}<-maps:to_list(Map),Pred(K,V)]); +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]). @@ -222,18 +226,20 @@ filter_1(Pred, Iter) -> [] end. --spec fold(Fun,Init,Map) -> Acc when +-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) -> - fold_1(Fun, Init, iterator(Map)); + lists:foldl(fun({K,V},A) -> Fun(K,V,A) end,Init,maps:to_list(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]). @@ -245,16 +251,18 @@ fold_1(Fun, Acc, Iter) -> Acc end. --spec map(Fun,Map1) -> Map2 when +-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(map_1(Fun, iterator(Map))); + maps:from_list([{K,Fun(K,V)}||{K,V}<-maps:to_list(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]). @@ -278,28 +286,45 @@ size(Val) -> Map :: map(), Iterator :: iterator(). -iterator(Map) when is_map(Map) -> - case maps:size(Map) < 42 of - true -> maps:to_list(Map); - false -> [[1 | Map]] +iterator(M) when is_map(M) -> iterator(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) -> - erlang:error(error_type(M),[M]). +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) -> {K,V,NextIterator} | 'none' when +-spec next(Iterator) -> {Key, Value, NextIterator} | 'none' when Iterator :: iterator(), - K :: term(), - V :: term(), + Key :: term(), + Value :: term(), NextIterator :: iterator(). -next([]) -> none; -next([[Index | Map] | St]) -> - case erts_internal:map_get_index(Index, Map) of - SubMap when is_map(SubMap) -> next([[1 | SubMap], [Index+1|Map] | St]); - [K|V] -> {K,V,[[Index+1 | Map] | St]}; - none -> next(St) - end; -next([{K, V} | I]) -> - {K, V, I}. +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) -> + none; +next(Iter) -> + erlang:error(badarg, [Iter]). -spec without(Ks,Map1) -> Map2 when Ks :: [K], @@ -332,5 +357,5 @@ 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/maps_SUITE.erl b/lib/stdlib/test/maps_SUITE.erl index 42e669a799..0021dd0657 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_iterator_2/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_iterator_2, 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,69 @@ 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 + + Vs = lists:seq(1,200), + M2 = maps:from_list([{{k,I},I}||I<-Vs]), + 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], + + 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 -> + []; + {K,V,NI} -> + [{K,V} | iter_kv(NI)] + end. t_size_1(Config) when is_list(Config) -> 0 = maps:size(#{}), -- cgit v1.2.3 From a1c796e7f6b86b4b506492ae6354382c565278d1 Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Thu, 12 Oct 2017 16:00:50 +0200 Subject: 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. --- bootstrap/lib/stdlib/ebin/maps.beam | Bin 2864 -> 3364 bytes erts/emulator/beam/atom.names | 1 + erts/emulator/beam/bif.tab | 3 +- erts/emulator/beam/erl_map.c | 375 +++++++++++++++++++-------------- erts/emulator/test/map_SUITE.erl | 57 ++--- erts/preloaded/ebin/erts_internal.beam | Bin 12100 -> 12128 bytes erts/preloaded/src/erts_internal.erl | 17 +- lib/hipe/cerl/erl_bif_types.erl | 20 -- lib/stdlib/doc/src/maps.xml | 52 +---- lib/stdlib/src/maps.erl | 61 ++---- lib/stdlib/test/maps_SUITE.erl | 39 +--- 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 Binary files a/bootstrap/lib/stdlib/ebin/maps.beam and b/bootstrap/lib/stdlib/ebin/maps.beam differ 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 Binary files a/erts/preloaded/ebin/erts_internal.beam and b/erts/preloaded/ebin/erts_internal.beam differ 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 @@

An iterator representing the key value associations in a map.

-

Created using maps:iterator/1 - and maps:iterator/2.

+

Created using maps:iterator/1.

Consumed by maps:next/1, maps:filter/2, maps:fold/3 and @@ -194,9 +193,9 @@ false

Returns a map iterator Iterator that can be used by maps:next/1 - to traverse the keys and values in a map. This call is equivalent - to calling maps:iterator/2 - with an empty map as the options.

+ 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.

The call fails with a {badmap,Map} exception if Map is not a map.

Example:

@@ -214,49 +213,6 @@ none - - - Create a map iterator. - -

Returns a map iterator Iterator that can - be used by maps:next/1 - to traverse the keys and values in a map. The iterator will behave - according to the given Opts.

- - optimize - - Configures whether the iterator should be optimized for speed - or for memory consumption. Default is speed. - - ordered - - Configures whether the iterator should return the key value - associations ordered on the keys according to erlang term order - or not. The default is false. - - -

Both options can be configured at the same time.

-

The call fails with a {badmap,Map} exception if - Map is not a map.

-

Example:

- -> M = maps:from_list([{I,I} || I <- 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} - - - 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 -> -- cgit v1.2.3 From f1666d981aab4e4cf94b91dc097675fa0b056c97 Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Thu, 12 Oct 2017 15:55:04 +0200 Subject: stdlib: Make io_lib and io_lib_pretty use maps iterator --- bootstrap/lib/stdlib/ebin/io_lib.beam | Bin 11948 -> 13240 bytes bootstrap/lib/stdlib/ebin/io_lib_pretty.beam | Bin 17140 -> 17288 bytes lib/stdlib/src/io_lib.erl | 13 ++++++++++++- lib/stdlib/src/io_lib_pretty.erl | 12 +++++++++++- lib/stdlib/test/io_SUITE.erl | 4 ++-- 5 files changed, 25 insertions(+), 4 deletions(-) diff --git a/bootstrap/lib/stdlib/ebin/io_lib.beam b/bootstrap/lib/stdlib/ebin/io_lib.beam index 82642fb353..c0a8f7212e 100644 Binary files a/bootstrap/lib/stdlib/ebin/io_lib.beam and b/bootstrap/lib/stdlib/ebin/io_lib.beam differ diff --git a/bootstrap/lib/stdlib/ebin/io_lib_pretty.beam b/bootstrap/lib/stdlib/ebin/io_lib_pretty.beam index 6ed1e3b7cc..76e56eb399 100644 Binary files a/bootstrap/lib/stdlib/ebin/io_lib_pretty.beam and b/bootstrap/lib/stdlib/ebin/io_lib_pretty.beam differ 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/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, -- cgit v1.2.3 From 488049bd59352670ba4df17df7cc8a288b273b63 Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Thu, 12 Oct 2017 16:01:43 +0200 Subject: erts: Remove erts_internal:maps_to_list/2 This function is no longer needed as maps:iterator has now been implemented. --- erts/emulator/beam/bif.tab | 1 - erts/emulator/beam/erl_map.c | 70 --------------------------------- erts/emulator/test/map_SUITE.erl | 2 - erts/preloaded/ebin/erts_internal.beam | Bin 12128 -> 11944 bytes erts/preloaded/src/erts_internal.erl | 11 +----- 5 files changed, 1 insertion(+), 83 deletions(-) diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab index b7b66e2ee7..5d5ea3cdc4 100644 --- a/erts/emulator/beam/bif.tab +++ b/erts/emulator/beam/bif.tab @@ -683,7 +683,6 @@ 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 diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 135053dd18..cbbd62f1a2 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,51 +138,6 @@ BIF_RETTYPE map_size_1(BIF_ALIST_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 */ @@ -1933,30 +1887,6 @@ 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; -} - static ERTS_INLINE Uint hashmap_node_size(Eterm hdr, Eterm **nodep) { diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl index 1e70d31b16..c9e971af8a 100644 --- a/erts/emulator/test/map_SUITE.erl +++ b/erts/emulator/test/map_SUITE.erl @@ -52,7 +52,6 @@ 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 @@ -120,7 +119,6 @@ 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 diff --git a/erts/preloaded/ebin/erts_internal.beam b/erts/preloaded/ebin/erts_internal.beam index 3257c68897..f0173a861e 100644 Binary files a/erts/preloaded/ebin/erts_internal.beam and b/erts/preloaded/ebin/erts_internal.beam differ diff --git a/erts/preloaded/src/erts_internal.erl b/erts/preloaded/src/erts_internal.erl index efff76f1fa..83439f0279 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]). + 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,15 +367,6 @@ term_type(_T) -> map_hashmap_children(_M) -> erlang:nif_error(undefined). -%% 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). - %% 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(), -- cgit v1.2.3 From 1ee0157ea2f7b7902f247722fe7d4b9cc3b16ee9 Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Wed, 18 Oct 2017 15:02:06 +0200 Subject: Update preloaded modules --- erts/preloaded/ebin/erl_prim_loader.beam | Bin 54872 -> 54696 bytes erts/preloaded/ebin/erl_tracer.beam | Bin 2220 -> 2184 bytes erts/preloaded/ebin/erlang.beam | Bin 107332 -> 107324 bytes erts/preloaded/ebin/erts_code_purger.beam | Bin 11412 -> 11372 bytes .../ebin/erts_dirty_process_code_checker.beam | Bin 2136 -> 2096 bytes erts/preloaded/ebin/erts_internal.beam | Bin 11944 -> 11956 bytes .../ebin/erts_literal_area_collector.beam | Bin 3316 -> 3284 bytes erts/preloaded/ebin/init.beam | Bin 50380 -> 50344 bytes erts/preloaded/ebin/otp_ring0.beam | Bin 1460 -> 1420 bytes erts/preloaded/ebin/prim_eval.beam | Bin 1540 -> 1492 bytes erts/preloaded/ebin/prim_file.beam | Bin 44024 -> 43960 bytes erts/preloaded/ebin/prim_inet.beam | Bin 76084 -> 75980 bytes erts/preloaded/ebin/prim_zip.beam | Bin 23032 -> 22948 bytes erts/preloaded/ebin/zlib.beam | Bin 19492 -> 19468 bytes 14 files changed, 0 insertions(+), 0 deletions(-) diff --git a/erts/preloaded/ebin/erl_prim_loader.beam b/erts/preloaded/ebin/erl_prim_loader.beam index af6facb5f2..5ffcaa9280 100644 Binary files a/erts/preloaded/ebin/erl_prim_loader.beam and b/erts/preloaded/ebin/erl_prim_loader.beam differ diff --git a/erts/preloaded/ebin/erl_tracer.beam b/erts/preloaded/ebin/erl_tracer.beam index 7ca25803be..9f07eb209b 100644 Binary files a/erts/preloaded/ebin/erl_tracer.beam and b/erts/preloaded/ebin/erl_tracer.beam differ diff --git a/erts/preloaded/ebin/erlang.beam b/erts/preloaded/ebin/erlang.beam index 181a718287..e6657e24b3 100644 Binary files a/erts/preloaded/ebin/erlang.beam and b/erts/preloaded/ebin/erlang.beam differ diff --git a/erts/preloaded/ebin/erts_code_purger.beam b/erts/preloaded/ebin/erts_code_purger.beam index b7c061d9a0..7278d71084 100644 Binary files a/erts/preloaded/ebin/erts_code_purger.beam and b/erts/preloaded/ebin/erts_code_purger.beam differ diff --git a/erts/preloaded/ebin/erts_dirty_process_code_checker.beam b/erts/preloaded/ebin/erts_dirty_process_code_checker.beam index 6467b1c016..b92c03d6d7 100644 Binary files a/erts/preloaded/ebin/erts_dirty_process_code_checker.beam and b/erts/preloaded/ebin/erts_dirty_process_code_checker.beam differ diff --git a/erts/preloaded/ebin/erts_internal.beam b/erts/preloaded/ebin/erts_internal.beam index f0173a861e..1dad5841fc 100644 Binary files a/erts/preloaded/ebin/erts_internal.beam and b/erts/preloaded/ebin/erts_internal.beam differ diff --git a/erts/preloaded/ebin/erts_literal_area_collector.beam b/erts/preloaded/ebin/erts_literal_area_collector.beam index fbd3249d70..187ea3cc28 100644 Binary files a/erts/preloaded/ebin/erts_literal_area_collector.beam and b/erts/preloaded/ebin/erts_literal_area_collector.beam differ diff --git a/erts/preloaded/ebin/init.beam b/erts/preloaded/ebin/init.beam index 1c8d0e626a..9c329e2ca4 100644 Binary files a/erts/preloaded/ebin/init.beam and b/erts/preloaded/ebin/init.beam differ diff --git a/erts/preloaded/ebin/otp_ring0.beam b/erts/preloaded/ebin/otp_ring0.beam index 73a017d981..a2df162521 100644 Binary files a/erts/preloaded/ebin/otp_ring0.beam and b/erts/preloaded/ebin/otp_ring0.beam differ diff --git a/erts/preloaded/ebin/prim_eval.beam b/erts/preloaded/ebin/prim_eval.beam index 7e46b79671..235e0d71f1 100644 Binary files a/erts/preloaded/ebin/prim_eval.beam and b/erts/preloaded/ebin/prim_eval.beam differ diff --git a/erts/preloaded/ebin/prim_file.beam b/erts/preloaded/ebin/prim_file.beam index 32755d5c28..d08e11ab2f 100644 Binary files a/erts/preloaded/ebin/prim_file.beam and b/erts/preloaded/ebin/prim_file.beam differ diff --git a/erts/preloaded/ebin/prim_inet.beam b/erts/preloaded/ebin/prim_inet.beam index c03415c758..988ef61413 100644 Binary files a/erts/preloaded/ebin/prim_inet.beam and b/erts/preloaded/ebin/prim_inet.beam differ diff --git a/erts/preloaded/ebin/prim_zip.beam b/erts/preloaded/ebin/prim_zip.beam index 77d0d2edb0..f0d41ed6bf 100644 Binary files a/erts/preloaded/ebin/prim_zip.beam and b/erts/preloaded/ebin/prim_zip.beam differ diff --git a/erts/preloaded/ebin/zlib.beam b/erts/preloaded/ebin/zlib.beam index 5048bdb846..e96d0dca5c 100644 Binary files a/erts/preloaded/ebin/zlib.beam and b/erts/preloaded/ebin/zlib.beam differ -- cgit v1.2.3 From 2994bda075a5119cd3b1d499b5897a3d1befdc6b Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Fri, 13 Oct 2017 15:50:04 +0200 Subject: Update primary bootstrap --- bootstrap/lib/compiler/ebin/compiler.appup | 2 +- bootstrap/lib/stdlib/ebin/io_lib.beam | Bin 13240 -> 12088 bytes bootstrap/lib/stdlib/ebin/maps.beam | Bin 3364 -> 3464 bytes 3 files changed, 1 insertion(+), 1 deletion(-) 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/stdlib/ebin/io_lib.beam b/bootstrap/lib/stdlib/ebin/io_lib.beam index c0a8f7212e..b6d6d49d26 100644 Binary files a/bootstrap/lib/stdlib/ebin/io_lib.beam and b/bootstrap/lib/stdlib/ebin/io_lib.beam differ diff --git a/bootstrap/lib/stdlib/ebin/maps.beam b/bootstrap/lib/stdlib/ebin/maps.beam index 6820b81db5..50678db509 100644 Binary files a/bootstrap/lib/stdlib/ebin/maps.beam and b/bootstrap/lib/stdlib/ebin/maps.beam differ -- cgit v1.2.3 From 10912210641fe7d784c4ba6398c24504200ed339 Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Wed, 18 Oct 2017 15:34:10 +0200 Subject: erts: Limit size of first iterator for hashmaps --- erts/emulator/beam/erl_map.c | 53 +++++++++++++++++++++++++++----------------- 1 file changed, 33 insertions(+), 20 deletions(-) diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index cbbd62f1a2..8047a9567f 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -2992,20 +2992,6 @@ 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) -/* 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)) - - BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { Eterm path, map; @@ -3059,7 +3045,7 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { Uint curr_path; Uint path_length = 0; Uint *path_rest = NULL; - int i, elems = NUM_ELEMS_TO_RETURN(BIF_P, map); + int i, elems, orig_elems; Eterm node = map, res, *path_ptr = NULL, *hp; /* A stack WSTACK is used when traversing the hashmap. @@ -3080,12 +3066,37 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { 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)) - goto badarg; + BIF_ERROR(BIF_P, BADARG); path_length = BIG_ARITY(big) - 1; curr_path = BIG_DIGIT(big, 0); path_rest = BIG_V(big) + 1; @@ -3096,15 +3107,17 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { 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)); + 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) * NUM_ELEMS_TO_RETURN(BIF_P, map)); + 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. */ @@ -3274,7 +3287,7 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { HRelease(BIF_P, hp + (2+3) * elems, hp); } } - BIF_P->fcalls -= 4 * (NUM_ELEMS_TO_RETURN(BIF_P, map) - elems); + BIF_P->fcalls -= 4 * (orig_elems - elems); DESTROY_WSTACK(stack); BIF_RET(res); @@ -3284,7 +3297,7 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { } else { HRelease(BIF_P, hp + (2+3) * elems, hp); } - BIF_P->fcalls -= 4 * (NUM_ELEMS_TO_RETURN(BIF_P, map) - elems); + BIF_P->fcalls -= 4 * (orig_elems - elems); DESTROY_WSTACK(stack); BIF_ERROR(BIF_P, BADARG); } -- cgit v1.2.3