Pangram verdict · v3.3
We believe that this text is a mix of AI and human-written content.
AI likelihood · overall
MixedArticle text · 1,264 words · 8 segments analyzed
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, 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.