Linear search is one of the simplest algorithms for finding a value in a sequence. It has a worst-case time complexity of \(O(n)\), making it asymptotically less efficient than algorithms such as binary search, which performs lookups in \(O(\log n)\) on sorted data.

If the data is initially unsorted, however, it must first be sorted at a cost of \(O(n \log n)\). For a single lookup, this preprocessing cost makes sorting followed by binary search slower than a linear scan. Binary search becomes advantageous when the same dataset is searched repeatedly.

This article focuses on optimizing linear search for modern hardware. While binary search is generally the better algorithm for repeated lookups on sorted data, a carefully optimized linear search can outperform it on small datasets due to superior cache locality, reduced branch overhead, and SIMD acceleration.

Unoptimized Linear Search

Consider the simple linear search implementation below. It scans the array from beginning to end, comparing each element against the search value (target). If a match is found, the function immediately returns the index of the matching element. Otherwise, it continues until the end of the array before returning -1 to indicate that the value was not found.

std::size_t linear_search(
    const std::span<const std::uint64_t> data,
    const std::uint64_t target)
{
    for (std::size_t i = 0; i < data.size(); ++i)
    {
        if (data[i] == target)
        {
            return i;
        }
    }

    return -1;
}

The performance of linear search depends entirely on where the target value is located:

• Best case: The target is the first element, requiring only a single comparison (\(O(1)\)).
• Average case: Assuming the target is equally likely to appear anywhere in the array, roughly half of the elements are examined before a match is found (\(O(n)\)).
• Worst case: The target is the last element, or it does not exist in the array at all. In either case, every element must be compared, requiring n comparisons (\(O(n)\)).

Although the algorithm performs at most one comparison per element, the cost of these comparisons is only part of the story. Every iteration also performs loop control, memory loads, and a conditional branch. Modern processors can execute multiple independent operations simultaneously, making this scalar implementation unable to fully utilize the available hardware resources.

The remainder of this article focuses on improving the constant factors of linear search rather than its asymptotic complexity. The algorithm remains \(O(n)\), but by exploiting SIMD instructions, cache-friendly memory access, and branch reduction, it is possible to significantly reduce the time required to scan large arrays.

Introduction to AVX

Advanced Vector Extensions (AVX) is an extension to the x86 instruction set that enables Single Instruction, Multiple Data (SIMD) execution. Rather than performing the same operation on a single value at a time, SIMD instructions operate on multiple values packed into a wide vector register. For example, AVX2 provides 256-bit registers capable of holding four 64-bit integers, while AVX-512 doubles the register width to 512 bits, allowing eight 64-bit integers to be processed simultaneously.

For linear search, this means that instead of comparing the target value against a single array element per iteration, the target can be compared against multiple elements simultaneously. By broadcasting the search value across an entire vector register and loading a block of consecutive elements from memory, a single SIMD comparison instruction can test every element in the block at once.

Although the algorithm remains \(O(n)\), SIMD allows each iteration to examine four elements with AVX2 or eight elements with AVX-512, significantly reducing the number of iterations, branches, and comparison instructions required to scan the array.

AVX Support on Modern x86 Processors

Most modern x86 processors support at least one version of the Advanced Vector Extensions (AVX) instruction set. For example, AMD’s flagship Ryzen 9 9950X3D includes support for AVX-512, enabling 512-bit SIMD operations on compatible workloads.

Intel’s recent consumer processors, however, present a different situation. While early Alder Lake processors physically included AVX-512 support on their Performance (P) cores, the feature was disabled in shipping products because the Efficiency (E) cores do not implement it. Maintaining two different instruction set capabilities within the same processor complicates scheduling and software compatibility. Additionally, AVX-512 significantly increases die area and power consumption while remaining a niche feature for most desktop applications, making it difficult to justify in mainstream consumer CPUs.

A robust implementation should detect the processor’s supported instruction sets at runtime and dispatch to the most suitable implementation. Depending on the available features, this may be the scalar linear search, an AVX2 implementation, or an AVX-512 implementation.

Detecting AVX Support

A processor’s SIMD capabilities can be queried using the CPUID instruction. The relevant feature flags are exposed by the Structured Extended Feature Flags Enumeration leaf, selected by setting EAX = 0x07 (subleaf ECX = 0) before executing CPUID.

