Array.prototype.sort: order and moment of the [[Get]]/[[Set]] calls

Till Schneidereit till at tillschneidereit.net
Mon Aug 18 03:59:03 PDT 2014


Do you have any examples of real-world issues caused by this difference? If
not, I don't think we should spec the behavior of .sort any more than it is
right now. (Well, I'd argue for requiring a stable sort, but then that's
easy for me as an implementor working on an engine that already has a
stable sort.)

The reason is the same as for the way .sort is currently specced: to enable
experimentation and substantial changes to implementations in an area where
meaningful changes in performance characteristics are to be expected. These
changes aren't likely to be gained by substantial advances in sorting
itself, granted. However, changes of performance characteristics of other
parts of the engine (say, memory allocation, reading Array elements, or
invocation of getters/setters) might make algorithms feasible for an
implementation that weren't, before.

Case in point, in SpiderMonkey we're likely to switch to a self-hosted
implementation of, probably, Timsort, soon-ish[1]. This will change our
implementation's behavior in precisely those characteristics you propose to
standardize. In the future, we might experiment with parallelizing parts of
the sorting. This might force us to read all values once and only write the
fully-sorted array back in the end, but it might also not, and precluding a
more efficient implementation for theoretical concerns would be bad.

Note also that, by my reading of the spec at least, all implementations
currently fully adhere to the spec: they "[p]erform an
implementation-dependent sequence of calls to the [[Get]] and [[Set]]
internal methods of obj, to the DeletePropertyOrThrow abstract operation
with obj as the first argument, and to SortCompare". My reading of this is
that "implementation-denendent sequence" refers to all four mentioned
functions, where an implementation might either intermix all of them (like
v8/JSC do) or first do a (sub-)sequence of only [[Get]] calls and then a
second (sub-)sequence intermixing calls to all the other functions (like
Chakra/SpiderMonkey).


[1]: https://bugzilla.mozilla.org/show_bug.cgi?id=715181


On Mon, Aug 18, 2014 at 12:22 PM, Claude Pache <claude.pache at gmail.com>
wrote:

> Hi,
>
> Exploring how web browsers implement Array.protototype.sort, I've found
> two patterns:
>
> On the one hand, Firefox (SpiderMonkey) and IE (Chakra) have three
> distinct phases:
>
> 1. Get the values from the target, in ascending order of the keys (from 0
> to the length exclusively) (using [[HasProperty]] + [[Get]]);
> 2. Perform a series of calls to the comparison function, using the values
> found in the previous step as arguments, in order to sort them;
> 3. Put the sorted values on the target, in ascending order of the keys
> (using [[Set]], or sometimes [[Delete]] in case of sparse array).
>
> On the other hand, in Safari (JSC), Chrome and Opera (V8), calls to the
> comparison function are intermingled with getting and putting the values of
> the target. It is more or less as follows (omitting minor complications
> irrelevant to the discussion):
>
> 1. Repeat, until finished:
>         a. Get the values from the target for two keys (using
> [[HasProperty]] + [[Get]]);
>         b. Perform (if necessary) a call to the comparison function, using
> the values found in previous step as arguments;
>         c. If necessary, put partially sorted values on the target for
> keys recently visited (using [[Set]], or sometimes [[Delete]] in case of
> sparse array).
>
> The SpiderMonkey/Chakra behaviour seems more appropriate for the following
> reasons:
>
> * Since the sorting phase is completely isolated from the
> retrieving/putting phases, even if the target has strange read/write
> semantics, that cannot make the sort algorithm go nuts (provided that the
> comparison function is sufficiently consistent, anyway).
> * The number of read/write accesses to the target is minimized, which is a
> win if the target is an object with slow read/write semantics (e.g., an
> object with convoluted getters/setters).
> * The order and the moment of each read/write access is exactly
> determined, so that the result is more predictable, even when confronted to
> a strange-behaving target, (provided that the comparison function doesn't
> do strange things).
>
> Therefore, I think we ought to normalise the SpiderMonkey/Chakra
> behaviour. (Currently, the specced semantics is nearer to the one of
> JSC/V8.)
>
> —Claude
>
>
>
> _______________________________________________
> 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/20140818/d5b4d651/attachment.html>


More information about the es-discuss mailing list