Question ConcurrentHashMap: évitez la création d'objets supplémentaires avec "putIfAbsent"?


Je regroupe plusieurs valeurs pour les clés dans un environnement multithread. Les clés ne sont pas connues à l'avance. Je pensais faire quelque chose comme ça:

class Aggregator {
    protected ConcurrentHashMap<String, List<String>> entries =
                            new ConcurrentHashMap<String, List<String>>();
    public Aggregator() {}

    public void record(String key, String value) {
        List<String> newList =
                    Collections.synchronizedList(new ArrayList<String>());
        List<String> existingList = entries.putIfAbsent(key, newList);
        List<String> values = existingList == null ? newList : existingList;
        values.add(value);
    }
}

Le problème que je vois est que chaque fois que cette méthode s'exécute, je dois créer une nouvelle instance d'un ArrayList, que je jette ensuite (dans la plupart des cas). Cela semble être un abus injustifié du ramasse-miettes. Existe-t-il un moyen plus efficace d’initialiser ce type de structure sans devoir synchronize la record méthode? Je suis un peu surpris par la décision d'avoir le putIfAbsent méthode ne retourne pas l'élément nouvellement créé, et par l'absence d'un moyen de différer l'instanciation à moins qu'elle ne soit appelée (pour ainsi dire).


36
2018-05-24 18:54


origine


Réponses:


Java 8 a introduit une API pour résoudre ce problème précis, créant une solution à 1 ligne:

public void record(String key, String value) {
    entries.computeIfAbsent(key, k -> Collections.synchronizedList(new ArrayList<String>())).add(value);
}

Pour Java 7:

public void record(String key, String value) {
    List<String> values = entries.get(key);
    if (values == null) {
        entries.putIfAbsent(key, Collections.synchronizedList(new ArrayList<String>()));
        // At this point, there will definitely be a list for the key.
        // We don't know or care which thread's new object is in there, so:
        values = entries.get(key);
    }
    values.add(value);
}

Ceci est le modèle de code standard lors du remplissage d'un ConcurrentHashMap.

La méthode spéciale putIfAbsent(K, V)) va soit mettre votre objet de valeur, ou si un autre thread est avant vous, alors il va ignorer votre objet de valeur. De toute façon, après l'appel à putIfAbsent(K, V)), get(key) est garanti pour être cohérent entre les threads et donc le code ci-dessus est threadsafe.

La seule perte de charge est si un autre thread ajoute une nouvelle entrée en même temps pour la même clé: Vous mai finir par jeter la valeur nouvellement créée, mais cela n'arrive que s'il n'y a pas déjà une entrée et il y a une course que votre fil perd, ce qui serait typiquement rare.


36
2018-05-24 19:00



A partir de Java-8, vous pouvez créer des cartes multi en utilisant le modèle suivant:

public void record(String key, String value) { entries.computeIfAbsent(key, k -> Collections.synchronizedList(new ArrayList<String>())) .add(value); }

La documentation ConcurrentHashMap (pas le contrat général) spécifie que ArrayList ne sera créé qu'une seule fois pour chaque clé, au coût initial léger du retard des mises à jour pendant la création de ArrayList pour une nouvelle clé:

http://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html#computeIfAbsent-K-java.util.function.Function-


14
2017-09-01 05:31



Finalement, j'ai apporté une légère modification à la réponse de @ Bohemian. Sa solution proposée remplace le values variable avec le putIfAbsent appel, ce qui crée le même problème que j'avais avant. Le code qui semble fonctionner ressemble à ceci:

    public void record(String key, String value) {
        List<String> values = entries.get(key);
        if (values == null) {
            values = Collections.synchronizedList(new ArrayList<String>());
            List<String> values2 = entries.putIfAbsent(key, values);
            if (values2 != null)
                values = values2;
        }
        values.add(value);
    }

Ce n'est pas aussi élégant que je le voudrais, mais c'est mieux que l'original qui crée une nouvelle ArrayList instance à chaque appel.


10
2018-05-24 21:28



Création de deux versions basées sur la réponse de Gene

public  static <K,V> void putIfAbsetMultiValue(ConcurrentHashMap<K,List<V>> entries, K key, V value) {
    List<V> values = entries.get(key);
    if (values == null) {
        values = Collections.synchronizedList(new ArrayList<V>());
        List<V> values2 = entries.putIfAbsent(key, values);
        if (values2 != null)
            values = values2;
    }
    values.add(value);
}

