Est-il une meilleure alternative à Java CopyOnWriteArrayList la mise en œuvre et comment puis-je demander un changement de Java spec?

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

  •  21-12-2019
  •  | 
  •  

Question

CopyOnWriteArrayList presque a le comportement que je veux, et si les recopies inutiles ont été supprimés, il serait exactement ce que je recherche.En particulier, il pourrait agir exactement comme ArrayList pour ajoute le fait à la fin de la liste de tableaux - c'est à dire, il n'y a pas de raison de le faire réellement une nouvelle copie de tous les temps, ce qui est donc du gaspillage.Il se pourrait presque restreindre la fin de la liste de tableaux pour saisir un instantané pour les lecteurs, et mise à jour de la suite de l'ajout de nouveaux éléments.

Cette amélioration semble qu'il serait utile d'avoir des depuis pour de nombreuses applications, le type le plus commun de l'addition serait à la fin de la liste de tableaux - ce qui est encore une raison pour le choix d'utiliser une ArrayList pour commencer.

Il y aurait pas une charge supplémentaire, car il ne pouvait pas copier lors de l'ajout et bien qu'il reste encore à vérifier si une re-taille est nécessaire ArrayList dispose pour ce faire de toute façon.

  1. Est-il une alternative ou une structure de données qui a ce comportement sans les recopies inutiles pour les ajouts à la fin (c'est à dire, thread-safe et optimisé afin de permettre à de fréquentes lectures avec écrit seulement des ajouts à la fin de la liste)?

  2. Comment puis-je soumettre une demande de modification de demander une modification de la spécification de Java pour supprimer les copies d'ajouts à la fin d'une CopyOnWriteArrayList (à moins d'une re-taille est nécessaire)?

J'aurais vraiment aimé voir ce qui a changé avec le noyau de bibliothèques Java plutôt que sur le maintien et l'aide de mon propre code.

Était-ce utile?

La solution

Pour répondre à vos questions:

  1. Je ne suis pas au courant d'une mise en œuvre alternative qui est une liste entièrement fonctionnelle.

  2. Si votre idée est vraiment viable, je peux penser à un certain nombre de façons de procéder:

    • Vous pouvez soumettre des "demandes d'amélioration" (RFE) via la base de données Java Bugs. Cependant, dans ce cas, je doute que vous obtiendrez une réponse positive. (Certainement, pas de temps en temps opportun!)

    • Vous pouvez créer une question RFE sur Guava ou Apache Commons Problèmes Tracker. Cela pourrait être plus fructueux, bien que cela dépend de leur convaincre ...

    • Vous pouvez soumettre un correctif à l'équipe OpenJDK avec une implémentation de votre idée. Je ne peux pas dire ce que le résultat pourrait être ...

    • Vous pouvez soumettre un correctif (comme ci-dessus) à Guava ou Apache Commons via leurs suiveurs de problèmes respectifs. C'est l'approche qui est la plus susceptible de réussir, bien qu'elle dépend toujours de convaincre les "eux" qu'il est techniquement sain et "une bonne chose".

    • Vous pouvez simplement mettre le code de votre mise en œuvre alternative proposée sur Github, et voir ce qui se passe.

    3. Cependant, tout cela présuppose que votre idée va réellement fonctionner. Basé sur les informations SAFANT que vous avez fournies, je suis douteux. Je soupçonne qu'il peut être problèmes avec une encapsulation, une simultanéité et / ou de ne pas mettre en œuvre l'abstraction de la liste entièrement / correctement.

    Je suggère de mettre votre code sur GitHub afin que d'autres personnes puissent le regarder bien.

Autres conseils

On dirait que vous êtes à la recherche d'un BlockingDeque, et en particulier un ArrayBlockingQueue.

Vous pouvez aussi vous voulez un ConcurrentLinkedQueue, qui utilise une attente "libre" de l'algorithme (aka non-bloquant) et peut donc être plus rapide dans de nombreuses circonstances.C'est seulement une Queue (pas un Dequeue) et donc vous ne pouvez insérer/enlever à la tête de la collection, mais ça à l'air qui pourrait être bon pour votre cas d'utilisation.Mais en échange de l'attente libre de l'algorithme, il doit utiliser une liste chaînée plutôt qu'un tableau à l'interne, ce qui signifie plus de mémoire (y compris plus de déchets lorsque vous pop les items) et le pire de la mémoire de la localité.L'attente sans algorithme s'appuie également sur une comparez et définir (CAS) en boucle, ce qui signifie que, même s'il est plus rapide dans le cas "normal", il peut effectivement être plus lent sous haute affirmation, comme chaque thread doit essayer de son CAS à plusieurs reprises avant qu'il ne gagne et est en mesure d'aller de l'avant.

Ma conjecture est que la raison pour laquelle des listes de ne pas obtenir autant d'amour dans java.util.concurrent c'est que la liste est en soi un racé structure de données dans la plupart des cas d'utilisation d'autres itération.Par exemple, quelque chose comme if (!list.isEmpty()) { return list.get(0); } racée, sauf si elle est entourée par un synchronized bloc, dans ce cas, vous n'avez pas besoin fondamentalement d'un thread-safe de la structure.Ce que vous avez vraiment besoin est une "liste-type" de l'interface qui permet seulement aux opérations à la fin-et c'est exactement ce que Queue et Deque sont.

Il n'y a aucune raison de faire une nouvelle copie chaque fois qui est si gaspillé.

Voici comment ça fonctionne. Il fonctionne par remplaçant le tableau précédent avec nouveau tableau dans une action de comparaison et de swap. Il s'agit d'une partie clé de la conception de sécurité du fil que vous avez toujours un nouveau tableau, même si tout ce que vous faites est de remplacer une entrée.

Safe-Safe et optimisé pour permettre des lectures fréquentes avec écrit uniquement des ajouts à la fin de la liste

Ceci est fortement optimisé pour les lectures, toute autre solution sera plus rapide pour les écritures, mais plus lente pour des lectures et vous devez décider lequel vous voulez vraiment.

Vous pouvez avoir une structure de données personnalisée qui sera la meilleure des deux mondes, mais il ne s'agit plus d'une solution générique qui est ce qu'est la liste de CopyWriRearrayList et ArrayDeque.

Comment puis-je soumettre une demande de changement pour demander une modification de la spécification Java pour éliminer les copies pour les ajouts à la fin d'une liste de copie -ritearrayliste (sauf si une réapparition n'est nécessaire)?

Vous pouvez le faire via la base de données des bugs, mais ce que vous proposez est un changement fondamental de la manière dont la structure de données fonctionne. Je suggère de proposer une nouvelle structure de données différente qui fonctionne comme vous le souhaitez. En attendant, je vous suggère de la mettre en œuvre comme un exemple de travail, car vous voulez que vous souhaitiez que vous souhaitiez plus rapidement.

Je commencerais avec un atomicreferenceArray car cela peut être utilisé pour effectuer les actions de faible niveau dont vous avez besoin. Le seul problème avec cela est qu'il n'est pas redimensionnable, vous devez donc déterminer la taille maximale que vous auriez besoin.

CopyOnwriDearrayList a un inconvénient de performance car il crée une copie de la matrice sous-jacente de la liste sur les opérations d'écriture. La copie du tableau rend les opérations d'écriture lent. Peut-être, la liste CopyWriRearrayRayRay est avantageuse pour une utilisation d'une liste avec un taux de lecture élevé et un faible taux d'écriture.

Finalement, j'ai commencé à coder ma propre implémentation à l'aide de Java.Util.ConCurrent.Locks, Readwritelock. J'ai fait ma mise en œuvre simplement en maintenant une instance Readwitelock de niveau d'objet et en gagnant le verrouillage de lecture dans les opérations de lecture et gagnez le verrouillage de l'écriture dans les opérations d'écriture. Le code ressemble à ceci. 

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
}

