[erlang-questions] IP search optimization

[Adam Cammack]

On Mon, Nov 23, 2015 at 01:34:20PM -0600, Adam Cammack wrote:
> It would be interesting to see how the two methods scale with IPv6
> addresses. I'll try to work up a benchmark later.

It took me a little while, but I finally got a chance to benchmark them
with IPv6 (I also added parallel testing, to see which algorithm scales
better). But first, a correction:

>   Delta = (A bor B) bxor (A band B),

This simplifies to A bxor B, I don't know what I was thinking.

Time for 100,000 CIDR lookups in a 1,000,000 element table on each of 10
processes, matching the /0 rule with nested routes.

ets:prev/2 (IPv4):   3.424219
ets:lookup/2 (IPv4): 2.446373
ets:prev/2 (IPv6):   4.067232
ets:lookup/2 (IPv6): 10.953924

https://gist.github.com/acammack/17118c377d8bcf7f98ab

The IPv6 mock data was done hastily and I would happily accept
improvements. Some notable results:

The lookup/2 algorithm benefits a lot more from concurrency on my 8 core
smp system. For the same total number of calls, lookup/2 runs in about a
quarter of the time on 10 threads, but prev/2 runs in only half to a
third. This is enough for lookup/2 to become a bit faster to match the
/0 block on IPv4 (prev/2 remains faster on matches against a flat
table).

The lookup/2 algorithm takes about 4-5 times as long to match the /0
rule on IPv6 addresses vs IPv4. Since its runtime is proportional to the
number of bits in an address that are not matched, it starts getting
expensive on my box for IPv6 (~0.4 μs for each bit shifted off in the
search, single threaded). Fine for 32 bits, questionable for 128 if
every microsecond counts.

The above effect causes the lookup/2 algorithm to take ~50% longer to
match a /64 IPv6 block as the prev/2 algorithm takes to match the /0
IPv6 block, even with the concurrency advantage.

My advice remains the same: if possible, flatten the lookup table and
use ets:prev/2 without worrying about traversing up the table.
Otherwise, measure with your lookup table and a sampling of actual
addresses (but I bet prev/2 will be faster for at least IPv6).

--
Adam Cammack