ConcurrentHashMap: "putIfAbsent" के साथ अतिरिक्त ऑब्जेक्ट निर्माण से बचें?

Question

मैं बहु-थ्रेडेड वातावरण में कुंजियों के लिए एकाधिक मान एकत्र कर रहा हूं। चाबियाँ पहले से ज्ञात नहीं हैं। मैंने सोचा कि मैं कुछ इस तरह करना होगा:

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); 
    } 
} 

समस्या मैं देख रहा हूँ हर बार इस विधि से चलाता है, मैं एक ArrayList, जो मैं तो दूर (अधिकांश मामलों में) फेंक का एक नया उदाहरण बनाने की जरूरत है। यह कचरा कलेक्टर के अन्यायपूर्ण दुरुपयोग की तरह लगता है। क्या record विधि के बिना इस तरह की संरचना को शुरू करने का एक बेहतर, थ्रेड-सुरक्षित तरीका है? मैं putIfAbsent विधि को नए बनाए गए तत्व को वापस नहीं करने के फैसले से कुछ हद तक आश्चर्यचकित हूं, और तत्कालता को स्थगित करने के तरीके की कमी के कारण इसे (इसलिए बोलने के लिए) कहा जाता है।

Answer 1

जावा 8 इस सटीक समस्या के लिए पूरा करने के लिए एक API शुरू की, एक 1-लाइन समाधान बन: जावा 7 के लिए

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

:

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); 
} 

इस मानक कोड पैटर्न जब एक पॉप्युलेट है ConcurrentHashMap।

विशेष विधि putIfAbsent(K, V)) या तो आपकी मान वस्तु को रखेगी, या यदि कोई अन्य थ्रेड आपके सामने हो, तो यह आपके मूल्य वस्तु को अनदेखा कर देगा। किसी भी तरह से, putIfAbsent(K, V)) पर कॉल करने के बाद, get(key) धागे के बीच संगत होने की गारंटी है और इसलिए उपरोक्त कोड थ्रेडसेफ है।

केवल व्यर्थ भूमि के ऊपर है, तो कुछ अन्य धागा एक ही कुंजी के लिए एक ही समय में एक नई प्रविष्टि जोड़ता है: आप नव निर्मित मूल्य बर्बाद हो सकती है, लेकिन यह केवल तब होता है, अगर वहाँ नहीं पहले से ही एक प्रविष्टि है और ऐसी दौड़ है जो आपका धागा खो देता है, जो आमतौर पर दुर्लभ होता है।

Answer 2

अंत में, मैंने @ बोहेमियन के जवाब का मामूली संशोधन लागू किया। उनके प्रस्तावित समाधान values वैरिएबल को putIfAbsent कॉल के साथ ओवरराइट करता है, जो पहले की समान समस्या उत्पन्न करता है। कोड काम करने के लिए लगता है कि इस तरह दिखता है:

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); 
    } 

यह रूप में सुंदर के रूप में मैं चाहता हूँ नहीं है, लेकिन यह मूल है कि हर कॉल पर एक नया ArrayList उदाहरण बनाता है की तुलना में बेहतर है।

Answer 3

निर्मित दो संस्करणों जीन के उत्तर के आधार पर

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); 
} 

यह अच्छी तरह से

Answer 4

काम करता है जावा-8 आप निम्नलिखित पद्धति का उपयोग कर मल्टी मैप्स बना सकते हैं के रूप में:

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

ConcurrentHashMap प्रलेखन (सामान्य अनुबंध नहीं) निर्दिष्ट करता है कि ArrayList केवल प्रत्येक कुंजी के लिए एक बार बनाया जाएगा, मामूली प्रारंभिक सह पर

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

Answer 5

