-
-
Save milahu/cf2b815df12f6fc912afd58aba934d84 to your computer and use it in GitHub Desktop.
trace sourcemap: binary search vs cache array / object / map / flat map (https://jsbench.github.io/#cf2b815df12f6fc912afd58aba934d84) #jsbench #jsperf
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<!DOCTYPE html> | |
<html> | |
<head> | |
<meta charset="utf-8"/> | |
<title>trace sourcemap: binary search vs cache array / object / map / flat map</title> | |
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/1.0.0/benchmark.min.js"></script> | |
<script src="./suite.js"></script> | |
</head> | |
<body> | |
<h1>Open the console to view the results</h1> | |
<h2><code>cmd + alt + j</code> or <code>ctrl + alt + j</code></h2> | |
</body> | |
</html> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
"use strict"; | |
(function (factory) { | |
if (typeof Benchmark !== "undefined") { | |
factory(Benchmark); | |
} else { | |
factory(require("benchmark")); | |
} | |
})(function (Benchmark) { | |
var suite = new Benchmark.Suite; | |
Benchmark.prototype.setup = function () { | |
const mappings = []; | |
for (let L = 0; L < 100; L++) { | |
const line = []; | |
for (let S = 0; S < 1000; S++) { | |
const C = S*10; // sparse columns (medium resolution sourcemap) | |
line.push([C, 0, L+10, S]); // output_column, source, line, column | |
} | |
mappings.push(line); | |
} | |
function binarySearch(haystack, needle, comparator) { | |
let low = 0; | |
let high = haystack.length - 1; | |
while (low <= high) { | |
const mid = low + ((high - low) >> 1); | |
const cmp = comparator(haystack[mid], needle); | |
if (cmp === 0) { | |
return mid; | |
} | |
if (cmp < 0) { | |
low = mid + 1; | |
} | |
else { | |
high = mid - 1; | |
} | |
} | |
return ~low; | |
} | |
function binarySearchBiased(haystack, needle, comparator, state) { | |
// find nearest low and high values = expand search range | |
let cmp = comparator(haystack[state.last], needle); | |
if (cmp == 0) return state.last; | |
function found(val) { state.last = val; return val } | |
let low, high; | |
const max_high = haystack.length - 1; | |
if (cmp > 0) { // item > needle | |
high = state.last; | |
// find nearest low value | |
for (let step = 0; ; step++) { | |
low = high - (1 << step); | |
if (low < 0) { low = 0; break } | |
let cmp = comparator(haystack[low], needle); | |
if (cmp == 0) return found(low); | |
if (cmp < 0) break; // item < needle | |
} | |
} | |
else { // item < needle | |
low = state.last; | |
// find nearest high value | |
for (let step = 0; ; step++) { | |
high = low + (1 << step); | |
if (high > max_high) { high = max_high; break } | |
let cmp = comparator(haystack[high], needle); | |
if (cmp == 0) return found(high); | |
if (cmp > 0) break; // item > needle | |
} | |
} | |
// binary search = reduce search range | |
while (low <= high) { | |
const mid = low + ((high - low) >> 1); | |
const cmp = comparator(haystack[mid], needle); | |
if (cmp == 0) return found(mid); | |
if (cmp < 0) { low = mid + 1 } | |
else { high = mid - 1 } | |
} | |
return -1; // not found | |
} | |
function sortSegments(segments) { | |
segments.sort(segmentComparator); | |
} | |
function compareSegmentColumn(haystack_item, needle) { | |
return haystack_item[0] - needle; | |
} | |
}; | |
suite.add("biased binary search", function () { | |
// biased binary search | |
// optimized for 'sequential search' | |
// = last result is similar to current result | |
search_state = { last: 0 }; | |
for (let i = 0; i < 25; i++) { | |
const line = mappings[i]; | |
for (let S = 0; S < 250; S++) { | |
const C = S*10; | |
binarySearchBiased(line, C, compareSegmentColumn, search_state); | |
} | |
} | |
}); | |
suite.add("binary search", function () { | |
// binary search | |
for (let i = 0; i < 25; i++) { | |
const line = mappings[i]; | |
for (let S = 0; S < 250; S++) { | |
const C = S*10; | |
binarySearch(line, C, compareSegmentColumn) | |
} | |
} | |
}); | |
suite.add("cache map", function () { | |
// cache map | |
// one object per line is very slow, see https://media.tojicode.com/sfjs-vectors/#9 | |
const cache_map = []; | |
for (let L = 0; L < mappings.length; L++) { | |
const line = mappings[L]; | |
cache_map.push(new Map()); | |
const cache_line = cache_map[cache_map.length - 1]; | |
for (let S = 0; S < line.length; S++) { | |
const seg = line[S]; | |
cache_line.set(seg[0], seg); // pass array by reference | |
} | |
} | |
for (let i = 0; i < 25; i++) { | |
const line = cache_map[i]; | |
for (let S = 0; S < 250; S++) { | |
const C = S*10; | |
line.get(C); | |
} | |
} | |
}); | |
suite.add("cache typed arrays", function () { | |
// cache typed arrays | |
// TODO manually resize array on demand | |
// one object per line is very slow, see https://media.tojicode.com/sfjs-vectors/#9 | |
const cache_buffer_list = []; | |
const cache_array_list = []; | |
const val_empty = 4294967295; | |
const val_undef = 4294967294; | |
const arr_len = 10000; // columns per line (wild guess) | |
for (let L = 0; L < mappings.length; L++) { | |
const line = mappings[L]; | |
const buffer = new ArrayBuffer(4*4*arr_len); | |
// uint32 = 4 byte | |
// segment without output_column = 4 uint32 | |
// arr_len columns per line | |
const array = new Uint32Array(buffer); | |
cache_buffer_list.push(buffer); | |
cache_array_list.push(array); | |
// fill with empty values | |
for (let i = 0; i < arr_len; i += 4) | |
array[i] = val_empty; | |
const cache_line = array; | |
for (let S = 0; S < line.length; S++) { | |
const seg = line[S]; | |
// pass array by value - javascript has no pointers :( | |
const column = seg[0]; | |
const idx_base = column * 4; // 4 uint32 per segment | |
for (let s = 1; s <= 4; s++) { | |
cache_line[idx_base + s - 1] = | |
seg[s] == undefined ? val_undef : seg[s]; | |
if (seg[s] == undefined) break; // lazy: only set first value | |
} | |
} | |
} | |
for (let i = 0; i < 25; i++) { | |
const line = cache_array_list[i]; | |
for (let S = 0; S < 250; S++) { | |
const C = S*10; | |
line[C]; | |
} | |
} | |
}); | |
suite.add("cache object", function () { | |
// cache object | |
// one object per line is very slow, see https://media.tojicode.com/sfjs-vectors/#9 | |
const cache_object = []; | |
for (let L = 0; L < mappings.length; L++) { | |
const line = mappings[L]; | |
cache_object.push({}); | |
const cache_line = cache_object[cache_object.length - 1]; | |
for (let S = 0; S < line.length; S++) { | |
const seg = line[S]; | |
cache_line[seg[0]] = seg; // pass array by reference | |
} | |
} | |
for (let i = 0; i < 25; i++) { | |
const line = cache_object[i]; | |
for (let S = 0; S < 250; S++) { | |
const C = S*10; | |
line[C]; | |
} | |
} | |
}); | |
suite.add("cache array", function () { | |
// cache array | |
// one object per line is very slow, see https://media.tojicode.com/sfjs-vectors/#9 | |
const cache_array = []; | |
for (let L = 0; L < mappings.length; L++) { | |
const line = mappings[L]; | |
cache_array.push([]); | |
const cache_line = cache_array[cache_array.length - 1]; | |
for (let S = 0; S < line.length; S++) { | |
const seg = line[S]; | |
cache_line[seg[0]] = seg; // pass array by reference | |
} | |
} | |
for (let i = 0; i < 25; i++) { | |
const line = cache_array[i]; | |
for (let S = 0; S < 250; S++) { | |
const C = S*10; | |
line[C]; | |
} | |
} | |
}); | |
suite.add("cache array - map from column to segment-index", function () { | |
// cache array - map from column to segment-index | |
// = manual pass-by-reference | |
// one object per line is very slow, see https://media.tojicode.com/sfjs-vectors/#9 | |
const cache_array = []; | |
for (let L = 0; L < mappings.length; L++) { | |
const line = mappings[L]; | |
cache_array.push([]); | |
const cache_line = cache_array[cache_array.length - 1]; | |
for (let S = 0; S < line.length; S++) { | |
const seg = line[S]; | |
cache_line[seg[0]] = S; // store segment-index | |
} | |
} | |
for (let L = 0; L < 25; L++) { | |
const line = mappings[L]; | |
const cache_line = cache_array[L]; | |
for (let S = 0; S < 250; S++) { | |
const C = S*10; | |
line[cache_line[C]]; | |
} | |
} | |
}); | |
suite.add("flat cache map", function () { | |
// flat cache map | |
// one object per sourcemap = object reuse, see https://media.tojicode.com/sfjs-vectors/#9 | |
// -> nope. still much slower than binary search | |
const cache_flat_map = new Map(); | |
let num_lines = 0; | |
for (let L = 0; L < mappings.length; L++) { | |
const line = mappings[L]; | |
for (let S = 0; S < line.length; S++) { | |
const seg = line[S]; | |
const C = seg[0]; | |
cache_flat_map.set([L, C], seg); | |
} | |
num_lines += 1; | |
} | |
for (let L = 0; L < 25; L++) { | |
for (let S = 0; S < 250; S++) { | |
const C = S*10; | |
cache_flat_map.get([L, C]); | |
} | |
} | |
}); | |
suite.on("cycle", function (evt) { | |
console.log(" - " + evt.target); | |
}); | |
suite.on("complete", function (evt) { | |
console.log(new Array(30).join("-")); | |
var results = evt.currentTarget.sort(function (a, b) { | |
return b.hz - a.hz; | |
}); | |
results.forEach(function (item) { | |
console.log((idx + 1) + ". " + item); | |
}); | |
}); | |
console.log("trace sourcemap: binary search vs cache array / object / map / flat map"); | |
console.log(new Array(30).join("-")); | |
suite.run(); | |
}); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment