Maximum number of entries in Node.js Map?

Question

I was making a large Map in Node.js v11.9.0 and it kept failing with "FATAL ERROR: invalid table size Allocation failed - JavaScript heap out of memory". My map's keys and values shouldn't be getting anywhere near the size of Node's heap size, so I tried just making a map and inserting numeric keys and values into it:

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

This program crashes Node after inserting roughly 16.6 million entries. That number seemed suspiciously close to 2^24, so replacing the logging above with if (i > 16777200) { console.log(i); }, I see that the program crashes immediately after successfully printing "16777215", which is one less than 2^24.

Question. Is there a documented limit on the number of entries in Node's Map close to 2^24? Is there any way to raise that limit?

(N.B. Running Node as node --max-old-space-size=4096 doesn't prevent the crash, since Node is using far less than 4 GB RAM.)

(N.B. 2. I don't think this is a hash collision issue since in my actual code, the map contains (short-ish) strings rather than numbers.)

(N.B. 3. Running the above programs in Firefox's JavaScript Console does not kill Firefox–Firefox keeps adding entries well past 30 million. However, Chrome crashes just like Node. So this is likely a V8 limitation.)

Solution 1

V8 developer here. I can confirm that 2^24 is the maximum number of entries in a Map. That's not a bug, it's just the implementation-defined limit.

The limit is determined by:

• The FixedArray backing store of the Map has a maximum size of 1GB (independent of the overall heap size limit)
• On a 64-bit system that means 1GB / 8B = 2^30 / 2^3 = 2^27 ~= 134M maximum elements per FixedArray
• A Map needs 3 elements per entry (key, value, next bucket link), and has a maximum load factor of 50% (to avoid the slowdown caused by many bucket collisions), and its capacity must be a power of 2. 2^27 / (3 * 2) rounded down to the next power of 2 is 2^24, which is the limit you observe.

FWIW, there are limits to everything: besides the maximum heap size, there's a maximum String length, a maximum Array length, a maximum ArrayBuffer length, a maximum BigInt size, a maximum stack size, etc. Any one of those limits is potentially debatable, and sometimes it makes sense to raise them, but the limits as such will remain. Off the top of my head I don't know what it would take to bump this particular limit by, say, a factor of two -- and I also don't know whether a factor of two would be enough to satisfy your expectations.

Solution 2

i wrote BigMap and BigSet classes that allow to go beyond that limit i simply create new Maps (or Sets) when the limit is reached. the API is exactly the same as with the built in Map and 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

Solution 3

What's interesting is if you change your code to create two Map objects and insert into them simultaneously, they both crash at exactly the same point, 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); }
}

There's something odd happening here when more than 2²⁴ entries are made in any given Map, not globally across all Map objects.

I think you've found a V8 bug that needs to be reported.