Hamming Bitwise Fast

Fast bitwise Hamming distance for byte arrays/slices, using auto-vectorization with runtime SIMD detection on x86.

Note: This is for comparing bit-vectors, not for comparing strings.

On x86, enable LTO for best performance — see Performance on x86.

Usage

For variable-length slices:

use hamming_bitwise_fast::slice;

// Single comparison
let a: Vec<u8> = vec![0xFF; 128];
let b: Vec<u8> = vec![0x00; 128];
let distance: u32 = slice::distance(&a, &b); // 1024

// Batch comparison (one source vs many targets)
// Pre-allocate result vec once and reuse across calls for best performance
let source: Vec<u8> = vec![0x00; 128];
let targets: Vec<&[u8]> = vec![&a, &b];
let mut distances: Vec<u32> = vec![0; 2];
slice::batch(&source, &targets, &mut distances); // [1024, 0]

For fixed-size arrays (recommended when size is known at compile time):

use hamming_bitwise_fast::array;

// Single comparison
let a: [u8; 128] = [0xFF; 128];  // 1024-bit vectors
let b: [u8; 128] = [0x00; 128];
let distance: u32 = array::distance(&a, &b); // 1024

// Batch comparison (one source vs many targets)
// Pre-allocate result vec once and reuse across calls for best performance
let source: [u8; 128] = [0x00; 128];
let targets: Vec<[u8; 128]> = vec![a, b];
let mut distances: Vec<u32> = vec![0; 2];
array::batch(&source, &targets, &mut distances); // [1024, 0]

API

• array::distance / slice::distance — single comparison
• array::batch / slice::batch — batch comparison (one source vs many targets)

Benchmarks

Compared against other Hamming distance crates: simsimd, hamming, triple_accel, hamming_rs (Linux/Windows only; AVX2 on x86 for ≥1024 bytes, v0.2.25+ uses this crate's v1.0 algorithm as fallback)

Single Comparison

ARM (Apple M2 Max)

x86 (AMD EPYC 9845 Zen 5, AVX-512 VPOPCNTDQ, with lto = true)

¹ The hamming crate's distance_fast hits a vectorized fast path at 256 bytes when its input happens to be sufficiently aligned. The 64 B and 128 B numbers reflect its slow path. Treat the 256 B cell as a best-case outlier.

x86 (AMD EPYC 7713 Zen 3, AVX2 only, with lto = true)

For users on Skylake-class Intel or pre-Genoa AMD CPUs that don't have AVX-512 VPOPCNTDQ. Multiversion picks the AVX2+POPCNT path.

² On Zen 3, triple_accel is competitive with array::distance at 128–256 B single-call (within 5–8%). For one-shot AVX2-only workloads at these sizes, either is reasonable. array::batch (below) still dominates by 1.5–2.5× for the one-to-many case.

Batch Comparison (1000 comparisons)

The batch functions are faster for one-to-many comparisons.

ARM (Apple M2 Max)

x86 (AMD EPYC 9845 Zen 5, AVX-512 VPOPCNTDQ, with lto = true)

¹ See the hamming footnote in the single-comparison table above.

x86 (AMD EPYC 7713 Zen 3, AVX2 only, with lto = true)

array::batch is the fastest option when sizes are known at compile time. For runtime-sized inputs, slice::batch is competitive with simsimd and faster than every other competitor, but is 5–13× slower than array::batch (see the LTO note for why).

Running benchmarks

# Run competitor comparison
cargo bench --bench competitors

Methodology note: x86 numbers were measured on dedicated-CPU cloud instances; ARM numbers on a quiescent Apple M2 Max. Cloud-VM placement variance can shift sub-ns single-call timings by 5–15% between physical hosts even at the same SKU. Treat the relative ranking as reliable and the absolute numbers as a representative sample of a well-behaved host.

Performance on x86

Enable LTO

This is the single most impactful optimization. This crate relies on auto-vectorization — the compiler widens u64 operations into SIMD instructions (e.g., AVX-512 VPOPCNTDQ). Without LTO, the compiler can't see through the crate boundary to vectorize effectively.

[profile.release]
lto = true

Use full LTO (true), not thin ("thin") — thin LTO doesn't give LLVM enough cross-module visibility for auto-vectorization.

Impact on single-call performance (128 bytes, AMD EPYC 9845 Zen 5)

Impact on batch performance

LTO is not universally a win for batch workloads. It modestly improves array::batch (a few hundred ns at most), but currently hurts slice::batch by 2–3× because LLVM picks a less favorable vectorization shape when it can see across the crate boundary.

128-byte vectors, 1000-comparison batch, AMD EPYC 9845 Zen 5:

If slice::batch is your hot path and you can't switch to array::batch, benchmark with and without LTO for your specific workload. When sizes are known at compile time, array::batch is always the right answer.

Runtime SIMD detection

Runtime SIMD detection is enabled by default via the multiversion crate. Rust targets baseline x86-64 (SSE2 only) by default; the multiversion_x86 feature compiles multiple code paths and selects the fastest at runtime via CPUID — including AVX-512 VPOPCNTDQ on Intel Ice Lake (2019+) and AMD Zen 4+ (2022+) CPUs.

cargo add hamming-bitwise-fast

What the feature buys you

128-byte vectors, lto = true, AMD EPYC 9845 Zen 5:

The dispatch overhead itself is negligible: when both paths produce the same AVX-512 codegen (e.g., compiled with target-cpu=native), the multiversion'd function and a statically-compiled equivalent are within 1% of each other. The win above comes entirely from CPUID picking VPOPCNTDQ over SSE2.

To disable (e.g., for zero dependencies or when using -C target-cpu=native):

[dependencies]
hamming-bitwise-fast = { version = "1", default-features = false }

Compile-time CPU targeting

If you know your target CPU, combine lto = true with RUSTFLAGS for the fastest single-call performance:

# Best single-call performance, but binary only runs on identical CPUs
RUSTFLAGS="-C target-cpu=native" cargo build --release

# Requires AVX-512 (2017+ server CPUs)
RUSTFLAGS="-C target-cpu=x86-64-v4" cargo build --release

Binaries built with compile-time CPU targeting will crash with "illegal instruction" if run on a CPU that doesn't support the required features. For portable deployments, use the default multiversion_x86 feature instead.

Caveat for batch workloads: target-cpu=native makes single-call faster (~45% on Zen 5) but currently makes the batch APIs slower at larger sizes. On a 256-byte vector, 1000-comparison batch:

LLVM picks a different (worse) vectorization shape for batch loops when compiled with native than when going through the multiversion dispatch boundary. If batch throughput matters, prefer the default features over target-cpu=native, or benchmark both for your specific workload.

License

This project is licensed under either of the following licenses, at your option:

• Apache License, Version 2.0
• MIT License

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this project by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.