L'amélioration de la performance observée était notable.

Temps total pris pour 5000 Lectures + 5000 écriture (le rapport écriture de lecture est de 1: 1) par 10 threads étaient

  • ArrayList - 16450 NS (pas le fil de fil)
  • Concurrentlist - 20999 NS
  • vecteur -35696 ns
  • CopyOnwriRearrayList - 197032 NS

Veuillez suivre ce lien pour plus d'informations sur le cas d'essai utilisé pour obtenir des résultats ci-dessus

Toutefois, afin d'éviter une exception simultancidification lors de l'utilisation de l'itérateur, je viens de créer une copie de la liste actuelle et j'ai renvoyé l'itérateur de cela. Cela signifie que cette liste ne retourne pas et itérateur qui peut modifier la liste d'origine. Eh bien, pour moi, c'est O.K. pour le moment. 

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

Après que certains googling, j'ai découvert que la liste CopyWriRearrayRayRrayliste a une implémentation similaire, car elle ne renvoie pas un itérateur pouvant modifier la liste d'origine. Javadoc dit,

L'itérateur renvoyé fournit un instantané de l'état de la liste lorsque l'itérateur a été construit. Aucune synchronisation n'est nécessaire lors de la traversée de l'itérateur. L'itérateur ne prend pas en charge la méthode Supprimer.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top