在 Firefox 中使用 BigInt 时，为什么递归阶乘函数比其等效的迭代函数运行得更快？

Question

在上下文中玩弄 BigInt 时在实现阶乘函数时，我注意到一些我没有预料到的行为。在 Firefox 中运行时，递归阶乘函数似乎比迭代函数的性能更高。在 Chrome 中运行时，性能发生了变化（这是我期望看到的）。

我创建了这个 GitHub Gist 来显示阶乘函数的多个版本之间的性能比较。这里还有一个内联 JavaScript 片段，相当于 Gist。注意：我使用 console.table 输出结果，当您运行代码片段时，它似乎没有显示，您必须打开实际的开发控制台才能查看该表。

function factorialIterBigInt(input) {
    let computedFactorial = 1n;
    for (let i = input; i >= 1n; i--) {
        computedFactorial *= i;
    }
    return computedFactorial;
}

function factorialForwardIterBigInt(input) {
    let computedFactorial = 1n;
    for (let i = 1n; i <= input; i++) {
        computedFactorial *= i;
    }
    return computedFactorial;
}

function factorialRecBigInt(input) {
    if (input === 0n) {
        return 1n;
    }
    else {
        return input * factorialRecBigInt(input - 1n);
    }
}

function factorialTailRecBigInt(input, accumulatedResult = 1n) {
    if (input === 0n) {
        return accumulatedResult;
    }
    else {
        return factorialTailRecBigInt(input - 1n, input * accumulatedResult);
    }
}

function factorialIterNumber(input) {
    let computedFactorial = 1;
    for (let i = input; i >= 1; i--) {
        computedFactorial *= i;
    }
    return computedFactorial;
}
function factorialForwardIterNumber(input) {
    let computedFactorial = 1;
    for (let i = 1; i <= input; i++) {
        computedFactorial *= i;
    }
    return computedFactorial;
}

function factorialRecNumber(input) {
    if (input === 0) {
        return 1;
    }
    else {
        return input * factorialRecNumber(input - 1);
    }
}

function factorialTailRecNumber(input, accumulatedResult = 1) {
    if (input === 0) {
        return accumulatedResult;
    }
    else {
        return factorialTailRecNumber(input - 1, input * accumulatedResult);
    }
}

function measurePerformanceOfFunction({ functionToMeasure, paramsToCallWith, timesToMeasure }) {
    timesToMeasure = timesToMeasure == null || timesToMeasure <= 0 ? 1 : timesToMeasure;
    let totalTime = 0;
    for (let i = 0; i < timesToMeasure; i++) {
        const start = performance.now();
        functionToMeasure.apply(null, paramsToCallWith);
        const end = performance.now();
        totalTime += end - start;
    }
    return totalTime / timesToMeasure;
}

const input = 5000;
const inputAsBigInt = BigInt(input);
const timesToMeasure = 100;

console.log(`Input: ${input}`);
console.log(`Measured: ${timesToMeasure} times`);

console.table({
    'Iterative Backward': {
        'BigInt': `${measurePerformanceOfFunction({ functionToMeasure: factorialIterBigInt, paramsToCallWith: [inputAsBigInt], timesToMeasure })}ms`,
        'Number': `${measurePerformanceOfFunction({ functionToMeasure: factorialIterNumber, paramsToCallWith: [input], timesToMeasure })}ms`
    },
    'Iterative Forward': {
        'BigInt': `${measurePerformanceOfFunction({ functionToMeasure: factorialForwardIterBigInt, paramsToCallWith: [inputAsBigInt], timesToMeasure })}ms`,
        'Number': `${measurePerformanceOfFunction({ functionToMeasure: factorialForwardIterNumber, paramsToCallWith: [input], timesToMeasure })}ms`
    },
    'Recursive': {
        'BigInt': `${measurePerformanceOfFunction({ functionToMeasure: factorialRecBigInt, paramsToCallWith: [inputAsBigInt], timesToMeasure })}ms`,
        'Number': `${measurePerformanceOfFunction({ functionToMeasure: factorialRecNumber, paramsToCallWith: [input], timesToMeasure })}ms`
    },
    'Tail Recursive': {
        'BigInt': `${measurePerformanceOfFunction({ functionToMeasure: factorialTailRecBigInt, paramsToCallWith: [inputAsBigInt], timesToMeasure })}ms`,
        'Number': `${measurePerformanceOfFunction({ functionToMeasure: factorialTailRecNumber, paramsToCallWith: [input], timesToMeasure })}ms`
    }
});

我真的很好奇是否有人知道为什么该函数的递归版本比 Firefox 中的迭代版本更快？

Answer 1

迭代版本可能较慢的原因之一是它没有按照与递归版本相同的顺序执行乘法。

递归版本实际上执行后序过程：首先进行递归，然后然后——同时回溯递归的出——乘法发生。这意味着最小值首先相乘。

迭代版本从高值循环到低值，因此乘法以相反的顺序发生。当我更改此设置时，迭代版本的速度提高了 5-15%，弥补了与递归版本的大部分差异。

加速的原因之一是整个过程中的内存分配占用（对于 BigInt）：当从较小的数字开始时，初始占用空间很小，而在相反的方向上，占用空间会更快地变大。

在这里您可以看到两个迭代版本都在运行。在 Firefox 中，我的前向版本获得了更好的性能：

function factorialIterBigIntForward(input) {
    let computedFactorial = 1n;
    for (let i = 1n; i <= input; i++) {
        computedFactorial *= i;
    }
    return computedFactorial;
}

function factorialIterBigIntBackward(input) {
    let computedFactorial = 1n;
    for (let i = input; i >= 1n; i--) {
        computedFactorial *= i;
    }
    return computedFactorial;
}

let input = 20000n;
// Run both functions twice
let time1 = performance.now();
factorialIterBigIntBackward(input);
let time2 = performance.now();
factorialIterBigIntForward(input);
let time3 = performance.now();
factorialIterBigIntBackward(input);
let time4 = performance.now();
factorialIterBigIntForward(input);
let time5 = performance.now();

console.log("backward", time2 - time1 + time4 - time3);
console.log("forward", time3 - time2 + time5 - time4);