Thnx Filip. Could you elaborate on how it works, or point me to the relevant code?
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. Zach Boldyga Scalabull | Founder 1 (866) 846-8771 x 101 On Sun, Feb 26, 2017 at 5:25 AM, Filip Pizlo <[email protected]> wrote: > Our queue optimizations are not JIT based. > > -Filip > > On Feb 25, 2017, at 20:38, Zach Boldyga <[email protected]> wrote: > > 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. > > 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: > https://github.com/petkaantonov/deque... 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. > > 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). > > 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. > > 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. > > 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? > > Best, > > Zach Boldyga > Scalabull | Founder > 1 (866) 846-8771 x 101 <(866)%20846-8771> > > On Sat, Feb 25, 2017 at 5:10 PM, Filip Pizlo <[email protected]> wrote: > >> 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 bugs.webkit.org. >> >> 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. >> >> -Filip >> >> On Feb 25, 2017, at 15:03, Zach Boldyga <[email protected]> wrote: >> >> Hello, >> Sorry if this is an ignorant request, I scanned the proposals and >> didn't see anything that appeared similar. >> >> 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. >> >> I see in the latest Array.prototype.shift documentation ( >> https://tc39.github.io/ecma262/#sec-array.prototype.shift) 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: >> https://github.com/petkaantonov/deque . >> >> 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. >> >> I'm sure someone has looked at this before - what do you think? >> >> Best, >> >> Zach Boldyga >> Scalabull | Founder >> 1 (866) 846-8771 x 101 <(866)%20846-8771> >> >> _______________________________________________ >> es-discuss mailing list >> [email protected] >> https://mail.mozilla.org/listinfo/es-discuss >> >> >
_______________________________________________ es-discuss mailing list [email protected] https://mail.mozilla.org/listinfo/es-discuss
