[求助] 求质数的 nodejs 程序内存溢出,能帮忙分析是哪儿溢出了吗?

2020-08-15 16:19:56 +08:00
 xiaoming1992

程序功能是将质数依次写入文件, 执行 ts-node main.ts, 代码在下面

常规判断是否是质数, 是逐个判断 [2, Math.sqrt(num)] 是否能整除目标数, 我的思路是维护一个质数数组, 先从该数组中逐个判断是否能整除, 然后再依次加一, 效率还行(?), 每秒能判断十万个左右, 加上写入文件的话每秒能 1.5 万个左右

但是跑到 2.2 千万时, 程序报错了, 重新执行, 从 2.2 千万跑到 3.5 千万时又报错了; 就我的渣渣水平来看, 大概是内存溢出? 但是我从头到尾看了我的程序, 除了那个质数数组一直占用内存, 其他的变量应该都能被回收啊, cpu 占用也一直在 50%左右, 不高啊, 求助为什么崩了呢?

部分报错如下

[4828:000002AA1DB95410]   818854 ms: Mark-sweep 1753.6 (2051.2) -> 1753.6 (2051.2) ms  (average mu = 0.191, current mu = 0.000) last resort GC in old space requeste
[4828:000002AA1DB95410]   819628 ms: Mark-sweep 1753.6 (2051.2) -> 1753.6 (2052.2) ms  (average mu = 0.207, current mu = 0.227) allocation failure GC in old space r

...

FATAL ERROR: Ineffective mark-compacts near heap limit Allocation failed - JavaScr
memory

------------ 代码 -----------

// main.ts

import * as fs from "fs"

const primeStr = fs.readFileSync("primes.txt", {
  encoding: "utf-8",
  flag: "a+",
})
const primes = primeStr.split(",").map((n) => +n).filter((n) => n >= 2)
let primeLastIdx = primes.length - 1

function checkIsInt(num: number) { return num === num >> 0 }

/**
 * 返回 a 是否是 b 的因子
 * 
 * 返回值 true: 是因子
 * 返回值 false: 不是因子, 且大于 a 的数都不是因子
 * 返回值 1: 不是因子, 但大于 a 的数可能存在因子
 */
function isFactorOf(a: number, b: number) {
  const devided = b / a
  if (a > devided) { return false }
  if (checkIsInt(devided)) { return true }
  return 1
}

function checkIsPrime(num: number) {
  let prime: number
  for (let i = 0; i <= primeLastIdx; i += 1) {
    prime = primes[i]
    const isFactor = isFactorOf(prime, num)
    if (isFactor === 1) {
      continue
    }
    return !isFactor
  }
  for (let i = prime + 1; true; i += 1) {
    const isFactor = isFactorOf(i, num)
    if (isFactor === 1) {
      continue
    }
    return !isFactor
  }
}

function main() {
  for (let i = primes[primeLastIdx] + 1 || 2; i < 101000000; i += 1) {
    process.stdout.write(`\r${i}`)
    if (checkIsPrime(i)) {
      primeLastIdx += 1
      primes.push(i)
      fs.writeFileSync("./primes.txt", `${i},`, {
        encoding: "utf-8",
        flag: "a+",
      })
    }
  }
}

main()
1543 次点击
所在节点    程序员
8 条回复
crella
2020-08-15 19:30:18 +08:00
我看不出来什么问题,建议用不同进程执行,每个进程读取指定区间的已知质数群的 txt 文件,运算后再写入文件
crella
2020-08-15 19:42:37 +08:00
或者试试 redis ?因为不是编译语言的语言的数组相对来说占内存多很多
roscoecheung1993
2020-08-15 21:24:35 +08:00
快照了一下,疑似写完文件后会往事件循环队列里放一个异步任务的对象,分配了相当多的 Object
noe132
2020-08-15 21:55:41 +08:00
你 stdout 写的太频繁了,影响了执行速度。
建议每 1024 个数输出一下,能快不少。我这目测有 6-8 倍的提升。

if (i % 1024 === 0) {
process.stdout.write(`\r${i}`)
}

质数判断也有优化空间,随便改一改似乎能有 1 倍的性能提升

node 12.16.1 似乎并没有出现内存泄漏
private bytes 一直稳定在 110MB 左右,
xiaoming1992
2020-08-15 23:50:26 +08:00
@crella #1 用多进程, 可能效率还会提升不少, 但由于目前已经存在未知的 bug, 所以不想再做其他优化引入新的变量了。 #2 redis 同理

@noe132 #4 对对对,我忘了 stdout 也会影响性能了。。。还有方便说说质数判断怎么优化吗?


@roscoecheung1993 方便说说如何快照任务队列吗?我这边想试试看看。毕竟看我的程序好像没有哪儿用到异步了,怎么会分配异步任务呢。。。
xiaoming1992
2020-08-15 23:55:32 +08:00
@noe132 原来一直是 stdout 影响了速度, 我改成 `if (i % 20000 === 0)` 后, 速度直接飙升到将近 1 千万 每秒。。。是我年轻了, 我直觉以为 stdout 性能没问题呢
learningman
2020-08-16 00:12:30 +08:00
质数算法那么多。。。线性筛,埃氏筛,一堆
roscoecheung1993
2020-08-16 00:34:43 +08:00
@xiaoming1992 跑的时候给 node 传参 --inspect,在浏览器里连上 inspector 可以捕获堆快照和调用栈

异步这个可能是 stdout.write 或者 fs.writeFileSync 触发的某些回调,没细看。
感觉也可能是算的比 IO 快太多,导致 IO 堆积了

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/698472

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX