[SR-413] AnySequence does not implement all methods on SequenceType

[swift-ci]

Previous ID	SR-413
Radar	None
Original Reporter	bnut (JIRA User)
Type	Bug
Status	Resolved
Resolution	Done

Additional Detail from JIRA

Votes	0
Component/s	Standard Library
Labels	Bug
Assignee	None
Priority	Medium

md5: f1f0d117a5204e887ab4187dd39016b6

relates to:

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

Issue Description:

TL;DR

At the moment (0...1000000000).suffix(2) is really efficient.
However, AnySequence(0...1000000000).suffix(2) is not.

Long version

AnySequence implements underestimateCount and generate, however it does not implement any of the other methods on SequenceType.

This means that if you've provided custom implementations of these methods it still uses the implementation from SequenceType's protocol extension.

For example:

struct MySequence: SequenceType {
    private static let array = [1,2,3]
    func generate() -> AnyGenerator<Int> {
        return anyGenerator(MySequence.array.generate())
    }
    func suffix(maxLength: Int) -> AnySequence<Int> {
        return AnySequence(MySequence.array.suffix(maxLength).map{$0 + 1})
    }
}

let a = MySequence()
let b = AnySequence(a)

print("\(Array(a.suffix(2))) == \(Array(b.suffix(2)))?")

Outputs:

[3, 4]==[2, 3]?

but it should output:

[3, 4]==[3, 4]?

This example is probably not something you would want to do, but it is representative of the problem. Other cases this may be an issue are when implementing infinite sequences, implementing suffix efficiently on a bidirectional indexed collection type, etc.

[palimondo]

I have rewritten the reported test case to compile with Swift 3 like this:

struct MySequence: Sequence {
    private static let array = [1,2,3]
    func makeIterator() -> AnyIterator<Int> {
        return AnyIterator(MySequence.array.makeIterator())
    }
    func suffix(_ maxLength: Int) -> AnySequence<Int> {
        let r = MySequence.array.suffix(maxLength)
        return AnySequence(r.map{$0 + 1})
    }
}

let a = MySequence()
let b = AnySequence(a)

print("\(Array(a.suffix(2))) == \(Array(b.suffix(2)))?”) // [3, 4] == [3, 4]?

Note: I had to split the map from suffix due to ambiguity (probably same issue as reported in SR-4256 ?), and the results match - custom suffix implementation is called in Swift 3.1.

I think this was fixed in Jan 6th 2016 in commit [commit 31f17e2, [stdlib] using static method dispatch instead of failable casts | 31f17e2#diff-d10f8c94467ccf15797e3610c67bb69c]. Marking as fixed.

[palimondo]

Mea culpa again, it works, my rewritten version incorrectly implemented func suffix(maxLength: Int) instead of func suffix(_ maxLength: Int). Marking as fixed.

[swift-ci]

Comment by Andrew Bennett (JIRA)

I believe that the example on this issue was poorly constructed, the issue still exists, although you have managed to rewrite the example to avoid it. The issue is not whether you can write code that avoids calling `suffix` on AnySequence, the issue is what happens when you do call suffix on AnySequence.

To clarify:

At the moment (0...1000000000).suffix(2) is really efficient.
However, AnySequence(0...1000000000).suffix(2) is not.

This is still an issue, and is unfixed, I'm going to mark it as unresolved again until AnySequence is removed, or its performance matches the underlying sequence.

[palimondo]

I see. Doesn't the problem stem from the fact that the efficient suffix implementation you’d like to see invoked is defined as part of conformance to the Collection protocol and AnySequence somehow has no visibility to that?

As far as AnySequence is concerned suffix returns AnySequence, the implementation you’d like to see invoked returns AnyCollection, right?

@dabrahams, would your ForwardingWrapper approach be able to work around that? Should there be some kind of forwarding on extension Sequence for Collection s, that wrap their Subsequence s in AnySequence to make them conform to Sequence protocol’s required signatures? (something, something about repackaging the boxed base s...)

[palimondo]

Given all that… I think based on this issue’s title and the provided test case this one should be closed and another issue opened to deal with the requested performance optimization for AnySequence to forward to better implementations available on Collection.

I have tried testing this extension, but it is never invoked:

extension Sequence where Self == CountableRange<Int> {
    public func suffix(_ n: Int) -> AnySequence<Int> {
        return AnySequence(self.suffix(n))
    }
}

[palimondo]

Upon further research, my previous two comments are incorrect.

bnut (JIRA User), you said:

At the moment (0...1000000000).suffix(2) is really efficient. However, AnySequence(0...1000000000).suffix(2) is not.”

I’ve tested this exact case and AnySequence is just fine in this case. It correctly invokes the suffix on the underlying CountableRange and reduces the sequence to just two elements in no time.

Profiling the test cases you’ve added in #7420, a different performance problem manifests itself when the remaining sequence is long, because the underlying iterator doesn’t get specialized and all elements are being vended through virtual dispatch on generic protocol. AnyCollection shares the same problem.

I really think we should resolve this bug as Done and file another for that remaining issue.

[palimondo]

I’ve created new issue to track the slow performance of iterating over elements of existential collections: SR-4499.

AnySequence now correctly implements all methods from Sequence protocol and forwards them to underlying base. Resolving as Done.