Array#sort() implementations not interoperable

David Bruant bruant.d at gmail.com
Fri Jun 14 00:50:26 PDT 2013


Le 14/06/2013 02:37, Mark S. Miller a écrit :
> Other things being equal, or even close, I am always in favor of specs 
> being more deterministic.
>
>  Even with this pinned down, we should still allow implementations to 
> switch among different algorithms based on the size of the array, the 
> cache hierarchy, or whatever. Because of getters/setters and proxies, 
> the differences between stable algorithms is still observable.
Maybe there is something that can be made more deterministic about sort.

     var a = ["yes", "no", "maybe", "I don't know", "can you repeat the 
question?"];

     var pa = new Proxy(a, {
         get: function(target, name){
             console.log('get', name);
             return target[name];
         },
         set: function(target, name, value){
             console.log('set', name);
             return target[name] = value;
         }
     })

     pa.sort()

In Firefox, I see:

   "get" "sort"
   "get" "length"
   "get" "0"
   "get" "1"
   "get" "2"
   "get" "3"
   "get" "4"
   "set" "0"
   "set" "1"
   "set" "2"
   "set" "3"
   "set" "4"

Forgetting about the 2 first "get", the behavior exposed here is:
1) [[Get]] all elements in order once
2) sort them internally (without touching the array!)
3) a serie of at most "a.length" [[Put]] calls

And this particular behavior might be standardizable without a loss 
(even with a gain), because:
1) a sort algorithm only needs all the array values once at least once 
(serie of [[Get]]s) and should probably avoiding touching the array 
again since getter or get traps may be costly and return inconsistent 
values (so [[Get]] the values at most once)
2) the sorting algorithms is on the values, not on the array (though 
with membranes, if the comparator function touches more than the object 
identity, it can be observable, but that's not the problem of the sort 
algorithm)
3) No sort algorithm requires to rearrange more elements than the number 
there is in the array.

In absolute terms, as you say, the sequence of [[Put]] may make the 
stable algorithm observable, but I don't think that's a problem.

Standardizing the above behavior has some impact on memory (copying all 
values out of the array for the sort algorithm) in theory. In practice, 
the [[Get]] and [[Put]] sequences are only observable if there is a 
getter or setter on the array or the array is a proxy, so the 
implementation is free to choose its memory behavior when there is no 
proxy nor getter/setter.
When there is a getter/setter or proxy, the reduction of number of 
[[Get]]/[[Put]] calls may be worth the additional memory.

David


More information about the es-discuss mailing list