Speeding up gearhash on ARM64 (2× faster)
a day ago
- gearhash crate version 0.1.4 adds a NEON backend for ARM64, making it roughly 2× faster at typical chunk sizes, selected automatically on aarch64 with backward compatibility.
- The challenge: gear hash is serial with a dependency chain and uses table lookups (gather), making vectorization difficult.
- Key insight: windowing the hash over 64 bytes allows splitting chunks into strips, enabling parallel processing.
- Porting SSE4.2 to NEON was straightforward except for mask extraction; initial result was slower (0.92×) due to loop-carried latency.
- Shortening the dependency chain by processing 4 bytes per step (via unrolling) initially improved to 1.46× before compiler reassociation issues were manually fixed.
- Further optimization included reducing load instructions (combining byte loads into 32-bit loads) and combining boundary tests to branch less frequently, achieving 1.81×.
- Final benchmarks show NEON speedup ranges from 0.25× (very sparse masks) to 2.17× (sparse masks), with 2.14× for typical use (16-bit mask).
- Future work includes revisiting x86 backends with learnings from NEON optimization.