[swift-dev] LazyFilterCollection is not a Collection

[Russ Bishop]

Naively (and thinking about how this works on other platforms), I would expect Array(lazyFilterSequence) to iterate only once and take the hit of reallocation.


Russ


> On May 11, 2016, at 2:46 PM, Rob Napier via swift-dev <swift-dev at swift.org> wrote:
> 
> 
> On Mon, May 9, 2016 at 4:16 PM, Dmitri Gribenko <gribozavr at gmail.com <mailto:gribozavr at gmail.com>> wrote:
> On Mon, May 9, 2016 at 11:46 AM, Rob Napier <robnapier at gmail.com <mailto:robnapier at gmail.com>> wrote:
> > It violates the performance requirements.
> > CollectionType.count requires O(1) access if Index is a
> > RandomAccessIndexType.
> 
> Hi Rob,
> 
> We don't have RandomAccessIndexType anymore.
> 
> 
> I don't understand how this addresses any of the original points. LazyFilterIndex explicitly notes that it breaks the performance promises of its protocol:
> 
> NOTE
> The performance of advancing a LazyFilterIndex depends on how sparsely the filtering predicate is satisfied, and may not offer the usual performance given by models of ForwardIndexType. 
> 
> And also LazyFilterCollection:
> 
> NOTE
> The performance of advancing a LazyFilterIndex depends on how sparsely the filtering predicate is satisfied, and may not offer the usual performance given by models of ForwardIndexType. Be aware, therefore, that general operations on LazyFilterCollection instances may not have the documented complexity.
> 
> 
> I believe there should be a very high performance bar before breaking a protocol's promises. The fact that filter predicates must be both pure and very fast is not obvious, and this can have a cascading effect of calling filters an ever-increasing number of times. For example:
> 
> var c1 = 0
> var c2 = 0
> var c3 = 0
> 
> let xs = Array(1...1000).lazy
>     .filter { _ in c1 += 1; return true }
>     .filter { _ in c2 += 1; return true }
>     .filter { _ in c3 += 1; return true }
> 
> _ = Array(xs)
> print(c1, c2, c3, c1+c2+c3) // 7986 3996 2000 13982
> 
> I don't think the caller would expect that these filters would be called a total of 14k times (rather than 3k).
> 
> This is rough, and I just tossed in Xcode and hit "Test" (so it's very possible that there's a mistake here due to oversimplifying), but I was unable to find any combination of count or number of filters (including one filter and up to 1M element arrays) where the current stdlib is faster than the sequence version:
> 
> extension LazySequenceType {
>     @warn_unused_result
>     public func seqFilter(
>         predicate: (Elements.Generator.Element) -> Bool
>         ) -> LazyFilterSequence<Elements> {
>         return LazyFilterSequence(
>             self.elements, whereElementsSatisfy: predicate)
>     }
> }
> 
> class testperfTests: XCTestCase {
>     func testPerformanceSeq() {
>         self.measureBlock {
>             let xs = Array(1...1000).lazy
>                 .seqFilter { _ in true }
>                 .seqFilter { _ in true }
>                 .seqFilter { _ in true }
>             
>             _ = Array(xs)
>         }
>     }
> 
>     func testPerformanceCollection() {
>         self.measureBlock {
>             let xs = Array(1...1000).lazy
>                 .filter { _ in true }
>                 .filter { _ in true }
>                 .filter { _ in true }
> 
>             _ = Array(xs)
>         }
>     }
> }
> 
> seqFilter was reliably over an order of magnitude faster than filter.  I tested this with various filters (to demonstrate actually removing some elements), on Mac and iOS, with between 1 and 3 filters, and with sizes between 1000 and 1M. The non-collection was always faster in my tests.
> 
> I don't see this as a performance slam dunk that justifies breaking the performance promises of CollectionType. Is there more to the story that I'm missing?
> 
> -Rob
> 
> _______________________________________________
> swift-dev mailing list
> swift-dev at swift.org
> https://lists.swift.org/mailman/listinfo/swift-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20160511/863065c2/attachment.html>