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;
}
}
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.