Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
palimondo mannequin opened this issue Apr 5, 2017 · 4 comments
Open

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

palimondo mannequin opened this issue Apr 5, 2017 · 4 comments
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. performance standard library Area: Standard library umbrella

Comments

@palimondo
Copy link
Mannequin

palimondo mannequin commented Apr 5, 2017

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
Copy link
Contributor

belkadan commented Apr 5, 2017

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.

@palimondo
Copy link
Mannequin Author

palimondo mannequin commented Apr 5, 2017

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})
}

@palimondo
Copy link
Mannequin Author

palimondo mannequin commented Apr 5, 2017

cc @gribozavr

@belkadan
Copy link
Contributor

belkadan commented Apr 5, 2017

Dmitri no longer works on Swift.

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. performance standard library Area: Standard library umbrella
Projects
None yet
Development

No branches or pull requests

1 participant