A cache-friendly IPv6 LPM with AVX-512 (linearized B+-tree, real BGP benchmarks)

Discussion (11 Comments)Read Original on HackerNews

debugga•about 6 hours ago

Clean-room, portable C++17 implementation of the PlanB IPv6 LPM algorithm.

Includes: - AVX-512 SIMD path + scalar fallback - Wait-free lookups with rebuild-and-swap dynamic FIB - Benchmarks on synthetic data and real RIPE RIS BGP (~254K prefixes)

Interesting result: on real BGP + uniform random lookups, a plain Patricia trie can sometimes match or beat the SIMD tree due to cache locality and early exits.

Would love feedback, especially comparisons with PopTrie / CP-Trie.

talsania•13 minutes ago

254K prefixes with skewed distribution means early exits dominate, and no SIMD throughput advantage survives a branch that terminates at depth 3. The interesting edge case is deaggregation events where prefix counts spike transiently and the rebuild-and-swap FIB has to absorb a table that's temporarily 2x normal size

Sesse__•about 3 hours ago

The obvious question, I guess: How much faster are you than whatever is in the Linux kernel's FIB? (Although I assume they need RCU overhead and such. I have no idea what it all looks like internally.)

zx2c4•about 2 hours ago

I likewise wonder from time to time whether I should replace WireGuard's allowedips.c trie with something better: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...

Sesse__•about 1 hour ago

I use Wireguard rarely enough that the AllowedIPs concept gets me every time. It gets easier when I replace it mentally with “Route=” :-)

newman314•about 2 hours ago

I wonder if this would port nicely over to rustybgp.

throwaway81523•about 2 hours ago

IPv6 longest-prefix-match (LPM).

ozgrakkurt•about 4 hours ago

Why detect avx512 in build system instead of using #ifdef ?

NooneAtAll3•about 3 hours ago

I wonder how this would look like in risc-v vector instructions

sylware•36 minutes ago

Sad it is c++.

A cache-friendly IPv6 LPM with AVX-512 (linearized B+-tree, real BGP benchmarks)

⚡ Community Insights

Discussion (11 Comments)Read Original on HackerNews