Benchmarking CIDR lookups in ETS

cidr_test.erl

%% ETS CIDR Benchmark
%%
%% Written in 2015 by Adam Cammack <[email protected]>
%%
%% To the extent possible under law, the author have dedicated all copyright and
%% related and neighboring rights to this software to the public domain
%% worldwide. This software is distributed without any warranty. 
%%
%% See <http://creativecommons.org/publicdomain/zero/1.0/>

-module(cidr_test).

-export([measure/0]).
-export([prev_test/2, select_test/2, decrementing_lookup_test/2]).

% 2015-11-20 | Erlang/OTP 18.1 -smp enable
%
% ets:prev/2 (ordered): 9.40000e-5
% ets:select/3 (ordered): 1.45619e+1
% ets:lookup/2 (ordered): 1.72300e-3
% ets:lookup/2 (unordered): 7.94000e-4

% IP: 170.236.72.48
-define(TARGET, 2867611696).
-define(TARGET_CIDR, {{2867609600, 20}}).

prev(T) ->
  [?TARGET_CIDR] = case ets:lookup(T, ets:prev(T, {?TARGET, 32})) of
    [] -> not_found;
    [{{Bits, Len}}] = R ->
      case (Bits bsr (32 - Len)) == (?TARGET bsr (32 - Len)) of
        true -> R;
        false -> not_found
      end
   end.

select(T) ->
  MS = [{
    {{'$1', '$2'}}, % $1: bits, $2: len
    [{'==',
      {'bsr', '$1', {'-', {const, 32},'$2'}},
      {'bsr', ?TARGET, {'-', {const, 32},'$2'}}}],
    ['$_']
  }],
  {[?TARGET_CIDR], _Cont} = ets:select(T, MS, 1).

decrementing_lookup(T) ->
  decrementing_lookup(T, {?TARGET, 32}).

decrementing_lookup(_T, {0, 0}) ->
  not_found;
decrementing_lookup(T, {Bits, Len}) ->
  case ets:lookup(T, {Bits, Len}) of
    [] ->
      Next = Len - 1,
      Next_Comp = 32 - Next
      decrementing_lookup(T, {(Bits bsr Next_Comp) bsl Next_Comp, Next});
    [?TARGET_CIDR] ->
      ?TARGET_CIDR
  end.

prev_test(0, _T) ->
    ok;
prev_test(N, T) ->
    prev(T),
    prev_test(N - 1, T).

select_test(0, _T) ->
    ok;
select_test(N, T) ->
    select(T),
    select_test(N - 1, T).

decrementing_lookup_test(0, _T) ->
    ok;
decrementing_lookup_test(N, T) ->
    decrementing_lookup(T),
    decrementing_lookup_test(N - 1, T).

measure() ->
    N = 100,
    TO = ets:new(cidr_ord_set, [ordered_set]),
    TU = ets:new(cidr_set, [set]),
    init_table(TO),
    init_table(TU),
    {T1, ok} = timer:tc(?MODULE, prev_test, [N, TO]),
    {T2, ok} = timer:tc(?MODULE, select_test, [N, TO]),
    {T3, ok} = timer:tc(?MODULE, decrementing_lookup_test, [N, TO]),
    {T4, ok} = timer:tc(?MODULE, decrementing_lookup_test, [N, TU]),
    io:format("Time for ~p CIDR lookups in a 1,000,000 element table~n~n", [N]),
    io:format("ets:prev/2 (ordered): ~e~n", [T1 / 1000000]),
    io:format("ets:select/3 (ordered): ~e~n", [T2 / 1000000]),
    io:format("ets:lookup/2 (ordered): ~e~n", [T3 / 1000000]),
    io:format("ets:lookup/2 (unordered): ~e~n", [T4 / 1000000]).

% [ 0.6.64.0/20, 244.42.64.0/20 ]
init_table(T) ->
  [ begin
      <<Bits:32/integer>> = <<I:20, 0:12>>,
      ets:insert(T, {{Bits, 20}})
    end
    || I <- lists:seq(100, 1000100) ].