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. --- 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 ++++++-------------------- 4 files changed, 36 insertions(+), 136 deletions(-) (limited to 'lib') 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