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

planb-lpm is a project that reimplements the IPv6 longest-prefix-match(LPM) algorithm from the PlanB paper as a portable, MIT-licensed C++17 library.

The core components are as follows.

• header-only core include/lpm6.hpp: builds even without AVX-512, automatically falling back to a scalar path
• Dynamic FIB lpm6::Dynamic: uses a rebuild-and-swap approach with std::atomic<std::shared_ptr> to make lookup wait-free
• Python bindings: based on pybind11, usable via pip install -e .
• Correctness tests: compares against a brute-force LPM reference and a synthetic FIB
• Sample generator: examples/generate_sample.py

Benchmarks were measured with 1 warmup run + 20 timed runs, and min/q1/median/q3/max along with the IQR are published together to reveal variability. The test environment was Intel i5-1035G7 Ice Lake, Ubuntu 24.04 on WSL, GCC 13.3, -O3, pinned to a single core for measurement.

As a result:

• single and batch<1> are nearly identical, meaning dispatch overhead is effectively nonexistent.
• batch<8> showed a throughput improvement of roughly 1.5x.
• batch<16> showed a temporary drop due to register pressure effects, and batch<32> recovered back to a similar level.
• Compared to the conventional baseline, the Patricia trie, it showed results about 20x faster based on median.

Memory footprint was also compared.

• At 100K prefixes, the tree is about 4.82 MB, while the Patricia trie is about 6.04 MB
• The tree was also smaller based on RSS delta, but at 250K and above, the footprint can jump sharply due to depth transitions in the linearized B+-tree, potentially exceeding Patricia's footprint.

In the FIB-size sweep:

• As the FIB grows larger, throughput drops significantly once it exceeds the L3 cache
• For small FIBs, batch<8> is advantageous, but for large FIBs, batch<32> yields better results
• rebuild time increases roughly linearly, from 1.5 ms at 10K to 213.4 ms at 1M

Overall, this post organizes the PlanB-family IPv6 LPM into a practically usable form and is a technical writeup that verifies speed, memory, and rebuild cost with numbers.