[SR-4499] Iterating over elements from existential collections is super slow

[56ed3025-6cad-4bf8-b972-9c308205a0af]

Previous ID	SR-4499
Radar	None
Original Reporter	@palimondo
Type	Bug

Attachment: Download

Environment

Apple Swift version 3.1 (swiftlang-802.0.48 clang-802.0.38) Target: x86_64-apple-macosx10.9

Additional Detail from JIRA

| | | |------------------|-----------------| |Votes | 1 | |Component/s | Standard Library | |Labels | Bug, Performance | |Assignee | None | |Priority | Medium | md5: cee46cb2c469d8962aa597f8a6f5f479

relates to:

• SR-413 AnySequence does not implement all methods on SequenceType

Issue Description:

Sequence and Collection methods that return existential collections (AnySequence and AnyCollections) suffer from very slow performance iterating over the elements of underlying collection.

Profiling the benchmark/single-source/Suffix.swift reveals that AnySequence correctly invokes the suffix implementation on the underlying collection, but the elements are vended using table dispatch from generic implementation on the protocol.

[belkadan]

I'm not sure how it would go any faster without something like collection segments (SR-3633). The whole point of the Any* types is that they can hold anything, with sequences or collections that can be implemented in any way.

[56ed3025-6cad-4bf8-b972-9c308205a0af]

When looked in isolation, sure. But AnySequence is smacked right into the middle of Sequence interface: dropFirst, dropLast, drop(while: ), prefix, prefix(while: ), suffix, they all return AnySequence. In most case you have static visibility at compile time to all the underlying types, but the current implementation never specializes. That makes it horrible from performance POV in practice.

For example, given let N: Int = 10_000_000; let oneLess = N - 1, it is orders of magnitude faster to do:

let se = (1...N).makeIterator().enumerated().lazy.prefix(while: {$0.0 < oneLess})
return se.map{$0.1}._count()}

then to do

return (1...N).makeIterator().prefix(oneLess)._count()

where _count is just

func _count() -> Int {
    return reduce(0, {i, _ in i + 1})
}

[56ed3025-6cad-4bf8-b972-9c308205a0af]

cc @gribozavr

[belkadan]

Dmitri no longer works on Swift.