iteration order for Object

Charles Kendrick charles at isomorphic.com
Fri Mar 11 12:14:58 PST 2011


On 3/10/2011 7:33 PM, Boris Zbarsky wrote:
> On 3/10/11 9:58 PM, Charles Kendrick wrote:
>> 1. tens of thousands of web applications that need to define a sorted
>> map plus perhaps billions of JSON messages per day
>>
>> .. to ..
>>
>> 2. a handful of crypto / computational use cases used by a tiny minority
>> of sites
>>
>> What should be optimized for?
>
> It depends on the relative slowdowns, possibly.

Billions of JSON messages vs a handful of sites should be pretty clear cut, but I've collected 
some numbers anyway just to make it more obvious.

Below are two partial implementations of LinkedHashMap in JavaScript, with test code to 
populate with lots of keys and remove half the keys at random, then alert() the results.  Both 
implementations add and maintain an index to provide O(1) lookups.

Each is compared to the speed of the equivalent use of Object assuming it supports ordering, 
which is just to use the JavaScript "delete" operator to remove keys.  My numbers are from 
Firefox 3.6.15 on a WinXP and a MacOSX laptop I have here.

The first is a straightforward implementation where insert and removal use splice() to modify 
an Array.  This is what most developers would probably implement.  This is approximately 
800-1000 times slower than a native Object.

The second leverages native speed better by using two Objects to store the forward and reverse 
pointers of a classic linked list.  I'll stipulate that everyone on this list would arrive at 
this implementation, but in my opinion a vanishing small number of JavaScript programmers at 
large would figure it out.

Even so it's 8-10x slower than native.

So if you will stipulate that having an LinkedHashMap is at least as common a JavaScript use 
case as in-memory crypto for evoting, it's pretty clear where the most bang for the buck is, 
*even before* you consider all the JSON messages that could be simplified if order is preserved.

>> Note that we don't really even have to choose. If you tell the guys
>> implementing these crypto / bignum libraries that their code is going to
>> run 6x faster in Firefox if they use an Array, they'll probably have
>> switched by Tuesday.
>
> I told them in September. There's been no change yet. I think you overestimate how much people
> are willing to change their code to work around what they think are bugs....

To be fair, what you told them was that you considered it a bug in Firefox that their code was 
still slower in Firefox than in Chrome.  So of course they would not change their code.





== first partial implementation: order maintained via an array

(function () {

var sourceDataObj = {};
var sourceDataArr = [];
var keysToRemove = [];

for (var i = 0; i < 30000; i++) {
     sourceDataObj["key" + i] = "value" + i;
     sourceDataArr[sourceDataArr.length] = "key" + i;
     sourceDataArr[sourceDataArr.length] = "value" + i;
     if (Math.random(1) > 0.5) {
         keysToRemove[keysToRemove.length] = "key" + i;
     }
}

var orderedMap = {
     init : function (data) {
         this.data = data;

         this.index = {};
         for (var i = 0; i < data.length; i++) {
             this.index[data[i]] = data[i+1];
             i++;
         }
     },
     get : function (key) {
         return this.index[key];
     },
     remove : function (key) {
         var arrIndex = this.data.indexOf(key);
         this.data.splice(arrIndex, 2);
         delete this.index[key];
     }
};

var start = new Date().getTime();
orderedMap.init(sourceDataArr);

for (var i = 0; i < keysToRemove.length; i++) {
     orderedMap.remove(keysToRemove[i]);
}
alert("orderedMap: " + (new Date().getTime() - start));

var start = new Date().getTime();
for (var i = 0; i < keysToRemove.length; i++) {
     delete sourceDataObj[keysToRemove[i]];
}
alert("object: " + (new Date().getTime() - start));

}());

== second partial implementation: linked list via dual Objects

(function () {

var sourceDataObj = {};
var sourceDataArr = [];
var keysToRemove = [];

for (var i = 0; i < 900000; i++) {
     sourceDataObj["key" + i] = "value" + i;
     sourceDataArr[sourceDataArr.length] = "key" + i;
     sourceDataArr[sourceDataArr.length] = "value" + i;
     if (Math.random(1) > 0.5) {
         keysToRemove[keysToRemove.length] = "key" + i;
     }
}

var orderedMap = {
     init : function (sourceData) {
         this.data = {};
         this.nextKeys = {};
         this.priorKeys = {};
         for (var i = 0; i < sourceData.length; i++) {
             var key = sourceData[i],
                 value = sourceData[i+1];
             this.put(key, value);
             i++;
         }
     },
     get : function (key) {
         return this.data[key];
     },
     put : function (key, value) {
         this.data[key] = value;

         if (this.firstKey == null) this.firstKey = key;

         if (this.nextKeys[key]) {
             // entry exists: not implemented
         } else {
             // new insertion
             if (this.lastKey == null) {
                 // empty list
                 this.lastKey = key;
             } else {
                 // new last key
                 this.nextKeys[this.lastKey] = key;
                 this.priorKeys[key] = this.lastKey;
                 this.lastKey = key;
             }
         }
     },
     remove : function (key) {
         delete this.data[key];
         var keyBefore = this.priorKeys[key],
             keyAfter = this.nextKeys[key];

         this.nextKeys[keyBefore] = keyAfter;
         this.priorKeys[keyAfter] = keyBefore;

         if (this.firstKey == key) this.firstKey = keyAfter;
         if (this.lastKey == key) this.lastKey = keyBefore;

         delete this.nextKeys[key];
         delete this.priorKeys[key];
     },
     getKeys : function () {
         var nextKey = this.firstKey,
             keys = [this.firstKey];
         while ((nextKey = this.nextKeys[nextKey]) != null) {
             keys[keys.length] = nextKey;
         }
         return keys;
     }
};
var start = new Date().getTime();
orderedMap.init(sourceDataArr);

for (var i = 0; i < keysToRemove.length; i++) {
     orderedMap.remove(keysToRemove[i]);
}
alert("orderedMap: " + (new Date().getTime() - start));

var start = new Date().getTime();
for (var i = 0; i < keysToRemove.length; i++) {
     delete sourceDataObj[keysToRemove[i]];
}
alert("object: " + (new Date().getTime() - start));

}());


More information about the es-discuss mailing list