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@swift.org> > wrote: > > > On Mon, May 9, 2016 at 4:16 PM, Dmitri Gribenko <griboz...@gmail.com > <mailto:griboz...@gmail.com>> wrote: > On Mon, May 9, 2016 at 11:46 AM, Rob Napier <robnap...@gmail.com > <mailto:robnap...@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@swift.org > https://lists.swift.org/mailman/listinfo/swift-dev
_______________________________________________ swift-dev mailing list swift-dev@swift.org https://lists.swift.org/mailman/listinfo/swift-dev
