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

Question

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.

also, it maybe worth using a fresh node instance each time - things get warmm — Callum Linington, Oct 22 '20 at 09:56
@CallumLinington I tried it on two different machines, randomizing the input. Same result every time — garritfra, Oct 22 '20 at 09:57
@Ifaruki i think the numbers is the total time, not the number of runs — Simen Fjellstad, Oct 22 '20 at 09:59
check it https://softwareengineering.stackexchange.com/questions/276346/why-is-the-latter-function-10-faster-although-it-must-create-the-variables-over — Momo Setti, Oct 22 '20 at 10:06
@MomoSetti in his case it's the exact opposite. I suspect it has to do with recursion. — garritfra, Oct 22 '20 at 10:09

GalAbra · Accepted Answer · 2021-01-24T11:19:50.403

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));

score 0 · Answer 2 · edited Oct 22 '20 at 11:59

0

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.

edited Oct 22 '20 at 11:59

shapiro yaacov

2,308
2
26
39

answered Oct 22 '20 at 10:50

Daniel

1

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

2 Answers2