<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">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.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Russ</div><div class=""><br class=""></div><br class=""><div><blockquote type="cite" class=""><div class="">On May 11, 2016, at 2:46 PM, Rob Napier via swift-dev <<a href="mailto:swift-dev@swift.org" class="">swift-dev@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><br class=""><div class="gmail_extra"><div class="gmail_quote">On Mon, May 9, 2016 at 4:16 PM, Dmitri Gribenko <span dir="ltr" class=""><<a href="mailto:gribozavr@gmail.com" target="_blank" class="">gribozavr@gmail.com</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span class="">On Mon, May 9, 2016 at 11:46 AM, Rob Napier <<a href="mailto:robnapier@gmail.com" class="">robnapier@gmail.com</a>> wrote:<br class="">
> It violates the performance requirements.<br class="">
> CollectionType.count requires O(1) access if Index is a<br class="">
> RandomAccessIndexType.<br class="">
<br class="">
</span>Hi Rob,<br class="">
<br class="">
We don't have RandomAccessIndexType anymore.<br class=""><span class=""><font color="#888888" class=""><br class=""></font></span></blockquote><div class=""><br class=""></div><div class="">I don't understand how this addresses any of the original points. LazyFilterIndex explicitly notes that it breaks the performance promises of its protocol:</div><div class=""><br class=""></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">NOTE<br class=""><span style="color:rgb(65,65,65);font-family:Helvetica,Arial,sans-serif;font-size:12px;background-color:transparent" class="">The performance of advancing a</span><span style="color:rgb(65,65,65);font-family:Helvetica,Arial,sans-serif;font-size:12px;background-color:transparent" class=""> </span><code class="" style="background-color:transparent;border:0px;font-size:0.9em;margin:0px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(128,128,128);font-family:Menlo,monospace;word-wrap:break-word">LazyFilterIndex</code><span style="color:rgb(65,65,65);font-family:Helvetica,Arial,sans-serif;font-size:12px;background-color:transparent" class=""> </span><span style="color:rgb(65,65,65);font-family:Helvetica,Arial,sans-serif;font-size:12px;background-color:transparent" class="">depends on how sparsely the filtering predicate is satisfied, and may not offer the usual performance given by models of</span><span style="color:rgb(65,65,65);font-family:Helvetica,Arial,sans-serif;font-size:12px;background-color:transparent" class=""> </span><code class="" style="background-color:transparent;border:0px;font-size:0.9em;margin:0px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(128,128,128);font-family:Menlo,monospace;word-wrap:break-word">ForwardIndexType</code><span style="color:rgb(65,65,65);font-family:Helvetica,Arial,sans-serif;font-size:12px;background-color:transparent" class="">.</span> </blockquote><div class=""><br class=""></div><div class="">And also LazyFilterCollection:</div><div class=""><br class=""></div><div class=""><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">NOTE<br class="">The performance of advancing a <code class="" style="background-color:transparent;border:0px;font-size:0.9em;margin:0px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(128,128,128);font-family:Menlo,monospace;word-wrap:break-word">LazyFilterIndex</code> depends on how sparsely the filtering predicate is satisfied, and may not offer the usual performance given by models of <code class="" style="background-color:transparent;border:0px;font-size:0.9em;margin:0px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(128,128,128);font-family:Menlo,monospace;word-wrap:break-word">ForwardIndexType</code>. Be aware, therefore, that general operations on <code class="" style="background-color:transparent;border:0px;font-size:0.9em;margin:0px;outline:0px;padding:0px;vertical-align:baseline;color:rgb(128,128,128);font-family:Menlo,monospace;word-wrap:break-word">LazyFilterCollection</code> instances may not have the documented complexity.</blockquote></div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">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:</div><div class=""><br class=""></div><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="color:rgb(187,44,162)" class="">var</span><span style="" class=""> c1 = </span><span style="color:rgb(39,42,216)" class="">0</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="color:rgb(187,44,162)" class="">var</span><span style="" class=""> c2 = </span><span style="color:rgb(39,42,216)" class="">0</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="color:rgb(187,44,162)" class="">var</span><span style="" class=""> c3 = </span><span style="color:rgb(39,42,216)" class="">0</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><span style="" class=""></span><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="color:rgb(187,44,162)" class="">let</span><span style="" class=""> xs = </span><span style="color:rgb(112,61,170)" class="">Array</span><span style="" class="">(</span><span style="color:rgb(39,42,216)" class="">1</span><span style="" class="">...</span><span style="color:rgb(39,42,216)" class="">1000</span><span style="" class="">).</span><span style="color:rgb(112,61,170)" class="">lazy</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> .</span><span style="color:rgb(61,29,129)" class="">filter</span><span style="" class=""> { </span><span style="color:rgb(187,44,162)" class="">_</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">in</span><span style="" class=""> </span><span style="color:rgb(79,129,135)" class="">c1</span><span style="" class=""> += </span><span style="color:rgb(39,42,216)" class="">1</span><span style="" class="">; </span><span style="color:rgb(187,44,162)" class="">return</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">true</span><span style="" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> .</span><span style="color:rgb(61,29,129)" class="">filter</span><span style="" class=""> { </span><span style="color:rgb(187,44,162)" class="">_</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">in</span><span style="" class=""> </span><span style="color:rgb(79,129,135)" class="">c2</span><span style="" class=""> += </span><span style="color:rgb(39,42,216)" class="">1</span><span style="" class="">; </span><span style="color:rgb(187,44,162)" class="">return</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">true</span><span style="" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> .</span><span style="color:rgb(61,29,129)" class="">filter</span><span style="" class=""> { </span><span style="color:rgb(187,44,162)" class="">_</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">in</span><span style="" class=""> </span><span style="color:rgb(79,129,135)" class="">c3</span><span style="" class=""> += </span><span style="color:rgb(39,42,216)" class="">1</span><span style="" class="">; </span><span style="color:rgb(187,44,162)" class="">return</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">true</span><span style="" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><span style="" class=""></span><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="color:rgb(187,44,162)" class="">_</span><span style="" class=""> = </span><span style="color:rgb(112,61,170)" class="">Array</span><span style="" class="">(</span><span style="color:rgb(79,129,135)" class="">xs</span><span style="" class="">)</span></div><p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo" class="">
</p><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(79, 129, 135);" class=""><span style="color:rgb(61,29,129)" class="">print</span><span style="" class="">(</span><span style="" class="">c1</span><span style="" class="">, </span><span style="" class="">c2</span><span style="" class="">, </span><span style="" class="">c3</span><span style="" class="">, </span><span style="" class="">c1</span><span style="" class="">+</span><span style="" class="">c2</span><span style="" class="">+</span><span style="" class="">c3</span><span style="" class="">) // </span><b style="color:rgb(34,34,34)" class="">7986 3996 2000 13982</b></div></div><div class=""><span style="" class=""><br class=""></span></div><div class="">I don't think the caller would expect that these filters would be called a total of 14k times (rather than 3k).</div><div class=""><br class=""></div><div class="">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:</div><div class=""><br class=""></div><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(112, 61, 170);" class=""><span style="color:rgb(187,44,162)" class="">extension</span><span style="" class=""> </span><span style="" class="">LazySequenceType</span><span style="" class=""> {</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(187, 44, 162);" class=""><span style="" class=""> </span><span style="" class="">@warn_unused_result</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">public</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">func</span><span style="" class=""> seqFilter(</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> predicate: (Elements.Generator.Element) -> </span><span style="color:rgb(112,61,170)" class="">Bool</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> ) -> </span><span style="color:rgb(112,61,170)" class="">LazyFilterSequence</span><span style="" class=""><Elements> {</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(112, 61, 170);" class=""><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">return</span><span style="" class=""> </span><span style="" class="">LazyFilterSequence</span><span style="" class="">(</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">self</span><span style="" class="">.</span><span style="color:rgb(112,61,170)" class="">elements</span><span style="" class="">, whereElementsSatisfy: predicate)</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class="">}</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><span style="" class=""></span><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="color:rgb(187,44,162)" class="">class</span><span style="" class=""> testperfTests: </span><span style="color:rgb(79,129,135)" class="">XCTestCase</span><span style="" class=""> {</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">func</span><span style="" class=""> testPerformanceSeq() {</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(49, 89, 93);" class=""><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">self</span><span style="" class="">.</span><span style="" class="">measureBlock</span><span style="" class=""> {</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">let</span><span style="" class=""> xs = </span><span style="color:rgb(112,61,170)" class="">Array</span><span style="" class="">(</span><span style="color:rgb(39,42,216)" class="">1</span><span style="" class="">...</span><span style="color:rgb(39,42,216)" class="">1000</span><span style="" class="">).</span><span style="color:rgb(112,61,170)" class="">lazy</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> .</span><span style="color:rgb(49,89,93)" class="">seqFilter</span><span style="" class=""> { </span><span style="color:rgb(187,44,162)" class="">_</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">in</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">true</span><span style="" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> .</span><span style="color:rgb(49,89,93)" class="">seqFilter</span><span style="" class=""> { </span><span style="color:rgb(187,44,162)" class="">_</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">in</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">true</span><span style="" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> .</span><span style="color:rgb(49,89,93)" class="">seqFilter</span><span style="" class=""> { </span><span style="color:rgb(187,44,162)" class="">_</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">in</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">true</span><span style="" class=""> }</span></div><p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px" class=""><span style="" class=""> </span><br class="webkit-block-placeholder"></p><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">_</span><span style="" class=""> = </span><span style="color:rgb(112,61,170)" class="">Array</span><span style="" class="">(xs)</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><span style="" class=""></span><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">func</span><span style="" class=""> testPerformanceCollection() {</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(49, 89, 93);" class=""><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">self</span><span style="" class="">.</span><span style="" class="">measureBlock</span><span style="" class=""> {</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">let</span><span style="" class=""> xs = </span><span style="color:rgb(112,61,170)" class="">Array</span><span style="" class="">(</span><span style="color:rgb(39,42,216)" class="">1</span><span style="" class="">...</span><span style="color:rgb(39,42,216)" class="">1000</span><span style="" class="">).</span><span style="color:rgb(112,61,170)" class="">lazy</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> .</span><span style="color:rgb(61,29,129)" class="">filter</span><span style="" class=""> { </span><span style="color:rgb(187,44,162)" class="">_</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">in</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">true</span><span style="" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> .</span><span style="color:rgb(61,29,129)" class="">filter</span><span style="" class=""> { </span><span style="color:rgb(187,44,162)" class="">_</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">in</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">true</span><span style="" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> .</span><span style="color:rgb(61,29,129)" class="">filter</span><span style="" class=""> { </span><span style="color:rgb(187,44,162)" class="">_</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">in</span><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">true</span><span style="" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><span style="" class=""></span><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> </span><span style="color:rgb(187,44,162)" class="">_</span><span style="" class=""> = </span><span style="color:rgb(112,61,170)" class="">Array</span><span style="" class="">(xs)</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class=""> }</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="" class="">}</span></div></div><div class=""><span style="" class=""><br class=""></span></div><div class="">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.</div><div class=""><br class=""></div><div class="">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?</div><div class=""><br class=""></div><div class="">-Rob</div><div class=""><br class=""></div></div><div class="gmail_signature"><div dir="ltr" class=""><div class=""></div></div></div>
</div></div>
_______________________________________________<br class="">swift-dev mailing list<br class=""><a href="mailto:swift-dev@swift.org" class="">swift-dev@swift.org</a><br class="">https://lists.swift.org/mailman/listinfo/swift-dev<br class=""></div></blockquote></div><br class=""></body></html>