-module(keyval_benchmark). -compile(export_all). %% Runs all benchmarks with Reps number of elements. bench(Reps) -> io:format("Base Case:~n"), io:format("Operation\tTotal (µs)\tAverage (µs)~n"), print(base_case(Reps)), io:format("~nNaive Orddict:~n"), io:format("Operation\tTotal (µs)\tAverage (µs)~n"), print(naive_orddict(Reps)), io:format("~nSmart Orddict:~n"), io:format("Operation\tTotal (µs)\tAverage (µs)~n"), print(smart_orddict(Reps)), io:format("~nNaive Dict:~n"), io:format("Operation\tTotal (µs)\tAverage (µs)~n"), print(naive_dict(Reps)), io:format("~nSmart Dict:~n"), io:format("Operation\tTotal (µs)\tAverage (µs)~n"), print(smart_dict(Reps)), io:format("~nNaive gb_trees:~n"), io:format("Operation\tTotal (µs)\tAverage (µs)~n"), print(naive_gb_trees(Reps)), io:format("~nSmart gb_trees:~n"), io:format("Operation\tTotal (µs)\tAverage (µs)~n"), print(smart_gb_trees(Reps)). %% formats the benchmark results cleanly. print([]) -> ok; print([{Op, Total, Avg} | Rest]) -> io:format("~8s\t~10B\t~.6f~n", [Op, Total, Avg]), print(Rest). %% Example of a base benchmark function. This one actually does %% nothing and can be used as a control for all the benchmark - it %% will measure how much time it takes just to loop over data and %% apply functions. base_case(Reps) -> benchmark(Reps, % N repetitions [], % Empty data structure fun ?MODULE:null/3, % Create fun ?MODULE:null/2, % Read fun ?MODULE:null/3, % Update fun ?MODULE:null/2). % Delete %% Ordered dictionaries. Assumes that the value is present on reads. smart_orddict(Reps) -> benchmark(Reps, orddict:new(), fun orddict:store/3, fun orddict:fetch/2, fun orddict:store/3, fun orddict:erase/2). %% Ordered dictionaries. Doesn't know whether a key is there or not on %% reads. naive_orddict(Reps) -> benchmark(Reps, orddict:new(), fun orddict:store/3, fun orddict:find/2, fun orddict:store/3, fun orddict:erase/2). %% Dictionary benchmark. Assumes that the value is present on reads. smart_dict(Reps) -> benchmark(Reps, dict:new(), fun dict:store/3, fun dict:fetch/2, fun dict:store/3, fun dict:erase/2). %% Dictionary benchmark. Doesn't know if the value exisst at read time. naive_dict(Reps) -> benchmark(Reps, dict:new(), fun dict:store/3, fun dict:find/2, fun dict:store/3, fun dict:erase/2). %% gb_trees benchmark. Uses the most general functions -- i.e.: it never %% assumes that the value is not in a tree when inserting and never assumes %% it is there when updating or deleting. naive_gb_trees(Reps) -> benchmark(Reps, gb_trees:empty(), fun gb_trees:enter/3, fun gb_trees:lookup/2, fun gb_trees:enter/3, fun gb_trees:delete_any/2). %% gb_trees benchmark. Uses specific function: it assumes that the values %% are not there when inserting and assumes it exists when updating or %% deleting. smart_gb_trees(Reps) -> benchmark(Reps, gb_trees:empty(), fun gb_trees:insert/3, fun gb_trees:get/2, fun gb_trees:update/3, fun gb_trees:delete/2). %% Empty functions used for the 'base_case/1' benchmark. They must do %% nothing interesting. null(_, _) -> ok. null(_, _, _) -> ok. %% Runs all the functions of 4 formats: Create, Read, Update, Delete. %% Create: it's a regular insertion, but it goes from an empty structure %% to a filled one. Requires an empty data structure, %% Read: reads every key from a complete data structure. %% Update: usually, this is the same as the insertion from 'create', %% except that it's run on full data structures. In some cases, %% like gb_trees, there also exist operations for updates when %% the keys are known that act differently from regular inserts. %% Delete: removes a key from a tree. Because we want to test the %% efficiency of it all, we will always delete from a complete %% structure. %% The function returns a list of all times averaged over the number %% of repetitions (Reps) needed. benchmark(Reps, Empty, CreateFun, ReadFun, UpdateFun, DeleteFun) -> Keys = make_keys(Reps), {TimeC, Struct} = timer:tc(?MODULE, create, [Keys, CreateFun, Empty]), {TimeR, _} = timer:tc(?MODULE, read, [Keys, Struct, ReadFun]), {TimeU, _} = timer:tc(?MODULE, update, [Keys, Struct, UpdateFun]), {TimeD, _} = timer:tc(?MODULE, delete, [Keys, Struct, DeleteFun]), [{create, TimeC, TimeC/Reps}, {read, TimeR, TimeR/Reps}, {update, TimeU, TimeU/Reps}, {delete, TimeD, TimeD/Reps}]. %% Generate unique random numbers. No repetition allowed make_keys(N) -> %% The trick is to generate all numbers as usual, but match them %% with a random value in a tuple of the form {Random, Number}. %% The idea is to then sort the list generated that way; done in %% this manner, we know all values will be unique and the randomness %% will be done by the sorting. Random = lists:sort([{random:uniform(N), X} || X <- lists:seq(1, N)]), %% it's a good idea to then filter out the index (the random index) %% to only return the real numbers we want. This is simple to do %% with a list comprehension where '_' removes the extraneous data. %% The keys are then fit into a tuple to make the test a bit more %% realistic for comparison. [{some, key, X} || {_, X} <- Random]. %% Loop function to apply the construction of a data structure. %% The parameters passed are a list of all keys to use and then the %% higher order function responsible of the creation of a data %% structure. This is usually a function of the form %% F(Key, Value, Structure). %% In the first call, the structure has to be the empty data structure %% that will progressively be filled. %% The only value inserted for each key is 'some_data'; we only care %% about the keys when dealing with key/value stuff. create([], _, Acc) -> Acc; create([Key|Rest], Fun, Acc) -> create(Rest, Fun, Fun(Key, some_data, Acc)). %% Loop function to apply successive readings to a data structure. %% The parameters passed are a list of all keys, the complete data %% structure and then a higher order function responsible for %% fetching the data. Such functions are usually of the form %% F(Key, Structure). read([], _, _) -> ok; read([Key|Rest], Struct, Fun) -> Fun(Key, Struct), read(Rest, Struct, Fun). %% Loop function to apply updates to a data structure. %% Takes a list of keys, a full data structure and a higher order %% function responsible for the updating, usually of the form %% F(Key, NewValue, Structure). %% All values for a given key are replaced by 'newval', again because %% we don't care about the values, but merely the operations with %% the keys. update([], _, _) -> ok; update([Key|Rest], Struct, Fun) -> Fun(Key, newval, Struct), update(Rest, Struct, Fun). %% Loop function to apply deletions to a data structure. %% Each deletion is made on a full data structure. %% Takes a list of keys, a data structure and a higher order function %% to do the deletion. Usually of the form %% F(Key, Structure). delete([], _, _) -> ok; delete([Key|Rest], Struct, Fun) -> Fun(Key, Struct), delete(Rest, Struct, Fun).