erts: Add test map_SUITE:t_hashmap_balance

2 files changed, 91 insertions, 0 deletions

diff --git a/erts/emulator/beam/erl_bif_info.c b/erts/emulator/beam/erl_bif_info.c
index d750e34be3..0774ab51af 100644
--- a/erts/emulator/beam/erl_bif_info.c
+++ b/erts/emulator/beam/erl_bif_info.c
@@ -3597,6 +3597,26 @@ BIF_RETTYPE erts_debug_get_internal_state_1(BIF_ALIST_1)
 
 		BIF_RET(erts_debug_reader_groups_map(BIF_P, (int) groups));
 	    }
+	    else if (ERTS_IS_ATOM_STR("internal_hash", tp[1])) {
+		Uint hash = (Uint) make_internal_hash(tp[2]);
+		Uint hsz = 0;
+		Eterm* hp;
+		erts_bld_uint(NULL, &hsz, hash);
+		hp = HAlloc(BIF_P,hsz);
+		return erts_bld_uint(&hp, NULL, hash);
+	    }
+	    else if (ERTS_IS_ATOM_STR("atom", tp[1])) {
+		Uint ix;
+		if (!term_to_Uint(tp[2], &ix))
+		    BIF_ERROR(BIF_P, BADARG);
+		while (ix >= atom_table_size()) {
+		    char tmp[20];
+		    erts_snprintf(tmp, sizeof(tmp), "am%x", atom_table_size());
+		    erts_atom_put((byte *) tmp, strlen(tmp), ERTS_ATOM_ENC_LATIN1, 1);
+		}
+		return make_atom(ix);
+	    }
+
 	    break;
 	}
 	default:
diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl
index 91a5706320..1da08beb8b 100644
--- a/erts/emulator/test/map_SUITE.erl
+++ b/erts/emulator/test/map_SUITE.erl
@@ -62,6 +62,7 @@
 	t_maps_without/1,
 
 	%% misc
+	t_hashmap_balance/1,
 	t_pdict/1,
 	t_ets/1,
 	t_dets/1,
@@ -111,6 +112,7 @@ all() -> [
 
 
         %% Other functions
+	t_hashmap_balance,
 	t_pdict,
 	t_ets,
 	t_tracing
@@ -1421,6 +1423,75 @@ 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_pdict(_Config) ->
 
     put(#{ a => b, b => a},#{ c => d}),