SBSTNDBS.
Back to archive
Field noteApr 08, 202612 min read

The Fastest std::find: How Doing More Work Makes You Faster

I tried to beat std::find with AVX2 intrinsics. The winning approach turned out to be branchless C++ that the compiler auto-vectorized better than my hand-written SIMD.

C++SIMDPerformance

The Fastest std::find

How fast can you find a number in an array? The obvious tool is SIMD intrinsics — load 8 or 16 elements at once, compare in parallel, profit. But when I actually benchmarked every approach I could think of, the winner was not what I expected.

The Baseline

Everyone writes this at some point:

int naive_find(int* vector, int size, int value) {
    for (int i = 0; i < size; i++) {
        if (vector[i] == value)
            return i;
    }
    return -1;
}

All benchmarks compiled with -Ofast -march=native (GCC 13). On my Intel Core Ultra 7 at 5.2 GHz, this scans 4096 integers at 8.4 billion elements per second. One comparison every ~0.12 ns. std::find does roughly the same: 9.1 G-elements/s.

What If You Remove One Line?

Same function with one change — instead of returning on a match, keep going:

int nobreak_find(int* vector, int size, int value) {
    int index = -1;
    for (int i = 0; i < size; i++) {
        if (vector[i] == value)
            index = i;  // no return — keep scanning
    }
    return index;
}

This does MORE work — always scans the entire array. Yet: 19.3 G-elements/s. That is 2.3x faster than naive_find (8.4 G/s).

Why? The return i creates a data-dependent branch that the compiler cannot vectorize. With the early exit gone, GCC auto-vectorizes with AVX2 — vpcmpeqd + vpblendvb processing 8 integers per cycle. The naive version stays scalar.

The lesson: the cost of asking "should I stop?" at every iteration is higher than the cost of just finishing the job.

The Counting Trick

If removing the branch helps that much, can we eliminate ALL branches from the loop body?

Important caveat up front: this next function is not a drop-in replacement for std::find. It only gives correct results on a sorted array of unique values (or more precisely, when every element less than the target comes before it). It does not actually find the element — it counts how many elements are smaller and infers the position from that count. If the target is absent, it silently returns a wrong index.

In this benchmark, the array is 4096 zeros with a single 1 at the last position. All the 0s are less than the target 1, so the count equals the index. That is a special case — but it lets us isolate the throughput question: how fast can the hardware crunch through comparisons when we remove every obstacle?

int compare_find(int* vector, int size, int value) {
    int index = -1;
    for (int i = 0; i < size; i++) {
        index += (vector[i] < value);
    }
    return index;
}

This transforms search into counting: "how many elements are less than the target?" The boolean (vector[i] < value) evaluates to 0 or 1, so the total count equals the index of the target (given the preconditions above).

Result: 38.8 G-elements/s. That is 4.6x faster than naive_find (8.4 G/s) — with zero intrinsics.

The assembly:

.L4:
    vpcmpgtd  ymm0, ymm2, YMMWORD PTR [rax]   ; compare 8 ints
    vpsubd    ymm1, ymm1, ymm0                 ; subtract mask (adds 1)
    add       rax, 32
    cmp       rax, rdx
    jne       .L4

Three instructions in the hot loop. GCC uses vpsubd of the comparison mask — since vpcmpgtd returns -1 (0xFFFFFFFF) for matches, subtracting -1 is adding 1. One instruction saved per iteration.

But Wait — I Wrote AVX2 Intrinsics

The "traditional" SIMD approach — broadcast target, load 8 elements, compare, extract mask, branch:

Result: 31.1 G-elements/s (3.7x vs naive_find). Processes 16 elements per iteration (two loads of 8 elements each — two AVX2 registers) but the if (mask != 0) branch makes it 20% slower than the pure C++ compare_find.

Writing SIMD intrinsics does not guarantee faster code. That said, a counting variant using AVX2 (intrinsic2_find) reaches 34.4 G-elements/s (4.1x vs naive_find) — only 11% behind compare_find — showing that hand-written SIMD can get close when it avoids branches too.

The Full Picture

All 10 implementations on 4096-element arrays. The branchless compare_find dominates.

compare_find keeps climbing as arrays grow — its throughput is limited only by memory bandwidth. Naive find plateaus at ~8 G/s.

