There's More to Performance Than Big-O

You are given a sorted vector of type u16 containing 0x200 (512) elements, and your task is to check whether a given element X is present in the vector.

You would probably choose binary search, as it provides the best asymptotic complexity for this problem which is O(log N).

⁕ Binary Search #

The basic implementation is as follows,

#[inline(always)]
fn binary_search(a: &[u16], target: u16) -> bool {
    let mut lo = 0usize;
    let mut hi = a.len();

    while lo < hi {
        let mid = lo + ((hi - lo) >> 1);
        let x = unsafe { *a.get_unchecked(mid) };

        if x < target {
            lo = mid + 1;
        } else if x > target {
            hi = mid;
        } else {
            return true;
        }
    }

    false
}

After benchmarking and profiling the implementation above,

Searching through 512 elements in around 66 nanoseconds ain't bad. For every search, the CPU executes about 0x74 (116) instructions while taking 0xAE (174) cycles to complete. This gives an IPC of 0.67, which leaves plenty of execution capacity unused.

⁕ SIMD #

Using vector instructions (assuming 256-bit YMM registers), we can process 0x10 (16) elements at the same time instead of checking them one by one.

Here is a basic implementation using the AVX2 extension on x86-64,

#[target_feature(enable = "avx2")]
unsafe fn simd_search(a: &[u16], target: u16) -> bool {
    let target_vec = _mm256_set1_epi16(target as i16);
    let mut i = 0;

    while i + 0x10 <= a.len() {
        let values =
            _mm256_loadu_si256(a.as_ptr().add(i) as *const __m256i);

        let cmp = _mm256_cmpeq_epi16(values, target_vec);

        if _mm256_movemask_epi8(cmp) != 0 {
            return true;
        }

        i += 0x10;
    }

    while i < a.len() {
        if *a.get_unchecked(i) == target {
            return true;
        }

        i += 1;
    }

    false
}

The SIMD implementation is O(N), but each iteration checks 0x10 values in parallel. It also has a simpler control flow, allowing the CPU to execute more independent work.

After benchmarking and profiling the implementation above,

The same search now takes around 49 nanoseconds, with about 158 instructions executed in 80 CPU cycles. This gives an IPC of almost 2, meaning the CPU executes close to two instructions per cycle.

The SIMD implementation is therefore about 1.33 times faster than binary search for this workload.

⁕ Conclusion #

Even though we are often told to choose the algorithm with the best asymptotic complexity, Big-O only describes how an algorithm scales as the input grows. It does not describe how efficiently the CPU can execute the code.

In real world scenarios, branch prediction, instruction-level parallelism, SIMD, and cache locality can all affect performance and not just Big-O.