aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/test
diff options
context:
space:
mode:
authorSverker Eriksson <[email protected]>2017-04-28 14:54:42 +0200
committerGitHub <[email protected]>2017-04-28 14:54:42 +0200
commit61e55780e2800e340e8ff16b5414f08373f89ef3 (patch)
treec584727c8695ac4c72c4fae9deff18931a8c54d4 /erts/emulator/test
parent2e2526b58f74c6c3209b3feca34866772be65335 (diff)
parente40ec046a2a1037b2f87b657503c5f21c5de4e2a (diff)
downloadotp-61e55780e2800e340e8ff16b5414f08373f89ef3.tar.gz
otp-61e55780e2800e340e8ff16b5414f08373f89ef3.tar.bz2
otp-61e55780e2800e340e8ff16b5414f08373f89ef3.zip
Merge PR1413 from g-andrade/feature/phash2_nif
Support hashing terms from NIF code
Diffstat (limited to 'erts/emulator/test')
-rw-r--r--erts/emulator/test/nif_SUITE.erl159
-rw-r--r--erts/emulator/test/nif_SUITE_data/nif_SUITE.c26
2 files changed, 183 insertions, 2 deletions
diff --git a/erts/emulator/test/nif_SUITE.erl b/erts/emulator/test/nif_SUITE.erl
index 693db42e58..8ad11d3bf3 100644
--- a/erts/emulator/test/nif_SUITE.erl
+++ b/erts/emulator/test/nif_SUITE.erl
@@ -56,7 +56,10 @@
nif_is_process_alive/1, nif_is_port_alive/1,
nif_term_to_binary/1, nif_binary_to_term/1,
nif_port_command/1,
- nif_snprintf/1
+ nif_snprintf/1,
+ nif_internal_hash/1,
+ nif_internal_hash_salted/1,
+ nif_phash2/1
]).
-export([many_args_100/100]).
@@ -90,7 +93,10 @@ all() ->
nif_is_process_alive, nif_is_port_alive,
nif_term_to_binary, nif_binary_to_term,
nif_port_command,
- nif_snprintf].
+ nif_snprintf,
+ nif_internal_hash,
+ nif_internal_hash_salted,
+ nif_phash2].
groups() ->
[{G, [], api_repeaters()} || G <- api_groups()]
@@ -2610,6 +2616,154 @@ nif_snprintf(Config) ->
<<"{{hello,world,-33},",0>> = format_term_nif(20,{{hello,world, -33}, 3.14, self()}),
ok.
+nif_internal_hash(Config) ->
+ ensure_lib_loaded(Config),
+ HashValueBitSize = nif_hash_result_bitsize(internal),
+ Terms = unique([random_term() || _ <- lists:seq(1, 5000)]),
+ HashValues = [hash_nif(internal, Term, 0) || Term <- Terms],
+ test_bit_distribution_fitness(HashValues, HashValueBitSize, 0.05).
+
+nif_internal_hash_salted(Config) ->
+ ensure_lib_loaded(Config),
+ test_salted_nif_hash(internal).
+
+nif_phash2(Config) ->
+ ensure_lib_loaded(Config),
+ HashValueBitSize = nif_hash_result_bitsize(phash2),
+ Terms = unique([random_term() || _ <- lists:seq(1, 5000)]),
+ HashValues =
+ lists:map(
+ fun (Term) ->
+ HashValue = erlang:phash2(Term),
+ Salt = random_uint32(), % phash2 should ignore salt
+ NifHashValue = hash_nif(phash2, Term, Salt),
+ (HashValue =:= NifHashValue
+ orelse ct:fail("Expected: ~p\nActual: ~p",
+ [HashValue, NifHashValue])),
+ HashValue
+ end,
+ Terms),
+ test_bit_distribution_fitness(HashValues, HashValueBitSize, 0.05).
+
+test_salted_nif_hash(HashType) ->
+ HashValueBitSize = nif_hash_result_bitsize(HashType),
+ Terms = unique([random_term() || _ <- lists:seq(1, 5000)]),
+ Salts = unique([random_uint32() || _ <- lists:seq(1, 100)]),
+ {HashValuesPerSalt, HashValuesPerTerm} =
+ lists:mapfoldl(
+ fun (Salt, Acc) ->
+ {HashValues, NewAcc} =
+ lists:mapfoldl(
+ fun (Term, AccB) ->
+ HashValue = hash_nif(HashType, Term, Salt),
+ NewAccB = dict:append(Term, HashValue, AccB),
+ {HashValue, NewAccB}
+ end,
+ Acc,
+ Terms),
+ {{Salt, HashValues}, NewAcc}
+ end,
+ dict:new(),
+ Salts),
+
+ % Test per-salt hash distribution of different terms
+ lists:foreach(
+ fun ({_Salt, HashValues}) ->
+ test_bit_distribution_fitness(HashValues, HashValueBitSize, 0.05)
+ end,
+ HashValuesPerSalt),
+
+ % Test per-term hash distribution of different salts
+ dict:fold(
+ fun (_Term, HashValues, Acc) ->
+ % Be more tolerant of relative deviation,
+ % as there's fewer hash values here.
+ test_bit_distribution_fitness(HashValues, HashValueBitSize, 0.30),
+ Acc
+ end,
+ ok,
+ HashValuesPerTerm).
+
+test_bit_distribution_fitness(Integers, BitSize, MaxRelativeDeviation) ->
+ MaxInteger = (1 bsl BitSize) - 1,
+ OnesPerBit =
+ lists:foldl(
+ fun (Integer, Acc) when Integer >= 0, Integer =< MaxInteger ->
+ lists:foldl(
+ fun (BitIndex, AccB) ->
+ BitValue = (Integer band (1 bsl BitIndex)) bsr BitIndex,
+ orddict:update_counter(BitIndex, BitValue, AccB)
+ end,
+ Acc,
+ lists:seq(0, BitSize - 1))
+ end,
+ orddict:new(),
+ Integers),
+
+ ExpectedNrOfOnes = length(Integers) div 2,
+ FailureText =
+ orddict:fold(
+ fun (BitIndex, NrOfOnes, Acc) ->
+ RelativeDeviation = abs(NrOfOnes - ExpectedNrOfOnes) / length(Integers),
+ case RelativeDeviation >= MaxRelativeDeviation of
+ false -> Acc;
+ true ->
+ [Acc,
+ io_lib:format(
+ "Unreasonable deviation on number of set bits (i=~p): "
+ "expected ~p, got ~p (relative dev. ~.3f)~n",
+ [BitIndex, ExpectedNrOfOnes, NrOfOnes, RelativeDeviation])]
+ end
+ end,
+ [],
+ OnesPerBit),
+
+ (FailureText =:= [] orelse ct:fail(FailureText)).
+
+nif_hash_result_bitsize(internal) -> 32;
+nif_hash_result_bitsize(phash2) -> 27.
+
+unique(List) ->
+ lists:usort(List).
+
+random_uint32() ->
+ rand:uniform(1 bsl 32) - 1.
+
+random_term() ->
+ case rand:uniform(6) of
+ 1 -> rand:uniform(1 bsl 27) - 1; % small
+ 2 -> (1 bsl 27) + rand:uniform(1 bsl 128); % big
+ 3 -> random_sign() * (rand:uniform() * (1 bsl 53)); % float
+ 4 -> random_binary();
+ 5 -> random_pid();
+ 6 ->
+ Length = rand:uniform(10),
+ List = [random_term() || _ <- lists:seq(1, Length)],
+ case rand:uniform(2) of
+ 1 ->
+ List;
+ 2 ->
+ list_to_tuple(List)
+ end
+ end.
+
+random_sign() ->
+ case rand:uniform(2) of
+ 1 -> -1.0;
+ 2 -> 1.0
+ end.
+
+random_binary() ->
+ list_to_binary(random_bytes(rand:uniform(32) - 1)).
+
+random_bytes(0) ->
+ [];
+random_bytes(N) when N > 0 ->
+ [rand:uniform(256) - 1 | random_bytes(N - 1)].
+
+random_pid() ->
+ Processes = erlang:processes(),
+ lists:nth(rand:uniform(length(Processes)), Processes).
%% The NIFs:
lib_version() -> undefined.
@@ -2621,6 +2775,7 @@ type_test() -> ?nif_stub.
tuple_2_list(_) -> ?nif_stub.
is_identical(_,_) -> ?nif_stub.
compare(_,_) -> ?nif_stub.
+hash_nif(_Type, _Term, _Salt) -> ?nif_stub.
many_args_100(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_) -> ?nif_stub.
clone_bin(_) -> ?nif_stub.
make_sub_bin(_,_,_) -> ?nif_stub.
diff --git a/erts/emulator/test/nif_SUITE_data/nif_SUITE.c b/erts/emulator/test/nif_SUITE_data/nif_SUITE.c
index 8fe5ee809a..a255c9f096 100644
--- a/erts/emulator/test/nif_SUITE_data/nif_SUITE.c
+++ b/erts/emulator/test/nif_SUITE_data/nif_SUITE.c
@@ -687,6 +687,31 @@ static ERL_NIF_TERM compare(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
return enif_make_int(env, enif_compare(argv[0],argv[1]));
}
+static ERL_NIF_TERM hash_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
+{
+ if (argc != 3) {
+ return enif_make_badarg(env);
+ }
+
+ ErlNifHash type;
+ if (enif_is_identical(argv[0], enif_make_atom(env, "internal"))) {
+ type = ERL_NIF_INTERNAL_HASH;
+ }
+ else if (enif_is_identical(argv[0], enif_make_atom(env, "phash2"))) {
+ type = ERL_NIF_PHASH2;
+ }
+ else {
+ return enif_make_badarg(env);
+ }
+
+ ErlNifUInt64 salt;
+ if (! enif_get_uint64(env, argv[2], &salt)) {
+ return enif_make_badarg(env);
+ }
+
+ return enif_make_uint64(env, enif_hash(type, argv[1], salt));
+}
+
static ERL_NIF_TERM many_args_100(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[])
{
int i, k;
@@ -2864,6 +2889,7 @@ static ErlNifFunc nif_funcs[] =
{"tuple_2_list", 1, tuple_2_list},
{"is_identical",2,is_identical},
{"compare",2,compare},
+ {"hash_nif",3,hash_nif},
{"many_args_100", 100, many_args_100},
{"clone_bin", 1, clone_bin},
{"make_sub_bin", 3, make_sub_bin},