C'è un'alternativa migliorata all'implementazione Java CopyonWriteArrayList e come posso richiedere una modifica a Java Specs?

StackOverflow https://stackoverflow.com//questions/21008033

  •  21-12-2019
  •  | 
  •  

Domanda

CopyonWriteArrayList ha quasi il comportamento che voglio, e se le copie non necessarie sono state rimosse, sarebbe esattamente quello che sto cercando. In particolare, potrebbe agire esattamente come Arraylist per aggiunge fatto alla fine dell'arraylist - I.e. Non c'è motivo di effettuare una nuova copia ogni singola volta che è così dispendiosa. Potrebbe solo limitare virtualmente la fine dell'arraylist per catturare l'istantanea per i lettori e aggiornare la fine dopo che i nuovi elementi vengono aggiunti.

Questo miglioramento sembra che valererebbe da allora per molte applicazioni il tipo più comune di aggiunta sarebbe alla fine dell'arraylist - che è anche un motivo per scegliere di utilizzare un arrayList per cominciare.

Non ci sarebbe anche un sovraccarico extra poiché non poteva solo copiare quando si aggiungeva e sebbene dovrà comunque verificare se una ridimensionamento è necessario che Arraylist è necessario farlo comunque.

    .

  1. Esiste un'implementazione alternativa o una struttura dati che ha questo comportamento senza le copie non necessarie per aggiunte alla fine (cioè, cabina del thread e ottimizzate per consentire le read frequenti con scritture solo aggiuntive alla fine della lista )?

  2. Come posso inviare una richiesta di modifica per richiedere una modifica alla specifica Java per eliminare le copie per aggiunte alla fine di un copyOnWriteArrayList (a meno che non sia necessario una ridimensionamento)?

    3. Mi è piaciuto molto vederlo cambiato con le librerie Java Core piuttosto che mantenere e usare il mio codice personalizzato.

È stato utile?

Soluzione

Per rispondere alle tue domande:

    .

  1. Non sono a conoscenza di un'implementazione alternativa che è un'elenco completamente funzionale.

  2. Se la tua idea è veramente praticabile, posso pensare a un certo numero di modi per procedere:

      .

    • È possibile inviare "richieste di miglioramento" (RFE) tramite il database Java Bugs. Tuttavia, in questo caso dubito che avrai una risposta positiva. (Certamente, non uno tempestivo!)

    • È possibile creare un problema RFE su Guava o Apache Commons Problemi Tracker. Questo potrebbe essere più fruttuoso, anche se dipende da convincarli ...

    • Puoi inviare una patch al team OpenJDK con un'implementazione della tua idea. Non posso dire cosa potrebbe essere il risultato ...

    • È possibile inviare una patch (come sopra) a Guava o Apache Commons tramite i rispettivi tracker di problemi. Questo è l'approccio che è più probabile che abbia successo, anche se dipende ancora dal convincere "loro" che è tecnicamente suono e "una buona cosa".

    • Potresti semplicemente mettere il codice per la tua proposta di implementazione alternativa su GitHub e vedere cosa succede.

    3. .

    Tuttavia, tutto ciò presuppone che la tua idea sia in realtà funzionante. Basato sulle scarse informazioni che hai fornito, sono dubbioso. Sospetto che ci sia può essere problemi con incapsulamento incompleto, concorrenza e / o non implementando l'astrazione elenco completamente / correttamente.

    Ti suggerisco di mettere il tuo codice su GitHub in modo che altre persone possano fare un bell'aspetto duro.

Altri suggerimenti

Sembra che tu stia cercando un BlockingDeque , e in particolare un ArrayBlockingQueue .

Puoi anche volere un ConcurrentLinkedQueue , che utilizza un algoritmo "wait-free" (aka non blocco) e può quindi essere più veloce in molte circostanze. È solo un Queue (non un Dequeue) e quindi è possibile inserire / rimuovere solo alla testa della raccolta, ma sembra che potrebbe essere buono per il tuo caso d'uso. Ma in cambio dell'elegoritmo senza attesa, deve utilizzare una lista collegata piuttosto che un array internamente, e questo significa più memoria (incluso più spazzatura quando si pop articoli) e peggiore località di memoria. L'algoritmo senza attesa si basa anche su un Confronta e imposta (CAS) Loop, Il che significa che mentre è più veloce nel caso "normale", può effettivamente essere più lento in alta contesa, poiché ogni thread ha bisogno di provare le sue cas più volte prima che vinca e sia in grado di andare avanti. < / P >.

La mia ipotesi è che il motivo per cui gli elenchi non ottengono tanto amore in java.util.concurrent è che una lista è una struttura dati intrinsecamente raciata nella maggior parte dei casi di utilizzo. Ad esempio, qualcosa come if (!list.isEmpty()) { return list.get(0); } è racy a meno che non sia circondato da un blocco synchronized, nel qual caso non hai bisogno di una struttura intrinsecamente causata. Ciò di cui hai veramente bisogno è un'interfaccia "List-Type" che consente le operazioni solo alle estremità - e questo è esattamente ciò che Queue e Deque sono.

.

Non c'è motivo di effettuare effettivamente una nuova copia ogni singola volta che è così dispendiosa.

