Skip to content

Instantly share code, notes, and snippets.

@normanrz

normanrz/bench.html

Last active July 15, 2022 06:44
Show Gist options
  • Save normanrz/235a5d92fe92112067d1a9494a915e8f to your computer and use it in GitHub Desktop.
Save normanrz/235a5d92fe92112067d1a9494a915e8f to your computer and use it in GitHub Desktop.
Download ZIP
ColMajorToRowMajor microbenchmark
Raw
bench.html
<html>
<body>
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/1.0.0/benchmark.min.js"></script>
<ul id='cycleResults'>
</ul>
<div id="result">
</div>
<br>
<button id="btn">
Run Tests
</button>
<script>
function colMajorToRowMajorConverter2D(src, out, shape) {
let idx = 0;
const shape0 = shape[0];
const shape1 = shape[1];
const stride0 = shape1;
for (let i1 = 0; i1 < shape1; i1++) {
for (let i0 = 0; i0 < shape0; i0++) {
out[i0 * stride0 + i1] = src[idx++];
}
}
}
function colMajorToRowMajorConverter3D(src, out, shape) {
let idx = 0;
const shape0 = shape[0];
const shape1 = shape[1];
const shape2 = shape[2];
const stride0 = shape2 * shape1;
const stride1 = shape2;
for (let i2 = 0; i2 < shape2; i2++) {
for (let i1 = 0; i1 < shape1; i1++) {
for (let i0 = 0; i0 < shape0; i0++) {
out[i0 * stride0 + i1 * stride1 + i2] = src[idx++];
}
}
}
}
function colMajorToRowMajorConverter4D(src, out, shape) {
let idx = 0;
const shape0 = shape[0];
const shape1 = shape[1];
const shape2 = shape[2];
const shape3 = shape[3];
const stride0 = shape3 * shape2 * shape1;
const stride1 = shape3 * shape2;
const stride2 = shape3;
for (let i3 = 0; i3 < shape3; i3++) {
for (let i2 = 0; i2 < shape2; i2++) {
for (let i1 = 0; i1 < shape1; i1++) {
for (let i0 = 0; i0 < shape0; i0++) {
out[i0 * stride0 + i1 * stride1 + i2 * stride2 + i3] = src[idx++];
}
}
}
}
}
function colMajorToRowMajorConverterGeneric(src, out, shape) {
const nDims = shape.length;
const size = shape.reduce((r, a) => r * a);
const rowMajorStrides = shape.map((_, i) =>
i + 1 === nDims ? 1 : shape.slice(i + 1).reduce((r, a) => r * a, 1)
);
const index = Array(nDims).fill(0);
for (let colMajorIdx = 0; colMajorIdx < size; colMajorIdx++) {
let rowMajorIdx = 0;
for (let dim = 0; dim < nDims; dim++) {
rowMajorIdx += index[dim] * rowMajorStrides[dim];
}
out[rowMajorIdx] = src[colMajorIdx];
index[0] += 1;
for (let dim = 0; dim < nDims; dim++) {
if (index[dim] === shape[dim]) {
if (dim + 1 === nDims) {
return;
}
index[dim] = 0;
index[dim + 1] += 1;
}
}
}
}
function codegen(nDims) {
const code = ["let idx = 0;"];
for (let dim = 0; dim < nDims; dim++) {
// Cache shape values in variables
code.push(`const shape${dim} = shape[${dim}];`);
}
for (let dim = 0; dim < nDims - 1; dim++) {
// Calculate strides for output buffer
code.push(
`const stride${dim} = ${Array.from(
{ length: nDims - 1 - dim },
(_, dim2) => `shape${nDims - 1 - dim2}`
).join(" * ")};`
);
}
for (let dim = nDims - 1; dim >= 0; dim--) {
// Iterating in the original order (ie. column major) is beneficial for memory pre-fetching
code.push(`for (let i${dim} = 0; i${dim} < shape${dim}; i${dim}++) {`);
}
code.push(
`out[${[
...Array.from({ length: nDims - 1 }, (_, dim) => `i${dim} * stride${dim}`),
`i${nDims - 1}`,
].join(" + ")}] = src[idx++];`
);
for (let dim = 0; dim < nDims; dim++) {
code.push("}");
}
return new Function("src", "out", "shape", code.join("\n"));
};
const colMajorToRowMajorConverter2DGen = codegen(2);
const colMajorToRowMajorConverter3DGen = codegen(3);
const colMajorToRowMajorConverter4DGen = codegen(4);
const colMajorToRowMajorConverter5DGen = codegen(5);
const colMajorToRowMajorConverter6DGen = codegen(6);
fetch("https://data-humerus.webknossos.org/data/zarr/scalable_minds/l4dense_motta_et_al_demo/color/1/0.4.4.4")
.then(res => res.arrayBuffer())
.then(buf => { window.src = new Uint8Array(buf); window.out = new Uint8Array(src.length); });
var cycleResults = document.getElementById('cycleResults');
var result = document.getElementById('result');
var btn = document.getElementById('btn');
// BENCHMARK ====================
btn.onclick = function runTests() {
btn.setAttribute('disable', true);
cycleResults.innerHTML = '';
result.textContent = 'Tests running...';
var suite = new Benchmark.Suite;
// add tests
suite
.add('specialized 2D', () => { colMajorToRowMajorConverter2D(window.src, window.out, [32 * 32, 32]); })
.add('specialized 3D', () => { colMajorToRowMajorConverter3D(window.src, window.out, [32, 32, 32]); })
.add('specialized 4D', () => { colMajorToRowMajorConverter4D(window.src, window.out, [1, 32, 32, 32]); })
.add('generic 2D', () => { colMajorToRowMajorConverterGeneric(window.src, window.out, [32 * 32, 32]); })
.add('generic 3D', () => { colMajorToRowMajorConverterGeneric(window.src, window.out, [32, 32, 32]); })
.add('generic 4D', () => { colMajorToRowMajorConverterGeneric(window.src, window.out, [1, 32, 32, 32]); })
.add('generic 5D', () => { colMajorToRowMajorConverterGeneric(window.src, window.out, [1, 4, 8, 32, 32]); })
.add('generic 6D', () => { colMajorToRowMajorConverterGeneric(window.src, window.out, [1, 4, 8, 4, 8, 32]); })
.add('generated 2D', () => { colMajorToRowMajorConverter2DGen(window.src, window.out, [32 * 32, 32]); })
.add('generated 3D', () => { colMajorToRowMajorConverter3DGen(window.src, window.out, [32, 32, 32]); })
.add('generated 4D', () => { colMajorToRowMajorConverter4DGen(window.src, window.out, [1, 32, 32, 32]); })
.add('generated 5D', () => { colMajorToRowMajorConverter5DGen(window.src, window.out, [1, 4, 8, 32, 32]); })
.add('generated 6D', () => { colMajorToRowMajorConverter6DGen(window.src, window.out, [1, 4, 8, 4, 8, 32]); })
// add listeners
.on('cycle', function(event) {
var result = document.createElement('li');
result.textContent = String(event.target);
document.getElementById('cycleResults')
.appendChild(result);
})
.on('complete', function() {
result.textContent = 'Fastest is ' + this.filter('fastest').pluck('name');
btn.setAttribute('disable', false);
})
// run async
.run({
'async': true
});
};
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment