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

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

# Claude Pache (11 years ago)

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.)

# Till Schneidereit (11 years ago)

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. 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).

# Claude Pache (11 years ago)

Le 18 août 2014 à 12:59, Till Schneidereit <till at tillschneidereit.net> a écrit :

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).

Nit: As currently specced, SortCompare includes obligatory calls to [[HasProperty]] and [[Get]] on some keys before invoking the comparison function: so, SpiderMonkey/Chakra don't adhere to the specs. Even JSC/V8 don't fully adhere to the spec on this point, because (as I've observed) they may omit a call to [[HasProperty]]/[[Get]] when the value is known. But I think it is a spec bug that can be corrected, in order to make all current implementations compliant (SortCompare should take the values, not the keys, as arguments).

# Till Schneidereit (11 years ago)

Oh, you're right. And I agree: SortCompare should take values.