debuggaop7 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.
talsania2 hours 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__4 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.)
zx2c44 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__3 hours ago
I use Wireguard rarely enough that the AllowedIPs concept gets me every time. It gets easier when I replace it mentally with “Route=” :-)
zx2c42 hours ago
It's like a routing table on the way out and an ACL on the way in. Maybe an easier way to think of it.
Sesse__an hour ago
Sure, but how does this differ from a routing table with RPF (which is default in Linux already)?
zx2c431 minutes ago
It's associated per-peer, so it assures a cryptographic mapping between src ip and public key.
newman3144 hours ago
I wonder if this would port nicely over to rustybgp.
ozgrakkurt5 hours ago
Why detect avx512 in build system instead of using #ifdef ?
ozgrakkurtan hour ago
It actually does detect it using ifdef [0] but uses cmake stuff to avoid passing "-mavx512" kind of flags to the compiler [1].
[0] https://github.com/esutcu/planb-lpm/blob/748d19d5fbd945cefa3...
[1] https://github.com/esutcu/planb-lpm/blob/748d19d5fbd945cefa3...
NooneAtAll34 hours ago
I wonder how this would look like in risc-v vector instructions
throwaway815233 hours ago
IPv6 longest-prefix-match (LPM).
sylware2 hours ago
Sad it is c++.
ozgrakkurtan hour ago
Why? It is 500 lines of pretty basic code. You can port it if you don't like C++ to any language, assuming you understand what it is.
It does look a bit AI generated though
simoncion3 minutes ago
> It does look a bit AI generated though
These days, when I hear a project owner/manager describe the project as a "clean room reimplementation", I expect that they got an LLM [0] to extrude it. This expectation will not always be correct, but it'll be correct more likely than not.
[0] ...whose "training" data almost certainly contains at least one implementation of whatever it is that it's being instructed to extrude...