Performance : Immutable.js Map vs Liste vs JS simple

Question

Pregunta

Y a-t-il quelque chose qui ne va pas dans mon benchmark ? Comment Immutable.js find() peut-il être 8 fois plus lent que array.find() ?

Ok, ce n'est pas tout à fait juste, puisque j'utilise Immutable.Map à l'intérieur de Immutable.List. Mais pour moi, c'est un exemple concret. Si j'utilise Immutable.js, c'est pour protéger l'immuabilité et pour gagner en performance sur certains aspects (où le partage structurel entre en jeu). Il n'y aurait aucun intérêt à utiliser Immutable.js uniquement à la racine de l'objet.

Le repère ci-dessous provient en fait de une autre question (le mien aussi). J'ai été tellement surpris par les résultats que j'ai dû le poster séparément pour bien comprendre. Ai-je fait quelque chose de mal dans mes benchmarks, ou la différence de performance est-elle vraiment si importante ?

Contexte

Certaines des données de mon application pourraient être considérées comme des métadonnées d'application. Les données originales se trouvent dans une base de données sur le serveur. Les mises à jour des métadonnées ne sont pas fréquentes. L'application vérifiera la mise à jour des métadonnées au démarrage.

J'utilise Immutable.js partout, mais je vais revenir au js simple pour les métadonnées. Il n'y a pas besoin de partage structurel fantaisiste pour ce type de données.

Le test consiste à trouver les valeurs par clé dans une collection

• Collection de 10 articles

• Trouver une valeur un million de fois

• Mac mini core i7 2.6

Résultat :

• Objet JS simple avec des clés coercitives : 8 ms

• Tableau JS simple utilisant find() : 127 ms

• Immuable.Map avec des clés numériques : 185 ms

• Immutable.List en utilisant find() : 972 ms ! ! Je suis déconcerté

Comme j'utilise React Native, je dois toujours faire attention à la limite de 16 ms si je veux atteindre 60 fps. Les valeurs de référence ne semblent pas être linéaires. L'exécution du test avec seulement 100 consultations prend 1 ms avec Map et 2 ms avec List. C'est assez coûteux.

Code de test

let Immutable = require('immutable');

let mapTest = Immutable.Map()
  .set(1, Immutable.Map({value: 'one'}))
  .set(2, Immutable.Map({value: 'two'}))
  .set(3, Immutable.Map({value: 'three'}))
  .set(4, Immutable.Map({value: 'four'}))
  .set(5, Immutable.Map({value: 'five'}))
  .set(6, Immutable.Map({value: 'six'}))
  .set(7, Immutable.Map({value: 'seven'}))
  .set(8, Immutable.Map({value: 'eight'}))
  .set(9, Immutable.Map({value: 'nine'}))
  .set(10, Immutable.Map({value: 'ten'}));

let listTest = Immutable.fromJS([
  {key: 1,  value: 'one'},
  {key: 2,  value: 'two'},
  {key: 3,  value: 'three'},
  {key: 4,  value: 'four'},
  {key: 5,  value: 'five'},
  {key: 6,  value: 'six'},
  {key: 7,  value: 'seven'},
  {key: 8,  value: 'eight'},
  {key: 9,  value: 'nine'},
  {key: 10, value: 'ten'}
])

let objTest = {
  1:  {value: 'one'},
  2:  {value: 'two'},
  3:  {value: 'three'},
  4:  {value: 'four'},
  5:  {value: 'five'},
  6:  {value: 'six'},
  7:  {value: 'seven'},
  8:  {value: 'eight'},
  9:  {value: 'nine'},
  10: {value: 'ten'}
};

let arrayTest = [
  {key: 1,  value: 'one'},
  {key: 2,  value: 'two'},
  {key: 3,  value: 'three'},
  {key: 4,  value: 'four'},
  {key: 5,  value: 'five'},
  {key: 6,  value: 'six'},
  {key: 7,  value: 'seven'},
  {key: 8,  value: 'eight'},
  {key: 9,  value: 'nine'},
  {key: 10, value: 'ten'}
];

const runs = 1e6;
let i;
let key;
let hrStart;

console.log(' ')
console.log('mapTest -----------------------------')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
  let result = mapTest.getIn([key, 'value'] )
  key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);

console.log(' ')
console.log('listTest -----------------------------')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
  let result = listTest
    .find(item => item.get('key') === key)
    .get('value');
  key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);

console.log(' ')
console.log('arrayTest -----------------------------')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
  let result = arrayTest
    .find(item => item.key === key)
    .value

  key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);

console.log(' ')
console.log('objTest -----------------------------')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
  let result = objTest[key].value
  key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);

Answer 1

La réponse courte est que la représentation des structures de données utilisée par Immutable.js nécessite beaucoup de frais supplémentaires pour itérer dans les éléments d'une liste, par rapport à un tableau JS natif.

Évaluation comparative de Immutable.List.find et Array.find

