art icon indicating copy to clipboard operation
art copied to clipboard

art: implement OverlapsPrefix

Open danderson opened this issue 2 years ago • 0 comments

Roughly 4-8x faster than the naive netipx.IPSet implementation (which the benchmark below is comparing against).

                                  │   old.txt    │               new.txt               │
                                  │    sec/op    │   sec/op     vs base                │
TableOverlapsPrefix/ipv4/10-32      211.70n ± 1%   16.07n ± 1%  -92.41% (p=0.000 n=10)
TableOverlapsPrefix/ipv4/100-32      66.12n ± 3%   15.11n ± 1%  -77.15% (p=0.000 n=10)
TableOverlapsPrefix/ipv4/1000-32     67.15n ± 3%   15.60n ± 1%  -76.77% (p=0.000 n=10)
TableOverlapsPrefix/ipv4/10000-32    66.00n ± 1%   16.16n ± 2%  -75.51% (p=0.000 n=10)
TableOverlapsPrefix/ipv6/10-32      200.30n ± 2%   15.76n ± 4%  -92.13% (p=0.000 n=10)
TableOverlapsPrefix/ipv6/100-32     121.85n ± 2%   20.54n ± 1%  -83.15% (p=0.000 n=10)
TableOverlapsPrefix/ipv6/1000-32    124.30n ± 2%   15.04n ± 1%  -87.90% (p=0.000 n=10)
TableOverlapsPrefix/ipv6/10000-32   123.50n ± 4%   14.89n ± 2%  -87.94% (p=0.000 n=10)
geomean                              111.1n        16.06n       -85.54%

                                  │   old.txt   │                new.txt                 │
                                  │   addrs/s   │   addrs/s     vs base                  │
TableOverlapsPrefix/ipv4/10-32      4.724M ± 1%   62.220M ± 1%  +1217.15% (p=0.000 n=10)
TableOverlapsPrefix/ipv4/100-32     15.12M ± 3%    66.20M ± 1%   +337.70% (p=0.000 n=10)
TableOverlapsPrefix/ipv4/1000-32    14.89M ± 3%    64.10M ± 1%   +330.38% (p=0.000 n=10)
TableOverlapsPrefix/ipv4/10000-32   15.15M ± 1%    61.86M ± 2%   +308.23% (p=0.000 n=10)
TableOverlapsPrefix/ipv6/10-32      4.993M ± 2%   63.435M ± 4%  +1170.40% (p=0.000 n=10)
TableOverlapsPrefix/ipv6/100-32     8.205M ± 2%   48.693M ± 1%   +493.47% (p=0.000 n=10)
TableOverlapsPrefix/ipv6/1000-32    8.043M ± 2%   66.505M ± 1%   +726.84% (p=0.000 n=10)
TableOverlapsPrefix/ipv6/10000-32   8.098M ± 4%   67.160M ± 2%   +729.31% (p=0.000 n=10)
geomean                             8.999M         62.24M        +591.64%

The overlap check is also alloc-free, same as the IPSet implementation.

danderson avatar Nov 09 '23 19:11 danderson