CODEWITHSUNDEEP
javascriptnode.js
garritfra
garritfra

Reputation: 578

Why is this wrapped function call faster than a regular function?

Executing this recursive fibonacci function takes around 9.5 seconds on my machine, using a traditional approach:

const fib = n => {
  if (n == 1) return 0;
  if (n == 2) return 1;
  return fib(n - 1) + fib(n - 2);
};

console.log(fib(45));

➜ time node index.js
701408733
node index.js  9,50s user 0,04s system 99% cpu 9,566 total

However, when I wrap the body of the function in another function that gets executed right away, execution drops to 7.5 seconds:

const fib = n => {
  return (() => {
    if (n == 1) return 0;
    if (n == 2) return 1;
    return fib(n - 1) + fib(n - 2);
  })();
};

console.log(fib(45));

➜ time node index.js
701408733
node index.js  7,58s user 0,25s system 99% cpu 7,852 total

This is a huge speedup (~30%!), but I cannot figure out why wrapping the function would make this difference.

Upvotes: 14

Views: 239

Answers (2)

GalAbra
GalAbra

Reputation: 5138

This is indeed a very strange behaviour.

After some digging, I see that it's mentioned in a few past questions (for example, this one) that JS performs worse with recursion, such as in fib1.

Now the question that rises is whether fib2 isn't a recursive function. I assume that because it creates a new anonymous function - rather than using the same memory reference to fib2 - it's practically "less recursive" and therefore performs better.

EDIT: After reading this question it looks like what's going on is some sort of Tail Call handling (fib2 uses tail recursion, as opposed to fib1, where each call is calculated before the result can be returned).

Another interesting observation is that - to a certain degree - the recursion does work better, but then it's getting exponentially slower.

function fib1(n) {
  if (n === 1) return 0;
  if (n === 2) return 1;
  return fib1(n - 1) + fib1(n - 2);
};

function fib2(n) {
  return (() => {
    if (n === 1) return 0;
    if (n === 2) return 1;
    return fib2(n - 1) + fib2(n - 2);
  })();
};

function calculateAverageTime(func, iterations = 5) {
  let sum = 0;

  [...Array(iterations)].forEach(() => {
    const start = new Date();
    func();
    const finish = new Date();
    sum += (finish - start);
  });

  return Math.round(sum / iterations);
}

function compare(i) {
  const fib1RunTime = calculateAverageTime(() => fib1(i));
  const fib2RunTime = calculateAverageTime(() => fib2(i));
  console.log(`Difference for fib(${i}) is ${(fib2RunTime - fib1RunTime)}ms`);
}

[10, 20, 30, 40].forEach(i => compare(i));

Upvotes: 5

Daniel
Daniel

Reputation: 1

return (() => {

I am not sure.. but probably this string wait for a response before the program control this line:

if (n == 1)

The program lodge a small portion of memory (stack) before the program starts to control if "n" is effectively "== 1" and put all the functions in that portion of memory.

Then start the function.

Upvotes: 0

Related Questions