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/test/map_SUITE.erl | 51 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 51 insertions(+) (limited to 'erts/emulator/test') 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, -- 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. --- erts/emulator/test/map_SUITE.erl | 57 ++++++++++++++-------------------------- 1 file changed, 19 insertions(+), 38 deletions(-) (limited to 'erts/emulator/test') 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 -- 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/test/map_SUITE.erl | 2 -- 1 file changed, 2 deletions(-) (limited to 'erts/emulator/test') 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 -- cgit v1.2.3