Current section
Files
Jump to
Current section
Files
src/tdiff_benchmark.erl
%%% Copyright (C) 2010-2011 Tomas Abrahamsson
%%%
%%% Author: Tomas Abrahamsson <tab@lysator.liu.se>
%%%
%%% This library is free software; you can redistribute it and/or
%%% modify it under the terms of the GNU Library General Public
%%% License as published by the Free Software Foundation; either
%%% version 2 of the License, or (at your option) any later version.
%%%
%%% This library is distributed in the hope that it will be useful,
%%% but WITHOUT ANY WARRANTY; without even the implied warranty of
%%% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
%%% Library General Public License for more details.
%%%
%%% You should have received a copy of the GNU Library General Public
%%% License along with this library; if not, write to the Free
%%% Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
-module(tdiff_benchmark).
-import(lists, [map/2, foreach/2]).
-export([start/0, start/1]).
%%-compile(export_all).
-record(telem, {sz :: integer(),
variation :: float(), %% 0..1
s1 :: string(),
s2 :: string()}).
start() ->
start(_Opts=[]).
start(Opts) ->
rand_seed(Opts),
Lengths = map(fun power_of_ten/1, lists:seq(1,3)),
OrigStrs = map(fun create_string_of_len/1, Lengths),
Changes = lists:append(
map(fun(OrigStr) ->
lists:append(
map(fun(V) ->
map(fun(_) ->
create_test_elem(
OrigStr, V)
end,
lists:seq(1,_NumPairs=3))
end,
_Variations=[0.05, 0.25, 0.50, 0.75]))
end,
OrigStrs)),
run_tdiff_bm(Changes).
power_of_ten(0) -> 1;
power_of_ten(N) -> 10 * power_of_ten(N-1).
create_string_of_len(N) -> lists:duplicate(N, $x).
create_test_elem(Str, DegreeOfVariation) ->
S1 = create_variation(Str, DegreeOfVariation),
S2 = create_variation(Str, DegreeOfVariation),
#telem{sz = length(Str),
variation = DegreeOfVariation,
s1 = S1,
s2 = S2}.
create_variation("", _ChangePercent) ->
"";
create_variation(Str, ChangePercent) ->
NumChangesPerStr = length(Str) * ChangePercent,
VariationChancePerChar = NumChangesPerStr / length(Str),
c_v_2(Str, VariationChancePerChar).
c_v_2([C|T]=Str, VariationChancePerChar) ->
DiceRoll = rand_uniform(),
if DiceRoll < VariationChancePerChar ->
case get_random_change() of
delete -> c_v_2(T, VariationChancePerChar);
{insert,C2} -> [C2 | c_v_2(Str, VariationChancePerChar)];
{change,C2} -> [C2 | c_v_2(T, VariationChancePerChar)]
end;
true ->
[C | c_v_2(T, VariationChancePerChar)]
end;
c_v_2("", _VariationChancePerChar) ->
"".
get_random_change() ->
case rand_uniform(3) of
1 -> delete;
2 -> {insert, get_random_char()};
3 -> {change, get_random_char()}
end.
get_random_char() -> $a + rand_uniform(26) - 1.
run_tdiff_bm(TestElems) ->
NumRuns = 10,
print_results(
lists:sort(
dict:to_list(
lists:foldl(fun(#telem{sz=Size,variation=V,s1=S1,s2=S2}, D) ->
{US,GC} = run_num_times(NumRuns,
fun tdiff:diff/2,
[S1,S2]),
Key = {Size,V},
{AccTime, AccGC, N} = case dict:find(Key, D) of
{ok,X} -> X;
error -> {0,0,0}
end,
NewValue = {AccTime+US, AccGC+GC, N+NumRuns},
dict:store(Key, NewValue, D)
end,
dict:new(),
TestElems)))).
print_results(Results) ->
io:format(" size variation avg time avg garbage~n"),
WordSize = erlang:system_info(wordsize),
foreach(
fun({{Size, Variation}, {US,GC,N}}) ->
if GC < 0 -> io:format("*** GC counter wrapped!~n"
"*** Please rerun the test!~n");
true -> ok
end,
io:format("~6w ~.2f ~10s ~15s~n",
[Size, Variation,
micros_to_pretty_time(round(US/N)),
bytes_to_pretty_size(round(GC*WordSize/N))])
end,
Results),
Results.
micros_to_pretty_time(US) when US >= 1000*1000 ->
f("~.2f s", [US/(1000*1000)]);
micros_to_pretty_time(US) when US >= 1000 ->
f("~.2f ms", [US/1000]);
micros_to_pretty_time(US) ->
f("~w us", [US]).
bytes_to_pretty_size(N) when N >= 1024*1024 ->
f("~.2f MB", [N / (1024*1024)]);
bytes_to_pretty_size(N) when N >= 1024 ->
f("~.2f kB", [N / 1024]);
bytes_to_pretty_size(N) ->
f("~w bytes", [N]).
f(F,A) -> lists:flatten(io_lib:format(F,A)).
run_num_times(N, Fun, Args) ->
run_num_times_2(N, Fun, Args, {0,0}).
run_num_times_2(N, Fun, Args, {AccTime, AccGC}) when N > 0 ->
{US, GC} = run_once(Fun,Args),
run_num_times_2(N-1, Fun, Args, {AccTime+US, AccGC+GC});
run_num_times_2(0, _Fun, _Args, Acc) ->
Acc.
run_once(Fun, Args) ->
Master = self(),
P = spawn(fun() ->
Ps = processes(),
[garbage_collect(P) || P <- Ps],
[garbage_collect(P) || P <- Ps],
{_,Reclaimed0,_} = erlang:statistics(garbage_collection),
{US, _Res} = timer:tc(erlang, apply, [Fun,Args]),
garbage_collect(),
garbage_collect(),
garbage_collect(),
{_,Reclaimed1,_} = erlang:statistics(garbage_collection),
GC = Reclaimed1 - Reclaimed0,
if GC < 0 ->
io:format("Reclaimed0=~w~nReclaimed1=~w~n",
[Reclaimed0, Reclaimed1]);
true ->
ok
end,
Master ! {self(), {US, GC}}
end),
receive
{P, Data} -> Data
end.
-ifndef(NO_HAVE_RAND).
%% Erlang 19 or later
rand_uniform(Limit) -> rand:uniform(Limit).
rand_uniform() -> rand:uniform().
rand_seed(Opts) ->
case proplists:get_value(random_seed, Opts) of
undefined ->
_ = rand:uniform();
{Alg, Seed} ->
rand:seed(Alg, Seed);
AlgOrStateOrExpState ->
rand:seed(AlgOrStateOrExpState)
end.
-else.
%% Erlang 18 or earlier
rand_uniform(Limit) -> random:uniform(Limit).
rand_uniform() -> random:uniform().
rand_seed() ->
{A, B, C} = os:timestamp(),
random:seed(erlang:phash2(A+B+C), erlang:phash2(B+C), erlang:phash2(A+C)).
rand_seed(Opts) ->
Seed = proplists:get_value(random_seed, Opts, random:seed0()),
set_random_seed(Seed).
set_random_seed({A,B,C}) ->
random_seed(A,B,C).
-endif. % NO_HAVE_RAND