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):
v8 vs js17 vs js18

其次是js001.exe(js 1.8, firefox3):
v8 vs js17 vs js18

最後是shell.exe(V8, google chrome):
v8 vs js17 vs js18

照測試結果,一般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編譯的還差一截呢。