Estamos acostumbrados al hecho de que las colecciones estándar en el JDK se hacen bastante bien y se comportan de manera intuitiva. Pero, ¿es realmente así? Ayer Roman Elizarovelizarovpublicó en Twitter las noticias sobre una nueva jamba interesante.Agárrate fuerte: Set.removeAll(list)en ciertos casos puede funcionar para O (N²). ¿Cómo es eso?
Roman descubrió un problema cuando depuró un código que, por una razón sorprendente, funcionó muy lentamente. Lo lanzó en el generador de perfiles incorporado en IntelliJ IDEA e instantáneamente vio en el gráfico de la llama que estaba perdiendo todo el tiempo dentro del método AbstractSet.removeAllen una llamada list.contains(enlace al lugar exacto en el código ).Para entender lo que está sucediendo, considere un ejemplo ligeramente diferente. Anteriormente, Jon Skeet escribió una publicación "Hay un agujero en mi abstracción, querida Liza, querida Liza" , en el que considera el siguiente caso interesante.Digamos que tenemos un HashSet del que vamos a eliminar algo. Supongamos que eliminamos elementos de otra colección B de una colección A. A menudo sucede que muchos elementos de B simplemente no existen en A. Analizaremos un caso especial cuando A y B no se cruzan en absoluto, es decir, no es necesario hacer nada.Escribiremos un programa simple en el que los tamaños de nuestras colecciones se establecen desde la línea de comandos. Para que estos conjuntos no se crucen exactamente, uno de ellos se completará solo con números positivos y el otro solo con números negativos. Luego eliminamos de la primera colección todos los elementos de la segunda y medimos el tiempo transcurrido usandoSystem.currentTimeMillis(). Esta no es la mejor manera del mundo para calcular el intervalo de tiempo, pero permite copiar y pegar el código directamente de Habr a Idea y nos evita tener que configurar un nuevo proyecto Maven para 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");
}
}
Código muy simple que se puede escribir sin recuperar la conciencia. Ahora vamos a ejecutarlo con diferentes parámetros. Primero, intente un conjunto de 100 elementos de los que necesita lanzar 100:$ java Test 100 100
Time taken: 1ms
Hasta ahora, todo es lo suficientemente rápido, pero ¿qué sucede si aumenta los números?java Test 1000000 300000
Time taken: 38ms
$java Test 300000 300000
Time taken: 178131ms
¿Qué te parece esto? Ahora esperamos tres minutos. Parece intuitivamente que el tiempo de procesamiento de una colección más pequeña (300,000 artículos en el segundo caso) debería ser menor que cuando se procesa una colección más grande (un millón de artículos en el primer caso). Inmediatamente lo contrario es cierto. La vida no se estaba preparando para esto, ¿verdad?Ahora el secreto del foco.De hecho, se describe en texto claro en el JavaDoc correspondiente :El código de implementación determina si es menor: conjunto o colección. Esto se hace usando el método sizeen cada uno de ellos. Si hay menos elementos en el conjunto, la iteración se realiza en el conjunto y en cada iteración se verifica si el elemento actual está en la colección. En caso afirmativo, el elemento se elimina del conjunto utilizando el método removeiterador. Si resulta que la colección es más pequeña en el número de elementos, entonces será necesario omitir la colección ya, eliminando del conjunto todos esos elementos utilizando el método removede conjunto.
En la práctica, esto significa que cuando se llama source.removeAll(removals):- Si la colección es
removalsmás pequeño que source, a continuación, se llama al método removeen HashSet, y es bastante rápido; - Si la colección es
removalsmás grande o igual en tamaño que source, entonces se llama a un método removals.containsque funciona muy lentamente ArrayList.
En JDK 8, algo como esto es responsable de este fragmento de código: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;
}
Parece que el JDK ha elegido una forma bastante pobre de hacer frente a la tarea, pero como ya se describe en JavaDoc, no hay vuelta atrás.O hayLa gente corrió al tuit de Roman Yelizarov, y Zheka Kozlov encontró un error correspondiente publicado en JDK 15 con el artista, Stuart Marx.Y después de esto, el propio Stuart Marx irrumpió en el hilo y confirmó que realmente estaba lidiando con este problema:Entonces hay luz al final del túnel. Si actualiza a las últimas versiones de Java, por supuesto.recomendaciones
Las conclusiones de esta historia son las siguientes: hay un problema que vale la pena conocer. El problema ya se está reparando, pero se reparó solo para usuarios felices de Java reciente, y realmente no debería esperarlo.En general, cuando intenta almacenar una gran cantidad de datos en colecciones en Java, puede experimentar varios problemas poco intuitivos para los que necesita estar preparado.
Entonces, niños, ¡hoy aprendimos algo nuevo!Como continuación del banquete, le recomiendo que mire algunos informes de Roman Elizarov, quien ayudó a sacar este error a la luz. Por supuesto, estos informes no tienen nada que ver con el error en sí, pero hay un montón de láminas diferentes:JPoint, , 2020 . , , , .