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));
}());
_______________________________________________
es-discuss mailing list
[email protected]
https://mail.mozilla.org/listinfo/es-discuss
