Una storia di due iteratori: strategie di modifica competitiva in Java

L'autore della nota è Grzegorz Mirek, uno sviluppatore di software di Cracovia (Polonia). Ha iniziato a sviluppare in Java circa 6 anni fa, mentre era ancora all'università, e da allora ha affinato instancabilmente le sue competenze in quest'area. È particolarmente interessato alle prestazioni e all'ottimizzazione della JVM, di cui scrive principalmente sul suo blog . Alcune delle domande più popolari nelle interviste Java includono: Qual è la differenza tra iteratori fail-fast e fail-safe? La risposta più semplificata a questa domanda è: un iteratore fail-fast lancia un'eccezione ConcurrentModificationException se la raccolta cambia durante l'iterazione, ma un iteratore fail-safe no. Sebbene ciò sembri abbastanza significativo, non è chiaro cosa intenda l'intervistatore per fail-safe? Le specifiche del linguaggio Java non definiscono questo termine in relazione agli iteratori. Tuttavia, ci sono quattro strategie di modifica competitiva.

Modifica competitiva

Innanzitutto, definiamo cos'è la modifica competitiva (o parallela). Diciamo che abbiamo una raccolta e quando l'iteratore è attivo, si verificano alcune modifiche che non provengono da questo iteratore. In questo caso, otteniamo una modifica competitiva. Lascia che ti faccia un semplice esempio: diciamo che abbiamo diversi thread. Il primo thread esegue un'iterazione e il secondo thread inserisce o rimuove elementi dalla stessa raccolta. Tuttavia, possiamo ottenere una ConcurrentModificationException durante l'esecuzione in un ambiente a thread singolo:

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

Fallisci velocemente

Il frammento di codice riportato sopra è un esempio di iteratore fail-fast . Come puoi vedere, è stata lanciata una ConcurrentModificationException durante il tentativo di recuperare il secondo elemento dall'iterator . Come fa un iteratore a sapere che la raccolta è stata modificata da quando è stata creata? Ad esempio, la raccolta potrebbe avere un indicatore di data/ora, ad esempio lastModified . Quando crei un iteratore, dovresti copiare questo campo e memorizzarlo in un oggetto iteratore. Quindi, ogni volta che viene chiamato il metodo next() , confronterai semplicemente il valore lastModified della raccolta con la copia dell'iteratore. Un approccio molto simile viene utilizzato, ad esempio, nell'implementazione della classe ArrayList . Ha una variabile di istanza modCount che memorizza il numero di volte in cui l'elenco è stato modificato:

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

È importante notare che gli iteratori fail-fast operano in modo ottimale, il che significa che non vi è alcuna garanzia che venga generata una ConcurrentModificationException in caso di una modifica simultanea. Quindi non dovresti fare affidamento su di loro, piuttosto dovrebbero essere usati per rilevare errori. La maggior parte delle raccolte non simultanee fornisce iteratori fail-fast .

Coerenza debole

La maggior parte delle raccolte simultanee nel pacchetto java.util.concurrent (come ConcurrentHashMap e la maggior parte di Queue ) forniscono iteratori poco coerenti. Il significato di questo termine è spiegato molto bene nella documentazione :

• Possono essere elaborati contemporaneamente ad altre operazioni
• Non lanciano mai una ConcurrentModificationException
• È garantito che attraverseranno gli elementi esistenti nel momento in cui l'iteratore è stato creato esattamente una volta e possono (ma non sono tenuti a) riflettere le modifiche successive.

Istantanea

Con questa strategia, l'iteratore è associato allo stato della raccolta al momento della sua creazione: si tratta di un'istantanea della raccolta. Qualsiasi modifica apportata alla raccolta originale comporta la creazione di una nuova versione della struttura dati sottostante. Ciò lascia invariata la nostra istantanea, quindi non riflette le modifiche alla raccolta avvenute dopo la creazione dell'iteratore. Questa è la buona vecchia tecnica copy-on-write (COW) . Risolve completamente il problema delle modifiche simultanee, quindi con questo approccio non viene generata una ConcurrentModificationException . Inoltre, gli iteratori non supportano le operazioni che modificano gli elementi. Le raccolte copy-on-write tendono ad essere troppo costose da utilizzare, ma ha senso utilizzarle se le modifiche si verificano molto meno frequentemente rispetto agli attraversamenti degli iteratori. Esempi sono le classi CopyOnWriteArrayList e CopyOnWriteArraySet .

Comportamento indefinito

Potresti riscontrare un comportamento indefinito nei tipi di raccolte legacy come Vector e Hashtable . Entrambi hanno iteratori standard fail-fast , ma in più consentono l'uso di implementazioni dell'interfaccia Enumeration e non sanno come comportarsi in caso di modifiche simultanee. Potresti riscontrare alcuni elementi ripetuti o mancanti, o anche alcune strane eccezioni. È meglio non giocare con loro!