Support for AVX2 is indicated by bit 5 of the returned EBX register.

AVX-512 support is centered around the AVX512F (AVX-512 Foundation) feature, indicated by bit 16 of EBX. AVX512F forms the baseline AVX-512 instruction set and provides the functionality, including:

• 512-bit vector registers (ZMM0-ZMM31)
• Eight mask registers (k0-k7) for predicated execution
• Masked arithmetic and logical operations
• 512-bit memory load and store instructions
• Basic integer and floating-point vector operations

Many processors also implement additional AVX-512 extensions. One of the most common is AVX512DQ (Doubleword and Quadword Instructions), indicated by bit 17 of EBX. This extension expands the instruction set with additional operations on 32-bit and 64-bit integers, including:

• Integer multiplication
• Bit manipulation instructions
• Additional broadcast operations
• Integer conversion instructions
• Extended logical and arithmetic operations

The AVX-512 implementation presented in this article relies only on AVX512F. None of the instructions used require AVX512DQ, making the baseline AVX-512 feature set sufficient.

Implementing linear search with AVX2

AVX2 provides 256-bit vector registers. Because each element in the input buffer is a 64-bit unsigned integer, one vector register can hold four elements at once:

A scalar linear search compares one array element against the target during each iteration. The AVX2 implementation instead loads and compares four elements simultaneously, reducing the number of loop iterations from approximately \(n\) to:

The algorithm remains \(O(n)\), because the amount of work still grows linearly with the size of the input. Vectorization only reduces the constant factor by processing several elements per instruction.

std::size_t linear_search_avx2(
    const std::span<const std::uint64_t> data,
    const std::uint64_t target)
{
    const __m256i needle = _mm256_set1_epi64x(static_cast<std::int64_t>(target));

    constexpr std::size_t elements_per_vector = 4;

    const std::size_t vectorized_end = data.size() - (data.size() % elements_per_vector);

    for (std::size_t i = 0; i < vectorized_end; i += elements_per_vector)
    {
        const __m256i chunk = _mm256_loadu_si256(
            reinterpret_cast<const __m256i*>(data.data() + i));

        const __m256i comparison = _mm256_cmpeq_epi64(chunk, needle);

        const auto mask = static_cast<std::uint32_t>(
            _mm256_movemask_epi8(comparison));

        if (mask != 0)
        {
            return i + (std::countr_zero(mask) / sizeof(std::uint64_t));
        }
    }

    for (std::size_t i = vectorized_end; i < data.size(); ++i)
    {
        if (data[i] == target)
        {
            return i;
        }
    }

    return -1;
}

Broadcasting the target value

The first step is to copy the target value into all four 64-bit lanes of a vector register:

const __m256i needle = _mm256_set1_epi64x(static_cast<std::int64_t>(target));

Conceptually, if the target is \(t\), the resulting register contains:

Although _mm256_set1_epi64x accepts a signed 64-bit integer, the comparison is purely bitwise. Casting std::uint64_t to std::int64_t preserves the underlying 64-bit bit pattern.

Determining the vectorized range

Each vectorized iteration processes four elements, so the AVX2 loop must stop at the largest multiple of four that does not exceed the buffer size.

This boundary is calculated as:

In the implementation:

const std::size_t vectorized_end = data.size() - (data.size() % elements_per_vector);

For example, if the buffer contains 14 elements:

The first 12 elements are processed using AVX2, while the final two elements are handled by the scalar cleanup loop.

The number of remaining elements is always:

Therefore, the scalar loop performs at most three comparisons.

Loading four elements

The intrinsic _mm256_loadu_si256 loads 256 bits (four 64-bit integers) from memory:

const __m256i chunk = _mm256_loadu_si256(
    reinterpret_cast<const __m256i*>(data.data() + i));

The u in loadu denotes an unaligned load, meaning the memory address does not have to be aligned to a 32-byte boundary.

At iteration \(i\), the loaded register contains:

Comparing four values simultaneously

The intrinsic _mm256_cmpeq_epi64 performs four independent 64-bit comparisons:

const __m256i comparison = _mm256_cmpeq_epi64(chunk, needle);

Each lane of the result is defined as

A matching lane therefore becomes

0xFFFFFFFFFFFFFFFF

while a nonmatching lane becomes

0x0000000000000000

Suppose the loaded vector contains

and the search target is 42.

The comparison result is

Converting the comparison into a bit mask

The comparison result is still a vector register. To determine whether any lane matched, _mm256_movemask_epi8 extracts the most significant bit of every byte into a 32-bit integer.

const auto mask = static_cast<std::uint32_t>(_mm256_movemask_epi8(comparison));

A 256-bit register contains

bytes, producing a 32-bit mask.

Since each 64-bit integer occupies eight bytes, every matching element contributes eight consecutive set bits:

mask bits per element.

The correspondence is

If only lane two matches, the mask conceptually becomes

00000000 11111111 00000000 00000000

(where the least significant byte is on the right).

A zero mask indicates that none of the four values matched.

Determining the matching index

Once a nonzero mask is obtained, std::countr_zero() returns the index of the least-significant set bit.

std::countr_zero(mask)

Because each lane contributes eight mask bits, dividing by eight converts the bit position into a lane index:

Since

the implementation simply writes

std::countr_zero(mask) / sizeof(std::uint64_t)

For example, if the first set bit appears at position 16,

meaning the matching value is located in lane two.

The corresponding array index is therefore

If multiple values inside the vector equal the target, std::countr_zero() naturally selects the first one, preserving the behavior of the scalar implementation.

Processing the remaining elements

If the array length is not divisible by four, between one and three elements remain after the vectorized loop.

These values are processed using the original scalar implementation:

for (std::size_t i = vectorized_end; i < data.size(); ++i)
{
    if (data[i] == target)
    {
        return i;
    }
}

The cleanup loop executes at most

comparisons.

Complexity

The asymptotic complexity remains unchanged:

The number of vector iterations is

followed by

scalar iterations.

Overall, the number of loop iterations becomes approximately

while the total number of elements examined remains exactly \(n\).

Implementing linear search with AVX-512

AVX-512 doubles the width of the vector registers from 256 bits to 512 bits. Since each element is a 64-bit unsigned integer, a single register can hold eight values:

Compared to the AVX2 implementation, this doubles the number of elements processed during each iteration.

The vectorized portion of the array consists of the largest multiple of eight that does not exceed the array size:

The algorithm still has a worst-case complexity of

but the number of vector iterations is approximately

std::size_t linear_search_avx512(
    const std::span<const std::uint64_t> data,
    const std::uint64_t target)
{
    const __m512i needle = _mm512_set1_epi64(static_cast<std::int64_t>(target));

    constexpr std::size_t elements_per_vector = 8;

    const std::size_t vectorized_end = data.size() - (data.size() % elements_per_vector);

    for (std::size_t i = 0; i < vectorized_end; i += elements_per_vector)
    {
        const __m512i chunk = _mm512_loadu_si512(data.data() + i);

        if (const __mmask8 mask = _mm512_cmpeq_epi64_mask(chunk, needle);
            mask != 0)
        {
            return i + std::countr_zero(mask);
        }
    }

    for (std::size_t i = vectorized_end; i < data.size(); ++i)
    {
        if (data[i] == target)
        {
            return i;
        }
    }

    return -1;
}

Broadcasting the target value

The search value is replicated into all eight 64-bit lanes:

const __m512i needle = _mm512_set1_epi64(static_cast<std::int64_t>(target));

Conceptually,

Loading eight values

Each iteration loads eight consecutive elements from memory:

const __m512i chunk = _mm512_loadu_si512(data.data() + i);

Conceptually,

Like its AVX2 counterpart, _mm512_loadu_si512 performs an unaligned load, meaning the memory address does not need to be aligned to a 64-byte boundary.

Comparing eight values simultaneously

The intrinsic

const __mmask8 mask = _mm512_cmpeq_epi64_mask(chunk, needle);

performs eight independent comparisons and returns a predicate mask instead of a vector register.

Each bit in the resulting __mmask8 corresponds directly to one 64-bit lane:

If the loaded values are

and the target is 42, the resulting mask is

00000100

