Tinkering with code and algorithms for fun
Public
Edited
Jan 9
benchmarkScheduler = {
const BATCH_DURATION = 1000 / 60; // 60 FPS
let timeOfLastYield = performance.now();
function shouldYield() {
const now = performance.now();
if (now - timeOfLastYield > (document.hidden ? 500 : BATCH_DURATION)) {
timeOfLastYield = now;
return true;
}
return false;
}
const makeArr = length => {
const arr = [0];
for (let i = 1; i < length; i++) arr[i] = 0;
return arr;
};
let length = 1 << 10;
let items = makeArr(length);
let i = 0;
const process = _ => items[i++] = i;
async function run() {
for (const item of items) {
if (shouldYield()) {
if (document.hidden) {
await new Promise(resolve => setTimeout(resolve, 1));
timeOfLastYield = performance.now();
} else {
await Promise.race([
new Promise(resolve => setTimeout(resolve, 100)),
new Promise(requestAnimationFrame)
]);
timeOfLastYield = performance.now();
await scheduler.yield();
}
}
process(item);
}
}
let time = 0;
do {
length = length << 1;
items = makeArr(length);
i = 0;
const t0 = performance.now();
await run();
time = performance.now() - t0;
} while (time < 200 && length < (1 << 24));
time = 0;
for (let j = 0; j < 10; j++) {
i = 0;
const t0 = performance.now();
await run();
time += performance.now() - t0;
}
time /= 10;
return {arr: items, time};
}
// Based on Glenn Maynar's solution discussed here:
// https://www.w3.org/Bugs/Public/show_bug.cgi?id=15007#c18
setZeroTimeout = {
const taskChannel = new MessageChannel(), taskQueue = [];
taskChannel.port1.onmessage = () => {
const [task, args] = taskQueue.shift();
task.apply(task, args);
};
// Note that one possible advantage that setZeroTimeout has
// over requestAnimationFrame is that one can pass it
// parameters like setTimeout. We'll make use of that later.
const setZeroTimeout = (task, ...args) => {
taskQueue.push([task, args]);
taskChannel.port2.postMessage(null);
};
// Let's try to minimize the odds of `setZeroTimeout` being
// JIT-optimized halfway through a benchmark by giving
// it a little warm-up loop.
const warmup = new Promise(resolve => {
const loop = (i) => {
if (i++ < 100000) setZeroTimeout(loop, i);
else resolve(setZeroTimeout);
};
setZeroTimeout(loop, 0);
});
return warmup;
}
function asyncForEachV000(arr, callback){
return new Promise(resolve => {
const t0 = performance.now();
let i = 0, t = t0;
const loop = () => {
callback(arr[i], i, arr);
i++
if (i < arr.length) setZeroTimeout(loop);
else {
const time = performance.now() - t0;
resolve({
arr,
time,
// dummy stats for now that will matter in later versions
batches: arr.length,
samples: arr.length
});
}
};
loop();
});
}
function asyncForEachV001(arr, callback, batchDuration){
return new Promise(resolve => {
const t0 = performance.now();
let i = 0, batches = 1, t = t0;
const loop = () => {
let tnext = t;
const batchEnd = t + batchDuration;
while(i < arr.length && (tnext = performance.now()) < batchEnd) {
callback(arr[i], i, arr);
i++;
}
if (i < arr.length) {
t = tnext;
batches++;
setZeroTimeout(loop);
} else {
const time = performance.now() - t0;
resolve({
arr,
time,
batches,
samples: arr.length
});
}
};
loop();
});
}
function asyncForEachV002(arr, callback, batchDuration){
return new Promise(resolve => {
const t0 = performance.now();
let i = 0, batches = 1, t = t0, samples = 0;
const loop = () => {
let tnext = t;
const batchEnd = t + batchDuration;
while(i < arr.length) {
callback(arr[i], i, arr);
// only check every 128 iterations. This is just a test,
// we'll make all of this auto-adjust later on.
if (!(++i&0x7f)){
samples++;
if ((tnext = performance.now()) > batchEnd) break;
}
}
if (i < arr.length) {
batches++;
t = tnext;
setZeroTimeout(loop);
} else {
const time = performance.now() - t0;
resolve({
arr,
time,
batches,
samples
});
}
};
loop();
});
}
function asyncForEachV003(arr, callback, batchDuration){
return new Promise(resolve => {
const t0 = performance.now();
let i = 0, batches = 1, itersPerCheck = 128, t = t0, samples = 0;
const loop = () => {
let tnext = t, iCheck = i + itersPerCheck;
const i0 = i, batchEnd = t + batchDuration;
while(i < arr.length) {
callback(arr[i], i, arr);
if (++i > iCheck) {
samples++;
if ((tnext = performance.now()) > batchEnd) break;
iCheck += itersPerCheck;
}
}
if (i < arr.length) {
batches++;
// i - i0 is the number of iterations in this batch
// by setting itersPerCheck to 1/1024th of that, we
// are essentially assuming iterations/batch won't
// slow down by more than 1000x on the next batch.
// If the iterations/batch value remains roughly the same,
// then we should hit our target batch duration with
// an error margin of around 0.01%
itersPerCheck = (i - i0 > 0xFFFFFFFF ? 0xFFFFFFFF : (i - i0)) >>> 10;
t = tnext;
setZeroTimeout(loop);
} else {
const time = performance.now() - t0;
resolve({
arr,
time,
batches,
samples
});
}
}
loop();
});
}
asyncForEachV004 = {
// This is admittedly quite awkward to write,
// and having this many parameters would be
// an obvious code smell in any other context.
function loop(t, itersPerCheck, i, batches, samples, t0, arr, callback, batchDuration, resolve) {
let tnext = t, iCheck = i + itersPerCheck;
const i0 = i, batchEnd = t + batchDuration;
while(i < arr.length) {
callback(arr[i], i, arr);
if (++i > iCheck) {
samples++;
if ((tnext = performance.now()) > batchEnd) break;
iCheck += itersPerCheck;
}
}
if (i < arr.length) {
setZeroTimeout(loop, tnext, ((i0 - i) > 0xFFFFFFFF ? 0xFFFFFFFF : (i0 - i)) >>> 10, i, batches + 1, samples, t0, arr, callback, batchDuration, resolve);
} else {
const time = performance.now() - t0;
resolve({
arr,
time,
batches,
samples
});
}
}
return function asyncForEachV004(arr, callback, batchDuration){
const t0 = performance.now();
return new Promise(resolve => loop(t0, 128, 0, 1, 0, t0, arr, callback, batchDuration, resolve));
};
}
asyncForEachV005 = {
// Almost the same as v004, but we also explicitly
// assign all parameters to local constants and variables.
// Yes this is getting extremely gnarly.
function loop(t, itersPerCheck, i, batches, samples, t0, arr, callback, batchDuration, resolve) {
// v_l = "v locally assigned"
const callback_l = callback,
arr_l = arr,
batchEnd = t + batchDuration,
itersPerCheck_l = itersPerCheck,
i0 = i;
let samples_l = samples,
tnext = t,
i_l = i,
iCheck = i + itersPerCheck;
while(i_l < arr_l.length) {
callback_l(arr_l[i_l], i_l, arr_l);
if (++i_l > iCheck) {
samples_l++;
if ((tnext = performance.now()) > batchEnd) break;
iCheck += itersPerCheck
}
}
if (i_l < arr_l.length) {
setZeroTimeout(loop, tnext, ((i0 - i_l) > 0xFFFFFFFF ? 0xFFFFFFFF : (i0 - i_l)) >>> 10, i_l, batches + 1, samples_l, t0, arr_l, callback_l, batchDuration, resolve);
} else {
const time = performance.now() - t0;
resolve({
arr,
time,
batches,
samples
});
}
}
return function asyncForEachV005(arr, callback, batchDuration){
const t0 = performance.now();
return new Promise(resolve => loop(t0, 128, 0, 1, 0, t0, arr, callback, batchDuration, resolve));
};
}
function asyncForEachV006(arr, callback, batchDuration){
return new Promise(resolve => {
const t0 = performance.now();
// v_c = "v closed over"
// v_l = "v locally assigned"
let i_c = 0, batches_c = 1, itersPerCheck_c = 128, t_c = t0, samples_c = 0;
const loop = () => {
let tnext = t_c,
i_l = i_c,
i0 = i_c,
iCheck = i_c + itersPerCheck_c,
samples_l = samples_c;
const batchEnd = t_c + batchDuration,
arr_l = arr,
callback_l = callback,
itersPerCheck_l = itersPerCheck_c;
while(i_l < arr_l.length) {
callback_l(arr_l[i_l], i_l, arr_l);
if (++i_l > iCheck) {
samples_l++;
if ((tnext = performance.now()) > batchEnd) break;
iCheck += itersPerCheck_l;
}
}
if (i_l < arr_l.length) {
batches_c++;
itersPerCheck_c = (i_l - i0 > 0xFFFFFFFF ? 0xFFFFFFFF : (i_l - i0)) >>> 10;
i_c = i_l;
samples_c = samples_l;
t_c = tnext;
setZeroTimeout(loop);
} else resolve({
arr,
time: performance.now() - t0,
batches: batches_c,
samples: samples_l
});
};
loop();
});
}
function asyncForEachV007(arr, callback, batchDuration, finishOnHide = true){
return new Promise(resolve => {
const t0 = performance.now();
// v_c = "v closed over"
// v_l = "v locally assigned"
let i_c = 0, batches_c = 1, itersPerCheck_c = 128, t_c = t0, samples_c = 0;
const loop = () => {
let tnext = t_c,
i_l = i_c,
i0 = i_c,
iCheck = i_c + itersPerCheck_c,
samples_l = samples_c;
const batchEnd = t_c + batchDuration,
arr_l = arr,
callback_l = callback,
itersPerCheck_l = itersPerCheck_c;
while(i_l < arr_l.length) {
callback_l(arr_l[i_l], i_l, arr_l);
if (++i_l > iCheck) {
samples_l++;
if ((tnext = performance.now()) > batchEnd) break;
iCheck += itersPerCheck_l;
}
}
if (finishOnHide && document.hidden) {
while(i_l < arr_l.length) {
callback_l(arr_l[i_l], i_l, arr_l);
i_l++;
}
}
if (i_l < arr_l.length) {
++batches_c;
itersPerCheck_c = (i_l - i0 > 0xFFFFFFFF ? 0xFFFFFFFF : (i_l - i0)) >>> 10;
i_c = i_l;
samples_c = samples_l;
t_c = tnext;
setZeroTimeout(loop);
} else resolve({
arr,
time: performance.now() - t0,
batches: batches_c,
samples: samples_l
});
};
loop();
});
}
function asyncForEach(arr, callback, batchDuration = 16, initialIters = 128, finishOnHide = true){
return new Promise(resolve => {
let i_c = 0, t_c = performance.now(), itersPerCheck_c = initialIters;
const loop = () => {
let tnext = t_c,
i_l = i_c,
i0 = i_c,
iCheck = i_c + itersPerCheck_c;
const batchEnd = t_c + batchDuration,
arr_l = arr,
callback_l = callback,
itersPerCheck_l = itersPerCheck_c;
while(i_l < arr_l.length) {
callback_l(arr_l[i_l], i_l, arr_l);
if (++i_l > iCheck) {
if ((tnext = performance.now()) > batchEnd) break;
iCheck += itersPerCheck_l;
}
}
if (finishOnHide && document.hidden) {
while(i_l < arr_l.length) {
callback_l(arr_l[i_l], i_l, arr_l);
i_l++;
}
}
if (i_l < arr_l.length) {
i_c = i_l;
t_c = tnext;
itersPerCheck_c = (i_l - i0 > 0xFFFFFFFF ? 0xFFFFFFFF : (i_l - i0)) >>> 10;
setZeroTimeout(loop);
} else resolve();
};
loop();
});
}
benchmarks = {
rerun;
const targetFrameRate = 1000 / 60;
const makeArr = length => {
const arr = [0];
for (let i = 0; i < length; i++) arr[i] = i;
return arr;
};
async function benchmark(foreach) {
let callback = (_, i, a) => a[i] = i;
let result;
let input;
let length = 1 << 9;
let time = 0;
while (time < 200 && length < (1 << 24)) {
length = length << 1;
input = makeArr(length);
const t0 = performance.now();
result = await foreach(input, callback, targetFrameRate);
time = performance.now() - t0;
}
input = makeArr(length);
if (result) {
result = await foreach(input, callback, targetFrameRate);
const keys = Object.keys(result);
for (let i = 0; i < 9; i++) {
const nresult = await foreach(input, callback, targetFrameRate);
for (const key of keys) {
if (Array.isArray(result[key])) continue;
else result[key] += nresult[key];
}
}
for (const key of keys) {
if (Array.isArray(result[key])) continue;
else result[key] /= 10;
}
return result;
} else {
const runs = [];
time = performance.now();
for (let i = 0; i < 10; i++){
const t0 = performance.now();
await foreach(input, callback, targetFrameRate);
runs[i] = performance.now() - t0;
}
return {length, runs, time: (performance.now() - time) / 10, arr: input, batches: NaN, samples: NaN};
}
}
const fns = [asyncForEachV000, asyncForEachV001, asyncForEachV002, asyncForEachV003, asyncForEachV004, asyncForEachV005, asyncForEachV006, asyncForEachV007, asyncForEach];
const results = {};
fns.map(fn => results[fn.name] = {started: false});
for (const fn of fns) {
results[fn.name].started = true;
yield results;
results[fn.name] = await benchmark(fn);
yield results;
}
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
