<div dir="ltr">Thnx Filip. Could you elaborate on how it works, or point me to the relevant code? <div><br></div><div>If you have a robust solution that trumps V8's, I can take it to the V8 contributor mailing list and try to implement it. <br><img src="https://t.yesware.com/t/5935242c34ebdf77e1f164cd199306eb32ad03af/65ce521c0cf058500d05d7035c0b2581/spacer.gif" style="border:0; width:0; height:0; overflow:hidden;" width="0" height="0"><img src="http://t.yesware.com/t/5935242c34ebdf77e1f164cd199306eb32ad03af/65ce521c0cf058500d05d7035c0b2581/spacer.gif" style="border:0; width:0; height:0; overflow:hidden;" width="0" height="0"></div><div class="gmail_extra"><div><div class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr" style="font-size:small;font-family:arial"><font face="arial, helvetica, sans-serif"><br></font></div><div dir="ltr" style="font-size:small;font-family:arial"><font face="arial, helvetica, sans-serif">Zach Boldyga</font></div><div dir="ltr" style="font-size:small;font-family:arial"><div><font face="arial, helvetica, sans-serif">Scalabull  |  Founder</font></div><div><font face="arial, helvetica, sans-serif">1 (866) 846-8771 x 101</font></div></div></div></div></div></div></div></div></div>
<br><div class="gmail_quote">On Sun, Feb 26, 2017 at 5:25 AM, Filip Pizlo <span dir="ltr"><<a href="mailto:fpizlo@apple.com" target="_blank">fpizlo@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><div>Our queue optimizations are not JIT based. <span class="HOEnZb"><font color="#888888"><br><br>-Filip</font></span></div><div><div class="h5"><div><br>On Feb 25, 2017, at 20:38, Zach Boldyga <<a href="mailto:zach@scalabull.com" target="_blank">zach@scalabull.com</a>> wrote:<br><br></div><blockquote type="cite"><div><div dir="ltr">So both the more modern versions of V8 and Webkit's JIT both make automatic, background attempts to amortize Array's deque-type operations. I wonder why both teams decided to make that change, which deviates from the ECMA standard. Either way, they are able to give a big performance boost without creating any breaking changes to javascript.<div><br></div><div>That said, I can't comment on WebKit's engine (B3 JIT?), but V8's attempt to amortize shift and unshift operations comes to a screeching halt with large arrays. See the benchmark at the bottom of the page: <a href="https://github.com/petkaantonov/deque." target="_blank">https://github.com/<wbr>petkaantonov/deque.</a>.. This creates a problem - shift appears like it's constant time, but then in some cases it's really slow. So developers, especially the less experienced ones, are thinking that Javascript's Array is meant to be shifted and pushed in tandem, but then that code breaks down depending on the browser or use case. </div><div><br></div><div>I notice that a common trend with the browsers is now to layer-up compilers, with general purpose compilers running first, then more optimal compilers running if code gets really hot. So in effect, there are a bunch of different compilers floating around. It seems awfully complex for all of them to try and figure out how to best optimize array shift operations. Something that works well for certain use cases is not going to work well for other use cases. V8 is case-in-point, in the way that it's optimized for small arrays (the more likely case). <br><div><br></div><div>Maybe the standards should reflect an approach more like Python's, which breaks lists and deques into two separate entities that excel in their unique use cases. By explicitly separating them, compilers don't have to do the extra leg-work. Then, in addition, slap a big warning on the Array shift operation that says - this is really slow. Compilers can leave in the optimizations if they want, but can also have the liberty of a more simple approach.</div><div><br></div><div>I think the fact that the compilers already have support for Map is useful, given the earlier comment on how it can be used for queue operations. But it would also need a way to support deque operations to fully close-out this re-design.</div><div><br></div><div>Maybe it makes sense to make an abstraction of the data structure underlying the Map, as it's implemented in the various compilers, add support for some type of reverse iterator, and then support both Map and Deque without the compiler teams having to do much additional work?</div><div><div><img src="https://t.yesware.com/t/5935242c34ebdf77e1f164cd199306eb32ad03af/481ba22f304dd0712b06cef9d10b0120/spacer.gif" style="border:0px;width:0px;height:0px;overflow:hidden" width="0" height="0"><img src="http://t.yesware.com/t/5935242c34ebdf77e1f164cd199306eb32ad03af/481ba22f304dd0712b06cef9d10b0120/spacer.gif" style="border:0px;width:0px;height:0px;overflow:hidden" width="0" height="0"></div></div></div></div><div class="gmail_extra"><br clear="all"><div><div class="m_-5671817788007131799gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div dir="ltr" style="font-size:small;font-family:arial"><font face="arial, helvetica, sans-serif">Best,</font></div><div dir="ltr" style="font-size:small;font-family:arial"><font face="arial, helvetica, sans-serif"><br></font></div><div dir="ltr" style="font-size:small;font-family:arial"><font face="arial, helvetica, sans-serif">Zach Boldyga</font></div><div dir="ltr" style="font-size:small;font-family:arial"><div><font face="arial, helvetica, sans-serif">Scalabull  |  Founder</font></div><div><font face="arial, helvetica, sans-serif"><a href="tel:(866)%20846-8771" value="+18668468771" target="_blank">1 (866) 846-8771 x 101</a></font></div></div></div></div></div></div></div></div></div></div></div></div></div>
<br><div class="gmail_quote">On Sat, Feb 25, 2017 at 5:10 PM, Filip Pizlo <span dir="ltr"><<a href="mailto:fpizlo@apple.com" target="_blank">fpizlo@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><div>In WebKit the array implementation switches to an amortized constant time deque if you use push/pop/shift/unshift in anger. So, a program that just treats arrays as if they were deques should perform great. If you find that it does not perform as well as you would like, then we would love to hear a bug report at <a href="http://bugs.webkit.org" target="_blank">bugs.webkit.org</a>. </div><div id="m_-5671817788007131799m_-8597693075915409851AppleMailSignature"><br></div><div id="m_-5671817788007131799m_-8597693075915409851AppleMailSignature">I think that adding a Deque type is an OK idea. But maybe it's better if all of the implementations get adaptive arrays right. </div><div id="m_-5671817788007131799m_-8597693075915409851AppleMailSignature"><br>-Filip</div><div><div class="m_-5671817788007131799h5"><div><br>On Feb 25, 2017, at 15:03, Zach Boldyga <<a href="mailto:zach@scalabull.com" target="_blank">zach@scalabull.com</a>> wrote:<br><br></div><blockquote type="cite"><div><div dir="ltr">Hello,<div><div style="font-size:12.8px">   Sorry if this is an ignorant request, I scanned the proposals and didn't see anything that appeared similar.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">   Is it appropriate for ECMAScript to include a Queue implementation, or adjust shifting to a constant amortized time operation? Server-side usage of the language is mostly formidable nowadays, and I've run into cases where it would have been convenient to have an in-language queue.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">   I see in the latest Array.prototype.shift documentation (<a href="https://tc39.github.io/ecma262/#sec-array.prototype.shift" target="_blank">https://tc39.github.io/ecma26<wbr>2/#sec-array.prototype.shift</a>) <wbr>that shift is still intended to be an O(n) operation, meaning those wanting to implement a proper queue may need to rely on external libraries, like this one: <a href="https://github.com/petkaantonov/deque" target="_blank">https://github.com/petkaa<wbr>ntonov/deque</a> . </div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">   As the github link mentions, V8 has a trick to get around array resizing, but for serious users we still need to rely on an external library. It'd be great if this was a built-in feature.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">   I'm sure someone has looked at this before - what do you think?</div><div style="font-size:12.8px"><br></div><div><div class="m_-5671817788007131799m_-8597693075915409851gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div dir="ltr" style="font-size:small;font-family:arial"><font face="arial, helvetica, sans-serif">Best,</font></div><div dir="ltr" style="font-size:small;font-family:arial"><font face="arial, helvetica, sans-serif"><br></font></div><div dir="ltr" style="font-size:small;font-family:arial"><font face="arial, helvetica, sans-serif">Zach Boldyga</font></div><div dir="ltr" style="font-size:small;font-family:arial"><div><font face="arial, helvetica, sans-serif">Scalabull  |  Founder</font></div><div><font face="arial, helvetica, sans-serif"><a href="tel:(866)%20846-8771" value="+18668468771" target="_blank">1 (866) 846-8771 x 101</a></font></div></div></div></div></div></div></div></div></div></div></div></div></div>
<img src="https://t.yesware.com/t/5935242c34ebdf77e1f164cd199306eb32ad03af/b978d0f914ec7aa62ba351cba93f80ed/spacer.gif" style="border:0px;width:0px;height:0px;overflow:hidden" width="0" height="0"><img src="http://t.yesware.com/t/5935242c34ebdf77e1f164cd199306eb32ad03af/b978d0f914ec7aa62ba351cba93f80ed/spacer.gif" style="border:0px;width:0px;height:0px;overflow:hidden" width="0" height="0"></div></div>
</div></blockquote></div></div><blockquote type="cite"><div><span>______________________________<wbr>_________________</span><br><span>es-discuss mailing list</span><br><span><a href="mailto:es-discuss@mozilla.org" target="_blank">es-discuss@mozilla.org</a></span><br><span><a href="https://mail.mozilla.org/listinfo/es-discuss" target="_blank">https://mail.mozilla.org/listi<wbr>nfo/es-discuss</a></span><br></div></blockquote></div></blockquote></div><br></div>
</div></blockquote></div></div></div></blockquote></div><br></div><font face="yw-5935242c34ebdf77e1f164cd199306eb32ad03af-65ce521c0cf058500d05d7035c0b2581--to" style="display:none"></font></div>