Can I pre-allocate memory for a Map/Set with a known number of elements?

Question

In the case of a JS array, it's possible to create one with predefined length. If we pass the length to the constructor, like new Array(itemCount), a JS engine could pre-allocate memory for the array, so it won't be needed to reallocate it while new items are added to the array.

Is it possible to pre-allocate memory for a Map or Set? It doesn't accept the length in the constructor like array does. If you know that a map will contain 10 000 items, it should be much more efficient to allocate the memory once than reallocate it multiple times.

Here is the same question about arrays.

---

There is discussion in the comments, whether the predefined array size has an impact on the performance or not. I've created a simple test to check it, the result is:

• Chrome - filling an array with a predefined size is about 3 times faster
• Firefox - there is no much difference, but the array with predefined length is a little bit faster
• Edge - filling of a predefined size array is about 1.5 times faster

---

There is a suggestion to create the entries array and pass it to the Map, so the map can take the length from the array. I've created such test too, the result is:

• Chrome - construction of a map which accepts entries array is about 1.5 times slower
• Firefox - there is no difference
• Edge - passing of entries array to the Map constructor is about 1.5 times faster

Answer 1

There is no way to influence the way the engine allocates memory, so whatever you do, you cannot guarantee that the trick you are using works on every engine or even at another version of the same engine.

There are however typed arrays in JS, they are the only datastructures with a fixed size. With them, you can implement your own hashmap with fixed size.

A very naive implementation is slightly faster² on inserting, not sure how it behaves on reads and others (also it can only store 8bit integers > 0):

function FixedMap(size) {
   const keys = new Uint8Array(size),
         values = new Uint8Array(size);
   
   return {
     get(key) {
        let pos = key % size;
        while(keys[pos] !== key) { 
          if(keys[pos] % size !== key % size) 
              return undefined;
          pos = (pos + 1) % size;
        }
        return values[pos];
     },
     set(key, value) {
       let pos = key % size;
       while(key[pos] && key[pos] !== key) pos = (pos + 1) % size;
       keys[pos] = value;
       values[pos] = value;
     }
   };
}
   

console.time("native");

const map = new Map();

for(let i = 0; i < 10000; i++)
  map.set(i, Math.floor(Math.random() * 1000));
  
console.timeEnd("native");

console.time("self");

const fixedMap = FixedMap(10000);

for(let i = 0; i < 10000; i++)
  fixedMap.set(i, Math.floor(Math.random() * 1000));
console.timeEnd("self");

---

_{² Marketing would say It is up to 20% faster! and I would say It is up to 2ms faster, and I spent more than 10minutes on this ...}

Answer 2

No, this is not possible. It's doubtful even that the Array(length) trick still works, engines have become much better at optimising array assignments and might have chosen a different strategy to (pre)determine the size of memory to allocate.

For Maps and Sets, no such trick exists. Your best bet will be creating them by passing an iterable to their constructor, like new Map(array), instead of using the set/add methods. This does at least offer the chance for the engine to take the iterable size as a hint - although filtering out duplicates can still lead to differences.
Disclaimer: I don't know whether any engines implement, or plan to implement, such an optimisation. It might not be worth the effort, especially if the current memory allocation strategy is already good enough to diminish any improvements.