[SR-12849] Inefficient/broken .prefix() implementation on .lazy collection views #55295
Labels
bug
A deviation from expected or documented behavior. Also: expected but undesirable behavior.
Collection
Area → standard library: The `Collection` protocol
run-time performance
standard library
Area: Standard library umbrella
swift 6.0
unexpected behavior
Bug: Unexpected behavior or incorrect output
Additional Detail from JIRA
md5: 6ecff5e3f62cd93e9d95eb3621436f7f
Issue Description:
There's two issues here but they are very related to each other.
Consider the following snippet (will be simplified more below):
This program results in a crash (and other not nice effects, explained below):
Problems with this output:
The crash. Sure, one may argue that the collection view should side effect in the filter, but the crash is pretty nasty and a result of:
The collection gets iterated twice
Last but not least: the
lazy...prefix
combination does not stop the iteration when n elements are found, rather, ALL elements are traversed each time.More mini examples:
That is a lot of extra iterations for finding the first element in this array.
Expected:
when
prefix(1)
is used, there should not be a need to iterate over the rest of the collection oncen
elements are collectedthere should not be a need to traverse the collection twice.
We did some digging with @Lukasa, and the troublesome places for this behavior are around:
LazyFilterSequence
not specializingprefix()
and thus defaulting to use the
Collection
's impl which does:which calls startIndex multiple times (we suspect that's the "multiple times" traverse), since the startIndex is implemented as:
on the lazy filter view.
And that explains the crasher as well – since the contents of the view changed depending on how many times it's run (it collects the "seen" elements), the indexes don't align anymore and we get the Range crash.
Fixing the lazy view's prefix to correctly iterate only once should fix this behavior.
Also, it should stop iteration once enough elements are collected.
For reference, a similar feature in Scala exhibits the correct behavior:
The text was updated successfully, but these errors were encountered: