<div dir="ltr"><br><div class="gmail_extra"><div class="gmail_quote">On Mon, May 9, 2016 at 4:16 PM, Dmitri Gribenko <span dir="ltr"><<a href="mailto:gribozavr@gmail.com" target="_blank">gribozavr@gmail.com</a>></span> wrote:<br><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">robnapier@gmail.com</a>> wrote:<br>
> It violates the performance requirements.<br>
> CollectionType.count requires O(1) access if Index is a<br>
> RandomAccessIndexType.<br>
<br>
</span>Hi Rob,<br>
<br>
We don't have RandomAccessIndexType anymore.<br><span class=""><font color="#888888"><br></font></span></blockquote><div><br></div><div>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><br></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><span style="color:rgb(65,65,65);font-family:Helvetica,Arial,sans-serif;font-size:12px;background-color:transparent">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"> </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"> </span><span style="color:rgb(65,65,65);font-family:Helvetica,Arial,sans-serif;font-size:12px;background-color:transparent">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"> </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">.</span> </blockquote><div><br></div><div>And also LazyFilterCollection:</div><div><br></div><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>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><br></div><div><br></div><div>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><br></div><div><p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style="color:rgb(187,44,162)">var</span><span style=""> c1 = </span><span style="color:rgb(39,42,216)">0</span></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style="color:rgb(187,44,162)">var</span><span style=""> c2 = </span><span style="color:rgb(39,42,216)">0</span></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style="color:rgb(187,44,162)">var</span><span style=""> c3 = </span><span style="color:rgb(39,42,216)">0</span></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"><span style=""></span><br></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style="color:rgb(187,44,162)">let</span><span style=""> xs = </span><span style="color:rgb(112,61,170)">Array</span><span style="">(</span><span style="color:rgb(39,42,216)">1</span><span style="">...</span><span style="color:rgb(39,42,216)">1000</span><span style="">).</span><span style="color:rgb(112,61,170)">lazy</span></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> .</span><span style="color:rgb(61,29,129)">filter</span><span style=""> { </span><span style="color:rgb(187,44,162)">_</span><span style=""> </span><span style="color:rgb(187,44,162)">in</span><span style=""> </span><span style="color:rgb(79,129,135)">c1</span><span style=""> += </span><span style="color:rgb(39,42,216)">1</span><span style="">; </span><span style="color:rgb(187,44,162)">return</span><span style=""> </span><span style="color:rgb(187,44,162)">true</span><span style=""> }</span></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> .</span><span style="color:rgb(61,29,129)">filter</span><span style=""> { </span><span style="color:rgb(187,44,162)">_</span><span style=""> </span><span style="color:rgb(187,44,162)">in</span><span style=""> </span><span style="color:rgb(79,129,135)">c2</span><span style=""> += </span><span style="color:rgb(39,42,216)">1</span><span style="">; </span><span style="color:rgb(187,44,162)">return</span><span style=""> </span><span style="color:rgb(187,44,162)">true</span><span style=""> }</span></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> .</span><span style="color:rgb(61,29,129)">filter</span><span style=""> { </span><span style="color:rgb(187,44,162)">_</span><span style=""> </span><span style="color:rgb(187,44,162)">in</span><span style=""> </span><span style="color:rgb(79,129,135)">c3</span><span style=""> += </span><span style="color:rgb(39,42,216)">1</span><span style="">; </span><span style="color:rgb(187,44,162)">return</span><span style=""> </span><span style="color:rgb(187,44,162)">true</span><span style=""> }</span></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"><span style=""></span><br></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style="color:rgb(187,44,162)">_</span><span style=""> = </span><span style="color:rgb(112,61,170)">Array</span><span style="">(</span><span style="color:rgb(79,129,135)">xs</span><span style="">)</span></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo">
</p><p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(79,129,135)"><span style="color:rgb(61,29,129)">print</span><span style="color:rgb(0,0,0)">(</span><span style="">c1</span><span style="color:rgb(0,0,0)">, </span><span style="">c2</span><span style="color:rgb(0,0,0)">, </span><span style="">c3</span><span style="color:rgb(0,0,0)">, </span><span style="">c1</span><span style="color:rgb(0,0,0)">+</span><span style="">c2</span><span style="color:rgb(0,0,0)">+</span><span style="">c3</span><span style="color:rgb(0,0,0)">) // </span><b style="color:rgb(34,34,34)">7986 3996 2000 13982</b></p></div><div><span style="color:rgb(0,0,0)"><br></span></div><div>I don't think the caller would expect that these filters would be called a total of 14k times (rather than 3k).</div><div><br></div><div>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><br></div><div><p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(112,61,170)"><span style="color:rgb(187,44,162)">extension</span><span style="color:rgb(0,0,0)"> </span><span style="">LazySequenceType</span><span style="color:rgb(0,0,0)"> {</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(187,44,162)"><span style="color:rgb(0,0,0)"> </span><span style="">@warn_unused_result</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> </span><span style="color:rgb(187,44,162)">public</span><span style=""> </span><span style="color:rgb(187,44,162)">func</span><span style=""> seqFilter(</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> predicate: (Elements.Generator.Element) -> </span><span style="color:rgb(112,61,170)">Bool</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> ) -> </span><span style="color:rgb(112,61,170)">LazyFilterSequence</span><span style=""><Elements> {</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(112,61,170)"><span style="color:rgb(0,0,0)"> </span><span style="color:rgb(187,44,162)">return</span><span style="color:rgb(0,0,0)"> </span><span style="">LazyFilterSequence</span><span style="color:rgb(0,0,0)">(</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> </span><span style="color:rgb(187,44,162)">self</span><span style="">.</span><span style="color:rgb(112,61,170)">elements</span><span style="">, whereElementsSatisfy: predicate)</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> }</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style="">}</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"><span style=""></span><br></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style="color:rgb(187,44,162)">class</span><span style=""> testperfTests: </span><span style="color:rgb(79,129,135)">XCTestCase</span><span style=""> {</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> </span><span style="color:rgb(187,44,162)">func</span><span style=""> testPerformanceSeq() {</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(49,89,93)"><span style="color:rgb(0,0,0)"> </span><span style="color:rgb(187,44,162)">self</span><span style="color:rgb(0,0,0)">.</span><span style="">measureBlock</span><span style="color:rgb(0,0,0)"> {</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> </span><span style="color:rgb(187,44,162)">let</span><span style=""> xs = </span><span style="color:rgb(112,61,170)">Array</span><span style="">(</span><span style="color:rgb(39,42,216)">1</span><span style="">...</span><span style="color:rgb(39,42,216)">1000</span><span style="">).</span><span style="color:rgb(112,61,170)">lazy</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> .</span><span style="color:rgb(49,89,93)">seqFilter</span><span style=""> { </span><span style="color:rgb(187,44,162)">_</span><span style=""> </span><span style="color:rgb(187,44,162)">in</span><span style=""> </span><span style="color:rgb(187,44,162)">true</span><span style=""> }</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> .</span><span style="color:rgb(49,89,93)">seqFilter</span><span style=""> { </span><span style="color:rgb(187,44,162)">_</span><span style=""> </span><span style="color:rgb(187,44,162)">in</span><span style=""> </span><span style="color:rgb(187,44,162)">true</span><span style=""> }</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> .</span><span style="color:rgb(49,89,93)">seqFilter</span><span style=""> { </span><span style="color:rgb(187,44,162)">_</span><span style=""> </span><span style="color:rgb(187,44,162)">in</span><span style=""> </span><span style="color:rgb(187,44,162)">true</span><span style=""> }</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"><span style=""> </span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> </span><span style="color:rgb(187,44,162)">_</span><span style=""> = </span><span style="color:rgb(112,61,170)">Array</span><span style="">(xs)</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> }</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> }</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"><span style=""></span><br></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> </span><span style="color:rgb(187,44,162)">func</span><span style=""> testPerformanceCollection() {</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(49,89,93)"><span style="color:rgb(0,0,0)"> </span><span style="color:rgb(187,44,162)">self</span><span style="color:rgb(0,0,0)">.</span><span style="">measureBlock</span><span style="color:rgb(0,0,0)"> {</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> </span><span style="color:rgb(187,44,162)">let</span><span style=""> xs = </span><span style="color:rgb(112,61,170)">Array</span><span style="">(</span><span style="color:rgb(39,42,216)">1</span><span style="">...</span><span style="color:rgb(39,42,216)">1000</span><span style="">).</span><span style="color:rgb(112,61,170)">lazy</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> .</span><span style="color:rgb(61,29,129)">filter</span><span style=""> { </span><span style="color:rgb(187,44,162)">_</span><span style=""> </span><span style="color:rgb(187,44,162)">in</span><span style=""> </span><span style="color:rgb(187,44,162)">true</span><span style=""> }</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> .</span><span style="color:rgb(61,29,129)">filter</span><span style=""> { </span><span style="color:rgb(187,44,162)">_</span><span style=""> </span><span style="color:rgb(187,44,162)">in</span><span style=""> </span><span style="color:rgb(187,44,162)">true</span><span style=""> }</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> .</span><span style="color:rgb(61,29,129)">filter</span><span style=""> { </span><span style="color:rgb(187,44,162)">_</span><span style=""> </span><span style="color:rgb(187,44,162)">in</span><span style=""> </span><span style="color:rgb(187,44,162)">true</span><span style=""> }</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"><span style=""></span><br></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> </span><span style="color:rgb(187,44,162)">_</span><span style=""> = </span><span style="color:rgb(112,61,170)">Array</span><span style="">(xs)</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> }</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style=""> }</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style="">}</span></p></div><div><span style=""><br></span></div><div>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><br></div><div>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><br></div><div>-Rob</div><div><br></div></div><div class="gmail_signature"><div dir="ltr"><div></div></div></div>
</div></div>