Производительность: Immutable.js Map vs List vs plain JS

Ответ 1

Короткий ответ заключается в том, что для представления структур данных, используемых Immutable.js, требуется много дополнительных накладных расходов для итерации элементов списка, по сравнению с собственным массивом JS.

Бенчмаркинг Immutable.List.find и Array.find

Ваш тест хорош, но мы можем немного упростить ситуацию, избавившись от вложенной карты; вы правы, чтобы рассматривать производительность для реалистичных проблем, но это может быть полезно для понимания различий в производительности, чтобы максимально упростить проблему. Это также часто полезно в бенчмаркинге для рассмотрения того, как изменения производительности изменяются по разным размерам ввода. Например, возможно, что в Immutable.js List.prototype.find реализовано таким образом, что интимный вызов и настройка занимают некоторое время, но последующая итерация через List выполняет аналогично встроенным массивам JS; в этом случае разница в производительности между собственными массивами JS и списками Immutable.js будет уменьшаться для длинных входных длин (это оказывается не так).

Давайте также создадим нашу собственную функцию поиска для собственных массивов JS, Array.prototype.ourFind, чтобы сравнить с нативной Array.prototype.find, чтобы определить, может ли разница быть частично из-за производительности самих функций JS и производительности встроенных функций, к реализации.

Array.prototype.ourFind = function(predicate) {
  for (let i = 0; i < this.length; i++) {
    if (predicate(this[i])) return this[i];
  }
}

function arrayRange(len) {
  return new Array(len).fill(null).map((_, i) => i);
}

function immutListRange(len) {
  return Immutable.fromJS(arrayRange(len));
}

function timeFind(coll, find, iters) {
  let startTime = performance.now();
  for (let i = 0; i < iters; i++) {
    let searchVal = i % coll.length,
      result = find.call(coll, item => item === searchVal);
  }
  return Math.floor(performance.now() - startTime);
}

const MIN_LEN = 10,
  MAX_LEN = 1e4,
  ITERS = 1e5;

console.log('\t\tArray.find\tArray.ourFind\tList.find');
for (let len = MIN_LEN; len <= MAX_LEN; len *= 10) {
  console.log(`${len}\t\t\t` +
    `${timeFind(arrayRange(len), Array.prototype.find, ITERS)}\t\t\t` +
    `${timeFind(arrayRange(len), Array.prototype.ourFind, ITERS)}\t\t\t` +
    `${timeFind(immutListRange(len), Immutable.List.prototype.find, ITERS)}`)
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/immutable/3.8.1/immutable.js"></script>

Ответ 2

JS-двигатели очень хорошо оптимизируют "горячие" операции - те, которые многократно повторяются и которые максимально просты (например, TurboFan в V8). Обычные объекты JS и функции массива всегда будут бить библиотеку, такую ​​как Immutable.js, где List вызывает Collection вызывает Seq вызывает Operations (и так далее), особенно когда действия повторяются много раз.

Immutable.js, по-видимому, предназначен для удобства использования и избегает многих неприятностей изменчивых коллекций JS, а не чистой производительности.

Если у вас есть миллион вещей, используйте объект или массив JS низкого уровня (или веб-сборку, если производительность критическая). Если у вас есть тысяча вещей и нужно быть уверенным в том, чтобы не отбрасывать кадр, тогда простой JS по-прежнему остается. Однако это специализированные случаи - для большинства случаев использование Immutable.js стоит снижения скорости.

Ответ 3

Тест не учитывает все типы данных, которые предлагает Immutable. Immutable на самом деле имеет некоторые особенности, которых нет у простых объектов/массивов: OrderedSet и OrderedMap обладают преимуществами как индексированных массивов /List, так и основанных на ключе структур, таких как object/Map.

Ниже приведена адаптированная версия прекрасно выполненного теста @Keith, которая показывает, что мы можем на самом деле стать быстрее, чем Array.find, особенно с большими наборами данных.

Конечно, это тоже стоит дорого:

• Set/Map не допускает дублирование (не отличается от объекта, хотя).
• За кулисами упорядоченные варианты объединяют карту/набор со списком, поэтому они занимают больше памяти.

Обратите внимание, что OrderedSet дороже, чем неупорядоченный набор, и может занимать больше памяти. OrderedSet # add амортизируется O (log32 N), но не стабильно.

function arrayFind(coll, searchVal) {
  return coll.find(item => item === searchVal);
}

function immutableSetGet(coll, searchVal) {
  return coll.get(searchVal);
}

function arrayRange(len) {
  return new Array(len).fill(null).map((_, i) => i);
}

function immutOrderedSetRange(len) {
  return Immutable.OrderedSet(arrayRange(len));
}

function timeFind(what, coll, find, iters) {
  let startTime = performance.now();
  let size = coll.length || coll.size;
  for (let i = 0; i < iters; i++) {
    let searchVal = i % size,
      result = find(coll, searchVal);
  }
  return Math.floor(performance.now() - startTime);
}

const MIN_LEN = 100,
  MAX_LEN = 1e4,
  ITERS = 50000;

console.log('\t\t\tArray.find\tOrderedSet.find');
for (let len = MIN_LEN; len <= MAX_LEN; len *= 10) {
  console.log('${len}\t\t\t' +
    '${timeFind('find', arrayRange(len), arrayFind, ITERS)}\t\t' +
    '${timeFind('set', immutOrderedSetRange(len), immutableSetGet, ITERS)}')
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/immutable/3.8.1/immutable.js"></script>