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 > >> 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 >>> >>> _______________________________________________ >>> 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
