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 --- lib/stdlib/test/maps_SUITE.erl | 63 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 63 insertions(+) (limited to 'lib/stdlib/test') 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. --- lib/stdlib/test/maps_SUITE.erl | 39 +++++++++------------------------------ 1 file changed, 9 insertions(+), 30 deletions(-) (limited to 'lib/stdlib/test') 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 --- lib/stdlib/test/io_SUITE.erl | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/stdlib/test') 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