Skip to content

Instantly share code, notes, and snippets.

@milahu
Forked from jridgewell/index.html
Last active Apr 6, 2021
Embed
What would you like to do?
trace sourcemap: binary search vs cache array / object / map / flat map (https://jsbench.github.io/#cf2b815df12f6fc912afd58aba934d84) #jsbench #jsperf
<!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>
"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