Why is one of these functions faster than the other, even though it should be the other way around?

user_6365531 0
Viewed 75

I'm making a program to calculate all primes up to a specific number. I've been using a timer to optimize the function and I can calculate primes up to 20 million in less than 4 seconds. The problem is, one of the optimizations actually made the program slower, even though it's doing less stuff.

Old function (the faster one):

function getPrimesOld(max) {
    const arr = [1];
    function isPrime(i) {
        const s = Math.sqrt(i);
        for (const h of arr) {
            if (h === 1) continue;
            if (h > s) break;
            if (!(i % h)) return false;
        }
        return true;
    }
    for (let i = 2 ; i < max ; i += 2) {
        if (isPrime(i)) arr.push(i);
        if (i === 2) i--;
    }
    return arr;
}

New function:

function getPrimes(max) {
    const arr = [2];
    function isPrime(i) {
        const s = Math.sqrt(i);
        for (const h of arr) {
            if (h > s) break;
            if (!(i % h)) return false;
        }
        return true;
    }
    for (let i = 3 ; i < max ; i += 2) {
        if (isPrime(i)) arr.push(i);
    }
    return arr;
}

I ran both functions 10 times and averaged the time it took them, here are the results:

New function: 3544ms,3188ms,3513ms,3510ms,3511ms,3512ms,3503ms,3515ms,3513ms,3509ms (avg: 3481.8ms)
Old function: 3368ms,3388ms,3363ms,3355ms,3359ms,3350ms,3354ms,3354ms,3353ms,3356ms (avg: 3360ms)

(Just to make it clear, running the old function 10 times first instead of the new one doesn't affect the results. Old always averages around 3.35s and new always averages around 3.5s)

Why is the old function faster than the new one?

javascript
1 Answers

I got a little obsessed with this, I admit, but I'm not seeing the performance degradation you are talking about. While the difference is extremely small, your new approach does appear to be every so slightly faster (running Chrome Version 94.0.4606.81 (Official Build) (x86_64) on macOS Big Sur 11.6 (20G165)).

One sample result from the test below:

Old Results:
- Mean: 3744 ms
- Median: 3735 ms
New Results:
- Mean: 3350 ms
- Median: 3276 ms

I'd be curious to see what other readers discover:

const debugElem = document.getElementById("debug");
debugElem.innerText = "Press Start to Begin";

function getPrimesOld(max) {
  const arr = [1];
  function isPrime(i) {
    const s = Math.sqrt(i);
    for (const h of arr) {
      if (h === 1) continue;
      if (h > s) break;
      if (!(i % h)) return false;
    }
    return true;
  }
  for (let i = 2 ; i < max ; i += 2) {
    if (isPrime(i)) arr.push(i);
    if (i === 2) i--;
  }
  return arr;
}

function getPrimes(max) {
  const arr = [2];
  function isPrime(i) {
    const s = Math.sqrt(i);
    for (const h of arr) {
      if (h > s) break;
      if (!(i % h)) return false;
    }
    return true;
  }
  for (let i = 3 ; i < max ; i += 2) {
    if (isPrime(i)) arr.push(i);
  }
  return arr;
}

async function testPrimes(fn) {
  await logMsg(`Running test for ${/function \w+/.exec(fn+"")}`);
  const stats = {
    times: [],
  };
  async function runTest() {
    const start = performance.now();
    await fn(20000000);
    const end = performance.now();
    return end - start;
  }
  for (let i = 10; i--;) {
    const diff = await runTest();
    await logMsg(`${i}... ${Math.round(diff)} ms`);
    stats.times.push(diff);
  }
  stats.times = stats.times.sort();
  stats.avg = stats.times.reduce(
    (acc, d) => acc + d,
    0
  ) / stats.times.length;
  stats.mdn = (stats.times[4] + stats.times[5])/2;
  
  return stats;
}

function logMsg(msg) {
  return new Promise(resolve => {
    debugElem.innerText += msg + "\n";
    // console.log(msg);
    // Due to JavaScript's single-threading, we need to introduce
    // a slight delay in order to update the UI. This only happens
    // AFTER a test has finished, so it won't affect the times
    // reported by the test
    setTimeout(resolve, 0);
  });
}

document.getElementById("start").onclick = (async function() {
  debugElem.innerText = "";
  const results = {};
  results.old = await testPrimes(getPrimesOld);
  debugElem.innerText = "";
  results.new = await testPrimes(getPrimes);
  debugElem.innerText = "";
  logMsg("Old Results:");
  logMsg(`- Mean: ${Math.round(results.old.avg)} ms`);
  logMsg(`- Median: ${Math.round(results.old.mdn)} ms`);
  logMsg("New Results:");
  logMsg(`- Mean: ${Math.round(results.new.avg)} ms`);
  logMsg(`- Median: ${Math.round(results.new.mdn)} ms`);
});
#debug {
  font-family: "Lucida Console", monospace, sans-serif;
}
<button id="start">Start</button>
<div id="debug"></div>

user_2116270
Related