JavaScript：阿特金筛法实施中的巨大结果数组内存不足

Question

目前我运行正在 JavaScript、asm.js 和 WebAssembly 之间进行一些基准测试。为此，我实现了一个使用阿特金筛算法搜索素数的小程序。

为了使上升可以忽略不计，我正在计算高达 500'000'000 的素数。我的问题是，JavaScript 实现运行内存不足，因为结果数组变得很大。

这是我当前的实现：

const AMOUNT = 500000000;

function getPrimes() {
  const limit = AMOUNT;
  const width = Math.sqrt(limit);
  let i, j, x, y, z;
  let primes = new Array(limit);

  const begin = performance.now();
  for (x = 1; x <= width; x++) {
    for (y = 1; y <= width; y++) {
      z = 4 * x * x + y * y;
      if (z < limit && (z % 60 == 1 || z % 60 == 13 || z % 60 == 17 || z
          % 60 == 29 || z % 60 == 37 || z % 60 == 41 || z % 60 == 49
          || z % 60 == 53)) {
        primes[z] = !primes[z];
      }

      z = 3 * x * x + y * y;
      if (z < limit && (z % 60 == 7 || z % 60 == 19 || z % 60 == 31 || z
          % 60 == 43)) {
        primes[z] = !primes[z];
      }

      z = 3 * x * x - y * y;
      if (x > y && z < limit && (z % 60 == 11 || z % 60 == 23 || z % 60
          == 47 || z % 60 == 59)) {
        primes[z] = !primes[z];
      }
    }
  }

  const end = performance.now();

  let last_prime = 0;
  for (i = limit; i >= 0; i--) {
    if(primes[i] == 1) {
      last_prime = i;
      break;
    }
  }

  primes = null;
  time_spent = end - begin;
  console.log(time_spent/1000 + ', ' + last_prime);
}

document.addEventListener("DOMContentLoaded", function() {
  let i;
  for (i = 0; i <= 10; i++) {
    getPrimes();
  }
});

这是我的HTML到运行吧：

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Find Primes</title>
    <script src="./find-primes.js"></script>
  </head>
  <body>
    Check the console.
  </body>
</html>

到目前为止我尝试过的： - 确保在每个运行之后收集 primes 数组，方法是使它无效。 - 分配整个数组一次。

你有更多的想法来优化我的 JavaScript 实现的内存使用吗？

我尽量避免拆分数组或在不同的迭代中计算结果，因为我想对原始计算性能进行基准测试。内存管理应该不会对测试有任何影响。

我正在使用：

Google Chrome：版本 75.0.3770.90（官方构建）（64 位）
Mozilla Firefox：版本 67.0.2（64 位）

提前致谢！

Answer 1

而不是 Array, which naïvely stores each of your flags as a double (and probably has even more memory overhead for its ability to store arbitrary mixed types), you might use a Uint8Array 或其他无符号整数格式，这将至少减少 64 倍的内存使用量。

不过，您需要修改初始化、切换和检查标志的方式。

初始化：

const BitArray = Uint8Array; // or Uint16Array, Uint32Array
const BITS_PER_ELEMENT = BitArray.BYTES_PER_ELEMENT * 8;
const BIT_SHIFT = Math.log2(BITS_PER_ELEMENT);
const BIT_MASK = BITS_PER_ELEMENT - 1;
let primes = new BitArray(Math.ceil(limit / BITS_PER_ELEMENT));

切换：

primes[z >> BIT_SHIFT] ^= 1 << (z & BIT_MASK);

正在检查：

if (primes[i >> BIT_SHIFT] & (1 << (i & BIT_MASK)))

Uint8Array、Uint16Array 和 Uint32Array 之间的任何选择都将使用相同数量的内存。

JavaScript：阿特金筛法实施中的巨大结果数组内存不足

JavaScript: Out of Memory for huge result array in Sieve of Atkin implementation

javascript

performance

benchmarking

primes

performance-testing