Kiedy należy używać ConcurrentSkipListMap?

Question

W języku Java, ConcurrentHashMap jest dostępne dla lepszego rozwiązania multithreading. Kiedy powinienem użyć ConcurrentSkipListMap? Czy to jest redundancja?

Czy wielowątkowe aspekty między tymi dwoma są częste?

Answer 1

Te dwie klasy różnią się na kilka sposobów.

ConcurrentHashMap nie gwarantuje * czasu pracy w ramach umowy. Umożliwia również dostrojenie pewnych czynników obciążenia (w przybliżeniu, liczba wątków jednocześnie modyfikujących go).

ConcurrentSkipListMap, z drugiej strony, gwarantuje średnią wydajność O (log (n)) w szerokim zakresie operacji. Nie obsługuje również strojenia dla celów współbieżności. ConcurrentSkipListMap ma również wiele operacji, których nie ma w pliku ConcurrentHashMap: ceilingEntry/Key, floorEntry/Key, itp. Utrzymuje także porządek sortowania, który w innym przypadku musiałby zostać obliczony (przy widocznym koszcie), jeśli używasz ConcurrentHashMap.

Zasadniczo dostępne są różne implementacje dla różnych przypadków użycia. Jeśli potrzebujesz szybkiego pojedynczego parowania klucz/wartość pary i szybkiego pojedynczego wyszukiwania klucza, użyj HashMap. Jeśli potrzebujesz szybszego przejścia w kolejce i możesz pozwolić sobie na dodatkowy koszt wstawienia, skorzystaj z SkipListMap.

_{* Chociaż oczekuję, że implementacja jest mniej więcej zgodna z ogólnymi hash-mapami gwarancji wstawienia/wyszukiwania O (1); ignorowanie ponownego mieszania}

Answer 2

Zobacz definicję struktury danych, patrz: Skip List. A ConcurrentSkipListMap przechowuje mapę w naturalnej kolejności jej kluczy (lub innej zdefiniowanej kolejności klawiszy). Będzie miał wolniejsze operacje get/put/contains niż HashMap, ale aby to zrekompensować, obsługuje interfejsy SortedMap i NavigableMap.

Answer 3

Pod względem wydajności, skipList, gdy jest używany jako mapa, wydaje się być 10-20 razy wolniejsze. Oto wynik moich testów (Java 1.8.0_102-b14, wygrać x32)

Benchmark     Mode Cnt Score Error Units 
MyBenchmark.hasMap_get  avgt 5 0.015 ? 0.001 s/op 
MyBenchmark.hashMap_put  avgt 5 0.029 ? 0.004 s/op 
MyBenchmark.skipListMap_get avgt 5 0.312 ? 0.014 s/op 
MyBenchmark.skipList_put  avgt 5 0.351 ? 0.007 s/op 

A dodatkowo, że - use-case gdzie porównując jeden do innego naprawdę ma sens. Wdrożenie pamięci podręcznej ostatnio używanych elementów przy użyciu obu tych kolekcji. Wydajność skipList wydaje się być bardziej wątpliwa.

MyBenchmark.hashMap_put1000_lru  avgt 5 0.032 ? 0.001 s/op 
MyBenchmark.skipListMap_put1000_lru avgt 5 3.332 ? 0.124 s/op 

Oto kod dla JMH (wykonany jako java -jar target/benchmarks.jar -bm avgt -f 1 -wi 5 -i 5 -t 1)

static final int nCycles = 50000; 
static final int nRep = 10; 
static final int dataSize = nCycles/4; 
static final List<String> data = new ArrayList<>(nCycles); 
static final Map<String,String> hmap4get = new ConcurrentHashMap<>(3000, 0.5f, 10); 
static final Map<String,String> smap4get = new ConcurrentSkipListMap<>(); 

static { 
    // prepare data 
    List<String> values = new ArrayList<>(dataSize); 
    for(int i = 0; i < dataSize; i++) { 
     values.add(UUID.randomUUID().toString()); 
    } 
    // rehash data for all cycles 
    for(int i = 0; i < nCycles; i++) { 
     data.add(values.get((int)(Math.random() * dataSize))); 
    } 
    // rehash data for all cycles 
    for(int i = 0; i < dataSize; i++) { 
     String value = data.get((int)(Math.random() * dataSize)); 
     hmap4get.put(value, value); 
     smap4get.put(value, value); 
    } 
} 

@Benchmark 
public void skipList_put() { 
    for(int n = 0; n < nRep; n++) { 
     Map<String,String> map = new ConcurrentSkipListMap<>(); 

     for(int i = 0; i < nCycles; i++) { 
      String key = data.get(i); 
      map.put(key, key); 
     } 
    } 
} 

@Benchmark 
public void skipListMap_get() { 
    for(int n = 0; n < nRep; n++) { 
     for(int i = 0; i < nCycles; i++) { 
      String key = data.get(i); 
      smap4get.get(key); 
     } 
    } 
} 

@Benchmark 
public void hashMap_put() { 
    for(int n = 0; n < nRep; n++) { 
     Map<String,String> map = new ConcurrentHashMap<>(3000, 0.5f, 10); 

     for(int i = 0; i < nCycles; i++) { 
      String key = data.get(i); 
      map.put(key, key); 
     } 
    } 
} 

@Benchmark 
public void hasMap_get() { 
    for(int n = 0; n < nRep; n++) { 
     for(int i = 0; i < nCycles; i++) { 
      String key = data.get(i); 
      hmap4get.get(key); 
     } 
    } 
} 

@Benchmark 
public void skipListMap_put1000_lru() { 
    int sizeLimit = 1000; 

    for(int n = 0; n < nRep; n++) { 
     ConcurrentSkipListMap<String,String> map = new ConcurrentSkipListMap<>(); 

     for(int i = 0; i < nCycles; i++) { 
      String key = data.get(i); 
      String oldValue = map.put(key, key); 

      if((oldValue == null) && map.size() > sizeLimit) { 
       // not real lru, but i care only about performance here 
       map.remove(map.firstKey()); 
      } 
     } 
    } 
} 

@Benchmark 
public void hashMap_put1000_lru() { 
    int sizeLimit = 1000; 
    Queue<String> lru = new ArrayBlockingQueue<>(sizeLimit + 50); 

    for(int n = 0; n < nRep; n++) { 
     Map<String,String> map = new ConcurrentHashMap<>(3000, 0.5f, 10); 

     lru.clear(); 
     for(int i = 0; i < nCycles; i++) { 
      String key = data.get(i); 
      String oldValue = map.put(key, key); 

      if((oldValue == null) && lru.size() > sizeLimit) { 
       map.remove(lru.poll()); 
       lru.add(key); 
      } 
     } 
    } 
}