milahu/index.html

## index.html
<!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>

## suite.js
"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();
});
	<!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(44arr_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();
	});