public  static <K,V> void putIfAbsetMultiValueSet(ConcurrentMap<K,Set<V>> entries, K key, V value) {
    Set<V> values = entries.get(key);
    if (values == null) {
        values = Collections.synchronizedSet(new HashSet<V>());
        Set<V> values2 = entries.putIfAbsent(key, values);
        if (values2 != null)
            values = values2;
    }
    values.add(value);
}

Ça marche bien


3
2017-07-05 18:21



C'est un problème, j'ai aussi cherché une réponse. La méthode putIfAbsent ne résout pas réellement le problème de création d'objet supplémentaire, il s'assure que l'un de ces objets ne remplace pas un autre. Mais les conditions de concurrence entre les threads peuvent provoquer une instanciation de plusieurs objets. Je pourrais trouver 3 solutions pour ce problème (et je suivrais cet ordre de préférence):

1- Si vous êtes sur Java 8, le meilleur moyen d'y parvenir est probablement le nouveau computeIfAbsent méthode de ConcurrentMap. Il vous suffit de lui donner une fonction de calcul qui sera exécutée de manière synchrone (du moins pour le ConcurrentHashMapla mise en oeuvre). Exemple:

private final ConcurrentMap<String, List<String>> entries =
        new ConcurrentHashMap<String, List<String>>();

public void method1(String key, String value) {
    entries.computeIfAbsent(key, s -> new ArrayList<String>())
            .add(value);
}

Ceci est du javadoc de ConcurrentHashMap.computeIfAbsent:

Si la clé spécifiée n'est pas déjà associée à une valeur, tente   calculer sa valeur en utilisant la fonction de mappage donnée et la saisir   dans cette carte à moins que null. L'appel de la méthode entière est effectué   atomiquement, la fonction est appliquée au plus une fois par clé. Certains   tentatives de mise à jour sur cette carte par d'autres threads peuvent être   bloqué pendant que le calcul est en cours, le calcul doit donc être   court et simple, et ne doit pas tenter de mettre à jour d’autres   cette carte.

2- Si vous ne pouvez pas utiliser Java 8, vous pouvez utiliser Guava's LoadingCache, qui est thread-safe. Vous définissez une fonction de chargement (tout comme le compute fonction ci-dessus), et vous pouvez être sûr qu’elle sera appelée de manière synchrone. Exemple:

private final LoadingCache<String, List<String>> entries = CacheBuilder.newBuilder()
        .build(new CacheLoader<String, List<String>>() {
            @Override
            public List<String> load(String s) throws Exception {
                return new ArrayList<String>();
            }
        });

public void method2(String key, String value) {
    entries.getUnchecked(key).add(value);
}

3- Si vous ne pouvez pas utiliser Guava non plus, vous pouvez toujours synchroniser manuellement et faire un double verrouillage. Exemple:

private final ConcurrentMap<String, List<String>> entries =
        new ConcurrentHashMap<String, List<String>>();

public void method3(String key, String value) {
    List<String> existing = entries.get(key);
    if (existing != null) {
        existing.add(value);
    } else {
        synchronized (entries) {
            List<String> existingSynchronized = entries.get(key);
            if (existingSynchronized != null) {
                existingSynchronized.add(value);
            } else {
                List<String> newList = new ArrayList<>();
                newList.add(value);
                entries.put(key, newList);
            }
        }
    }
}

J'ai réalisé un exemple d'implémentation de toutes ces 3 méthodes et, en outre, la méthode non synchronisée, qui crée une création supplémentaire d'objets: http://pastebin.com/qZ4DUjTr


3
2017-07-22 14:58



Le gaspillage de mémoire (aussi GC, etc.) que le problème de création de liste de tableau vide est traité avec Java 1.7.40. Ne vous préoccupez pas de la création d'arraylist vide. Référence : http://javarevisited.blogspot.com.tr/2014/07/java-optimization-empty-arraylist-and-Hashmap-cost-less-memory-jdk-17040-update.html


1
2017-09-01 05:42



L'approche avec putIfAbsent a le temps d'exécution le plus rapide, il est de 2 à 50 fois plus rapide que l'approche "lambda" dans des environnements à forte contention. Le Lambda n'est pas la raison de ce "powerloss", le problème est la synchronisation obligatoire à l'intérieur de computeIfAbsent avant les optimisations Java-9.

