Recursion is an operation that a lot of developers are trying to avoid since it is very dangerous, and can break the execution of applications in a fraction of a bug, but it is needed in some scenarios (e.g tree iteration). This post is for technical readers who want to learn how to use recursion efficiently using Microtasks. I assume that you're already familiar with JavaScript event loop mechanism
So, my story is not too long and started on the last weekend when I needed to write code to traverses a tree object.
I needed to create a code with a recursive logic, so I needed to split my code to avoid stack overflows (RangeError exceptions) since the stack is limited to maximum stack frames.
You can check your browser stack limitation here
Naturally, I knew that I need to "break" the iteration using timing API (setTimeout/setInterval) and I started with a naive approach that is similar to this structure:
function run() {
const max = 50000;
let count = 0;
const start = performance.now();
(function run() {
if (count < max) {
count++;
if (count % 100 === 0) {
setTimeout(run, 0);
} else {
run();
}
} else {
console.log(`Done: ${performance.now() - start}`);
}
})();
}
When I checked the execution time of this given code I wasn't too happy ( ~2500ms ) and I wanted to get better results.
I was thinking about a better approach to my problem, I came up with a new pattern. I replaced the usage of Timing API with microtasks.
function run() {
const max = 50000;
let count = 0;
const start = performance.now();
return new Promise((resolve) => {
(function _run() {
if (count < max) {
count++;
if (count % 100 === 0) {
queueMicrotask(_run);
} else {
_run();
}
} else {
console.log(`Done: ${performance.now() - start}`);
resolve(performance.now() - start);
}
})();
});
}
The execution time of this pattern was 675.6 times faster! ( 3.7ms)
Microtask usage approach is working better rin such scenarios for two main reasons:
-
Timing API is not deterministic
- browsers are using throttling on repetitive timing API calls (official minimal timeout time is 4ms )
- Timing API:
- Micro task examples (no throttling)
- browsers are using throttling on repetitive timing API calls (official minimal timeout time is 4ms )
Micro tasks execution vs tasks execution
According to the processing model algorithm, the micro-tasks execution algorithm is fast and efficient. All it does is to execute all the micro-tasks once the stack is empty (no queue management).
conclusion
Javascript is not a language for heavy computations or recursions logic, but if you need to execute recursive execution as fast as you can,
without stack size limitation, using micro-tasks might help you.
Top comments (0)