where bit 2 is set.

Unlike AVX2, there is no need to convert a comparison vector into a scalar mask using _mm256_movemask_epi8. The comparison instruction produces the mask directly.

Determining the matching index

Since every bit represents one lane, finding the first matching element is straightforward:

std::countr_zero(mask)

returns the index of the first matching lane.

The corresponding array index is simply

No division is required because there is exactly one mask bit per element.

Processing the remaining elements

If the array size is not divisible by eight, the remaining elements are processed using the scalar implementation:

for (std::size_t i = vectorized_end; i < data.size(); ++i)
{
    if (data[i] == target)
    {
        return i;
    }
}

The cleanup loop executes at most

comparisons.

Complexity

The asymptotic complexity is unchanged:

The number of vector iterations becomes

followed by at most

scalar iterations.

Compared to the AVX2 implementation, AVX-512 halves the number of vector iterations and simplifies the comparison logic by producing a native predicate mask. Eliminating the additional movemask operation reduces instruction count and makes the implementation both shorter and easier to understand.

Putting it together: runtime-dispatched linear search

The scalar, AVX2, and AVX-512 implementations can now be combined behind a single interface. During construction, the class detects the instruction sets that are usable on the current system and selects the most capable implementation.

The CPUID structure definitions used in this example are provided by Satoshi Tanda’s ia32-doc project.

Runtime dispatch follows this priority:

1. Use AVX-512 when both the processor and operating system support it.
2. Otherwise, use AVX2 when it is available.
3. Fall back to the scalar implementation on systems without usable AVX support.

The selected implementation is stored as a plain function pointer. Unlike std::function, a function pointer does not require type erasure and is sufficient because every implementation has the same fixed signature.

#include <bit>
#include <cstddef>
#include <cstdint>
#include <immintrin.h>
#include <intrin.h>
#include <span>
#include <type_traits>

#include "ia32.hpp"

namespace x86
{
    template <typename T>
	requires (  sizeof(T) == sizeof(std::int32_t) * 4 &&
				alignof(T) >= alignof(std::int32_t) &&
				std::is_trivially_copyable_v<T>)
	[[nodiscard]] T cpuid(const std::int32_t leaf, const std::int32_t subleaf = 0) noexcept
    {
        T result = { };

        __cpuidex(reinterpret_cast<std::int32_t*>(&result), leaf, subleaf);

        return result;
    }

    [[nodiscard]] bool os_supports_avx() noexcept
    {
	    if (const auto basic = cpuid<cpuid_eax_00>(CPUID_SIGNATURE);
	    	basic.max_cpuid_input_value < CPUID_VERSION_INFORMATION)
        {
            return false;
        }

        if (const auto features = cpuid<cpuid_eax_01>(CPUID_VERSION_INFORMATION); 
        	!features.cpuid_feature_information_ecx.avx_support ||
        	!features.cpuid_feature_information_ecx.osx_save)
        {
            return false;
        }

        constexpr std::uint64_t xmm_state = 1ull << 1;
        constexpr std::uint64_t ymm_state = 1ull << 2;

        constexpr std::uint64_t required_state = xmm_state | ymm_state;

        const std::uint64_t xcr0 = _xgetbv(0);

        return (xcr0 & required_state) == required_state;
    }

    [[nodiscard]] bool os_supports_avx512() noexcept
    {
        if (!os_supports_avx())
        {
            return false;
        }

        constexpr std::uint64_t opmask_state = 1ull << 5;
        constexpr std::uint64_t zmm_hi256_state = 1ull << 6;
        constexpr std::uint64_t hi16_zmm_state = 1ull << 7;

        constexpr std::uint64_t required_state =
            opmask_state |
            zmm_hi256_state |
            hi16_zmm_state;

        const std::uint64_t xcr0 = _xgetbv(0);

        return (xcr0 & required_state) == required_state;
    }

    [[nodiscard]] static bool supports_avx2() noexcept
    {
        if (!os_supports_avx())
        {
            return false;
        }

        if (const auto basic = cpuid<cpuid_eax_00>(CPUID_SIGNATURE);
            basic.max_cpuid_input_value < CPUID_STRUCTURED_EXTENDED_FEATURE_FLAGS)
        {
            return false;
        }

        const auto features = cpuid<cpuid_eax_07>(CPUID_STRUCTURED_EXTENDED_FEATURE_FLAGS);

        return features.ebx.avx2;
    }

