Speeding up gearhash on ARM64 (2× faster)

tl;dr: As of version 0.1.4, the gearhash crate has gained a NEON backend which makes it roughly 2× faster on ARM64 at typical chunk sizes. It is selected automatically on aarch64 and backwards compatible, so consumers of the crate don't need to do more than just update. Read on if you're interested in the details of how this was achieved.

How it all started

At the end of 2019, I was building a personal backup system, and as part of this, became interested in a technique called content-defined chunking. The key idea behind it is that instead of chunking files on fixed chunk boundaries, you run a sliding window hash function across the file and trigger a chunk boundary whenever the hash has a particular value. The downside is that this gives you variable length chunks over a distribution, but the upside is that your chunking is now much more resilient to byte sequences being inserted or removed from the middle of files.

Anyway, as part of this I came across the FastCDC paper. Its building block is the GEAR rolling hash. Because I like fast things, I spent quite some time trying to work out how to convert the serial algorithm published in the paper into a SIMD algorithm. I ended up publishing the result of this as gearhash, a small Rust crate with optimizations for SSE4.2 and AVX2.

When I wrote the crate, ARM64 was not really a target worth optimizing for. AWS had offered ARM64 instances for a year, but only the first-generation Graviton A1 family, built on Cortex-A72 cores and marketed for scale-out workloads rather than general compute. Graviton2, the first generation with a competitive core, was announced at re:Invent the same month as my first commit and did not reach general availability until May 2020. Apple announced the M1 in November 2020.

Fast forward to today, a lot has changed. Apple has pushed ARM64 into the mainstream of consumer hardware. AWS has shipped several further Graviton generations and says that for three years running more than half of the new CPU capacity it added has been Graviton. GitHub Actions added free ARM64 runners for public repositories in 2025. On all of those machines, the gearhash crate was falling back to the scalar loop.

On top of this, while gearhash initially had virtually no production users aside from myself, it has since become a core part of the Xet client, Hugging Face's storage protocol for large files on the Hub, which has replaced Git LFS as the default. For gearhash this means we're now doing between 10k and 20k downloads per day. This renewed interest in the crate helped me find the motivation to see where I can push things further.

The insight that unlocked parallelization

The gear hash kernel is defined as a serial function over 64-bit unsigned integers:

hash = (hash << 1).wrapping_add(table[byte as usize]);

Two properties make this difficult to vectorize:

1. It is a serial dependency chain. Every byte's hash depends on the previous byte's. There is no data parallelism to extract from a single stream.
2. The table lookup is a gather. 256 × 8 bytes is 2 KB, far too large for any in-register permute. Every byte costs a real load.

After banging my head against this for a bit, I ended up making an observation about the first property: the hash is 64 bits wide and shifts left by one bit per byte, so after 64 bytes the starting value has been shifted out completely. That means you can start hashing at any offset in a buffer with hash = 0, warm up over 64 bytes, and from then on the hash is bit-identical to a pass from the start.

What this enables is that a chunk can be split into strips: seed lane 0 with the real incoming hash, seed every other lane by hashing the 64 bytes that precede its strip, and run all strips in lockstep. When a lane reports a match, you just need to work out which match is earliest, which is where most of the complexity in the implementation ended up being.

Beginning the port to NEON

I started out by doing a straight port from the SSE4.2 implementation. uint64x2_t is two 64-bit lanes, the same as __m128i, so the SSE4.2 structure maps over almost mechanically.

The one thing that did not map over is the mask extraction. NEON has no equivalent of pmovmskb, so getting the lane comparison results into a scalar register takes a narrowing shift and a move, which I wrapped in a small movemask helper.

The result was disappointing: 0.92×, slower than the scalar code.

To understand why, we need to take a look at the loop-carried latency on ARM64. Per iteration the NEON version would do this:

add.2d   v1, v1, v1      ; h << 1, which LLVM emits as an add to itself
add.2d   v1, v1, v_g