स्मृति के अपशिष्ट (भी जीसी आदि: अद्यतन में देरी, जबकि ArrayList एक नई कुंजी के लिए बनाया जा रहा है की सेंट) कि खाली ऐरे सूची निर्माण समस्या जावा 1.7.40 के साथ संभाली जाती है। खाली सरणीसूची बनाने के बारे में चिंता न करें। संदर्भ: http://javarevisited.blogspot.com.tr/2014/07/java-optimization-empty-arraylist-and-Hashmap-cost-less-memory-jdk-17040-update.html

Answer 6

यह एक समस्या है जिसे मैंने एक उत्तर भी देखा। विधि putIfAbsent वास्तव में अतिरिक्त ऑब्जेक्ट निर्माण समस्या को हल नहीं करती है, यह केवल यह सुनिश्चित करती है कि उनमें से एक ऑब्जेक्ट किसी अन्य को प्रतिस्थापित नहीं करता है। लेकिन धागे के बीच दौड़ की स्थिति कई ऑब्जेक्ट त्वरण का कारण बन सकती है। मुझे इस समस्या के लिए 3 समाधान मिल सकते हैं (और मैं वरीयता के इस क्रम का पालन करता हूं):

1- यदि आप जावा 8 पर हैं, तो इसे प्राप्त करने का सबसे अच्छा तरीका शायद ConcurrentMap की विधि है। आपको बस इसे एक गणना समारोह देने की आवश्यकता है जिसे समकालिक रूप से निष्पादित किया जाएगा (कम से कम ConcurrentHashMap कार्यान्वयन के लिए)। उदाहरण:

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); 
} 

यह ConcurrentHashMap.computeIfAbsent की जावाडोक से है:

निर्दिष्ट कुंजी पहले से ही एक मूल्य के साथ संबद्ध नहीं है, तो प्रयास करता दिया मानचित्रण समारोह का उपयोग कर अपने मूल्य की गणना करने के लिए और इसे में प्रवेश करती है इस मानचित्र में शून्य तक। संपूर्ण विधि आमंत्रण परमाणु रूप से किया जाता है, इसलिए कार्य प्रति कुंजी एक बार में लागू होता है। कुछ अन्य धागे द्वारा इस मानचित्र पर अद्यतन संचालन का प्रयास हो सकता है जबकि गणना प्रगति पर है, इसलिए गणना छोटी और सरल होनी चाहिए, और इस मानचित्र को के किसी भी अन्य मैपिंग को अपडेट करने का प्रयास नहीं करना चाहिए।

2- आप जावा 8 उपयोग नहीं कर सकते हैं, तो आप उपयोग कर सकते हैं Guava के LoadingCache, जो धागे की सुरक्षित है। आप इसे एक लोड फ़ंक्शन परिभाषित करते हैं (जैसे ऊपर compute फ़ंक्शन), और आप सुनिश्चित हो सकते हैं कि इसे समकालिक रूप से समझा जाएगा। उदाहरण:

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- आप या तो अमरूद उपयोग नहीं कर सकते हैं, तो आप मैन्युअल रूप से कभी सिंक्रनाइज़ और एक की दोबारा जांच कर ताला कर सकते हैं। उदाहरण:

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); 
      } 
     } 
    } 
} 

मैं उन सभी 3 तरीकों में से एक उदाहरण दिया गया बनाया है और इसके अलावा, गैर सिंक्रनाइज़ विधि है, जिसमें अतिरिक्त ऑब्जेक्ट निर्माण का कारण बनता है: http://pastebin.com/qZ4DUjTr

Answer 7

putIfAbsent साथ दृष्टिकोण सबसे तेजी से निष्पादन समय है, यह उच्च विवाद के साथ evironments में "lambda" दृष्टिकोण से 2 से 50 गुना तेजी से है। लैम्ब्डा इस "पावरलोस" के पीछे कारण नहीं है, यह मुद्दा जावा-9 ऑप्टिमाइज़ेशन से पहले computeIfAbsent के अंदर अनिवार्य सिंक्रनाइज़ेशन है।

बेंचमार्क:

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"); 
    } 

} 

परिणाम:

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