quick sort with wasm

bench.js

// see http://indiegamr.com/generate-repeatable-random-numbers-in-js/
// the initial seed
Math.seed = 6;
 
// in order to work 'Math.seed' must NOT be undefined,
// so in any case, you HAVE to provide a Math.seed
Math.seededRandom = function(max, min) {
    max = max || 1;
    min = min || 0;
 
    Math.seed = (Math.seed * 9301 + 49297) % 233280;
    var rnd = Math.seed / 233280;
 
    return min + rnd * (max - min);
}

// see http://qiita.com/minodisk/items/94b6287468d0e165f6d9
var goodShuffle = function (arr) {
  var i, j, temp;
  arr = arr.slice();
  i = arr.length;
  if (i === 0) {
    return arr;
  }
  while (--i) {
    j = Math.floor(Math.seededRandom() * (i + 1));
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  return arr;
};

var source = new Uint32Array(new ArrayBuffer(256 * 64 * 1024)).map((x, i) => i);
var u32Array = goodShuffle(source);
var jsArray = Array.from(u32Array);

var bench = (label, fn) => {
    const t0 = performance.now();
    fn();
    const t1 = performance.now();
    console.log(label, t1 - t0, 'ms');
};

var test = (result) => {
    console.log(result.every((x, i) => x === source[i]) ? 'ok': 'ng');
};

bench('js array sort', () => {
    jsArray.sort((a, b) => a - b);
});
test(jsArray);

var u32Array1 = u32Array.slice();
bench('u32 array sort', () => {
    u32Array1.sort();
});
test(u32Array1);

var u32Array2 = u32Array.slice();
var wasmModule = Wasm.instantiateModule(new Uint8Array([0,97,115,109,11,0,0,0,4,116,121,112,101,18,3,64,1,1,1,1,64,2,1,1,0,64,3,1,1,1,1,1,8,102,117,110,99,116,105,111,110,5,4,0,1,2,1,6,109,101,109,111,114,121,5,128,2,128,2,1,6,101,120,112,111,114,116,27,4,0,4,108,111,97,100,1,5,115,116,111,114,101,2,4,109,101,100,51,3,5,113,115,111,114,116,4,99,111,100,101,137,2,4,11,0,20,0,16,2,74,42,2,0,9,1,11,0,20,0,16,2,74,20,1,51,2,0,62,0,20,0,20,1,79,3,1,20,1,20,2,79,3,20,1,9,1,15,20,2,20,0,79,3,20,0,9,1,15,20,2,9,1,15,15,20,2,20,1,79,3,20,1,9,1,15,20,0,20,2,79,3,20,0,9,1,15,20,2,9,1,175,1,1,4,1,20,0,20,1,79,3,1,20,0,21,2,20,1,21,3,20,0,22,1,0,20,1,22,1,0,20,0,20,1,64,16,1,75,22,1,0,22,3,2,21,4,2,2,20,2,22,1,0,20,4,79,3,1,20,2,16,1,64,21,2,6,0,2,15,4,6,0,2,15,15,2,20,4,20,3,22,1,0,79,3,1,20,3,16,1,65,21,3,6,0,2,15,4,6,0,2,15,15,20,2,20,3,86,3,6,0,2,15,20,2,22,1,0,21,5,20,2,20,3,22,1,0,22,2,1,20,3,20,5,22,2,1,20,2,16,1,64,21,2,20,3,16,1,65,21,3,6,0,0,15,20,0,20,2,16,1,65,22,2,3,20,3,16,1,64,20,1,22,2,3,15,15]), {});
bench('wasm sort', () => {
    var arr = new Uint32Array(wasmModule.exports.memory);
    arr.set(u32Array2, 0);
    wasmModule.exports.qsort(0, arr.length - 1);
    u32Array2.set(arr, 0);
});
test(u32Array2);

qsort.wast

(module
    (memory 256 256)
    (export "memory" memory)
    
    (func $load (param i32) (result i32)
        (return
            (i32.load
                (i32.shl (get_local 0) (i32.const 2))
            )
        )
    )
    (export "load" $load)
    
    (func $store (param i32 i32)
        (i32.store (i32.shl (get_local 0) (i32.const 2)) (get_local 1))
    )
    (export "store" $store)
        
    (func $med3 (param i32 i32 i32) (result i32)
        (if (i32.lt_s (get_local 0) (get_local 1))
            (block
                (if (i32.lt_s (get_local 1) (get_local 2))
                    (return (get_local 1))
                )
                (if (i32.lt_s (get_local 2) (get_local 0))
                    (return (get_local 0))
                )
                (return (get_local 2))
            )
        )
        (if (i32.lt_s (get_local 2) (get_local 1))
            (return (get_local 1))
        )
        (if (i32.lt_s (get_local 0) (get_local 2))
            (return (get_local 0))
        )
        (return (get_local 2))
    )
    (export "med3" $med3)
        
    (func $qsort (param $left i32) (param $right i32)
        (local $i i32)
        (local $j i32)
        (local $pivot i32)
        (local $tmp i32)        
        
        (if (i32.lt_s (get_local $left) (get_local $right))
            (block
                (set_local $i (get_local $left))
                (set_local $j (get_local $right))
                (set_local $pivot
                    (call $med3
                        (call $load (get_local $left))
                        (call $load (get_local $right))
                        (call $load
                            (i32.shr_u
                                (i32.add (get_local $left) (get_local $right))
                                (i32.const 1)
                            )
                        )
                    )
                )
                (loop $exit $cont
                    (loop $exit $cont
                        (if (i32.lt_s (call $load (get_local $i)) (get_local $pivot))
                            (block
                                (set_local $i (i32.add (get_local $i) (i32.const 1)))
                                (br $cont)
                            )
                            (br $exit)
                        )
                    )
                    (loop $exit $cont
                        (if (i32.lt_s (get_local $pivot) (call $load (get_local $j)))
                            (block
                                (set_local $j (i32.sub (get_local $j) (i32.const 1)))
                                (br $cont)
                            )
                            (br $exit)
                        )
                    )
                    (if (i32.ge_u (get_local $i) (get_local $j)) (br $exit))
                    (set_local $tmp (call $load (get_local $i)))
                    (call $store (get_local $i) (call $load (get_local $j)))
                    (call $store (get_local $j) (get_local $tmp))
                    (set_local $i (i32.add (get_local $i) (i32.const 1)))
                    (set_local $j (i32.sub (get_local $j) (i32.const 1)))
                    (br $cont)
                )
                (call $qsort (get_local $left) (i32.sub (get_local $i) (i32.const 1)))
                (call $qsort (i32.add (get_local $j) (i32.const 1)) (get_local $right))
            )
        )
    )
    (export "qsort" $qsort)
)

result.md

environment

• OS: OS X El Capitan 10.11.4
• CPU: 2.4CHz Intel Core i5
• Browser: Chrome 52.0.2738.0 canary (64-bit)

result

sort method	speed(ms)
js array sort	2278.6850000000013
u32 array sort	2728.555000000002
wasm sort	874.8450000000012