Last active
April 6, 2023 21:57
-
-
Save vastus/8018bdd2448a17e17d4d98adfa26786c to your computer and use it in GitHub Desktop.
Imperative and declarative
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* Notes | |
* | |
* Make sure you know the size of your data and use proper functions or style | |
* to not introduce bottlenecks by mistake. | |
* | |
* If we get inlined functions to Node/JS, using declarative programs will be | |
* almost as fast as imperative ones by the magic of transducers. Transducers | |
* will do a single pass (reduce) on the input with the composition of the | |
* given transformation functions. | |
* | |
* As this simple example benchmark shows that the `imperative` and | |
* `singlePassInlinedReduce` are performing almost at the same rate. | |
* | |
* Also it's worth to mention that the single pass reduce version isn't too | |
* bad either; roughly ~6 times slower than the imperative one. | |
* | |
* Motivated by: https://jackmott.github.io/programming/2016/07/22/making-obvious-fast.html | |
* Thanks Otto :) | |
*/ | |
/* | |
* Helpers | |
*/ | |
function withTime(f, ...args) { | |
console.time(f.name); | |
const x = f(...args); | |
console.timeEnd(f.name); | |
return x; | |
} | |
// Note: eager. | |
function range(from, until) { | |
return Array | |
.from(Array(until - from).keys()) | |
.map(x => x + from); | |
} | |
function map(f, xs) { | |
const ys = []; | |
for (let i = 0; i < xs.length; i++) { | |
ys.push(f(xs[i])); | |
} | |
return ys; | |
} | |
function reduce(f, initial, xs) { | |
let acc = initial; | |
for (let i = 0; i < xs.length; i++) { | |
acc = f(acc, xs[i]); | |
} | |
return acc; | |
} | |
/* | |
* Implementations | |
*/ | |
function imperative(values) { | |
var sum = 0.0; | |
for (var i = 0; i < values.length;i++){ | |
var x = values[i]; | |
sum += x*x; | |
} | |
return sum; | |
} | |
function declarative(values) { | |
return values | |
.map(x => x * x) | |
.reduce((total, num) => total + num, 0); | |
} | |
function mydeclarative(values) { | |
return reduce((total, num) => total + num, 0, map(x => x * x, values)) | |
} | |
function twoPasses(values) { | |
const ys = []; | |
for (let i = 0; i < xs.length; i++) { | |
ys.push(xs[i] * xs[i]); | |
} | |
let acc = 0; | |
for (let i = 0; i < xs.length; i++) { | |
acc = acc + xs[i]; | |
} | |
return acc; | |
} | |
function singlePassNative(values) { | |
return values.reduce((acc, elem) => acc + elem * elem, 0); | |
} | |
function singlePassOwn(values) { | |
return reduce((acc, elem) => acc + elem * elem, 0, values); | |
} | |
function singlePassOwnInlinedReduce(values) { | |
const f = (acc, elem) => acc + elem * elem | |
let acc = 0; | |
for (let i = 0; i < values.length; i++) { | |
acc = f(acc, values[i]); | |
} | |
return acc; | |
} | |
/* | |
* Run 'em. | |
*/ | |
const xs = range(0, 1000000); | |
// call the functions a few times | |
// to make sure JIT kicks in | |
range(0, 4) | |
.forEach(() => { | |
[ | |
imperative, | |
declarative, | |
mydeclarative, | |
twoPasses, | |
singlePassNative, | |
singlePassOwn, | |
singlePassOwnInlinedReduce, | |
].map(f => withTime(f, xs)) | |
}); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Node 8.10 vs 10.x