Una historia de dos iteradores: estrategias de modificación competitiva en Java

El autor de la nota es Grzegorz Mirek, un desarrollador de software de Cracovia (Polonia). Comenzó a desarrollarse en Java hace unos 6 años, cuando aún estaba en la universidad, y desde entonces ha ido puliendo incansablemente sus habilidades en esta área. Está particularmente interesado en el rendimiento y la optimización de JVM, que es sobre lo que escribe principalmente en su blog . Algunas de las preguntas más populares de las entrevistas sobre Java incluyen: ¿ Cuál es la diferencia entre iteradores rápidos y a prueba de fallos? La respuesta más simplificada a esto es: un iterador a prueba de fallas arroja una excepción ConcurrentModificationException si la colección cambia durante la iteración, pero un iterador a prueba de fallas no. Aunque esto suena bastante significativo, aún no está claro qué quiere decir el entrevistador con "a prueba de fallos". Las Especificaciones del lenguaje Java no definen este término en relación con los iteradores. Sin embargo, existen cuatro estrategias de modificación competitiva.

Modificación competitiva

Primero, definamos qué es la modificación competitiva (o paralela). Digamos que tenemos una colección y cuando el iterador está activo, ocurren algunos cambios que no provienen de este iterador. En este caso, obtenemos una modificación competitiva. Déjame darte un ejemplo simple: digamos que tenemos varios hilos. El primer hilo itera y el segundo inserta o elimina elementos de la misma colección. Sin embargo, podemos obtener una excepción ConcurrentModificationException cuando ejecutamos en un entorno de un solo subproceso:

List<String> cities = new ArrayList<>();
cities.add(“Warsaw”);
cities.add(“Prague”);
cities.add(“Budapest”);

Iterator<String> cityIterator = cities.iterator();
cityIterator.next();
cities.remove(1);
cityIterator.next(); // генерирует ConcurrentModificationException

Fallar rapido

El fragmento de código anterior es un ejemplo de un iterador a prueba de fallos . Como puede ver, se lanzó una excepción ConcurrentModificationException al intentar recuperar el segundo elemento del iterador . ¿Cómo sabe un iterador que la colección ha sido modificada desde que se creó? Por ejemplo, la colección podría tener una marca de fecha y hora, por ejemplo, lastModified . Al crear un iterador, debes copiar este campo y almacenarlo en un objeto iterador. Luego, cada vez que llame al método next() , simplemente comparará el valor lastModified de la colección con la copia del iterador. Se utiliza un enfoque muy similar, por ejemplo, en la implementación de la clase ArrayList . Tiene una variable de instancia modCount que almacena el número de veces que se ha modificado la lista:

final void checkForComodification() {
   if (modCount != expectedModCount)
       throw new ConcurrentModificationException();
}

Es importante tener en cuenta que los iteradores a prueba de fallos funcionan con la mejor calidad de su clase, lo que significa que no hay garantía de que se genere una excepción ConcurrentModificationException en caso de una modificación simultánea. Por lo tanto, no debería confiar en ellos; más bien, debería utilizarlos para detectar errores. La mayoría de las colecciones no concurrentes proporcionan iteradores a prueba de fallos .

Consistencia débil

La mayoría de las colecciones concurrentes en el paquete java.util.concurrent (como ConcurrentHashMap y la mayoría de Queue ) proporcionan iteradores débilmente consistentes. El significado de este término está muy bien explicado en la documentación :

• Se pueden procesar simultáneamente con otras operaciones.
• Nunca lanzan una excepción ConcurrentModificationException
• Se garantiza que atravesarán elementos existentes en el momento en que se creó el iterador exactamente una vez y pueden (pero no están obligados a hacerlo) reflejar modificaciones posteriores.

Instantánea

Con esta estrategia, el iterador está asociado con el estado de la colección en el momento de su creación; esta es una instantánea de la colección. Cualquier cambio realizado en la colección original da como resultado la creación de una nueva versión de la estructura de datos subyacente. Esto deja nuestra instantánea sin cambios, por lo que no refleja los cambios en la colección que ocurrieron después de que se creó el iterador. Esta es la vieja técnica de copia en escritura (COW) . Resuelve completamente el problema de las modificaciones concurrentes, por lo que no se genera una excepción ConcurrentModificationException con este enfoque. Además, los iteradores no admiten operaciones que cambien elementos. Las colecciones de copia en escritura tienden a ser demasiado costosas de usar, pero tiene sentido usarlas si los cambios ocurren con mucha menos frecuencia que los recorridos de iteradores. Algunos ejemplos son las clases CopyOnWriteArrayList y CopyOnWriteArraySet .

Comportamiento indefinido

Es posible que encuentre un comportamiento indefinido en tipos de colecciones heredadas, como Vector y Hashtable . Ambos tienen iteradores estándar a prueba de fallos , pero además permiten el uso de implementaciones de la interfaz Enumeration y no saben cómo comportarse en caso de modificación concurrente. Es posible que algunos elementos se repitan o falten, o incluso algunas excepciones extrañas. ¡Es mejor no jugar con ellos!