Swift-span-algorithms — allocation-free algorithms over Span / RawSpan

Community Showcase
, ,
1

Repo: Dave861/swift-span-algorithms

SPI Releases: swiftpackageindex.com/Dave861/swift-span-algorithms

Zero dependencies, Apache-2.0, macOS 13 deployment floor for the Span/RawSpan surface, 181 tests.

Why

Span is ~Escapable, so it can't conform to Collection or Sequence and none of the stdlib's generic algorithms come along for free. In practice everyone re-derives split, firstRange(of:) and trimming by hand. Wrote this so you don't have to.

What are the sub-results?

chunks/windows/split classically return lazy collections. Here there's no Collection to return, [Span<T>] isn't expressible at all, and [Range<Int>] would allocate, which defeats the point.

So there are two shapes:

// push — pieces borrow the parent, valid for the closure body
span.forEachSplit(separator: 0) { piece in … }

// pull — same guarantee, but the control flow is yours
var lines = bytes.split(separator: crlf)
while let line = lines.next() { … }

Early exit from the closure form is a typed throws, so it stays allocation-free.

An initial mistak

0.1.0 annotated cursor next() as @_lifetime(&self): each vended piece depended on a mutable borrow of the cursor. That sounds reasonable and is wrong, a cursor mutates its own offset, never the elements. Result:

var c = span.split(separator: 0)
guard let a = c.next(), let b = c.next() else { return }
// error: overlapping accesses to 'c', but modification requires exclusive
//        access; consider copying to a local variable

Holding two pieces at once, ordinary look-ahead parsing, was rejected, by a diagnostic that names the caller's variable and suggests a fix that doesn't work.

@_lifetime(copy self) states the actual rule (the piece inherits the base storage's lifetime) and gives up no safety: outliving the storage, returning the piece, and stashing it in a class are all still rejected. Both directions are pinned, the newly-allowed patterns are tests that fail to compile under the old annotation, and the rejections are compile-fail fixtures asserting the diagnostic text.

Multi-source dependence also works, which the pattern-split cursor needs since it borrows both the base and the separator:

@_lifetime(copy base, copy separator)

Performance

memchr/memcmp fast paths for byte spans, as where Element == UInt8 overloads, more specialised than the generic Element: Equatable one, so dispatch is compile-time and free.

M4, ns/op, against a hand-written scalar loop:

size hit at 0 25% depth absent
8 0.39× 0.66× 2.25×
32 0.31× 1.46× 5.13×
256 0.31× 6.94× 11.49×
1024 0.35× 10.41× 14.51×
65536 0.33× 15.49× 16.13×

On a first-byte hit memchr is ~3× slower at every size, a constant ~1.4 ns call overhead. The deciding variable is bytes scanned, not buffer size: scalar ≈0.24 ns/byte vs memchr ≈1.7 ns + 0.015 ns/byte, so break-even is ~7–8 bytes scanned. I've left it unconditional, since the loss is bounded and hit depth isn't knowable in advance, but I'd take arguments.

Reverse search stays scalar: memrchr is a GNU extension and doesn't exist on Darwin, and platform-divergent performance seemed worse than a consistent scalar loop.

Questions I have

  1. split(separator:) returning a cursor, is it the right call, or does borrowing a name that returns an Array in the stdlib mislead more than the muscle memory helps?
  2. Is @_lifetime(copy self) what you'd expect on a cursor's next(), or is there a spelling that expresses "valid while the base storage lives" more directly?
  3. Anything here that's obviously stdlib-destined and shouldn't live in a package at all?

Thank you for reading!

5 Likes