¿Cuándo debo usar ConcurrentSkipListMap?

82

En Java, ConcurrentHashMapexiste una mejor multithreadingsolución. Entonces, ¿cuándo debería usar ConcurrentSkipListMap? ¿Es una redundancia?

¿Son comunes los aspectos de subprocesos múltiples entre estos dos?

DKSRathore
fuente

Respuestas:

80

Estas dos clases varían de varias formas.

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

ConcurrentSkipListMap , por otro lado, garantiza un rendimiento promedio de O (log (n)) en una amplia variedad de operaciones. Tampoco admite el ajuste por simultaneidad. ConcurrentSkipListMaptambién tiene una serie de operaciones que ConcurrentHashMapno las tiene: techoEntry / Key, floorEntry / Key, etc. También mantiene un orden de clasificación, que de otro modo tendría que calcularse (a un costo considerable) si estuviera usando un ConcurrentHashMap.

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

* Aunque espero que la implementación esté aproximadamente en línea con las garantías generales del mapa hash de la inserción / búsqueda de O (1); ignorando el re-hash

Kevin Montrose
fuente
Okay. Log (n) está bien, pero ¿ConcurrentSkipListMap ahorra espacio?
DKSRathore
1
Las listas de omisión son necesariamente más grandes que las Hashtables, pero la naturaleza ajustable de ConcurrentHashMap hace posible construir una Hashtable que sea más grande que el ConcurrentSkipListMap equivalente. En general, esperaría que la lista de omisión sea más grande pero en el mismo orden de magnitud.
Kevin Montrose
"Tampoco es compatible con el ajuste por simultaneidad". ¿Por qué? ¿Cual es el enlace?
Pacerier
2
@Pacerier: no quise decir que admite el ajuste porque es concurrente, quiero decir que no le permite ajustar los parámetros que influyen en su rendimiento concurrente (mientras que ConcurrentHashMap lo hace).
Kevin Montrose
@KevinMontrose Ic, por lo que quiso decir "Tampoco admite el ajuste de simultaneidad".
Pacerier
8

En términos de rendimiento, skipListcuando se usa como mapa, parece ser de 10 a 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 en el que comparar uno con otro realmente tiene sentido. Implementación de la caché de los últimos elementos utilizados recientemente utilizando ambas colecciones. Ahora la eficiencia de skipList parece ser aún más dudosa.

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);
            }
        }
    }
}
Codificador Xtra
fuente
2
Creo que ConcurrentSkipListMap debería compararse con su contraparte no concurrente, TreeMap.
abbas
2
Como comentó abbas, comparar el rendimiento con ConcurrentHashMap parece una tontería. El propósito de ConcurrentSkipListMap es (a) proporcionar concurrencia y (b) mantener el orden de clasificación entre las claves. ConcurrentHashMap hace a, pero no b. Comparar la velocidad de 0 a 60 de un Tesla y un camión volquete no tiene sentido, ya que sirven para diferentes propósitos.
Basil Bourque
Si bien no conoce las métricas de rendimiento, no sabe cuál es Tesla y cuál es "camión volquete" :) Además ... no conoce el precio de "b" sin métricas. Por lo tanto, comparar el rendimiento es algo generalmente útil.
Xtra Coder
1
¡Quizás agregue una comparación al mapa del árbol! : D
simgineer
4

Entonces, ¿cuándo debería usar ConcurrentSkipListMap?

Cuando (a) necesita mantener las claves ordenadas, y / o (b) necesita las características de primer / último, cabeza / cola y submapa de un mapa navegable.

La ConcurrentHashMapclase implementa la ConcurrentMapinterfaz, al igual que lo hace ConcurrentSkipListMap. Pero si también quieres los comportamientos de SortedMapy NavigableMap, usaConcurrentSkipListMap

ConcurrentHashMap

  • ❌ Ordenado
  • ❌ Navegable
  • ✅ concurrente

ConcurrentSkipListMap

  • ✅ Ordenado
  • ✅ Navegable
  • ✅ concurrente

Aquí hay una tabla que lo guía a través de las principales características de las diversas Mapimplementaciones incluidas con Java 11. Haga clic / toque para ampliar.

Tabla de implementaciones de mapas en Java 11, comparando sus características

Tenga en cuenta que puede obtener otras Mapimplementaciones y estructuras de datos similares de otras fuentes, como Google Guava .

Albahaca Bourque
fuente
Esta foto es asombrosa. ¿Tiene imágenes similares para algunas o todas las colecciones normales y concurrentes?
2020
1
@Anv Gracias, hacer ese gráfico requirió bastante trabajo. Es parte de mi presentación para grupos de usuarios de Java: un mapa de mapas de Java . Y no, solo he creado otro diagrama de Stringclases para las clases y la interfaz relacionadas .
Basil Bourque
1

Según las cargas de trabajo, ConcurrentSkipListMap podría ser más lento que TreeMap con métodos sincronizados como en KAFKA-8802 si se necesitan consultas de rango.

Anurag Sharma
fuente
Gracias por compartir. Estoy pensando en reemplazar TreeMap con ConcurrentSkipListMap en uno de mis proyectos, ¡así que es bueno saber esto! ¿Tiene más contexto sobre por qué ConcurrentSkipListMap es más lento y más detalles sobre la comparación de rendimiento?
yusong
0

ConcurrentHashMap: cuando desee obtener / poner basado en índices multiproceso, solo se admiten operaciones basadas en índices. Get / Put son de O (1)

ConcurrentSkipListMap: más operaciones que solo obtener / poner, como n elementos de arriba / abajo ordenados por clave, obtener la última entrada, buscar / recorrer el mapa completo ordenado por clave, etc. La complejidad es de O (log (n)), así que el rendimiento de la puesta no tan bueno como ConcurrentHashMap. No es una implementación de ConcurrentNavigableMap con SkipList.

Para resumir, use ConcurrentSkipListMap cuando desee realizar más operaciones en el mapa que requieran características ordenadas en lugar de simplemente obtener y colocar.

polainas
fuente