On Apple cores each of these are ~2 cycles each (per Dougall Johnson's M1 tables), so ~4 cycles per iteration, and an iteration covers 2 bytes (one per lane), which comes out to ~2 cycles per byte.

The scalar version, hash = (hash << 1) + table[b], compiles to a single shifted-register add, add x0, x1, x0, lsl #1, with ~2 cycles of latency. That is also ~2 cycles per byte.

Which means that the vector version does the same amount of work per unit of critical path as the scalar one, but on top of that has to pay for the loads and the mask extraction. It cannot come out ahead.

To win on NEON, the dependency chain itself has to get shorter.

Shortening the chain

If the chain is 2 ops per 2 bytes, why not make it 2 ops per 4 bytes by writing out two steps of the per-byte update and multiplying through:

h₁ = (h << 1) + g₀
h₂ = (h << 2) + (g₀ << 1) + g₁

With this, h₂ depends on h through a single shift and a single add, provided you precompute G = (g₀ << 1) + g₁. G depends only on table lookups, not on h, so it is off the critical path.

Result: 0.92× → 1.13×, better, but still well short of the expected 2×.

The reason hiding in the disassembly

add.2d  v2, v1, v1      ; h << 1
add.2d  v2, v3, v2      ; h₁ = (h<<1) + g₀
shl.2d  v1, v1, #2      ; h << 2
add.2d  v3, v3, v3      ; g₀ << 1
add.2d  v1, v1, v4      ; (h<<2) + g₁      <-- on the h chain
add.2d  v1, v3, v1      ; ... + (g₀<<1)    <-- also on the h chain

Turns out, LLVM had just gone and reassociated it! I wrote (h << 2) + (G₀ + G₁) and it emitted ((h << 2) + G₁) + G₀. This is a legal transformation of course, but it puts a second add back on the dependency chain.

The somewhat naughty fix

You cannot stop the compiler reassociating a sum, but you can (try to) stop it seeing one. The combined term is built from two table lookups, and those arrive in general-purpose registers anyway, so the combining can just happen there:

let (t00, t01) = (table[b00 as usize], table[b01 as usize]);
let (t10, t11) = (table[b10 as usize], table[b11 as usize]);
 
// Combining the two table entries in scalar registers keeps the vector operand
// opaque, which stops the compiler from reassociating the addition below into two
// dependent vector adds on the loop-carried `h` chain.
let g1 = vcombine_u64(
    vcreate_u64((t00 << 1).wrapping_add(t01)),
    vcreate_u64((t10 << 1).wrapping_add(t11)),
);
 
let h2 = vaddq_u64(vshlq_n_u64::<2>(h), g1);

Checking disassembly now showed only shl.2d → add.2d on the chain. This version was also cheaper: The scalar shift-add replaces a vector shift and a vector add, and the scalar unit had spare capacity.

Result: 1.13× → 1.46×, finally starting to be meaningfully faster, but not quite fast enough!

From latency-bound to throughput-bound

Encouraged by the result of unrolling to two steps at once, I tried the same with four intermediate states, each still computed directly from h:

let h1 = vaddq_u64(vshlq_n_u64::<1>(h), g[0]);   // hk == (h << k) + g[k-1]
// ...
let h4 = vaddq_u64(vshlq_n_u64::<4>(h), g[3]);

This halves the length of the dependency chain per byte again, so I expected another large step. Measuring it however, there was no difference at all. It was at this point that I suspected the limit may no longer be the latency between iterations, but instead simply the CPU throughput.

Following that hunch, my focus shifted to try and reduce instruction counts instead. The loop was now doing two loads per byte: one for the byte itself and one for its table entry. While the latter is unavoidable, we can now can replace those four consecutive byte loads with one unaligned 32-bit load, then peel one byte off each word per step with a shift.

Result: 1.46× → 1.63×, another large step towards the 2× goal.

Testing four states with one branch

With the loads optimized, the next largest block of instructions per iteration was the boundary test: at every step, the code checks for a chunk boundary by masking the hash and comparing it to zero.

While I had unrolled to four intermediate states per iteration, it was still probing them one by one. That is four separate moves out of the vector unit, each with a branch waiting on it.

Because the common case is no match, what we can actually do is combine the four tests inside the vector unit and make one trip out. If none of the four positions in either strip is a boundary, then the iteration can move on after one move to a general-purpose register and one branch:

let t = vandq_u64(
    vandq_u64(vtstq_u64(h1, maskv), vtstq_u64(h2, maskv)),
    vandq_u64(vtstq_u64(h3, maskv), vtstq_u64(h4, maskv)),
);
 
if movemask(t) == u64::MAX {
    i += UNROLL;
    continue;
}

Only in the uncommon case when that check fails does the code look at the four states one by one. With the 16-bit mask the Xet client uses for its 64 KiB chunks, that happens about once every 8192 iterations.

Result: 1.63× → 1.81×. Quite happy with this, and here is where I stopped for now.

Final results

Everything combined, on the crate's 11-bit benchmark mask, that takes the NEON path from 0.92× for the direct port to 1.81× in the version that I published as 0.1.4.

However, one thing I realized while working on this which is quite obvious in retrospect, is how dependent the benchmark is on the mask density. That's because the optimized path has a fixed cost per call that the scalar path does not, and sparser mask means more boundaries and more calls. To see how much that matters, I ran benchmarks across a range of masks with 4 to 20 bits set.

The crate's own benchmark, at 1.8×, sits on the steep part of the curve, which keeps rising until it flattens out at about 2.17× between 64 KiB and 1 MiB. The 16-bit row is the mask the Xet client uses, at 2.14×.

Sidenote: Below roughly 350-byte average chunks the per-call cost outweighs the gain and the NEON path becomes progressively slower than scalar. I wouldn't expect anyone to use this type of configuration, but falling back to the scalar path for masks with few bits set seems like a cheap way to close that gap.

What's next

With NEON now roughly twice as fast as scalar, it feels like it's time to take another look at the x86 backends. Who knows, some of the tricks I learned along the way on the NEON implementation might carry over. Stay tuned!