javascript Node.js Map中的最大条目数？

4nkexdtk  于 2023-04-10  发布在  Java
关注(0)|答案(5)|浏览(276)

我在Node.js v11.9.0中做了一个很大的Map，它一直失败，并显示“致命错误：invalid table size Allocation failed - JavaScript heap out of memory”.我的map的键和值不应该接近Node的堆大小，所以我试着只做一个map并插入数字键和值：

var N = Math.pow(2, 26);
var map = new Map();
for (var i = 0; i < N; i++) {
  map.set(i, i + 1);
  if (i % 1e5 === 0) { console.log(i / 1e6); }
}
  • 这个数字似乎可疑地接近2^24，因此将上面的日志记录替换为if (i > 16777200) { console.log(i); }，我看到程序在成功打印“16777215”后立即崩溃，这比2^24少一个。

问题：Node的Map中是否有记录限制条目数接近2^24？是否有任何方法可以提高该限制？
(N.B.将Node作为node --max-old-space-size=4096运行并不能防止崩溃，因为Node使用的RAM远远少于4 GB。
(N.B. 2.我不认为这是哈希冲突问题，因为在我的实际代码中，Map包含（短）字符串而不是数字。
(N.B. 3.在Firefox的JavaScript控制台中运行上述程序并不会杀死Firefox-Firefox一直在添加超过3000万的条目。然而，Chrome就像Node一样崩溃。所以这可能是V8的限制。）

JavaScript

5条答案

按热度按时间
6l7fqoea

6l7fqoea1#

V8开发人员在这里。我可以确认2^24是Map中的最大条目数。这不是一个bug，它只是实现定义的限制。
限值由以下各项确定：

  • Map的FixedArray后备存储的最大大小为1GB（与整个堆大小限制无关）
  • 在64位系统上，这意味着每FixedArray的最大元素数为1GB / 8B = 2^30 / 2^3 = 2^27 ~= 1.34亿
  • 一个Map每个条目需要3个元素（键、值、下一个存储桶链接），最大负载因子为50%（以避免多次存储桶冲突导致的速度减慢），其容量必须是2的幂。2^27 /（3 * 2）向下舍入到2的下一个幂是2^24，这是您观察到的限制。

FWIW，凡事都有限度：除了最大堆大小之外，还有最大String长度、最大Array长度、最大ArrayBuffer长度、最大BigInt大小、最大堆栈大小等。这些限制中的任何一个都可能是有争议的，有时提高它们是有意义的，但是限制仍然存在。我不知道要怎么样才能突破这个限制，比如说，我也不知道2的因素是否足以满足你们的期望。

赞(0）分享  回复(0）举报  2023-04-10
lvmkulzt

lvmkulzt2#

我写了BigMap和BigSet类，允许超出限制，当达到限制时，我只需创建新的Map（或Set）。API与内置的Map和Set完全相同。

const kMaxSize = Math.pow(2, 24)

const BigMap = class {
  /*
    public api, compatible with "Map"
  */

  constructor (...parameters) {
    this.maps = [new Map(...parameters)]
  }

  set (key, value) {
    const map = this.maps[this.maps.length - 1]

    if (map.size === kMaxSize) {
      this.maps.push(new Map())
      return this.set(key, value)
    } else {
      return map.set(key, value)
    }
  }

  has (key) {
    return _mapForKey(this.maps, key) !== undefined
  }

  get (key) {
    return _valueForKey(this.maps, key)
  }

  delete (key) {
    const map = _mapForKey(this.maps, key)

    if (map !== undefined) {
      return map.delete(key)
    }

    return false
  }

  clear () {
    for (let map of this.maps) {
      map.clear()
    }
  }

  get size () {
    let size = 0

    for (let map of this.maps) {
      size += map.size
    }

    return size
  }

  forEach (callbackFn, thisArg) {
    if (thisArg) {
      for (let value of this) {
        callbackFn.call(thisArg, value)
      }
    } else {
      for (let value of this) {
        callbackFn(value)
      }
    }
  }

  entries () {
    return _iterator(this.maps, 'entries')
  }

  keys () {
    return _iterator(this.maps, 'keys')
  }

  values () {
    return _iterator(this.maps, 'values')
  }

  [Symbol.iterator] () {
    return _iterator(this.maps, Symbol.iterator)
  }
}

/*
  private function
*/

function _mapForKey (maps, key) {
  for (let index = maps.length - 1; index >= 0; index--) {
    const map = maps[index]

    if (map.has(key)) {
      return map
    }
  }
}

function _valueForKey (maps, key) {
  for (let index = maps.length - 1; index >= 0; index--) {
    const map = maps[index]
    const value = map.get(key)

    if (value !== undefined) {
      return value
    }
  }
}

function _iterator (items, name) {
  let index = 0

  var iterator = items[index][name]()

  return {
    next: () => {
      let result = iterator.next()

      if (result.done && index < (items.length - 1)) {
        index++
        iterator = items[index][name]()
        result = iterator.next()
      }

      return result
    },
    [Symbol.iterator]: function () {
      return this
    }
  }
}

BigMap.length = 0

/*
 Big Set
 */

const BigSet = class {
  /*
    public api, compatible with "Set"
  */

  constructor (...parameters) {
    this.sets = [new Set(...parameters)]
  }

  add (key) {
    const set = this.sets[this.sets.length - 1]

    if (set.size === kMaxSize) {
      this.sets.push(new Set())
      return this.add(key)
    } else {
      return set.add(key)
    }
  }

  has (key) {
    return _setForKey(this.sets, key) !== undefined
  }

  delete (key) {
    const set = _setForKey(this.sets, key)

    if (set !== undefined) {
      return set.delete(key)
    }

    return false
  }

  clear () {
    for (let set of this.sets) {
      set.clear()
    }
  }

  get size () {
    let size = 0

    for (let set of this.sets) {
      size += set.size
    }

    return size
  }

  forEach (callbackFn, thisArg) {
    if (thisArg) {
      for (let value of this) {
        callbackFn.call(thisArg, value)
      }
    } else {
      for (let value of this) {
        callbackFn(value)
      }
    }
  }

  entries () {
    return _iterator(this.sets, 'entries')
  }

  keys () {
    return _iterator(this.sets, 'keys')
  }

  values () {
    return _iterator(this.sets, 'values')
  }

  [Symbol.iterator] () {
    return _iterator(this.sets, Symbol.iterator)
  }
}

/*
  private function
*/

function _setForKey (sets, key) {
  for (let index = sets.length - 1; index >= 0; index--) {
    const set = sets[index]

    if (set.has(key)) {
      return set
    }
  }
}

function _iterator (items, name) {
  let index = 0

  var iterator = items[index][name]()

  return {
    next: () => {
      let result = iterator.next()

      if (result.done && index < (items.length - 1)) {
        index++
        iterator = items[index][name]()
        result = iterator.next()
      }

      return result
    },
    [Symbol.iterator]: function () {
      return this
    }
  }
}

BigSet.length = 0
赞(0）分享  回复(0）举报  2023-04-10
2o7dmzc5

2o7dmzc53#

有趣的是，如果您更改代码以创建两个Map对象并同时插入它们，它们都会在完全相同的点16.7崩溃：

var N = Math.pow(2, 26);
var m1 = new Map();
var m2 = new Map();

for (var i = 0; i < N; i++) {
  m2.set(i, i + 1);
  m1.set(i, i + 1);

  if (i % 1e5 === 0) { console.log(m1.size / 1e6); }
}

当在任何给定的Map中创建的条目超过224个时，这里会发生一些奇怪的事情，而不是全局地跨所有Map对象。
我想你发现了一个需要报告的V8错误。

赞(0）分享  回复(0）举报  2023-04-10
fruv7luv

fruv7luv4#

我在48,408,186元素后得到了这个：

RangeError: Map maximum size exceeded

在Node.js 17中使用node --max-old-space-size=8192 script.js。
一个普通的对象{}做得更好。

赞(0）分享  回复(0）举报  2023-04-10
zz2j4svz

zz2j4svz5#

小的解决方法是在达到限制时将其划分为较小的Map，从而能够存储和访问比内置Map更多的元素：

class LargeMap {
    get size() {
        return this.maps.reduce((p, c) => p + c.size, 0);
    }
    constructor(limit = 16777216) {
        this.limit = limit;
        this.maps = [new Map()];
    }
    has(key) {
        return this.maps.some(map => map.has(key));
    }
    set(key, value) {
        if (this.maps[this.maps.length - 1].size >= this.limit) {
            this.maps.push(new Map());
        }
        let map = this.maps[this.maps.length - 1];
        for (let i = 0; i < this.maps.length - 1; i++) {
            if (this.maps[i].has(key)) {
                map = this.maps[i];
                break;
            }
        }
        map.set(key, value);
        return this;
    }
    get(key) {
        const map = this.maps.find(map => map.has(key));
        if (map) return map.get(key);
        return undefined;
    }
    delete(key) {
        for (let i = this.maps.length - 1; i >= 0; i--) {
            const map = this.maps[i];
            if (map.delete(key)) {
                return true;
            }
        }
        return false;
    }
    clear() {
        this.maps = [new Map()];
    }
}

试试这个测试：

const largeMap = new LargeMap();
for (let i = 0; i <= 16777216; i++) {
  largeMap.set(i, 1); // No errors will be thrown
}

const map = new Map();
for (let i = 0; i <= 16777216; i++) {
  map.set(i, 1); // Throws a 'RangeError: Value undefined out of range for undefined options property undefined'
}

如果您有兴趣使用与内置插件完全相同的接口的NPM包，您可以尝试large-map和large-set用于Set。

赞(0）分享  回复(0）举报  2023-04-10
我来回答

相关问题

    查看更多
    微信公众号

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com