The key metric is elements per instruction. compare_find processes 2.7 elements per instruction — the best ratio.

The Caveats (Read This Before You Ship It)

Before you drop compare_find into production, there are several things to be honest about.

The array must be sorted (or have the specific layout used here). The counting trick index += (vector[i] < value) only gives the correct position when every element less than the target appears before it and every element greater appears after. In this benchmark the array is all zeros with a single 1 at the end, which satisfies that constraint. On an unsorted array with arbitrary values, the count of "elements less than value" has no relationship to the position of the target.

compare_find returns a wrong index if the element is absent. A real find returns -1 (or end) when the target is not in the array. compare_find always returns a position — it just counts smaller elements and assumes the target is there. If the element is missing, you silently get a bogus index. You would need a separate existence check, which adds cost.

For sorted data, std::lower_bound is the real competitor. If your data is sorted (which compare_find requires), binary search finds the target in O(log n) — about 12 comparisons for 4096 elements. That is far fewer operations than scanning all 4096 elements, even at 38.8 G/s throughput. For large arrays, binary search wins on total time despite lower throughput per comparison. The branchless linear scan is competitive mainly for small-to-medium arrays where the setup cost of binary search dominates.

This benchmark is worst-case for early exit. The target is always at the last position. That is the scenario where early-exit code gets zero benefit from its exit, but still pays the branch cost on every iteration. If your target is usually near the beginning, naive_find with early exit wins handily — it checks 10 elements and stops, while the branchless version scans all 4096.

On real workloads with early hits, naive_find can win. If your targets are uniformly distributed, the expected scan length for early-exit is N/2. The branchless approach always scans N. So branchless needs to be at least 2x faster per-element to break even on average — and for nobreak_find (2.3x), that is barely enough. Only compare_find (4.6x) has a comfortable margin for the average case.

What Does AutoPerf Find?

I also ran AutoPerf on the naive_find kernel (K=5, B=5, D=3, Gemini Flash). Starting from the same 873 ns baseline, it reached 117 ns — a 7.4x speedup in 55 evaluations.

The LLM took a completely different path than I did. Instead of removing branches (my approach), it kept the early-exit paradigm but made it dramatically more efficient: load 64 elements into 8 AVX2 registers, OR all comparison results into a single register, test once with _mm256_testz_si256. One branch for 64 elements instead of one per element.

It never discovered the counting trick. It never tried removing the early exit. It stayed in the "search and stop" paradigm — but optimized it to the point where the branch is taken once every 64 elements instead of once per element.

Comparing the approaches on 4096 elements:

Approachns/opWho found it
naive_find (baseline)873Everyone
AutoPerf (OR-tree + early exit)117LLM agent
compare_find (branchless counting)106Hand-written

The hand-written branchless approach is still 10% faster. But the LLM's solution is more general — it preserves the original semantics (early exit, works on unsorted data, correct "not found" behavior) while the counting trick requires sorted input.

This is the pattern I keep seeing: the LLM optimizes within the existing paradigm. It makes the search-and-branch approach 7x faster by reducing branches. But it does not question whether branching is the right paradigm. That conceptual leap — "what if finding is just counting?" — remains a human insight.

What I Took Away

  1. Branches are the enemy of throughput. Removing one return gave 2.3x vs naive_find. Removing all branches gave 4.6x.

  2. Auto-vectorized branchless code beat hand-written SIMD with branches. To be clear: the compiler IS writing SIMD for compare_find — the assembly is full of vpcmpgtd and vpsubd. The point is not "C++ beats SIMD." It is that branchless scalar code gives the compiler a clean loop it can vectorize perfectly, while my hand-written intrinsics version had an if (mask != 0) branch that limited throughput. When I wrote a branchless AVX2 counting variant (intrinsic2_find at 34.4 G/s), it closed the gap to 11%, confirming that the real issue was always branches, not intrinsics vs. auto-vectorization.

  3. Elements per instruction matters more than elements per iteration. Less is more.

  4. Rethink the algorithm before reaching for intrinsics. The biggest speedup came from changing the algorithm — turning a search into a count. But remember: that change also changed the semantics (see caveats above).

The code is on GitHub: vectorized_find.