    [[nodiscard]] bool supports_avx512f() noexcept
    {
        if (!os_supports_avx512())
        {
            return false;
        }

        if (const auto basic = cpuid<cpuid_eax_00>(CPUID_SIGNATURE);
        	basic.max_cpuid_input_value < CPUID_STRUCTURED_EXTENDED_FEATURE_FLAGS)
        {
            return false;
        }

        const auto features = cpuid<cpuid_eax_07>(CPUID_STRUCTURED_EXTENDED_FEATURE_FLAGS);

        return features.ebx.avx512f;
    }
}

class runtime_dispatched_linear_search_t
{
public:
    using value_type = std::uint64_t;
    using size_type = std::size_t;

    static constexpr size_type npos = static_cast<size_type>(-1);

private:
    using search_function_t = size_type(*)(std::span<const value_type>, value_type);

    search_function_t m_search_function;

    [[nodiscard]] static size_type linear_search(
        const std::span<const value_type> data,
        const value_type target) noexcept
    {
        for (size_type i = 0; i < data.size(); ++i)
        {
            if (data[i] == target)
            {
                return i;
            }
        }

        return npos;
    }

    [[nodiscard]] static size_type linear_search_avx2(
        const std::span<const value_type> data,
        const value_type target) noexcept
    {
        constexpr size_type elements_per_vector = sizeof(__m256i) / sizeof(value_type);

        const __m256i needle = _mm256_set1_epi64x(static_cast<std::int64_t>(target));

        const size_type vectorized_end = data.size() - (data.size() % elements_per_vector);

        for (size_type i = 0; i < vectorized_end; i += elements_per_vector)
        {
            const __m256i chunk = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(data.data() + i));

            const __m256i comparison = _mm256_cmpeq_epi64(chunk, needle);

            if (const auto mask = static_cast<std::uint32_t>(_mm256_movemask_epi8(comparison));
                mask != 0)
            {
                const size_type lane = std::countr_zero(mask) / sizeof(value_type);

                return i + lane;
            }
        }

        for (size_type i = vectorized_end; i < data.size(); ++i)
        {
            if (data[i] == target)
            {
                return i;
            }
        }

        return npos;
    }

    [[nodiscard]] static size_type linear_search_avx512(
        const std::span<const value_type> data,
        const value_type target) noexcept
    {
        constexpr size_type elements_per_vector = sizeof(__m512i) / sizeof(value_type);

        const __m512i needle = _mm512_set1_epi64(static_cast<std::int64_t>(target));

        const size_type vectorized_end = data.size() - (data.size() % elements_per_vector);

        for (size_type i = 0; i < vectorized_end; i += elements_per_vector)
        {
            const __m512i chunk = _mm512_loadu_si512(data.data() + i);

            if (const __mmask8 mask = _mm512_cmpeq_epi64_mask(chunk, needle);
                mask != 0)
            {
                const auto scalar_mask = static_cast<std::uint8_t>(mask);

                return i + std::countr_zero(scalar_mask);
            }
        }

        for (size_type i = vectorized_end; i < data.size(); ++i)
        {
            if (data[i] == target)
            {
                return i;
            }
        }

        return npos;
    }

    [[nodiscard]] static search_function_t select_implementation() noexcept
    {
        if (x86::supports_avx512f())
        {
            return &linear_search_avx512;
        }

        if (x86::supports_avx2())
        {
            return &linear_search_avx2;
        }

        return &linear_search;
    }

public:
    runtime_dispatched_linear_search_t() noexcept
        : m_search_function(select_implementation())
    {
    }

    [[nodiscard]] size_type find(
        const std::span<const value_type> data,
        const value_type target) const noexcept
    {
        return this->m_search_function(data, target);
    }
};

Querying CPUID

The helper wraps the __cpuidex intrinsic and returns the four output registers as an ia32-doc structure:

template <typename T>
T cpuid(
    const std::int32_t leaf,
    const std::int32_t subleaf = 0);

