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
[email protected]
https://mail.mozilla.org/listinfo/es-discuss
