V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
xiaoming1992
V2EX  ›  程序员

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

  •  
  •   xiaoming1992 · 2020-08-15 16:19:56 +08:00 · 1552 次点击
    这是一个创建于 1561 天前的主题,其中的信息可能已经有所发展或是发生改变。

    程序功能是将质数依次写入文件, 执行 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()
    
    第 1 条附言  ·  2020-08-15 23:43:40 +08:00

    ---------------- 新增 bug report ---------------
    bug report, 有兴趣的可以帮忙看看(我是一点看不懂 T_T)

    第 2 条附言  ·  2020-08-16 15:06:27 +08:00

    估计是 #8 所说的原因,文件写入改用:

    const fd = fs.openSync(fileName, "a+")    
    __for (...) {    
    ____if (isPrime(...)) {    
    ________fs.writeSync(fd, "...")    
    ____}    
    __}    
    

    之后速度很快,也不崩溃了,在十几亿的情况下还能保持每秒100万左右。(我还用C++重写了,结果C++的速度还不如js,果然菜鸟写什么语言都慢。。。)
    执行情况如下:

    >>> 开始执行 加载质数表文件: [质数表.txt]...
    <<< 执行完毕 加载质数表文件: [质数表.txt], 耗时 240 ms

    >>> 开始执行 解析质数表文件...
    <<< 执行完毕 解析质数表文件, 耗时 45.267 秒

    >>> 开始执行 检测 [616399999, 2147483643]...
    100.0%: 2,147,200,001
    <<< 执行完毕 检测 [616399999, 2147483643], 耗时 22 分 42 秒

    共计检测 1,531,083,644 个数, 平均每秒检测 1,123,675

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

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

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

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

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


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

    异步这个可能是 stdout.write 或者 fs.writeFileSync 触发的某些回调,没细看。
    感觉也可能是算的比 IO 快太多,导致 IO 堆积了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1112 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 23:49 · PVG 07:49 · LAX 15:49 · JFK 18:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.