example - concurrent list java

¿Cuándo debería usar ConcurrentSkipListMap?

Question

En Java, ConcurrentHashMap está ahí para una mejor solución de multithreading . Entonces, ¿cuándo debería usar ConcurrentSkipListMap ? ¿Es una redundancia?

¿Los aspectos de subprocesamiento múltiple entre estos dos son comunes?

Answer 1

Consulte Omitir lista para obtener una definición de la estructura de datos. Un ConcurrentSkipListMap almacena el mapa en el orden natural de sus claves (o algún otro orden de clave que defina). Por lo tanto, tendrá operaciones get / put / contains más lentas que HashMap, pero para compensar esto, admite las interfaces SortedMap y NavigableMap.

Answer 2

En términos de rendimiento, skipList cuando se usa como mapa, parece ser 10-20 veces más lento. Aquí está el resultado de mis pruebas (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

Y además de eso - caso de uso donde la comparación de uno a otro realmente tiene sentido. Implementación de la memoria caché de los últimos elementos usados ​​recientemente utilizando ambas colecciones. Ahora la eficiencia de skipList parece ser un evento más dudoso.

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

Aquí está el código para JMH (ejecutado como 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);
            }
        }
    }
}

Answer 3

Estas dos clases varían de algunas maneras.

ConcurrentHashMap no garantiza * el tiempo de ejecución de sus operaciones como parte de su contrato. También permite ajustar ciertos factores de carga (más o menos, el número de subprocesos que lo modifican simultáneamente).

ConcurrentSkipListMap , por otro lado, garantiza el rendimiento promedio de O (log (n)) en una amplia variedad de operaciones. Tampoco es compatible con el ajuste por simultaneidad. ConcurrentSkipListMap también tiene una serie de operaciones que ConcurrentHashMap no tiene: ceilingEntry / Key, floorEntry / Key, etc. También mantiene un orden de clasificación, que de otro modo tendría que calcularse (a un costo notable) si usaba ConcurrentHashMap .

Básicamente, se proporcionan diferentes implementaciones para diferentes casos de uso. Si necesita una adición rápida de par de clave / valor único y búsqueda rápida de una sola clave, utilice HashMap . Si necesita un recorrido más rápido en el pedido y puede pagar el costo adicional por la inserción, use el SkipListMap .

_{* Aunque espero que la implementación esté más o menos en línea con las garantías generales de hash-map de O (1) inserción / búsqueda; haciendo caso omiso de volver a mezclar}