Function hamming::distance_fast

pub fn distance_fast(x: &[u8], y: &[u8]) -> Result<u64, DistanceError>

Computes the bitwise Hamming distance between x and y, that is, the number of bits where x and y differ, or, the number of set bits in the xor of x and y.

This is a highly optimised version of the following naive version:

fn naive(x: &[u8], y: &[u8]) -> u64 {
    x.iter().zip(y).fold(0, |a, (b, c)| a + (*b ^ *c).count_ones() as u64)
}

This function requires that x and y have the same 8-byte alignment (that is, x.as_ptr() as usize % 8 == y.as_ptr() as usize % 8). If not, Err is returned. If sub-optimal performance can be tolerated, consider using distance which incorporates a fallback to a slower but less restrictive algorithm.

It is essentially guaranteed that x and y will have the same 8-byte alignment if they are both just Vec<u8>s of non-trivial length (e.g. larger than 8) as in the example below.

This is implemented using the same tree-merging approach as weight, see there for details.

Panics

x and y must have the same length, or else distance_fast panics.

Performance Comparison

length	naive (ns)	distance_fast (ns)	naive/distance_fast
1	5	6	0.83
10	44	45	0.97
100	461	473	0.97
1,000	4,510	397	11
10,000	46,700	2,740	17
100,000	45,600	20,400	22
1,000,000	4,590,000	196,000	23

Examples

let x = vec![0xFF; 1000];
let y = vec![0; 1000];
assert_eq!(hamming::distance_fast(&x, &y), Ok(8 * 1000));

// same alignment, but moderately complicated
assert_eq!(hamming::distance_fast(&x[1..1000 - 8], &y[8 + 1..]), Ok(8 * (1000 - 8 - 1)));

// differing alignments
assert!(hamming::distance_fast(&x[1..], &y[..999]).is_err());