Javaでは、ConcurrentHashMap
より良いmultithreading
解決策があります。では、いつ使用する必要がありますConcurrentSkipListMap
か?それは冗長性ですか?
これら 2 つの間のマルチスレッドの側面は共通ですか?
Javaでは、ConcurrentHashMap
より良いmultithreading
解決策があります。では、いつ使用する必要がありますConcurrentSkipListMap
か?それは冗長性ですか?
これら 2 つの間のマルチスレッドの側面は共通ですか?
これら 2 つのクラスはいくつかの点で異なります。
ConcurrentHashMapは、コントラクトの一部としての操作の実行時間を保証しません*。また、特定の負荷要因 (大まかに言えば、それを同時に変更するスレッドの数) を調整することもできます。
一方、 ConcurrentSkipListMapは、さまざまな操作で平均 O(log(n)) パフォーマンスを保証します。また、並行性のためのチューニングもサポートしていません。 また、ceilingEntry/Key、floorEntry/Key など、そうでないConcurrentSkipListMap
操作もいくつかあります。また、 .ConcurrentHashMap
ConcurrentHashMap
基本的に、ユースケースごとに異なる実装が提供されます。1 つのキーと値のペアをすばやく追加し、1 つのキーをすばやく検索する必要がある場合は、HashMap
. 順序通りのトラバーサルを高速化する必要があり、挿入のための追加コストを許容できる場合は、SkipListMap
.
*私は、実装が O(1) 挿入/ルックアップの一般的なハッシュ マップの保証とほぼ一致していると予想しています。再ハッシュを無視する
データ構造の定義については、 スキップ リストを参照してください。
Aは、そのキーの自然な順序 (または定義した他のキー順序) で をConcurrentSkipListMap
格納します。そのため、 / /よりも操作Map
が遅くなりますが、これを相殺するために、 、、およびインターフェースがサポートされています。get
put
contains
HashMap
SortedMap
NavigableMap
ConcurrentNavigableMap
パフォーマンスに関しては、skipList
を Map として使用すると、10 ~ 20 倍遅くなるようです。これが私のテストの結果です(Java 1.8.0_102-b14、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);
}
}
}
}
Based on workloads ConcurrentSkipListMap could be slower than TreeMap with synchronized methods as in KAFKA-8802 if range queries are needed.
ConcurrentHashMap : マルチスレッド インデックス ベースの get/put が必要な場合は、インデックス ベースの操作のみがサポートされます。Get/Put は O(1) です
ConcurrentSkipListMap : get/put だけでなく、上位 / 下位 n 個のアイテムをキーでソート、最後のエントリを取得、キーでソートされたマップ全体をフェッチ/トラバースするなどの操作。複雑さは O(log(n)) であるため、put のパフォーマンスは高くありません。 ConcurrentHashMap と同じくらい素晴らしいです。これは、SkipList を使用した ConcurrentNavigableMap の実装ではありません。
要約すると、単純な get と put ではなく、並べ替えられた機能を必要とするマップでより多くの操作を実行する場合に ConcurrentSkipListMap を使用します。