https://github.com/JasonXuDeveloper/Nino

I maintain Nino, a source-generated binary serializer for C#. One optimization I’ve been working on is deserializing into an existing .NET SortedList. The wire format interleaves keys and values, while SortedList stores them in separate arrays. If the destination already has room, can we check the order and fill both arrays in one pass?

Here’s one Arm64 NEON iteration for int keys and values. Each input vector is 128 bits:

    a = [k1, v1, k2, v2]
    b = [k3, v3, k4, v4]

    UZP1(a, b)               -> [k1, k2, k3, k4]
    UZP2(a, b)               -> [v1, v2, v3, v4]
    EXT(previous, keys, #12) -> [k0, k1, k2, k3]

The last lane of `previous` holds k0. `EXT #12` lines it up with k1, so a single lane-wise comparison checks four adjacent pairs, including the one that crosses the vector boundary. The key vector we compare is also the one we store and carry into the next iteration.

The old path already used SIMD, but it walked the interleaved input twice. Fusing the loops saves two 128-bit input loads and one UZP1 per four pairs. The ordered reuse path is still O(n), with O(1) extra space. The win is doing less work per pair. We update the list’s count only after validation succeeds. Unsorted input falls back to insertion, which can still be O(n²).

The first generic version had a surprise: the Arm64 JIT’s on-stack replacement spilled the previous key vector. The loop now uses AggressiveOptimization so it starts with optimized code and keeps that vector in a register in the listing I checked.

There’s also a four-byte counterexample. A custom index can wrap an int and sort it in descending order. UZP still splits those bytes correctly, but an ascending integer comparison would reject the right order. For that case, Nino checks the actual comparer first, then uses the same SIMD splitter when the staged pair layout matches. That path still needs the staging array.