Queue Feature Request

[Zach Boldyga]

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 <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.
>
> -Filip
>
> On Feb 25, 2017, at 15:03, Zach Boldyga <zach at scalabull.com> 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
> es-discuss at mozilla.org
> https://mail.mozilla.org/listinfo/es-discuss
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20170225/9215ba8e/attachment.html>