Pénalité de performance inattendue en Java

J’ai implémenté une liste GapBuffer en Java et je ne comprends pas pourquoi cela entraîne une telle pénalité en termes de performances. Un code similaire écrit en C # se comporte comme prévu: l’insertion au milieu de la liste est beaucoup plus rapide que la mise en oeuvre de C # par List. Mais la version Java se comporte étrangement.

Voici quelques informations de benchmarking:

Adding/removing 10,000,000 items @ the end of the dynamic array... ArrayList: 683 milliseconds GapBufferList: 416 milliseconds Adding/removing 100,000 items @ a random spot in the dynamic array... - ArrayList add: 721 milliseconds - ArrayList remove: 612 milliseconds ArrayList: 1333 milliseconds - GapBufferList add: 1293 milliseconds - GapBufferList remove: 2775 milliseconds GapBufferList: 4068 milliseconds Adding/removing 100,000 items @ the beginning of the dynamic array... ArrayList: 2422 milliseconds GapBufferList: 13 milliseconds Clearly, the GapBufferList is the better option.

Comme vous pouvez le constater, lorsque vous insérez au début de la liste, le tampon d’écart se comporte comme prévu: il est beaucoup, beaucoup, bien mieux que ArrayList. Cependant, lors de l’insertion et de la suppression en un point aléatoire de la liste, le tampon d’intervalle a une pénalité de performance étrange que je ne peux pas expliquer. Encore plus étrange, le fait de supprimer des éléments de GapBufferList est plus lent que de les append. Selon tous les tests que j’ai effectués jusqu’à présent, il faut environ trois fois plus de temps pour supprimer un élément que pour en append un, malgré le fait que leur code est presque identique:

 @Override public void add(int index, T t) { if (index  back.length - gapSize) throw new IndexOutOfBoundsException(); if (gapPos > index) { int diff = gapPos - index; for (int q = 1; q  gapPos) { int diff = gapPos - index; for (int q = 0; q < diff; q++) back[gapPos + q] = back[gapPos + gapSize + q]; } gapPos = index; if (gapSize == 0) increaseSize(); back[gapPos++] = t; gapSize--; } @Override public T remove(int index) { if (index = back.length - gapSize) throw new IndexOutOfBoundsException(); if (gapPos > index + 1) { int diff = gapPos - (index + 1); for (int q = 1; q <= diff; q++) back[gapPos - q + gapSize] = back[gapPos - q]; } else { int diff = (index + 1) - gapPos; for (int q = 0; q < diff; q++) back[gapPos + q] = back[gapPos + gapSize + q]; } gapSize++; return back[gapPos = index]; }

Vous trouverez le code du tampon de l’espace ici , et celui du point d’entrée du repère, ici . (Vous pouvez remplacer toute référence à Flow.***Exception avec RuntimeException .)

Vous copiez manuellement tout le contenu du tableau. Utilisez plutôt System.arraycopy. C’est beaucoup plus rapide qu’une copie manuelle (c’est natif et utilise une magie spéciale). Aussi, vous pouvez regarder la source ArrayList, elle déplace certainement des éléments avec System.arraycopy et non pas un par un.

A propos des performances différentes des méthodes d’ajout / suppression. Ecrire des micro-repères en Java n’est pas une tâche facile. Pour plus de détails, lisez Comment écrire un micro-benchmark correct en Java? Il est difficile de dire ce qui se passe exactement dans votre cas. Mais je vois que vous remplissez d’abord votre liste et que vous n’en supprimez que les éléments. Dans ce scénario, seule la twig (index> gapPos) est exécutée. Ainsi, si JIT comstack ce code, une prédiction de twig CPU peut avoir lieu, ce qui accélérera davantage ce code (car la première twig est peu probable dans votre scénario de test). L’enlèvement touchera les deux twigs presque autant de fois et aucune optimisation ne pourra avoir lieu. Il est donc très difficile de dire ce qui se passe réellement. Vous devriez essayer d’autres modèles d’access, par exemple. Ou tableau spécialement conçu avec un espace vide à l’intérieur. Ou d’autres exemples. Et vous devriez aussi sortir quelques informations de débogage à partir de la machine virtuelle Java, cela peut être utile

  public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // Let gc do its work return oldValue; }

C’est la source de la méthode remove d’ArrayList. Puisqu’il utilise System.arraycopy (assez intelligemment) et que vous utilisez des boucles, les scores ArrayList. Essayez de mettre en œuvre quelque chose de similaire et vous verrez des performances similaires.