Speeding up gearhash on ARM64 (2× faster) — sam reis← WritingSpeeding up gearhash on ARM64 (2× faster)September 6, 2026tl;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, or skip straight to the final
results.
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:

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.
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.
aarch64::uint64x2_t is two 64-bit lanes, the same as x86_64::__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.
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.

bits setmean chunkscalar MB/sNEON MB/sratio416 B9962500.25×8256 B186416410.88×112 KiB198135651.80×1664 KiB199942772.14×201 MiB200043472.17×
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!Pixel art by Gustavo Vituri

The effort to speed up the gearhash crate on ARM64 resulted in a roughly two-fold performance increase by leveraging specific architectural insights and algorithmic restructuring. The impetus for this work stemmed from the crate's utility in storage protocols like the Xet client, which was gaining significant traction as ARM64 became mainstream in consumer hardware. Initially, the goal was to port the existing implementation, which was optimized for SSE4.2 and AVX2, to the NEON instruction set on ARM64.

The core challenge lay in the inherent serial nature of the gear hash kernel, where each byte's hash calculation depends directly on the previous byte's result, inhibiting traditional data parallelism. To overcome this, the author explored how the 64-bit hash structure could be utilized for vectorization. The insight was that because the hash shifts left by one bit per byte, the sequence of 64 bytes could be processed in parallel by dividing the chunk into strips, where each strip is seeded with a separate initial hash value, allowing the strips to be processed in lockstep.

The initial port to NEON proved challenging; a direct implementation yielded only a modest speedup of 0.92 times compared to the scalar code, suggesting that loop-carried latency was the primary bottleneck. To improve this, the author focused on shortening the dependency chain by calculating multiple hash updates simultaneously. This involved extending the update to cover four bytes at once, which required precomputing the necessary intermediate values from table lookups. Further optimization involved recognizing issues with the compiler's reassociation of operations, using scalar registers to hold table entries to prevent reassociation across the vector operations. This iterative process improved the performance to 1.13 times, still short of the target 2 times.

Further enhancements targeted throughput rather than latency by optimizing memory access patterns. The focus shifted to reducing instruction counts by replacing sequential byte loads with fewer, unaligned 32-bit loads followed by shifts, which increased the speed to 1.63 times. Finally, the optimization addressed the boundary checking required for chunk delimitation. Instead of checking chunk boundaries sequentially, the optimization combined the comparison tests for multiple potential boundaries within the vector unit, allowing the code to proceed with a single branch based on a mask result. This step resulted in a further performance gain to 1.81 times.

The final results demonstrated that the speedup is highly dependent on the mask density used during benchmarking, with performance rising up to 2.17 times on larger chunks, whereas the specific mask used by the Xet client achieved 2.14 times. The final optimized path achieved 1.81 times speedup on the 11-bit benchmark mask, illustrating a complex interplay between reducing instruction latency, optimizing memory throughput, and parallelizing boundary conditions.