Benchmarking CIDR lookups in ETS - nested blocks and IPv6 in parallel

cidr_nested_test.erl

%% ETS CIDR Benchmark (nested blocks, IPv4 and IPv6)
%%
%% Written in 2015 by Adam Cammack <adam@acammack.com>
%%
%% 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_nested_test).

-export([measure/0]).
-export([test_p/3, prev_test/2, prev_test6/2, decrementing_lookup_test/2, decrementing_lookup_test6/2]).

% 2015-11-24 | Erlang/OTP 18.1 -smp enable

% IP: 244.42.192.0 - simulates non-match on nested routes with a default rule
-define(TARGET, 4096442368).
-define(TARGET_BLOCK, [{{0, 0}}]).
% IP: 170.236.72.48 - simulates match on flat table
%-define(TARGET, 2867611696).
%-define(TARGET_BLOCK, [{{2867609600, 20}}]).

% IP: 0:0:F:42E4:: - simulates non-match on nested routes with a default rule
-define(TARGET6, 18449769339737639982465024).
-define(TARGET_BLOCK6, [{{0, 0}}]).
% IP: ::A:AEC4:9C8:BE00:0:0 - simulates match on flat table
%-define(TARGET6, 12914566231026305979121664).
%-define(TARGET_BLOCK6, [{{12914565526004057086361600, 64}}]).

prev(T, {Mask, Len}) ->
  % Len + 1 to catch exact matches
  case ets:prev(T, {Mask, Len + 1}) of
    {Bits, L} = K
      when (Bits bxor Mask) bsr (32 - L) == 0 ->
      ets:lookup(T, K);
    {Bits, _L} ->
      prev(T, common_prefix32(Mask, Bits));
    '$end_of_table' ->
      []
  end;
prev(T, Addr) ->
  prev(T, {Addr, 32}).


common_prefix32(A, B) ->
  Delta = A bxor B,
  First_Difference = trunc(math:log2(Delta)) + 1,
  Prefix = (A bsr First_Difference) bsl First_Difference,
  {Prefix, 32 - First_Difference}.

prev6(T, {Mask, Len}) ->
  % Len + 1 to catch exact matches
  case ets:prev(T, {Mask, Len + 1}) of
    {Bits, L} = K
      when (Mask bxor Bits) bsr (128 - L) == 0 ->
      ets:lookup(T, K);
    {Bits, _L} ->
      prev6(T, common_prefix128(Mask, Bits));
    '$end_of_table' ->
      []
  end;
prev6(T, Addr) ->
  prev6(T, {Addr, 128}).

common_prefix128(A, B) ->
  Delta = A bxor B,
  First_Difference = trunc(math:log2(Delta)) + 1,
  Prefix = (A bsr First_Difference) bsl First_Difference,
  {Prefix, 128 - First_Difference}.

decrementing_lookup(T, {0, 0}) ->
  ets:lookup(T, {0, 0});
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});
    R ->
      R
  end;
decrementing_lookup(T, Addr) ->
  decrementing_lookup(T, {Addr, 32}).

decrementing_lookup6(T, {0, 0}) ->
  ets:lookup(T, {0, 0});
decrementing_lookup6(T, {Bits, Len}) ->
  case ets:lookup(T, {Bits, Len}) of
    [] ->
      Next = Len - 1,
      Next_Comp = 128 - Next,
      decrementing_lookup6(T, {(Bits bsr Next_Comp) bsl Next_Comp, Next});
    R ->
      R
  end;
decrementing_lookup6(T, Addr) ->
  decrementing_lookup6(T, {Addr, 128}).

prev_test(0, _T) ->
    ok;
prev_test(N, T) ->
    ?TARGET_BLOCK = prev(T, ?TARGET),
    prev_test(N - 1, T).

prev_test6(0, _T) ->
    ok;
prev_test6(N, T) ->
    ?TARGET_BLOCK6 = prev6(T, ?TARGET6),
    prev_test6(N - 1, T).

decrementing_lookup_test(0, _T) ->
    ok;
decrementing_lookup_test(N, T) ->
    ?TARGET_BLOCK = decrementing_lookup(T, ?TARGET),
    decrementing_lookup_test(N - 1, T).

decrementing_lookup_test6(0, _T) ->
    ok;
decrementing_lookup_test6(N, T) ->
    ?TARGET_BLOCK6 = decrementing_lookup6(T, ?TARGET6),
    decrementing_lookup_test6(N - 1, T).

test_p(Function, Args, Proc) ->
  Parent = self(),
  [ spawn(fun() -> apply(?MODULE, Function, Args), Parent ! done end)
  || _I <- lists:seq(1, Proc)],
  join(Proc).

join(0) -> ok;
join(N) -> receive done -> join(N - 1) end.

measure() ->
  N = 100000, P = 10,
  io:format("Time for ~p CIDR lookups in a 1,000,000 element table on each of ~p processes~n~n", [N, P]),

  %% IPv4
  TO4 = ets:new(cidr_ord_set, [ordered_set, {read_concurrency, true}]),
  TU4 = ets:new(cidr_set, [set, {read_concurrency, true}]),
  init_table4(TO4),
  init_table4(TU4),
  {T1, ok} = timer:tc(?MODULE, test_p, [prev_test, [N, TO4], P]),
  {T2, ok} = timer:tc(?MODULE, test_p, [decrementing_lookup_test, [N, TU4], P]),
  io:format("ets:prev/2 (IPv4):   ~f~n", [T1 / 1000000]),
  io:format("ets:lookup/2 (IPv4): ~f~n", [T2 / 1000000]),
  ets:delete(TO4),
  ets:delete(TU4),

  %% IPv6
  TO6 = ets:new(cidr6_ord_set, [ordered_set, {read_concurrency, true}]),
  TU6 = ets:new(cidr6_set, [set, {read_concurrency, true}]),
  init_table6(TO6),
  init_table6(TU6),
  {T3, ok} = timer:tc(?MODULE, test_p, [prev_test6, [N, TO6], P]),
  {T4, ok} = timer:tc(?MODULE, test_p, [decrementing_lookup_test6, [N, TU6], P]),
  io:format("ets:prev/2 (IPv6):   ~f~n", [T3 / 1000000]),
  io:format("ets:lookup/2 (IPv6): ~f~n", [T4 / 1000000]),
  ets:delete(TO6),
  ets:delete(TU6),

  ok.

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

% [ 0:0:0:64::/64, 0:0:F:42A4::/64 ]
init_table6(T) ->
  [ begin
      <<Bits:128/integer>> = <<I:64, 0:64>>,
      ets:insert(T, {{Bits, 64}})
    end
    || I <- lists:seq(100, 1000100) ],
  ets:insert(T, {{0, 0}}).