swift-span-algorithms

swift-span-algorithms is a zero-dependency, allocation-free collection of algorithms over Swift's borrowed-view types: Span, RawSpan, MutableSpan, and InlineArray. The goal is to give these new non-owning views the kind of algorithm surface the standard library already provides for collections, without introducing hidden allocations, copies, or external dependencies.

Installation

Add the package to Package.swift:

dependencies: [
  .package(
    url: "https://github.com/Dave861/swift-span-algorithms.git",
    from: "0.2.0"
  )
]

Then add SpanAlgorithms to the targets that use it:

.target(
  name: "YourTarget",
  dependencies: [
    .product(name: "SpanAlgorithms", package: "swift-span-algorithms")
  ]
)

Toolchain support

Swift version	What you get
6.2	Full API surface over Span / RawSpan / MutableSpan / InlineArray: search and multi-element matching, min/max, comparison, trimming, chunk/window/split visitation, and pull-style chunk/window/split cursors.
6.4	Same surface today. Generic entry points across the borrowing-sequence family are planned once Swift's BorrowingSequence (SE-0516) ships in a non-experimental, back-deployable form.

API surface

Every algorithm below is a concrete extension. There is no generic layer yet (see the toolchain-support note above). "Types" lists which of Span / RawSpan / MutableSpan / InlineArray ship the member; MutableSpan and InlineArray entries are read-only forwarders onto the Span algorithm (via .span), so their semantics and complexity are identical to Span's.

Algorithm family	Types	Complexity	Result lifetime / notes
firstIndex(where:/of:), lastIndex(where:/of:)	Span, RawSpan, MutableSpan, InlineArray	O(n) time, O(1) space	Escapable Int?; predicate forms use typed throws. Span<UInt8>, Span<Int8>, and RawSpan.firstIndex(of:) use memchr.
contains(_ element:), min(), max()	Span, RawSpan, MutableSpan, InlineArray	O(n) time, O(1) space	Escapable scalar/value result.
firstRange(of:), lastRange(of:), contains(_ pattern:)	Span, RawSpan, MutableSpan, InlineArray	O(n·m) worst case, O(1) space	Escapable Range<Int>? / Bool; empty-pattern semantics are defined. Byte firstRange uses memchr + memcmp.
starts(with:), ends(with:)	Span, RawSpan, MutableSpan, InlineArray	O(m) time, O(1) space	Escapable Bool; byte overloads use memcmp.
elementsEqual(_:), lexicographicallyPrecedes(_:)	Span, RawSpan, MutableSpan, InlineArray	O(n) time, O(1) space	Escapable Bool; byte equality uses memcmp.
trimming(while:), trimmingPrefix/Suffix(while:)	Span, RawSpan, MutableSpan, InlineArray	O(k) time, O(1) space	Borrowed sub-span tied to the receiver's storage.
trimmingASCIIWhitespace(), trimmingASCIIWhitespacePrefix/Suffix()	Span<UInt8>, RawSpan	O(k) time, O(1) space	Borrowed sub-span; trims the six C-locale isspace bytes. WHATWG whitespace excludes vertical tab (0x0B).
forEachChunk, forEachWindow, forEachSplit (element/byte, predicate, and multi-element separator forms)	Span, RawSpan, MutableSpan, InlineArray	O(n) for element separators; O(n·m) worst case for patterns	Each borrowed piece is closure-scoped; typed throws enables allocation-free early exit. Empty pattern separators trap.
chunks(ofCount:), windows(ofCount:), split(separator:...)	Span	O(1) create; O(1), O(1), or O(k) per next()	~Escapable cursor borrows the base. Pieces borrow base storage and remain valid across later next() calls.
chunks(ofByteCount:), windows(ofByteCount:), split(separator:...)	RawSpan	O(1) create; O(1), O(1), or O(k·m) per next()	Same cursor lifetime rule; pattern cursors conservatively borrow both base and separator.
validatedUTF8()	RawSpan	O(n) time, O(1) space	Borrowed UTF8Span; Apple 26 platform family only, matching the standard library API.

The 0.1.x factory spellings chunkCursor, windowCursor, and splitCursor remain as deprecated forwarders for the 0.2.x line and are planned for removal in 0.3.0. InlineArray and MutableSpan members require macOS 26 / iOS 26 / tvOS 26 / watchOS 26 / visionOS 26 or later (the availability of InlineArray.span and MutableSpan themselves), independent of this package's macOS 13 deployment floor.

Benchmarks

Measured with swift package benchmark (benchmark 1.36.2, jemalloc 5.3.0) on the host and toolchain in the footnote below. Full output: Benchmarks/results/latest.md. Malloc (total) is the p50 sample; Time is wall-clock p50 in microseconds.

Operation (10,000,000 bytes)	Match position	Span/RawSpan p50	Scalar/Array p50	Speedup	Borrowed-view malloc p50
firstIndex(of:)	10% depth	16 μs	254 μs	15.9×	0
firstIndex(of:)	absent	159 μs	2,523 μs	15.9×	0
firstIndex(of:)	final byte	159 μs	2,533 μs	15.9×	0
firstRange(of:) (4-byte pattern)	10% depth	16 μs	495 μs	30.9×	0
firstRange(of:) (4-byte pattern)	absent	159 μs	4,993 μs	31.4×	0
firstRange(of:) (4-byte pattern)	end	158 μs	5,001 μs	31.7×	0
forEachSplit(separator:)	separators every 16 bytes	4,028 μs	10,150 μs (Array.split)	2.5×	0 vs. 20

The complete HTTP-style RawSpan parser from the DocC article measures about 8.0 million operations/second at p50 with zero mallocs. RawSpan and Span<UInt8> search measurements are equivalent because both dispatch to the same byte-specialized implementation.

The allocation-free proof: every Span/RawSpan benchmark reports Malloc (total) of 0 at every percentile from p0 to p99 across all input sizes. The one exception in either direction is Array.split(separator:), which allocates a real and consistent 7 / 14 / 20 mallocs (at 1,000 / 100,000 / 10,000,000 elements, respectively) because Sequence.split materializes an array of ArraySlice results. That is exactly the allocation Span.forEachSplit(separator:) avoids by visiting pieces through a non-escaping closure instead. (A 36-malloc blip appears identically at p100 across all benchmarks, including Array-based ones with no per-call heap work. That is the benchmark harness's own sampling noise, not attributable to the algorithm under test.)

^{Host: Apple M4, 16 GB RAM, macOS 26.5.2 (build 25F84), Darwin kernel 25.5.0, arm64. Toolchain: Apple Swift 6.2 (swiftlang-6.2.0.19.9), Xcode 26.0. benchmark 1.36.2, jemalloc 5.3.0. See Benchmarks/results/latest.md for the full per-percentile data and Benchmarks/ for the benchmark sources.}

Status

0.2.0 is the byte-parsing release. The package is pre-1.0, so API details may still change as Swift's borrowed-view APIs settle. See CONTRIBUTING.md for the process used to decide what belongs in the package.

License

Apache License 2.0. See LICENSE.