When should I use ConcurrentSkipListMap?

java performance multithreading map concurrenthashmap

31951 просмотра

5 ответа

In Java, ConcurrentHashMap is there for better multithreading solution. Then when should I use ConcurrentSkipListMap? Is it a redundancy?

Does multithreading aspects between these two are common?

Автор: DKSRathore Источник Размещён: 14.08.2019 09:45

Ответы (5)


66 плюса

Решение

These two classes vary in a few ways.

ConcurrentHashMap does not guarantee* the runtime of its operations as part of its contract. It also allows tuning for certain load factors (roughly, the number of threads concurrently modifying it).

ConcurrentSkipListMap, on the other hand, guarantees average O(log(n)) performance on a wide variety of operations. It also does not support tuning for concurrency's sake. ConcurrentSkipListMap also has a number of operations that ConcurrentHashMap doesn't: ceilingEntry/Key, floorEntry/Key, etc. It also maintains a sort order, which would otherwise have to be calculated (at notable expense) if you were using a ConcurrentHashMap.

Basically, different implementations are provided for different use cases. If you need quick single key/value pair addition and quick single key lookup, use the HashMap. If you need faster in-order traversal, and can afford the extra cost for insertion, use the SkipListMap.

*Though I expect the implementation is roughly in line with the general hash-map guarantees of O(1) insertion/lookup; ignoring re-hashing

Автор: Kevin Montrose Размещён: 28.11.2009 06:50

14 плюса

See Skip List for a definition of the data structure. A ConcurrentSkipListMap stores the Map in the natural order of its keys (or some other key order you define). So it'll have slower get/put/contains operations than a HashMap, but to offset this it supports the SortedMap and NavigableMap interfaces.

Автор: Jim Ferrans Размещён: 28.11.2009 06:48

6 плюса

In terms of performance, skipList when is used as Map - appears to be 10-20 times slower. Here is the result of my tests (Java 1.8.0_102-b14, win 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

И в дополнение к этому - вариант использования, где сравнение одного с другим действительно имеет смысл. Реализация кэша последних недавно использованных элементов с использованием обеих этих коллекций. Теперь эффективность skipList выглядит как событие более сомнительное.

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

Вот код для JMH (выполняется как 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);
            }
        }
    }
}
Автор: Xtra Coder Размещён: 15.09.2016 08:53

0 плюса

ConcurrentHashMap: когда вы хотите получить / поставить многопоточный индекс на основе, поддерживаются только операции на основе индекса. Получить / положить имеют O (1)

ConcurrentSkipListMap: больше операций, чем просто получить / поставить, например отсортировать верхний / нижний n элементов по ключу, получить последнюю запись, получить / просмотреть всю карту, отсортированную по ключу и т. Д. Сложность равна O (log (n)), поэтому производительность по положению не так же хорошо, как ConcurrentHashMap. Это не реализация ConcurrentNavigableMap с SkipList.

Для подведения итогов используйте ConcurrentSkipListMap, когда вы хотите выполнить больше операций с картой, требующих отсортированных функций, а не просто получить и положить.

Автор: spats Размещён: 06.02.2019 11:26

0 плюса

На основе рабочих нагрузок ConcurrentSkipListMap может работать медленнее, чем TreeMap с синхронизированными методами, как в KAFKA-8802

Автор: Anurag Sharma Размещён: 14.08.2019 06:44
Вопросы из категории :
32x32