la référence:

import java.util.Random;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;

public class ConcurrentHashMapTest {
    private final static int numberOfRuns = 1000000;
    private final static int numberOfThreads = Runtime.getRuntime().availableProcessors();
    private final static int keysSize = 10;
    private final static String[] strings = new String[keysSize];
    static {
        for (int n = 0; n < keysSize; n++) {
            strings[n] = "" + (char) ('A' + n);
        }
    }

    public static void main(String[] args) throws InterruptedException {
        for (int n = 0; n < 20; n++) {
            testPutIfAbsent();
            testComputeIfAbsentLamda();
        }
    }

    private static void testPutIfAbsent() throws InterruptedException {
        final AtomicLong totalTime = new AtomicLong();
        final ConcurrentHashMap<String, AtomicInteger> map = new ConcurrentHashMap<String, AtomicInteger>();
        final Random random = new Random();
        ExecutorService executorService = Executors.newFixedThreadPool(numberOfThreads);

        for (int i = 0; i < numberOfThreads; i++) {
            executorService.execute(new Runnable() {
                @Override
                public void run() {
                    long start, end;
                    for (int n = 0; n < numberOfRuns; n++) {
                        String s = strings[random.nextInt(strings.length)];
                        start = System.nanoTime();

                        AtomicInteger count = map.get(s);
                        if (count == null) {
                            count = new AtomicInteger(0);
                            AtomicInteger prevCount = map.putIfAbsent(s, count);
                            if (prevCount != null) {
                                count = prevCount;
                            }
                        }
                        count.incrementAndGet();
                        end = System.nanoTime();
                        totalTime.addAndGet(end - start);
                    }
                }
            });
        }
        executorService.shutdown();
        executorService.awaitTermination(Long.MAX_VALUE, TimeUnit.DAYS);
        System.out.println("Test " + Thread.currentThread().getStackTrace()[1].getMethodName()
                + " average time per run: " + (double) totalTime.get() / numberOfThreads / numberOfRuns + " ns");
    }

    private static void testComputeIfAbsentLamda() throws InterruptedException {
        final AtomicLong totalTime = new AtomicLong();
        final ConcurrentHashMap<String, AtomicInteger> map = new ConcurrentHashMap<String, AtomicInteger>();
        final Random random = new Random();
        ExecutorService executorService = Executors.newFixedThreadPool(numberOfThreads);
        for (int i = 0; i < numberOfThreads; i++) {
            executorService.execute(new Runnable() {
                @Override
                public void run() {
                    long start, end;
                    for (int n = 0; n < numberOfRuns; n++) {
                        String s = strings[random.nextInt(strings.length)];
                        start = System.nanoTime();

                        AtomicInteger count = map.computeIfAbsent(s, (k) -> new AtomicInteger(0));
                        count.incrementAndGet();

                        end = System.nanoTime();
                        totalTime.addAndGet(end - start);
                    }
                }
            });
        }
        executorService.shutdown();
        executorService.awaitTermination(Long.MAX_VALUE, TimeUnit.DAYS);
        System.out.println("Test " + Thread.currentThread().getStackTrace()[1].getMethodName()
                + " average time per run: " + (double) totalTime.get() / numberOfThreads / numberOfRuns + " ns");
    }

}

Les resultats:

Test testPutIfAbsent average time per run: 115.756501 ns
Test testComputeIfAbsentLamda average time per run: 276.9667055 ns
Test testPutIfAbsent average time per run: 134.2332435 ns
Test testComputeIfAbsentLamda average time per run: 223.222063625 ns
Test testPutIfAbsent average time per run: 119.968893625 ns
Test testComputeIfAbsentLamda average time per run: 216.707419875 ns
Test testPutIfAbsent average time per run: 116.173902375 ns
Test testComputeIfAbsentLamda average time per run: 215.632467375 ns
Test testPutIfAbsent average time per run: 112.21422775 ns
Test testComputeIfAbsentLamda average time per run: 210.29563725 ns
Test testPutIfAbsent average time per run: 120.50643475 ns
Test testComputeIfAbsentLamda average time per run: 200.79536475 ns

1
2017-07-07 11:05