tl;dr: As of version 0.1.4, the\ngearhash crate has gained a NEON backend\nwhich makes it roughly 2× faster on ARM64 at typical chunk sizes. It is\nselected automatically on aarch64 and backwards compatible, so consumers of the\ncrate don't need to do more than just update. Read on if you're interested in\nthe details of how this was achieved, or skip straight to the final\nresults.
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.
\nAnyway, as part of this I came across the FastCDC\npaper. Its building block is the GEAR\nrolling hash. Because I like fast things, I spent quite some time trying to work\nout how to convert the serial algorithm published in the paper into a SIMD\nalgorithm. I ended up publishing the result of this as\ngearhash, a small Rust crate with\noptimizations 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.
\nFast forward to today, a lot has changed. Apple has pushed ARM64 into the\nmainstream of consumer hardware. AWS has shipped several further Graviton\ngenerations and says that for three years running more than half of the new CPU\ncapacity it added has been Graviton. GitHub Actions added free ARM64 runners for\npublic repositories in 2025. On all of those machines, the gearhash crate was\nfalling back to the scalar loop.
On top of this, while gearhash initially had virtually no production users\naside from myself, it has since become a core part of the Xet\nclient, Hugging Face's storage\nprotocol for large files on the Hub, which has replaced Git LFS as the default.\nFor gearhash this means we're now doing between 10k and 20k downloads per day.\nThis renewed interest in the crate helped me find the motivation to see where I\ncan push things further.
The gear hash kernel is defined as a serial function over 64-bit unsigned integers:
\nTwo properties make this difficult to vectorize:
\nIt 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\nstream.
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\nabout the first property: the hash is 64 bits wide and shifts left by one bit\nper byte, so after 64 bytes the starting value has been shifted out completely.\nThat means you can start hashing at any offset in a buffer with hash = 0, warm\nup over 64 bytes, and from then on the hash is bit-identical to a pass from the\nstart.
What this enables is that a chunk can be split into strips: seed lane 0 with\nthe real incoming hash, seed every other lane by hashing the 64 bytes that\nprecede its strip, and run all strips in lockstep. When a lane reports a match,\nyou just need to work out which match is earliest, which is where most of the\ncomplexity in the implementation ended up being.
\nI started out by doing a straight port from the SSE4.2 implementation.\naarch64::uint64x2_t is two 64-bit lanes, the same as x86_64::__m128i, so the SSE4.2 structure\nmaps over almost mechanically.
The one thing that did not map over is the mask extraction. NEON has no\nequivalent of pmovmskb, so getting the lane comparison results into a scalar\nregister takes a narrowing shift and a move, which I wrapped in a small\nmovemask helper.
The result was disappointing: 0.92×, slower than the scalar code.
\nTo understand why, we need to take a look at the loop-carried latency on ARM64. Per iteration the NEON version would do this:
\nOn Apple cores each of these are ~2 cycles each (per Dougall Johnson's M1\ntables), so ~4 cycles\nper iteration, and an iteration covers 2 bytes (one per lane), which comes out\nto ~2 cycles per byte.
\nThe scalar version, hash = (hash << 1) + table[b], compiles to a single\nshifted-register add, add x0, x1, x0, lsl #1, with ~2 cycles of latency. That\nis 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.
\nTo win on NEON, the dependency chain itself has to get shorter.
\nIf 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:
\nh₁ = (h << 1) + g₀\nh₂ = (h << 2) + (g₀ << 1) + g₁With this, h₂ depends on h through a single shift and a single add,\nprovided you precompute G = (g₀ << 1) + g₁. G depends only on table\nlookups, not on h, so it is off the critical path.
Result: 0.92× → 1.13×, better, but still well short of the expected 2×.
\nTurns 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\ncourse, but it puts a second add back on the dependency chain.
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:
\nChecking 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!
\nEncouraged by the result of unrolling to two steps at once, I tried the same\nwith four intermediate states, each still computed directly from h:
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.
\nFollowing 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.
\nResult: 1.46× → 1.63×, another large step towards the 2× goal.
\nWith 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.
\nWhile 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.
\nBecause 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:
\nOnly 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.
\nResult: 1.63× → 1.81×. Quite happy with this, and here is where I stopped for now.
\nEverything combined, on the crate's 11-bit benchmark mask, that takes the NEON\npath from 0.92× for the direct port to 1.81× in the version that I published as\n0.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.
\n| bits set | mean chunk | scalar MB/s | NEON MB/s | ratio |
|---|---|---|---|---|
| 4 | 16 B | 996 | 250 | 0.25× |
| 8 | 256 B | 1864 | 1641 | 0.88× |
| 11 | 2 KiB | 1981 | 3565 | 1.80× |
| 16 | 64 KiB | 1999 | 4277 | 2.14× |
| 20 | 1 MiB | 2000 | 4347 | 2.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×.
\nSidenote: 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.
\nWith 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!
","headings":[]}}