V8 vs JS 1.7(firefox2) vs JS 1.8(firefox3)陣列排序速度比較
Mon, 08 Sep 2008 17:06:07 +0800前幾天試著練習把SpiderMonkey整合進程式中，寫了一個簡單的程式來執行javascript檔案，global物件除了標準以外提供了print函數來列印訊息。
今天下載了V8，編譯了他的shell sample來試試看。我電腦裡還留著幾年前編譯的JS 1.7，也同樣有一個jsshell，所以就把之前做的陣列排序測試用這三個來測試一下。結果大致符合預期，JS 1.8還是贏過V8。
先看看測試的javascript：
var query;
var getquery;
try {
(function(){
query = function(_cm) {
var order=[];
var selection=[];
var from=[];
var criteria=[];
var limit=[];
var result=[];
var cm = _cm
/**
// valid format for parameter a is
// [int,int,int...]
// each number for zero based index number to select from the from array
*/
this.select = function(a) {
if (a instanceof Array) {
selection = a;
} else {
print("The argument for 'select' function must be an Array");
}
return this;
}
/**
// valid format for parameter a is Array
*/
this.from = function(a) {
if (a instanceof Array) {
from = a;
} else {
print("The argument for 'select' function must be an Array");
}
return this;
}
/**
// valid format for parameter a is
// [[[and1],[and2],...], [[or1],[or2],...]]
// each criteria is in the following format:
// ["index", "compare method","value"]
// index is the zero based number of the column index of from array
// compare methods maybe one of the following:
// "eq", "gt", "lt", "gteq", "lteq"....
*/
this.where = function(a) {
if (a instanceof Array) {
criteria = a;
} else {
print("The argument for 'select' function must be an Array");
}
return this;
}
/**
// valid format for parameter a is
// ["index","sort method"]
// index is the zero based number of the column index of the from array which the sort action depends on
// sort method may be one of the following:
// "desc", "asc"
*/
this.orderby = function(a) {
if (a instanceof Array) {
order = a;
} else {
print("The argument for 'select' function must be an Array");
}
return this;
}
/**
// valid format for paramater a is
// ["start", "limit"]
// where start is the zero based index of the from array the result array start
// and the limit is the length of the result array
*/
this.limit = function(a) {
if (a instanceof Array) {
limit = a;
} else {
print("The argument for 'select' function must be an Array");
}
return this;
}
function comp(a,b) {
var col = 0;
for(var i=0; i<selection.length; i++) {
if(selection[i] == order[0]) col = i;
}
if(!isNaN(a[col]) || !isNaN(b[col])) {
return (order[1]=="asc")? a[col]-b[col]:0-a[col]+b[col];
}else{
var factor = 10;
var tmp1 = a[col].toString();
var tmp2 = b[col].toString();
var r1 = 0;
var r2 = 0;
var n1 = (tmp1.length>factor)? factor:tmp1.length;
var n2 = (tmp2.length>factor)? factor:tmp2.length;
for(var m=0; m<n1; m++) {
r1 = r1*32 + tmp1.charCodeAt(m);
}
for(var m=0; m<n2; m++) {
r2 = r2*32 + tmp2.charCodeAt(m);
}
return (order[1]=="asc")? r1-r2:0-r1+r2;
}
}
/**
// the final treatment function
// the flow is as the following:
// 1. prepare to treat each item of the from array
// 2. if no criteria, then put the "selection" fields into ret array
// 3. if there're criterias, then do the following treatment:
// 3.1. sum up the "AND" criteria and the result in selornot1
// 3.2. sum up the "OR" criteria and the result in selornot2
// 3.3. determin the result by combine the two result using "OR" logic
// 4. sort the ret array according to the "order" condition
// 5. return the ret array as result
*/
this.exec = function() {
result = [];
if(!selection.length>0) {
return [];
}
if(!from.length>0) {
return [];
}
var ret = [];
// step 1.
for(var i=0; i<from.length; i++) {
// step 2.
if(criteria.length==0) {
var tmp = [];
if(selection.length==1 || selection[0] == "*") {
tmp = from[i];
} else {
for(var j in selection) {
tmp.push(from[i][selection[j]]);
}
}
ret.push(tmp);
// step 3.
} else {
// if there're existing criterias...
for(var i=0; i<from.length; i++) {
//tranversing all AND criteria to determin which row to add to the result set
//to speed up the query, any "FALSE" condition will force the loop to stop and give the result to "FALSE"
var selornot1 = false;
// 3.1
if(criteria.length > 0) {
for(var m=0; m<criteria[0].length; m++) {
if(cm[criteria[0][m][1]]!==undefined) {
selornot1 = cm[criteria[0][m][1]](from[i][criteria[0][m][0]], criteria[0][m][2]);
if(!selornot1) break;
}
}
}
//tranversing all AND criteria to determin which row to add to the result set
//to speed up the query, any "TRUE" condition will force the loop to stop and give the result to "TRUE"
var selornot2 = false;
// 3.2
if(criteria.length > 1) {
for(var m=0; m<criteria[1].length; m++){
if(cm[criteria[1][m][1]]!==undefined) {
selornot2 = cm[criteria[1][m][1]](from[i][criteria[1][m][0]], criteria[1][m][2]);
if(selornot2) break;
}
}
}
// 3.3
if(selornot1 || selornot2) {
var tmp = [];
if(selection.length==1 || selection[0] == "*") {
tmp = from[i];
} else {
for(var j in selection) {
tmp.push(from[i][selection[j]]);
}
}
ret.push(tmp);
}
}
}
}
// step 4.
if(order.length > 0) {
ret.sort(comp);
}
// step 5.
if(limit.length>0) {
result = ret.slice(limit[0],limit[0]+limit[1]);
return ret.slice(limit[0],limit[0]+limit[1]);
} else {
result = ret;
return ret;
}
}
this.result = function() {
return result;
}
this.count = function() {
return result.length;
}
this.test = function() {
print(selection);
print(from);
print(criteria);
print(order);
print(limit);
}
}
var cm = {
"eq": function(a,b) {
if(a==b) return true;
return false;
},
"gt": function(a,b) {
if(a>b) return true;
return false;
},
"lt": function(a,b) {
if(a<b) return true;
return false;
},
"gteq": function(a,b) {
if(a>=b) return true;
return false;
},
"lteq": function(a,b) {
if(a<=b) return true;
return false;
}
};
getquery = function() {
return new query(cm);
}
})();
}catch(e){print(e);}
try{
(function(){
var b = [];
for (var i=0; i<10000; i++) {
var j=10000+i;
var tmp = [];
tmp.push(i);
tmp.push(i+1);
tmp.push(i+2);
tmp.push(String.fromCharCode(j,j+1,j+2));
b.push(tmp);
}
function test002() {
var a = getquery();
a.select(['*']).from(b).orderby([3,"asc"]);
var t1 = new Date().getTime();
var c = a.exec();
print("asc "+a.count()+" rows: "+(new Date().getTime() - t1)+"ms\n");
a.orderby([3,"desc"]);
var t2 = new Date().getTime();
c = a.exec();
print("desc "+a.count()+" rows: "+(new Date().getTime() - t2)+"ms\n");
a.orderby([]);
var t3 = new Date().getTime();
c = a.exec();
print("no sort "+a.count()+" rows: "+(new Date().getTime() - t3)+"ms\n");
}
test002();
})();
}catch(e){print(e);}
接下來用三支程式來做測試。js001.exe是我練習整合SpiderMonkey時做的，使用動態連結方式呼叫在js32.dll等裡面的函數來執行javascript（這些dll是我直接從Firefox3目錄裡面拷貝過來的）。jsshell.exe是從JS 1.7原始碼編譯的。shell.exe則是V8提供的sample，在編譯時下sample=shell參數就可以編譯出來（靜態編譯）。執行程式以後，再利用他提供的load函數來載入測試程式。以下是簡單的測試結果畫面：
首先是jsshell.exe(js 1.7, firefox2)：
其次是js001.exe(js 1.8, firefox3)：
最後是shell.exe(V8, google chrome)：
照測試結果，一般javascript速度是V8(Chrome) > JS 1.8(Firefox3) > JS 1.7(Firefox2)，但是陣列排序速度是JS 1.8(Firefox3) > V8(Chrome) > JS 1.7(Firefox2)。因為Array.sort會呼叫我自己寫的排序函數，所以強烈懷疑這個結果是因為JS 1.8的context switching速度比較快的關係。
有空時把V8整合到程式裡面以後，再做一次測試吧。
阿，文貼上來才發現，其實shell這一支只要傳檔名當做參數就可以了，我進去shell再用load跑有一點多此一舉。但是速度差不多。
剛剛發現為什麼陣列排序速度會比較慢了。我剛剛在V8的Issue List上看到：Issue 5: Poor Performance in Benchmark，進去V8的src目錄下，會看到array.js，打開看看，嗯......看起來是真的。所以原因就是：在V8中，陣列是用Javascript來實作的喔！！！（其實不只啦，可以看到其他的js檔案，所以像Math也是...其他還沒看。）JS 理所當然是用C，編譯過後比較快是理所當然。V8也很厲害，他可以把javascript編譯到速度那麼快。JS 1.7的陣列當然還是用C實作的，但是速度比javascript編譯的還差一截呢。