CPUID places its results in the EAX, EBX, ECX, and EDX registers. Some leaves, including structured extended feature leaf 0x07, use ECX as a subleaf selector.

For this reason, __cpuidex is preferable to __cpuid, because it allows both the leaf and subleaf to be specified.

The template is restricted to trivially copyable types whose size matches the four 32-bit registers written by the intrinsic:

Checking the maximum supported leaf

Before querying leaf 0x07, the implementation first requests basic leaf 0x00:

const auto basic = cpuid<cpuid_eax_00>(CPUID_SIGNATURE);

The returned EAX value identifies the highest basic CPUID leaf supported by the processor.

The program should not interpret a leaf unless the processor reports that the leaf is available.

For structured extended feature information, the following condition must hold:

basic.max_cpuid_input_value >= CPUID_STRUCTURED_EXTENDED_FEATURE_FLAGS

This prevents the program from interpreting feature fields from an unsupported CPUID leaf.

Checking operating-system AVX support

A processor advertising AVX or AVX2 support is not sufficient by itself. The operating system must also preserve the extended SIMD register state during context switches.

The AVX check first verifies the AVX and OSXSAVE feature flags:

if (const auto features = cpuid<cpuid_eax_01>(CPUID_VERSION_INFORMATION); 
	!features.cpuid_feature_information_ecx.avx_support ||
	!features.cpuid_feature_information_ecx.osx_save)
{
	return false;
}

When OSXSAVE is set, the program may execute XGETBV to inspect XCR0.

For AVX instructions, both the XMM and YMM state components must be enabled:

and

The required mask is therefore:

In code:

constexpr std::uint64_t xmm_state = 1ull << 1;
constexpr std::uint64_t ymm_state = 1ull << 2;

constexpr std::uint64_t required_state = xmm_state | ymm_state;

The check succeeds only when all required bits are present:

return (xcr0 & required_state) == required_state;

Without this check, executing an AVX instruction may raise an invalid-opcode exception even when the processor itself supports AVX.

Checking operating-system AVX-512 support

AVX-512 requires the AVX state components as well as three additional components:

The additional state mask is:

Together with the XMM and YMM state, the complete AVX-512 requirement is:

The processor must also advertise the AVX512F feature through CPUID leaf 0x07.

Selecting an implementation

The implementation is selected once when the object is created:

runtime_dispatched_linear_search_t() noexcept
    : m_search_function(select_implementation())
{
}

The selection function attempts the implementations in descending order of capability:

if (x86::supports_avx512f())
{
    return &linear_search_avx512;
}

if (x86::supports_avx2())
{
    return &linear_search_avx2;
}

return &linear_search;

Once selected, subsequent calls to find() do not repeat feature detection:

return this->m_search_function(data, target);

The only additional runtime cost is an indirect function call. This is normally preferable to executing multiple CPUID and XGETBV checks for every search.

Using a function pointer

No stateful callable, lambda capture, or arbitrary function object is needed here. A plain function pointer expresses the requirement more directly:

using search_function_t = size_type (*)(std::span<const value_type>, value_type);

This avoids the unnecessary abstraction and potential overhead of std::function.

Representing a failed search

Because the return type is unsigned, returning -1 converts it to the largest representable std::size_t value.

A named constant makes that behavior explicit:

static constexpr size_type npos = static_cast<size_type>(-1);

Callers can test the result using:

const auto index = search.find(data, target);

if (index != runtime_dispatched_linear_search_t::npos)
{
    // The target was found.
}

This follows the same convention as std::string::npos.

Compilation considerations

Runtime dispatch prevents an unsupported implementation from being called, but it does not automatically solve compiler-targeting requirements.

The scalar, AVX2, and AVX-512 implementations must be compiled so that:

• the scalar path does not contain AVX instructions;
• the AVX2 path may contain AVX2 instructions;
• the AVX-512 path may contain AVX-512 instructions;
• the initialization and dispatch code can execute safely on the oldest supported processor.

Depending on the compiler, this can be implemented using per-function target attributes, compiler-specific function multiversioning, or separate translation units compiled with different architecture options.

Feature detection protects execution, but it cannot protect baseline code if the compiler has already emitted unsupported instructions into it.