Можно ли предварительно выделить память для карты / набора с известным количеством элементов?

Question

В случае массива JS можно создать массив с предварительно определенной длиной. Если мы передадим длину конструктору, например, new Array(itemCount), механизм JS может предварительно выделить память для массива, поэтому не потребуется перераспределять ее, пока новые элементы добавляются в массив.

Можно ли предварительно выделить память для Map или Set? Он не принимает длину в конструкторе, как массив. Если вы знаете, что карта будет содержать 10 000 элементов, было бы гораздо эффективнее распределить память один раз, чем перераспределять ее несколько раз.

Вот тот же вопрос о массивах.

---

В комментариях обсуждается, влияет ли предопределенный размер массива на производительность или нет. Я создал простой тест , чтобы проверить его, результат:

• Chrome - заполнение массива с заданным размером примерно в 3 раза быстрее
• Firefox - нет большой разницы, но массив с предопределенной длиной немного быстрее
• Edge - заполнение массива предопределенного размера примерно в 1,5 раза быстрее

---

Существует предложение создать массив записей и передать его на карту, чтобы карта могла взять длину из массива. Я также создал такой тест , результат:

• Chrome - построение карты, которая принимает массив записей, примерно в 1,5 раза медленнее
• Firefox - нет разницы
• Edge - передача массива записей в конструктор Map примерно в 1,5 раза быстрее

Answer 1

Нет способа повлиять на то, как движок распределяет память, поэтому, что бы вы ни делали, вы не можете гарантировать , что используемый вами прием работает на каждом движке или даже на другой версии того же движка.

Однако в JS есть типизированные массивы, это единственные структуры данных с фиксированным размером. С их помощью вы можете реализовать свой собственный hashmap с фиксированным размером.

Очень наивная реализация немного быстрее ² при вставке, не уверен, как она ведет себя при чтениях и других (также он может хранить только 8-битные целые числа> 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");

---

_{² Маркетинг сказал бы Это на 20% быстрее! и я бы сказал Это до На 2 мс быстрее, и я потратил на это более 10 минут ...}

Answer 2

Нет, это невозможно. Сомнительно даже, что трюк Array(length) все еще работает, движки стали намного лучше оптимизировать назначения массивов и, возможно, выбрали другую стратегию для (предварительного) определения объема выделяемой памяти.

Для Map s и Set s, такого трюка не существует. Лучше всего создавать их, передавая итерируемый конструктор, например new Map(array), вместо использования методов set / add. Это по крайней мере дает возможность для движка принять итеративный размер в качестве подсказки - хотя фильтрация дубликатов все же может привести к различиям.
Отказ от ответственности: я не знать, реализуют или планируют ли какие-либо двигатели такую ​​оптимизацию. Это может не стоить усилий, особенно если текущая стратегия выделения памяти уже достаточно хороша, чтобы минимизировать sh любые улучшения.