ReadOnlySpan<T>.Split() does not share splitting semantics with string.Split()

[bbartels]

The parameter-less overload of ReadOnlySpan<T>.Split will use a single white space token ' ' to split on the input buffer. The original string.Split() implementation however splits on any character that returns true when calling char.IsWhiteSpace(char).

[bbartels]

The issues I see with implementing ReadOnlySpan<T>.Split() to share the behavior of string.Split is, that there doesn't seem to be way to do this with the current generic enumerator. We would have to pass a ReadOnlySpan<char> of separators to ReadOnlySpan<T>.IndexOfAny(ROS<T>), which at least to my limited knowledge doesn't seem to be possible, as we would have to either cast the ReadOnlySpan<char> to ReadOnlySpan<T> or vice versa.

MemoryMarshal.Cast<TFrom, TTo> doesn't seem to work either, because T must be a value type, of which there is no generic constraint added to SpanSplitEnumerator<T>

/cc @stephentoub
/cc @layomia
/cc @GrabYourPitchforks

[stephentoub]

You can just pass a bool to the ctor indicating the mode, and then iterate calling IsWhitespace.

[bbartels]

But such an implementation would then not be vectorised.
Which, if string.Split() uses HWInstrinsics may result in an indirect regression in perf.

[stephentoub]

But such an implementation would then not be vectorised.

Correct (for the parameterless case). String.Split doesn't either.

[bbartels]

For clarification, is it not vectorised for both the parameter-less case, as well as the one with parameters? (re str.Split)

EDIT: Huh, interesting. Seems like none of them are vectorised. Did not expect that. What exactly is stopping us from using ROS.IndexOf() or ROS.IndexOfAny() in at least the first couple cases here.
I feel like I must be missing something.

[stephentoub]

What exactly is stopping us from using ROS.IndexOf() or ROS.IndexOfAny() in at least the first couple cases here.

Someone taking the time to measure the impact on a wide array of commonly-expected inputs to see whether it helps or potentially even hurts.

[GrabYourPitchforks]

From an algorithmic complexity perspective, the only real requirements are this:

let str := input string to search within
let n := length of str
let S := set of chars to search for
let |S| := size of set S
let f := index in str where any char in S first appears

Then, for all inputs str and any realistic input S:

str.Split(S) must have algorithmic complexity no worse than O(n * |S|).
(this is already the case)

str.IndexOfAny(S) must have algorithmic complexity no worse than O(f * |S|).
(this is already the case)

MemoryExtensions.IndexOfAny(str, S) must have algorithmic complexity no worse than O(f * |S|).
(this is already the case)

foreach (var range in MemoryExtensions.Split(str, S)) { /* no-op */ } must have algorithmic complexity no worse than O(n * |S|).

From my perspective any implementation of MemoryExtensions.Split which fulfills that requirement is fine. I leave it to the perf-oriented folks to weigh in on how much of a constant factor is acceptable. :)

[stephentoub]

I leave it to the perf-oriented folks to weigh in on how much of a constant factor is acceptable. :)

I'm amused, as this would seem to be you leaving it to you :)

[GrabYourPitchforks]

When I start talking algorithmic complexity I'm wearing a security hat, not a perf hat. :)

We can't be in a world where "attacker-controlled-input".Split() has O(n^2) complexity. But "attacker-controlled-input".Split(new char[] { /* attacker-controller search chars */ }) isn't anywhere near as much of a concern.

[bbartels]

From my perspective any implementation of MemoryExtensions.Split which fulfills that requirement is fine. I leave it to the perf-oriented folks to weigh in on how much of a constant factor is acceptable. :)

Glad that you aren't opposed to my idea of adding Thread.Sleep() somewhere in MoveNext() ;)

[bbartels]

Closing for now as per #37742 (comment)