Queue Feature Request
zach at scalabull.com
Mon Feb 27 00:42:48 UTC 2017
Thnx Filip. Could you elaborate on how it works, or point me to the
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.
Scalabull | Founder
1 (866) 846-8771 x 101
On Sun, Feb 26, 2017 at 5:25 AM, Filip Pizlo <fpizlo at apple.com> wrote:
> Our queue optimizations are not JIT based.
> On Feb 25, 2017, at 20:38, Zach Boldyga <zach at scalabull.com> 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
> 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
> 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
> 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?
> Zach Boldyga
> Scalabull | Founder
> 1 (866) 846-8771 x 101 <(866)%20846-8771>
> On Sat, Feb 25, 2017 at 5:10 PM, Filip Pizlo <fpizlo at apple.com> 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.
>> On Feb 25, 2017, at 15:03, Zach Boldyga <zach at scalabull.com> wrote:
>> 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?
>> Zach Boldyga
>> Scalabull | Founder
>> 1 (866) 846-8771 x 101 <(866)%20846-8771>
>> es-discuss mailing list
>> es-discuss at mozilla.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the es-discuss