alt.hn

4/20/2026 at 3:24:21 AM

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

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

by debugga

4/20/2026 at 4:08:50 PM

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)

by matt-p

4/20/2026 at 3:24:21 AM

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.

by debugga

4/20/2026 at 9:09:03 AM

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

by talsania

4/20/2026 at 6:31:30 AM

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.)

by Sesse__

4/20/2026 at 6:53:58 AM

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...

by zx2c4

4/20/2026 at 7:52:41 AM

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

by Sesse__

4/20/2026 at 8:59:05 AM

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.

by zx2c4

4/20/2026 at 9:43:49 AM

Sure, but how does this differ from a routing table with RPF (which is default in Linux already)?

by Sesse__

4/20/2026 at 10:09:27 AM

It's associated per-peer, so it assures a cryptographic mapping between src ip and public key.

by zx2c4

4/20/2026 at 6:54:27 AM

I wonder if this would port nicely over to rustybgp.

by newman314

4/20/2026 at 7:23:07 AM

IPv6 longest-prefix-match (LPM).

by throwaway81523

4/20/2026 at 6:23:50 AM

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

by NooneAtAll3

4/20/2026 at 10:57:58 AM

The lines

    __m512i vx  = _mm512_set1_epi64(static_cast<long long>(x));
    __m512i vk  = _mm512_load_si512(reinterpret_cast<const __m512i*>(base));
    __mmask8 m  = _mm512_cmp_epu64_mask(vx, vk, _MM_CMPINT_GE);
    return static_cast<std::uint32_t>(__builtin_popcount(m));
would be replaced with:

    return __riscv_vcpop(__riscv_vmsgeu(__riscv_vle64_v_u64m1(base, FANOUT), x, FANOUT), FANOUT);
and you set FANOUT to __riscv_vsetvlmax_e32m1() at runtime.

Alternatively, if you don't want a dynamic FANOUT you keep the FANOUT=8 (or another constant) and do a stripmining loop

    size_t cnt = 0;
    for (size_t vl, n = 8; n > 0; n -= vl, base += vl) {
     vl = __riscv_vsetvl_e64m1(n);
     cnt += __riscv_vcpop(__riscv_vmsgeu(__riscv_vle64_v_u64m1(base, vl), x, vl), vl);
    }
    return cnt;
This will take FANOUT/VLEN iterations and the branches will be essentially almost predicted.

If you know FANOUT is always 8 and you'll never want to changes it, you could alternatively use select the optimal LMUL:

    size_t vl = __riscv_vsetvlmax_e32m1();
    if (vl == 2) return __riscv_vcpop(__riscv_vmsgeu(__riscv_vle64_v_u64m4(base, 8), x, 8), 8);
    if (vl == 4) return __riscv_vcpop(__riscv_vmsge(u__riscv_vle64_v_u64m2(base, 8), x, 8), 8);
    return __riscv_vcpop(__riscv_vmsgeu(__riscv_vle64_v_u64m1(base, 8), x, 8), 8);

by camel-cdr

4/20/2026 at 8:46:06 AM

Sad it is c++.

by sylware

4/20/2026 at 9:54:53 AM

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

by ozgrakkurt

4/20/2026 at 10:37:24 AM

> 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...

by simoncion

4/20/2026 at 1:05:09 PM

As far as LLM-produced correctness goes, it all comes down to the controls that have been put in place (how valid the tests are, does it have a microbenchmark suite, does it have memory leak detection, etc.)

by pmarreck

4/20/2026 at 1:34:12 PM

side note, but I hate that we've reach the point where we don't know what's written by a human and what's written by an LLM.

That goes for a lot of comments here accusing each other of being a bot.

I feel like we've known internet trust at its highest and it can only go one way now.

by alex_duf