Clast.FastLanes 0.2.0

FastLanes

A .NET implementation of the FastLanes compression primitives — the column compression layout introduced by Afroozeh & Boncz (VLDB 2023) and used on disk by the Lance file format. Wire-compatible byte-for-byte with the spiraldb/fastlanes Rust crate, so packed pages produced by either implementation can be read by the other.

Targets net10.0, net8.0, and netstandard2.0.

What it does

Two primitives:

• Bit-packing. Given 1024 unsigned integers of type T ∈ {byte, ushort, uint, ulong} and a bit width W ∈ [0, sizeof(T) * 8], pack them into 1024 * W / 8 bytes using the FastLanes Unified Transposed Layout — and reverse. The transpose places values so SIMD lanes decode in parallel with no cross-lane shuffles.
• Delta encoding. Per-lane wrapping difference / prefix sum on a 1024-element chunk in transposed layout. Designed to be fused with bit-packing on the encode side and unfused or fused (UndeltaUnpackChunk) on the decode side.

API

namespace Clast.FastLanes;

public static class BitPacking
{
    public const int ElementsPerChunk = 1024;

    // 1024 * bitWidth / 8
    public static int PackedByteCount<T>(int bitWidth) where T : unmanaged;

    // Minimum bit width needed to represent every value in input;
    // 0 if all zero, else 1..sizeof(T)*8.
    public static int MaxBits<T>(ReadOnlySpan<T> input) where T : unmanaged;

    public static void PackChunk<T>(int bitWidth, ReadOnlySpan<T> input, Span<byte> packed)
        where T : unmanaged;

    public static void UnpackChunk<T>(int bitWidth, ReadOnlySpan<byte> packed, Span<T> output)
        where T : unmanaged;
}

public static class Delta
{
    public const int ElementsPerChunk = 1024;

    // 1024 / (sizeof(T) * 8): 128, 64, 32, 16 for byte, ushort, uint, ulong.
    public static int LaneCount<T>() where T : unmanaged;

    // Encode per-lane wrapping deltas. base is the per-lane "previous value" — pass
    // zeros for the first chunk in a stream, or carry forward the per-lane terminal
    // values from the previous chunk. Input must already be in transposed layout.
    public static void DeltaChunk<T>(ReadOnlySpan<T> input, ReadOnlySpan<T> @base, Span<T> output)
        where T : unmanaged;

    // Reverse encoding: per-lane running prefix sum.
    public static void UndeltaChunk<T>(ReadOnlySpan<T> input, ReadOnlySpan<T> @base, Span<T> output)
        where T : unmanaged;

    // Fused unpack + undelta in one pass — combines bit-unpack with the per-lane
    // prefix sum so values do not transit memory between the two stages.
    public static void UndeltaUnpackChunk<T>(int bitWidth, ReadOnlySpan<byte> packed, ReadOnlySpan<T> @base, Span<T> output)
        where T : unmanaged;
}

Typical bit-packing usage:

var input = new uint[1024];         // fill with data
int w = BitPacking.MaxBits<uint>(input);
var packed = new byte[BitPacking.PackedByteCount<uint>(w)];
BitPacking.PackChunk<uint>(w, input, packed);

// later …
var output = new uint[1024];
BitPacking.UnpackChunk<uint>(w, packed, output);

Delta + bit-pack pipeline (mirrors the upstream Delta::delta → BitPacking::pack → Delta::undelta_pack workflow):

// transposed: 1024 values already in FastLanes transposed layout.
var @base = new uint[Delta.LaneCount<uint>()]; // zeros = first chunk
var deltas = new uint[1024];
Delta.DeltaChunk<uint>(transposed, @base, deltas);

int w = BitPacking.MaxBits<uint>(deltas);
var packed = new byte[BitPacking.PackedByteCount<uint>(w)];
BitPacking.PackChunk<uint>(w, deltas, packed);

// decode side — fused
var reconstructed = new uint[1024];
Delta.UndeltaUnpackChunk<uint>(w, packed, @base, reconstructed);
// or unfused: BitPacking.UnpackChunk + Delta.UndeltaChunk

For Lance-style pages with a partial trailing chunk, pad the packed input with zero bytes and slice the output after decoding.

Performance

Measured on an Intel i9-12900K running .NET 10 (AVX2; the CPU has AVX-512 disabled in microcode, so Vector512 emulates as 2× Vector256 here). One chunk = 1024 values.

At W=3 the hand-SIMD path matches the published spiraldb/fastlanes AVX2 numbers (~50 ns/chunk) — that's the AVX2 ceiling. On a host with native AVX-512 you would expect V512 to run closer to half the V256 time.

How it works

Each (T, W) pair gets four specialized kernels — one scalar, one Vector128<T>, one Vector256<T>, one Vector512<T> — produced by a Roslyn source generator (src/FastLanes.Generator). All the inner loops are fully unrolled with masks, shifts, and word offsets folded to literals, which is what lets the compiler emit straight-line SIMD. At runtime the dispatcher picks the widest variant whose vector type reports IsHardwareAccelerated:

V512 → V256 → V128 → Scalar

On ARM64 (no native 256/512-bit SIMD), Vector128 is the accelerated tier and handles the NEON path. On x86 AVX2 machines, Vector256 wins. On netstandard2.0, only the scalar path exists because System.Runtime.Intrinsics isn't available.

The layout permutation is the verbatim FL_ORDER = [0, 4, 2, 6, 1, 5, 3, 7] from spiraldb/fastlanes, with logical input index for row r, lane l given by FL_ORDER[r/8] * 16 + (r%8) * 128 + l. See src/FastLanes.Generator/BitPackingGenerator.cs for the emitter.

Tests

dotnet test

Runs ~340 tests:

• Round-trip pack/unpack for every (T, W) pair, including W=0 and full-width.
• Cross-variant agreement for bit-packing: scalar, V128, V256, and V512 must produce byte-identical output for every (T, W).
• Input-masking semantics (values wider than W are truncated).
• MaxBits on spans of various sizes, including sizes that force vector tail handling.
• W=T permutation identity check, locking the FL_ORDER layout in place.
• Delta / Undelta round-trip and reference-oracle agreement for every T, with random per-lane base.
• Fused UndeltaUnpackChunk byte-for-byte agreement with two-stage UnpackChunk + UndeltaChunk for every (T, W).
• Cross-variant agreement for Delta and UndeltaUnpack.
• Wrapping-arithmetic edge case — saturated values cleanly wrap around to match upstream wrapping_sub / wrapping_add.

Benchmarks

cd bench/FastLanes.Bench
dotnet run -c Release -- --filter '*' --job short

The benchmark project has:

• U32Benchmarks / U64Benchmarks — end-to-end Pack / Unpack / MaxBits via the public API at representative widths.
• VariantComparison — forced-variant (Scalar vs V128 vs V256 vs V512) head-to-head for UnpackU32, for diagnosing which tier wins on a given host.

Known gaps

These are real but not blockers for the core use case. Flagged here so they're not surprises.

1. No cross-implementation golden-bytes test. The W=32 permutation-identity test locks down the layout formula, but there's no test that asserts "given this input, the packed bytes are exactly these bytes as produced by spiraldb/fastlanes." Adding one would require dumping a reference byte array from the Rust crate and checking it in. Strongly recommended if shipping as a Lance-interop library.

2. Big-endian hosts. The library reinterprets Span<byte> as Span<T> via MemoryMarshal.Cast, which is native-endian. On a big-endian host (increasingly rare — essentially z/OS and a few embedded targets) the on-disk bytes would be byte-swapped relative to what Lance expects. The code would still round-trip locally but would not be wire-compatible with a little-endian producer. Adding explicit LE reads would cost a perf hit; for now we assume little-endian.

3. No benchmark for the Pack-side SIMD speedup. The VariantComparison benchmark only forces variants for Unpack. Pack correctness is covered by the cross-variant tests, and the generator emits the same structure for both directions, so Pack performance should track Unpack — but that's an extrapolation, not a measurement.

CI

.github/workflows/ci.yml runs on push and pull request: restores, builds in Release, and runs the test suite on ubuntu-latest, windows-latest, and ubuntu-22.04-arm (the ARM64 leg exercises the Vector128 / NEON path on real NEON hardware rather than emulation). The library's three target frameworks (net10.0, net8.0, netstandard2.0) all build from a single .NET 10 SDK install.

.github/workflows/publish.yml triggers on v* tags, packs src/FastLanes/FastLanes.csproj in Release, and pushes both the .nupkg and .snupkg to nuget.org using a NUGET_API_KEY secret.

NuGet packaging

dotnet pack src/FastLanes/FastLanes.csproj -c Release produces Clast.FastLanes.<version>.nupkg (and .snupkg for symbols) with three TFM folders under lib/. The package embeds README and LICENSE.

The source generator project (Clast.FastLanes.Generator) is build-time only and is not shipped in the package. It runs at this repo's build time and emits IL directly into Clast.FastLanes.dll; consumers receive a self-contained assembly with all generated kernels already compiled in. This is why IsPackable=false on FastLanes.Generator.csproj and there is no analyzers/dotnet/cs/ folder in the produced .nupkg.

References

• Azim Afroozeh and Peter Boncz, "The FastLanes Compression Layout: Decoding >100 Billion Integers per Second with Scalar Code," PVLDB 16(9), 2023.
• spiraldb/fastlanes — the Rust crate Lance uses; the C# code in this repo mirrors its pack! / unpack! macro semantics and its Delta trait (delta / undelta / undelta_pack).
• lancedb/lance — the on-disk file format that consumes FastLanes-packed pages.

License

Apache 2.0. See LICENSE.