Queue Feature Request

Mon Feb 27 00:42:48 UTC 2017

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 <fpizlo at apple.com> wrote:

> Our queue optimizations are not JIT based.
>
> -Filip
>
> 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
> 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 <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/20170226/f51aad38/attachment-0001.html>