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.
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.)
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
This is cool! In my experience the absolute most important factor for performance is that we are able to hold the FIB in CPU Cache, and my reading of this is that at >250K prefixes patrica may use less space? Did you find this?
E.g with a CPU with say 256MB L3 cache lookups are many many times more performant because you don't need to check ram on many/any lookups. Hot top levels in L2 > hot path in local CCD L3 > rest somewhere in socket L3 > DRAM misses (ideally almost 0)
9 comments
[ 3.0 ms ] story [ 32.3 ms ] threadIncludes: - 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.
E.g with a CPU with say 256MB L3 cache lookups are many many times more performant because you don't need to check ram on many/any lookups. Hot top levels in L2 > hot path in local CCD L3 > rest somewhere in socket L3 > DRAM misses (ideally almost 0)