37

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.)

2
  • 1
    I can reproduce this crash, but it is odd that some 24-bit value is involved here.
    – tadman
    Jan 31, 2019 at 3:39
  • this is because of an underlying limit to the size of a block, i read all the C++ code involved, it fails because the block containing the pointers to the entries cannot grow, they actually hard coded a limit there, it is not in the code for Map and Set themselves Feb 14, 2022 at 16:49

6 Answers 6

75

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.

3
  • 1
    Thanks for the valuable insight 🙇! My personal need right now is for 20 million keys but that could rise tomorrow. I’ll try to find a workaround, by using multiple maps to store all my data. Jan 31, 2019 at 19:52
  • Consider sharding?
    – ccov77
    Aug 27, 2021 at 18:27
  • Limits for String, Buffer, and TypedArray are publicly available in Node.js: require('buffer').constants.MAX_STRING_LENGTH, require('buffer').constants.MAX_LENGTH nodejs.org/api/buffer.html#buffer-constants BTW buffer length has increased in Node.js v14 and then in v15 again, and string length has decreased(!) in v16
    – Victor
    Dec 28, 2022 at 11:11
8

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

5
  • note that the BigSet and BigMap classes are written to be in separate source files May 28, 2019 at 3:32
  • 2
    Very nice. Publish to npmjs? May 30, 2019 at 0:26
  • Note that this code has a bug - set will always try to set the last map of the list, so if you have a key in one of the first maps, it will be duplicated with a new value in the last map. The get function will always get the right thing though, so maybe not too big of a deal to have some duplicated memory. That said, if you call _mapForKey() at the beginning of set, you can easily fix the issue. Feb 13, 2022 at 6:30
  • 1
    Also note that just checking for the max size isn't good enough - Node JS can tell you that you have a full Map even with less items than that (if the Map has 1GB of stuff in it) - so this class will throw an error in that case instead of adding another Map like you would expect. Feb 13, 2022 at 6:32
  • oh it's not throwing an error, it will crash !, thanks for your comments, i might fix the duplicate key problem, i also don't allow to delete a key, it's not perfect, i wrote that code for the case where u only keep adding values. i wasn't aware of the 1GB limit, i think the limit is only on the number of entries in the array. Feb 14, 2022 at 16:46
2

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 224 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.

2
  • 6
    It's not a bug, just an implementation-defined limit.
    – jmrk
    Feb 1, 2019 at 18:51
  • 3
    It would be nice to have this documented somewhere
    – Willa
    Oct 20, 2020 at 8:38
1

Small workaround by partitioning into the smaller maps when it reached the limit, enabling to store and access more elements than the built-in 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()];
    }
}

Try this for testing:

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'
}

If you are interested in using an NPM package with exactly the same interface as the built-ins, you can try large-map and large-set for Set.

1
  • These npm pkgs are very handy, nice job!
    – David
    Sep 22 at 6:58
0

I just got this after 48,408,186 elements:

RangeError: Map maximum size exceeded

In Node.js 17 with node --max-old-space-size=8192 script.js.

A regular object {} is doing a lot better.

1
  • 4
    When I try in Node 18, the limit for a Map is still around 16.7 million elements (2**24). -- A regular object might do better if and only if all your keys are integers in array-index range; if the keys are strings, a regular object becomes unusably slow after ~8.3M elements (for which there is a technical reason: a certain bit field being 23 bits wide and taking a very slow fallback path when exceeded).
    – jmrk
    May 8, 2022 at 0:11
0

Separate each size max.
BigMap => handle [Map(MAX_SIZE), Map(MAX_SIZE),...]

    class BigMap {
      lastKey = this.nextKey();
      keys = {
        [this.lastKey]: new Map()
      };
      constructor(MAX_SIZE){
         this.MAX_SIZE = MAX_SIZE || 2 ** 24;
      }
      nextKey(){
        let len = Object.keys(this.keys || []).length;
        return len + 1;
      };
      has(key){
        for (let k in this.keys) {
          const res = this.keys[k].has(key);
          if (res) return true;
        }
        return false
      }
      get(key){
        for (let k in this.keys) {
          const pas = this.keys[k].has(key);
          if (pas) return this.keys[k].get(key);
        }
      };
      set(key, value){
        // update map[key] = newValue
        if (this.keys[this.lastKey].size < this.MAX_SIZE) {
          return this.keys[this.lastKey].set(key, value);
        }
        // create map[newKey] = new map()
        const newMapKey = this.nextKey();
        this.keys[newMapKey] = new Map();
        this.keys[newMapKey].set(key, value);
        this.lastKey = newMapKey;
      }
    }
    const largeMap = new BigMap();
    for (let i = 0; i <= 2 ** 26; i++) {
      largeMap.set(i, i+11);
    }
    console.log(largeMap.get(2**24)) // 16777227
    console.log(largeMap.keys) //{"1": Map(16777216), "2": Map(16777216), "3": Map(16777216), "4": Map(16777216), "5": Map(1)}
2
  • 1
    While this approach should work, this answer adds nothing useful to the question: it's essentially the same approach as Yogi Anderson's older answer describes, but with a worse implementation. What's the point of randomKey? And why are all functions installed as direct fields on each BigMap instance, rather than on the prototype, e.g. by using class syntax?
    – jmrk
    Jul 5 at 21:11
  • maybe like this Jul 13 at 17:38

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.