partialy_bound_index.erl

#!/usr/bin/env escript
%%
%%

-mode(compile).

-include_lib("stdlib/include/ms_transform.hrl").


% This benchmark is trying to measure how to store and access in ets tuples with partially bound
% and partially compared index.
% We keep tuples with key:  {Username,MessageUtc}  and want to find all messages of user User
% that were send from From to To

% Seems that only way is to hack around matchspec and edit it by hands.
% I get following results on Macbook pro with erlang 20:

% $ ./bm.erl 
% filling 1
% filling 2
% filled: 12399 and 18738 ms
% hash selct 3921
% tree selct 1628
% hash scan  0
% tree scan  1
% hash bound 3342
% tree bound 2



main([]) ->
  ets:new(mytab1,[public,named_table]),
  ets:new(mytab2,[public,named_table,ordered_set]),

  Tags = 1000,
  Entries = 10000,

  io:format("filling 1\n"),
  Tf1 = fill(mytab1,Tags,Entries),
  io:format("filling 2\n"),
  Tf2 = fill(mytab2,Tags,Entries),
  io:format("filled: ~p and ~p ms\n",[Tf1,Tf2]),

  io:format("hash selct ~p\n",[search(mytab1,<<"tag43">>,143,433)]),
  io:format("tree selct ~p\n",[search(mytab2,<<"tag43">>,143,433)]),

  io:format("hash scan  ~p\n",[search_raw(mytab1,<<"tag43">>,143,433)]),
  io:format("tree scan  ~p\n",[search_raw(mytab2,<<"tag43">>,143,433)]),

  io:format("hash bound ~p\n",[search2(mytab1,<<"tag43">>,143,433)]),
  io:format("tree bound ~p\n",[search2(mytab2,<<"tag43">>,143,433)]),

  ok.

fill(Table, TagCount, EntryCount) ->
  T1 = erlang:system_time(milli_seconds),
  [ets:insert(Table, [{{<<"tag",(integer_to_binary(T))/binary>>,I},I*I} || I <- lists:seq(1,EntryCount)])
    || T <- lists:seq(1,TagCount)],
  T2 = erlang:system_time(milli_seconds),
  T2-T1.

search(Table,Tag,From,To) ->
  T1 = erlang:system_time(milli_seconds),
  ets:select(Table,ets:fun2ms(fun({{Tag0,K},V}) when Tag0 == Tag andalso K > From andalso K < To -> {Tag0,K,V} end)),
  T2 = erlang:system_time(milli_seconds),
  T2-T1.


search2(Table,Tag,From,To) ->
  T1 = erlang:system_time(milli_seconds),
  % MS = [{{{Tag,'$2'},'$3'},[{'andalso',{'>','$2',{const,From}},{'<','$2',{const,To}}}],[{{Tag,'$2','$3'}}]}],
  [{Head,Cond,[{Out}]}] = ets:fun2ms(fun({{Tag0,K},V}) when K > From andalso K < To -> {Tag0,K,V} end),
  Head1 = setelement(1,Head,{Tag,'$2'}),
  Out1 = setelement(1,Out,Tag),
  MS = [{Head1,Cond,[{Out1}]}],
  ets:select(Table,MS),
  T2 = erlang:system_time(milli_seconds),
  T2-T1.


search_raw(Table,Tag,From,To) ->
  T1 = erlang:system_time(milli_seconds),
  List = search_raw0(Table,Tag,From,To),
  Length = length(List),
  To-From == Length orelse error({From,To,Length}),
  T2 = erlang:system_time(milli_seconds),
  T2-T1.



search_raw0(_Table, _Tag, From,To) when From >= To ->
  [];

search_raw0(Table, Tag, From,To) ->
  case ets:lookup(Table,{Tag,From}) of
    [] -> search_raw0(Table,Tag,From+1,To);
    [E] -> [E|search_raw0(Table,Tag,From+1,To)]
  end.