diff options
Diffstat (limited to 'erts/emulator/test/map_SUITE.erl')
-rw-r--r-- | erts/emulator/test/map_SUITE.erl | 128 |
1 files changed, 128 insertions, 0 deletions
diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl index 91a5706320..228832ac0a 100644 --- a/erts/emulator/test/map_SUITE.erl +++ b/erts/emulator/test/map_SUITE.erl @@ -62,6 +62,8 @@ t_maps_without/1, %% misc + t_hashmap_balance/1, + t_erts_internal_order/1, t_pdict/1, t_ets/1, t_dets/1, @@ -111,6 +113,8 @@ all() -> [ %% Other functions + t_hashmap_balance, + t_erts_internal_order, t_pdict, t_ets, t_tracing @@ -1147,6 +1151,20 @@ t_map_encode_decode(Config) when is_list(Config) -> 97,55 % 55 :: integer() >>), + %% Maps of different sizes + lists:foldl(fun(Key, M0) -> + M1 = M0#{Key => Key}, + case Key rem 17 of + 0 -> + M1 = binary_to_term(term_to_binary(M1)); + _ -> + ok + end, + M1 + end, + #{}, + lists:seq(1,10000)), + %% many maps in same binary MapList = lists:foldl(fun(K, [M|_]=Acc) -> [M#{K => K} | Acc] end, [#{}], @@ -1421,6 +1439,116 @@ t_maps_without(_Config) -> %% MISC + +%% Verify that the the number of nodes in hashmaps +%% of different types and sizes does not deviate too +%% much from the theoretical model. +t_hashmap_balance(_Config) -> + io:format("Integer keys\n", []), + hashmap_balance(fun(I) -> I end), + io:format("Float keys\n", []), + hashmap_balance(fun(I) -> float(I) end), + io:format("String keys\n", []), + hashmap_balance(fun(I) -> integer_to_list(I) end), + io:format("Binary (big) keys\n", []), + hashmap_balance(fun(I) -> <<I:16/big>> end), + io:format("Binary (little) keys\n", []), + hashmap_balance(fun(I) -> <<I:16/little>> end), + io:format("Atom keys\n", []), + erts_debug:set_internal_state(available_internal_state, true), + hashmap_balance(fun(I) -> erts_debug:get_internal_state({atom,I}) end), + erts_debug:set_internal_state(available_internal_state, false), + + ok. + +hashmap_balance(KeyFun) -> + F = fun(I, {M0,Max0}) -> + Key = KeyFun(I), + M1 = M0#{Key => Key}, + Max1 = case erts_internal:map_type(M1) of + hashmap -> + Nodes = hashmap_nodes(M1), + Avg = maps:size(M1) * 0.4, + StdDev = math:sqrt(maps:size(M1)) / 3, + SD_diff = abs(Nodes - Avg) / StdDev, + %%io:format("~p keys: ~p nodes avg=~p SD_diff=~p\n", + %% [maps:size(M1), Nodes, Avg, SD_diff]), + {MaxDiff0, _} = Max0, + case {Nodes > Avg, SD_diff > MaxDiff0} of + {true, true} -> {SD_diff, M1}; + _ -> Max0 + end; + + flatmap -> Max0 + end, + {M1, Max1} + end, + + {_,{MaxDiff,MaxMap}} = lists:foldl(F, + {#{}, {0, 0}}, + lists:seq(1,10000)), + io:format("Max std dev diff ~p for map of size ~p (nodes=~p, flatsize=~p)\n", + [MaxDiff, maps:size(MaxMap), hashmap_nodes(MaxMap), erts_debug:flat_size(MaxMap)]), + + true = (MaxDiff < 6), % The probability of this line failing is about 0.000000001 + % for a uniform hash. I've set the probability this "high" for now + % to detect flaws in our make_internal_hash. + % Hard limit is 15 (see hashmap_over_estimated_heap_size). + ok. + +hashmap_nodes(M) -> + Info = erts_debug:map_info(M), + lists:foldl(fun(Tpl,Acc) -> + case element(1,Tpl) of + bitmaps -> Acc + element(2,Tpl); + arrays -> Acc + element(2,Tpl); + _ -> Acc + end + end, + 0, + Info). + +t_erts_internal_order(_Config) when is_list(_Config) -> + + -1 = erts_internal:cmp_term(1,2), + 1 = erts_internal:cmp_term(2,1), + 0 = erts_internal:cmp_term(2,2), + + + -1 = erts_internal:cmp_term(1,a), + 1 = erts_internal:cmp_term(a,1), + 0 = erts_internal:cmp_term(a,a), + + -1 = erts_internal:cmp_term(1,1.0), + 1 = erts_internal:cmp_term(1.0,1), + 0 = erts_internal:cmp_term(1.0,1.0), + + -1 = erts_internal:cmp_term(1,1 bsl 65), + 1 = erts_internal:cmp_term(1 bsl 65,1), + 0 = erts_internal:cmp_term(1 bsl 65, 1 bsl 65), + + -1 = erts_internal:cmp_term(1 bsl 65,float(1)), + 1 = erts_internal:cmp_term(float(1),1 bsl 65), + -1 = erts_internal:cmp_term(1,float(1 bsl 65)), + 1 = erts_internal:cmp_term(float(1 bsl 65),1), + 0 = erts_internal:cmp_term(float(1 bsl 65), float(1 bsl 65)), + + %% reported errors + -1 = erts_internal:cmp_term(0,2147483648), + 0 = erts_internal:cmp_term(2147483648,2147483648), + 1 = erts_internal:cmp_term(2147483648,0), + + M = #{0 => 0,2147483648 => 0}, + true = M =:= binary_to_term(term_to_binary(M)), + + F1 = fun(_, _) -> 0 end, + F2 = fun(_, _) -> 1 end, + M0 = maps:from_list( [{-2147483649, 0}, {0,0}, {97, 0}, {false, 0}, {flower, 0}, {F1, 0}, {F2, 0}, {<<>>, 0}]), + M1 = maps:merge(M0, #{0 => 1}), + 8 = maps:size(M1), + 1 = maps:get(0,M1), + ok. + t_pdict(_Config) -> put(#{ a => b, b => a},#{ c => d}), |