Nous sommes habitués au fait que les collections standard dans le JDK sont assez bien faites et se comportent intuitivement. Mais est-ce vraiment le cas? Hier Roman Elizarovelizarova publié sur Twitter les nouvelles d'un nouveau montant intéressant.Tenez bon: Set.removeAll(list)dans certains cas, cela peut fonctionner pour O (N²). Comment?
Roman a découvert un problème en déboguant un code qui, pour une raison incroyable, fonctionnait trop lentement. Il l'a lancé dans le profileur intégré dans IntelliJ IDEA et a instantanément vu sur le graphique de la flamme qu'il perdait tout le temps à l'intérieur de la méthode AbstractSet.removeAlllors d'un appel list.contains(lien vers l' emplacement exact dans le code ).Pour comprendre ce qui se passe, considérons un exemple légèrement différent. Plus tôt, Jon Skeet a écrit un article "Il y a un trou dans mon abstraction, chère Liza, chère Liza" , dans lequel il considère le cas intéressant suivant.Disons que nous avons un HashSet à partir duquel nous allons supprimer quelque chose. Supposons que nous supprimions des éléments d'une autre collection B d'une collection A. Il arrive souvent que de nombreux éléments de B n'existent tout simplement pas dans A. Nous analyserons un cas spécial où A et B ne se coupent pas du tout - c'est-à-dire, rien ne doit être fait.Nous allons écrire un programme simple dans lequel les tailles de nos collections sont définies à partir de la ligne de commande. Pour que ces ensembles ne se coupent pas exactement, nous remplissons l'un d'eux uniquement avec des nombres positifs et l'autre avec des nombres négatifs uniquement. Ensuite, nous supprimons de la première collection tous les éléments de la seconde et mesurons le temps écoulé en utilisantSystem.currentTimeMillis(). Ce n'est pas la meilleure façon au monde de calculer l'intervalle de temps, mais cela permet de copier-coller le code directement de Habr vers Idea et nous évite d'avoir à mettre en place un nouveau projet Maven pour JMH.import java.util.*;
public class Test {
public static void main(String[] args) {
int sourceSize = Integer.parseInt(args[0]);
int removalsSize = Integer.parseInt(args[1]);
Set<Integer> source = new HashSet<Integer>();
Collection<Integer> removals = new ArrayList<Integer>();
for (int i = 0; i < sourceSize; i++) {
source.add(i);
}
for (int i = 1; i <= removalsSize; i++) {
removals.add(-i);
}
long start = System.currentTimeMillis();
source.removeAll(removals);
long end = System.currentTimeMillis();
System.out.println("Time taken: " + (end - start) + "ms");
}
}
Code très simple qui peut être écrit sans reprendre conscience. Maintenant, exécutons-le avec différents paramètres. Tout d'abord, essayez un ensemble de 100 éléments dont vous devez lancer 100:$ java Test 100 100
Time taken: 1ms
Jusqu'à présent, tout est assez rapide, mais que se passe-t-il si vous augmentez le nombre?java Test 1000000 300000
Time taken: 38ms
$java Test 300000 300000
Time taken: 178131ms
Comment aimez-vous cela: maintenant, nous attendons trois minutes. Il semble intuitivement que le temps de traitement d'une collection plus petite (300 000 articles dans le deuxième cas) devrait être inférieur à celui du traitement d'une collection plus grande (un million d'articles dans le premier cas). Immédiatement l'opposé est vrai. La vie ne s'y préparait pas, non?Maintenant, le secret de la concentration.En fait, il est décrit en texte clair dans le JavaDoc correspondant :Le code d'implémentation détermine s'il est inférieur: ensemble ou collection. Cela se fait en utilisant la méthode sizesur chacun d'eux. S'il y a moins d'éléments dans l'ensemble, l'itération est effectuée sur l'ensemble et à chaque itération, il est vérifié si l'élément actuel se trouve dans la collection. Si oui, l'élément est supprimé de l'ensemble à l'aide de la méthode removeitérateur. S'il s'avère que la collection est plus petite en nombre d'éléments, alors il sera déjà nécessaire de contourner la collection, en supprimant de l'ensemble tous ces éléments en utilisant la méthode removede set.
En pratique, cela signifie que lorsqu'il est appelé source.removeAll(removals):- Si la collection est
removalsplus petite que source, la méthode est appelée removedans HashSet, et il est assez rapide; - Si la collection est
removalsplus grande ou de taille égale à source, alors une méthode est appelée removals.containsqui fonctionne très lentement pour ArrayList.
Dans JDK 8, quelque chose comme ça est responsable de ce morceau de code:public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
if (size() > c.size()) {
for (Iterator<?> i = c.iterator(); i.hasNext(); )
modified |= remove(i.next());
} else {
for (Iterator<?> i = iterator(); i.hasNext(); ) {
if (c.contains(i.next())) {
i.remove();
modified = true;
}
}
}
return modified;
}
Il semble que le JDK ait choisi une manière plutôt médiocre de faire face à la tâche, mais comme il est déjà décrit dans JavaDoc, il n'y a pas de retour en arrière.Ou y en a-t-il?Les gens se sont précipités sur le tweet de Roman Elizarov, et Zheka Kozlov a trouvé le bug correspondant publié sur JDK 15 avec l'artiste, Stuart Marx.Et après cela, Stuart Marx lui-même a fait irruption dans le fil et a confirmé qu'il traitait vraiment ce problème:Il y a donc de la lumière au bout du tunnel. Si vous effectuez une mise à niveau vers les dernières versions de Java, bien sûr.résultats
Les conclusions de cette histoire sont les suivantes: il y a un problème à connaître. Le problème est déjà en cours de réparation, mais uniquement pour les utilisateurs satisfaits de Java frais, et vous ne devriez pas vraiment l'espérer.En général, lorsque vous essayez de stocker un grand nombre de données dans des collections en Java, vous pouvez rencontrer divers problèmes non intuitifs auxquels vous devez vous préparer.
Alors, les enfants, aujourd'hui, nous avons appris quelque chose de nouveau!Dans le prolongement du banquet, je vous recommande de consulter certains rapports de Roman Elizarov, qui a aidé à mettre ce bug en lumière. Bien sûr, ces rapports n'ont rien à voir avec le bogue lui-même, mais il existe un tas de plaques d'étain différentes:JPoint, , 2020 . , , , .