Node.js 地图中的最大条目数？

Question

我在 Node.js v11.9.0 中做了一个很大的 Map，但一直失败 "FATAL ERROR: invalid table size Allocation failed - JavaScript heap out of memory"。我的地图的键和值不应该接近 Node 的堆大小，所以我尝试制作一个地图并在其中插入数字键和值：

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); }
}

这个程序在插入大约 1660 万个条目后使 Node 崩溃。 这个数字似乎可疑地接近 2^24，所以用 if (i > 16777200) { console.log(i); } 替换上面的日志记录，我明白了程序在成功打印“16777215”后立即崩溃，它比 2^24 小一。

问题。 Node 的 Map 中的条目数是否有记录限制接近 2^24？有什么办法可以提高这个限制吗？

(N.B。运行 Node as node --max-old-space-size=4096 不能防止崩溃，因为 Node 使用的 RAM 远少于 4 GB。)

(N.B。2. 我不认为这是哈希冲突问题，因为在我的实际代码中，地图包含（短的）字符串而不是数字。）

(N.B。3. 运行 Firefox JavaScript 控制台中的上述程序不会杀死 Firefox – Firefox 不断添加超过 3000 万的条目。但是，Chrome 和 Node 一样崩溃。所以这可能是 V8 的限制。）

Answer 1

有趣的是，如果您更改代码以创建两个 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); }
}

当在任何给定的地图中创建超过 2²⁴ 个条目时，这里会发生一些奇怪的事情，而不是全局跨所有地图对象。

我认为您发现了一个需要报告的 V8 错误。

Answer 2

这里是 V8 开发人员。我可以确认 2^24 是 Map 中的最大条目数。这不是错误，这只是实现定义的限制。

限制由以下因素决定：

Map 的 FixedArray 后备存储的最大大小为 1GB（独立于整体堆大小限制）
在 64 位系统上，这意味着 1GB / 8B = 2^30 / 2^3 = 2^27 ~= 每个 FixedArray
一个Map每个entry需要3个元素（key,value,next bucketlink），最大加载因子为50%（避免很多bucket碰撞导致的减速），它的容量必须是 2 的次方。2^27 / (3 * 2) 四舍五入到下一个 2 的次方是 2^24，这是你观察到的极限。

FWIW，一切都有限制：除了最大堆大小之外，还有最大 String 长度、最大 Array 长度、最大 ArrayBuffer 长度、最大 BigInt 大小，最大堆栈大小等。这些限制中的任何一个都可能存在争议，有时提高它们是有意义的，但这些限制将保留下来。在我的脑海中，我不知道如何才能将这个特定限制提高两倍，比如说，两倍——而且我也不知道两倍是否足以满足您的期望。

Answer 3

我编写了 BigMap 和 BigSet 类允许超出该限制我只是在达到限制时创建新的地图（或集）。 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

Answer 4

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

RangeError: Map maximum size exceeded

在 Node.js 17 和 node --max-old-space-size=8192 script.js.

常规对象 {} 做得更好。

Node.js 地图中的最大条目数？

Maximum number of entries in Node.js Map?

javascript

dictionary

v8

node.js