Votre benchmark est bon, mais nous pouvons simplifier un peu les choses en nous débarrassant de la carte imbriquée. Vous avez raison de prendre en compte les performances pour des problèmes réalistes, mais il peut être utile pour comprendre les différences de performances de simplifier le problème autant que possible. Il est également souvent utile, dans le cadre d'une analyse comparative, d'examiner comment les performances changent en fonction de la taille des entrées. Par exemple, il est possible que dans Immutable.js, List.prototype.find est implémenté de telle sorte que l'appel initial et la configuration prennent un certain temps, mais que l'itération ultérieure dans la liste s'effectue de la même manière que pour les tableaux JS natifs ; dans ce cas, la différence de performance entre les tableaux JS natifs et les listes Immutable.js diminuerait pour les grandes longueurs d'entrée (ce qui ne s'avère pas être le cas).

Créons également notre propre fonction find pour les tableaux JS natifs, Array.prototype.ourFind à comparer avec le natif Array.prototype.find pour déterminer si la différence pourrait en partie être due à la performance des fonctions JS elles-mêmes par rapport à la performance des fonctions intégrées à l'implémentation.

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>

Dans Chrome, j'obtiens :

Length .    Array.find  Array.ourFind   List.find
10          28          13              96
100         60          44              342
1000        549         342             3016
10000       5533        3142            36423

J'ai obtenu des résultats à peu près similaires dans Firefox et Safari. Quelques points à noter :

1. La différence entre List.find contra. Array.find n'est pas simplement due aux implémentations natives (c'est-à-dire intégrées à l'interpréteur) par rapport aux implémentations JS, car une implémentation JS de Array.ourFind est au moins aussi performant que Array.find .
2. Toutes les implémentations fonctionnent en temps O(n) (c'est-à-dire que le temps d'exécution est linéaire par rapport à la longueur de l'entrée). Il faut s'y attendre, car un algorithme de recherche devra toujours travailler en itérant à travers les éléments de la collection jusqu'à ce qu'il en trouve un pour lequel le prédicat retourne vrai.
3. Immutable.List.find est ~6 fois plus lent que Array.find en accord avec les résultats de votre analyse comparative.

Représentation de données Immutable.List

Pour comprendre pourquoi Immutable.List.find est tellement plus lent, vous devez d'abord considérer comment Immutable.List représente le contenu de la liste.

Un moyen rapide d'y parvenir est de générer un fichier Immutable.List et l'examiner dans la console :

console.log(immutListRange(1000));  // immutListRange defined above

Donc, essentiellement, cela ressemble à Immutable.List représente le contenu comme un arbre avec un facteur de branchement de 32.

Considérez maintenant ce qu'il faut faire pour exécuter une opération de recherche sur des données représentées de cette manière. Vous devrez commencer par le nœud racine, parcourir l'arbre jusqu'au premier nœud feuille (qui contient un tableau avec les données réelles), et itérer à travers le contenu de la feuille ; si l'élément n'est pas trouvé, vous devez aller au nœud feuille suivant et rechercher ce tableau, et ainsi de suite. Il s'agit d'une opération plus complexe qu'une simple recherche dans un tableau unique, et son exécution nécessite des frais généraux.

Observer Immutable.List.find au travail

Une excellente façon d'apprécier le travail que Immutable.List.find est de définir un point d'arrêt dans le débogueur de votre choix et de suivre l'opération. Vous verrez que Immutable.List.Find est loin d'être une opération aussi simple que le simple passage en boucle d'un seul tableau.

Commentaires supplémentaires

La représentation arborescente des données dans Immutable.js accélère vraisemblablement d'autres opérations, mais entraîne une pénalité de performance avec certaines fonctions, telles que find.

Soit dit en passant, je ne pense pas que, dans la plupart des cas, le choix d'utiliser des structures de données immuables soit motivé par des considérations de performance. Il peut y avoir des cas où les structures de données immuables sont plus performantes que les structures mutables (et il est certain que les structures de données immuables rendent le calcul parallèle moins complexe, ce qui permet un gain de performance significatif), mais il y aura de nombreux cas où le contraire sera vrai. Dans la plupart des cas, le choix de l'immuabilité est plutôt dicté par des considérations de conception, c'est-à-dire que l'utilisation de structures de données immuables oblige à concevoir des programmes qui seront plus robustes et, à long terme, augmenteront la productivité des développeurs.

Answer 2

Les moteurs JS sont très bons pour optimiser les opérations "chaudes", c'est-à-dire celles qui se répètent souvent et qui sont aussi simples que possible (par exemple TurboFan en V8 ). Les objets JS ordinaires et les fonctions de tableau sont toujours va battre une bibliothèque comme Immutable.js, où List appelle Collection appelle Seq appelle Operations (et ainsi de suite), surtout lorsque les actions sont répétées de nombreuses fois.

Immutable.js semble avoir été conçu pour la commodité d'utilisation et pour éviter une grande partie des désagréments des collections JS mutables, plutôt que pour la performance pure.

Si vous avez un million de choses, utilisez un objet ou un tableau JS de bas niveau (ou un Web Assembly, si les performances sont critiques). Si vous avez un millier de choses et necesito pour être certain de ne pas faire tomber un cadre, le JS simple reste la solution. Il s'agit toutefois de cas particuliers - pour la plupart des cas d'utilisation, la commodité d'Immutable.js vaut la réduction de vitesse.

Answer 3

Le benchmark ne prend pas en compte tous les types de données qu'Immutable a à offrir. Immutable possède en fait certaines caractéristiques que les objets/rays ordinaires n'ont pas : Ensemble ordonné y Carte ordonnée présentent les avantages des tableaux indexés/List et des structures basées sur des clés comme object/Map.

Vous trouverez ci-dessous une version adaptée du test joliment réalisé par @Keith, qui montre que nous pouvons effectivement devenir plus rapides que Array.find, surtout avec de grands ensembles de données.

Bien sûr, cela a aussi un coût :

• Set/Map n'autorise pas les doublons (pas différent de l'objet cependant).
• Dans les coulisses, les variantes ordonnées combinent un Map/Set avec une liste, ce qui consomme plus de mémoire.

Notez que les OrderedSet sont plus coûteux que les Set non ordonnés et peuvent consommer plus de mémoire. OrderedSet#add est amorti O(log32 N), mais n'est pas stable.

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 = 1e5,
  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>

Exemples de résultats, dans Chrome 86 :

        Array.find   OrderedSet.find
100        10             18
1000       10              6
10000      74             10
100000    346             11