Array.prototype.sort: order and moment of the [[Get]]/[[Set]] calls
claude.pache at gmail.com
Mon Aug 18 03:22:16 PDT 2014
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.)
More information about the es-discuss