GitHub

Equality search

This page documents the package's equality-search routines — findfirstequal and findfirstsortedequal. They answer a different question from the Search strategies covered elsewhere:

  • Sorted-search strategies answer "where would x insert?". The return value is always an in-range index — the bracketing position.
  • Equality search answers "does x exist, and if so at what index?". The return value is nothing if x is not present.

These two surfaces live side-by-side because the second cannot be expressed as a SearchStrategy — its return type differs (Union{Int, Nothing} vs. in-range Int), and the unsorted variant doesn't even require a sorted input.

For a strategy-framework-compatible sorted equality search that returns Int with a sentinel (so it composes with the rest of the strategy dispatch), see findequal on the Search strategies page. findequal(BisectThenSIMD(), v, x) is the strategy entry point that internally calls into the same algorithm as findfirstsortedequal.

API reference

FindFirstFunctions.findfirstequal — Function
findfirstequal(x, A) -> Union{Int, Nothing}

Find the first index in A where the value equals x. Returns nothing if x does not occur in A.

This function does not assume A is sorted. For sorted vectors, see findfirstsortedequal (a bisect-then-SIMD specialization on DenseVector{Int64}) or findequal (the strategy-framework equality wrapper that returns an Int with a sentinel).

The (x::Int64, A::DenseVector{Int64}) method uses a custom LLVM IR SIMD scan (load 8 lanes, icmp eq, cttz on the mask) — about 8× faster than the scalar findfirst(==(x), v) on modern x86-64. Every other element-type and array-storage combination falls back to findfirst(isequal(x), A).

source
FindFirstFunctions.findfirstsortedequal — Function
findfirstsortedequal(var::Int64, vars::DenseVector{Int64}) -> Union{Int64, Nothing}

Find the index of the first occurrence of var in the sorted vector vars. Returns nothing if var does not occur. Specialized for DenseVector{Int64} via a branchless binary bisection down to a small basecase, followed by the same SIMD equality scan that backs findfirstequal — faster than plain findfirst(==(var), vars) or searchsortedfirst + post-check for typical Int64 vectors.

The strategy-framework equivalent is findequal(BisectThenSIMD(), vars, var); that wrapper returns an Int with a sentinel (firstindex(v) - 1) for "not found", which is type-stable and composes with the rest of the strategy dispatch. Prefer findequal for new code; findfirstsortedequal remains as the dedicated Union{Int64, Nothing}-returning name.

source

When to use which

QuestionVectorRecommended
Does x occur in this unsorted vector?anyfindfirstequal
Does x occur in this sorted vector?DenseVector{Int64} + Int64findfirstsortedequal (or findequal(BisectThenSIMD(), v, x) for the sentinel-returning variant)
Does x occur in this sorted vector?other eltypesfindequal with any strategy
Where would x insert into this sorted vector?anysearchsorted_first(strategy, v, x[, hint])

SIMD primitives

Both equality functions are backed by the same SIMD-equality LLVM IR scaffolding used internally throughout the package (load <8 x i64>, icmp eq, cttz on the bitmask of the 8-wide compare). The IR template FindFirstFunctions._simd_scan_ir (internal) generates this for the equality predicate; the same template generates the > / >= variants for SIMDLinearScan.

The SIMD path is Int64-only — the LLVM IR is keyed off i64 element width and 8-byte stride. Every other element type and storage layout falls through to a scalar findfirst(==(x), v) path. Specifically:

  • findfirstequal(x::Int64, v::DenseVector{Int64}) — full SIMD scan.
  • findfirstequal(x, v) (generic) — findfirst(isequal(x), v).
  • findfirstsortedequal(x::Int64, v::DenseVector{Int64}) — branchless binary bisection to a small basecase, then SIMD equality scan within the basecase window. The bisection uses a strict < predicate so that earlier duplicates are not skipped (a previous version of the routine used <= and could return a later duplicate; fixed in 2.0).

Sentinel vs. Nothing

The two equality APIs differ in how they report "not found":

findfirstequal(x, v)        # -> Union{Int, Nothing}, `nothing` on miss
findfirstsortedequal(x, v)  # -> Union{Int, Nothing}, `nothing` on miss
findequal(strategy, v, x)   # -> Int, firstindex(v) - 1 on miss

findequal's sentinel is type-stable and composes with the rest of the strategy dispatch — that's the recommended choice for new sorted-equality code. The two findfirst*equal names continue to return Union{Int, Nothing} for backwards compatibility with callers and pattern matching against nothing.