SIMD IPv6 lookup vs Patricia trie: surprising real-world results

I’ve been working on a C++ implementation of a SIMD-accelerated IPv6 longest-prefix-match (LPM) structure based on the PlanB paper (linearized B+-tree + AVX-512).



On synthetic workloads, the results were as expected:

\~20× faster than a naive Patricia trie.



But when I switched to a real BGP table (RIPE RIS rrc00, \~254K IPv6 prefixes), I got a surprising result:



A simple Patricia trie can actually match or even outperform the SIMD-based tree.



Numbers (single core, Ice Lake laptop):

\- SIMD tree: \~65–137 MLPS

\- Patricia: \~95 MLPS median



The reason seems to be cache locality and early exits:

\- Patricia often resolves lookups after just a few pointer hops in hot regions of the address space

\- The SIMD tree always pays a fixed traversal cost (depth \~7)



So even though the SIMD approach is more “theoretically efficient”, real-world prefix distribution and access patterns change the outcome quite a bit.



I’m curious if others have observed similar effects in routing / packet processing systems, or when comparing structures like PopTrie / CP-Trie.



Repo (MIT, includes benchmarks + real BGP reproduction):

https://github.com/esutcu/planb-lpm

https://redd.it/1sqe08e
@r_cpp