È così che funziona. Funziona in Sostituzione L'array precedente con nuovo array in un'azione Confronta e swap. È una parte chiave del design della sicurezza del filo che hai sempre un nuovo array anche se tutto ciò che fai è sostituire una voce.

.

Discussione e ottimizzata per consentire letture frequenti con scritture solo per essere aggiunte alla fine dell'elenco

Questo è fortemente ottimizzato per letture, qualsiasi altra soluzione sarà più veloce per le scritture, ma più lento per letture e devi decidere quale vuoi veramente.

È possibile avere una struttura dati personalizzata che sarà il migliore dei due mondi, ma non è più una soluzione generica che è ciò che copyOnWriteArRayList e ArrayDeque forniscono.

.

Come posso inviare una richiesta di modifica per richiedere una modifica alla specifica Java per eliminare le copie per aggiunte alla fine di un copyOnWriteArrayList (a meno che non sia necessario una ridimensionamento)?

Puoi farlo attraverso il database Bugs, ma ciò che proponi è un cambiamento fondamentale in che modo la struttura dei dati funziona. Suggerisco di proporre una nuova / diversa struttura dei dati che funziona il modo desiderato. Nel frattempo, suggerisco di implementarti da solo come esempio di funzionamento come vuoi che tu voglia volerai più velocemente.

Inizierei con un atomicreferentenearray in quanto ciò può essere utilizzato per eseguire le azioni di basso livello che ti serve. L'unico problema con esso è non è ristabile in modo da poter determinare la dimensione massima che desideri ogni esigenza.

CopyonWriteArrayList ha un inconveniente performance perché crea una copia dell'array sottostante dell'elenco sulle operazioni di scrittura. La copia dell'array sta rendendo le operazioni di scrittura lenti. Può essere, CopyOnWriteArrayList è vantaggioso per un utilizzo di un elenco con alta velocità di lettura e bassa tasso di scrittura.

Alla fine ho iniziato a codificare la mia implementazione utilizzando Java.util.concurrent.locks, ReadWriteLock. Ho fatto la mia implementazione semplicemente mantenendo l'istanza di lettura del livello dell'oggetto e guadagnando il blocco lettura nelle operazioni di lettura e guadagnando il blocco della scrittura nelle operazioni di scrittura. Il codice sembra questo. 

public class ConcurrentList< T > implements List< T >
{
    private final ReadWriteLock  readWriteLock = new ReentrantReadWriteLock();
    private final List< T > list;

    public ConcurrentList( List<T> list )
    {
        this.list = list;
    }

    public boolean remove( Object o )
    {
        readWriteLock.writeLock().lock();
        boolean ret;
        try
        {
            ret = list.remove( o );
        }
        finally
        {
            readWriteLock.writeLock().unlock();
        }
        return ret;
    }

    public boolean add( T t )
    {
        readWriteLock.writeLock().lock();
        boolean ret;
        try
        {
            ret = list.add( t );
        }
        finally
        {
            readWriteLock.writeLock().unlock();
        }
        return ret;
    }

    public void clear()
    {
        readWriteLock.writeLock().lock();
        try
        {
            list.clear();
        }
        finally
        {
            readWriteLock.writeLock().unlock();
        }
    }


    public int size()
    {
        readWriteLock.readLock().lock();
        try
        {
            return list.size();
        }
        finally
        {
            readWriteLock.readLock().unlock();
        }
    }

    public boolean contains( Object o )
    {
        readWriteLock.readLock().lock();
        try
        {
            return list.contains( o );
        }
        finally
        {
            readWriteLock.readLock().unlock();
        }
    }

    public T get( int index )
    {
        readWriteLock.readLock().lock();
        try
        {
            return list.get( index );
        }
        finally
        {
            readWriteLock.readLock().unlock();
        }
    }

//etc
}
.

Il miglioramento delle prestazioni osservato è stato notevole.

Totale tempo prelevato per 5000 Leggi + 5000 Scrivi (Leggi il rapporto di scrittura è 1: 1) per 10 discussioni erano

    .
  • Arraylist - 16450 NS (non thread sicuro)
  • ConcurrentList - 20999 NS
  • Vector -35696 NS
  • copyonwritearraylist - 197032 NS

Segui questo link per ulteriori informazioni sulla custodia di prova utilizzata per ottenere i risultati di cui sopra

Tuttavia, al fine di evitare concupurrentModificationException quando si utilizza l'iteratore, ho appena creato una copia dell'elenco corrente e ho restituito l'iteratore di questo. Ciò significa che questo elenco non restituisce e Iteratore che può modificare l'elenco originale. Bene, per me, questo è o.k. per il momento. 

public Iterator<T> iterator()
    {
        readWriteLock.readLock().lock();
        try
        {
            return new ArrayList<T>( list ).iterator();
        }
        finally
        {
            readWriteLock.readLock().unlock();
        }
    }
.

Dopo alcuni googling ho scoperto che CopyOnWriteArrayList ha un implementazione simile, in quanto non restituisce un iteratore che può modificare l'elenco originale. Javadoc dice,

.

L'iteratore restituito fornisce un'istantanea dello stato dell'elenco quando è stato costruito l'iteratore. Nessuna sincronizzazione è necessaria mentre attraversa l'iteratore. L'iteratore non supporta il metodo Rimuovi.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top