Searching: needles, prefixes, slices
Everything on this page answers a question and stops: is this element here, where does this run end, does this sequence contain that one. Half the family is the short-circuit engine, which has to be able to stop at any element; the other half is slice search, which wins 2–3× not by a cleverer algorithm but by not examining elements the answer doesn't need. Every chart runs Int beside String, so boxing effects and structural effects separate.
The short-circuit engine
find, exists, forall, indexWhere, indexOf, contains (the findFirst / anyMatch /
allMatch family, in java.util.stream terms) share one engine: a forward scan
that must be able to stop at any element. It carries this library's founding loop-shape lesson.
The first implementations ran at 0.2–0.4× of a raw array, and every intuitive suspect (virtual
dispatch, the tree, the consumer object) was individually ruled out by measurement. The real cost
was the shape of the loop body: writing result/stop flags mid-loop kept the JIT from treating the
scan as a simple counted loop. The fix was structural, an empty-bodied loop with the predicate in
the loop condition, and it took the family from a 3–5× deficit to the raw array's doorstep:
contains is the engine with equality instead of a predicate. On Int the compare is unboxed on
both sides; the boxing collections unwrap an Integer per element to answer. On references it's
an equals walk for everyone, and the field runs close (FArray ~1.05× over the best rival on a
full 100k miss-scan):
Backward scans
lastIndexOf, lastIndexWhere run the same engine mirrored: the traversal drivers are
forward/backward twins that flip at each ReverseNode, so a backward search over a reversed tree
is a forward scan over its child, never a materialization. The serialized numbers, in
full: at 100k lastIndexOf leads ~2.1×, but through the small and mid sizes the family sits
at parity-to-slightly-behind the raw array (0.78–1.15×), the same nano-op floor as above, paid on
a scan that finds its answer near the end it starts from. The structural win (reversed trees for
free) doesn't show in a flat-leaf benchmark at all; it shows in code that never has to call
.reverse first.
Slice search: winning by not being clever
indexOfSlice, lastIndexOfSlice, containsSlice, startsWith, endsWith: needle-in-haystack
ops. The textbook answer is KMP, which the standard library implements. Measured on real
JVMs, that's the wrong call: KMP's per-element state machine defeats the very loop optimizations
that make scans fast, to guard against pathological inputs that collection code essentially never
sees.
FArray's slice search is a candidate scan: the short-circuit engine's indexOf, the
fastest thing on this page, finds occurrences of the needle's first element, and the rest of the
needle is verified only at those candidate positions. The common case does a raw unboxed scan for
one value and a handful of short verifications:
The boundary: a pathological input (long needle of one repeated value over a haystack of the same value) degrades toward O(n·m), which KMP's guarantee avoids. Collection workloads don't look like that, and the 0.76× → 2.2× swing is what the guarantee was costing on everything else.