art
art copied to clipboard
art: implement OverlapsPrefix
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.