Indexed access: apply, head, last
A single read is the one place a wrapper can't hide: there's no loop to amortize into, no lambda to
specialize, just "give me element i". This page prices what
xs(i) (Scala's indexing syntax, a method named apply),
head and last cost on a structure that is sometimes a
flat array and sometimes a lazy tree.
The cost model
On a leaf, the flat array every elementwise op leaves behind, an indexed read is a bounds
check, one type test (which node shape is this?), and the array load. That type test is the entire
price of the wrapper relative to a raw int[], and on this page it is visible: a lone read is the
one op with nothing to amortize into, so the measured ~25% gap below is the wrapper tax stated
exactly. It's the same hair that buys value equals, hashCode and a printable toString,
the trade named early. (Loop-shaped ops read the backing array
directly and pay the test once per traversal, which is why every other page shows ties and wins.)
On a lazy tree, a read is O(depth): a Concat of two leaves resolves one comparison and
recurses left or right; a SliceNode adds an offset; a ReverseNode flips the index. Nothing
materializes: reading element 3 of a twenty-array concat touches one leaf. head and last are
the special cases the nodes answer directly: last of an Append is the appended element, head
of a Prepend likewise, O(1) even on trees built by a million-element cons chain (one prepend at a
time).
Int and String land almost identically here, and that is the point: a single read is the op where
element kind matters least — no lambda crosses a boundary, so there is nothing to box on the way
in. (On the way out, a List[Int].head still unboxes an Integer; an FArray[Int]'s read is a
primitive load.) The
summary: against a bare array, a lone read costs the type test (~25–35%, stated above, nothing
hidden). Against the other wrapped structures, FArray's reads are
at par or ahead. And no loop-shaped op on any other page pays this per element; traversals resolve
the node shape once and read the backing array directly.
isDefinedAt(i) belongs to this family, not to conversions: it's the bounds check that guards a
read (i >= 0 && i < length), with length read straight off the node. It runs ~1.2× over a bare
IArray.isDefinedAt (which routes through ArraySeq), the mirror of the small tax apply pays: a
comparison against a directly-available length beats a wrapped one.
The floor
One cell in the suite goes against us and is worth naming: at size 1, ops that read before
looping (reduce, scan) sit measurably behind a bare array. That floor was hunted properly: an
int-tag tableswitch instead of the sealed-trait match (an instanceof chain over the closed node
hierarchy) was built and measured (17–20% slower for
monomorphic reads; HotSpot folds the match better), and a dedicated single-element fast path
measured as a no-op. The conclusion stands as measured: the size-1 read floor is the irreducible
price of being a data structure rather than a pointer, and it's paid only where n=1.