- PR -

HashMapの同期化について

«前のページへ 1|2|3 次のページへ»
投稿者投稿内容
yamasa
ベテラン
会議室デビュー日: 2003/02/15
投稿数: 80
投稿日時: 2003-06-07 21:28
yamasaです。

まずはパフォーマンスチューニングの鉄則ですが、必ず変更前後の
パフォーマンスを実際に測定し、比較するようにしましょう。
例えば、
Map map = new HashMap();
と
Map map = Collections.synchronizedMap(new HashMap());
をそれぞれ実際に実行させてみて、本当に同期処理がパフォーマンスの
ボトルネックとなっていることがわかったときだけチューニングを行なうべきです。
呂布さんの発言の繰り返しとなりますが、得られるリターンが割にあうものだと
確信したときだけ、リスクのある方法を取るべきです。

で、話題になっているcommons-collectionsのFastHashMapですが、
はっきり言って私はお勧めしません。

m-takaさんの指摘された通り、マルチスレッド下でのsetFastメソッドの
呼び出しは安全ではありませんし、そもそもJavaのメモリモデルは
現在のFastHashMapの実装が正しく動作することを保証していません。
# 一応API仕様書では警告されていますが、修正する気はあるのやら…
# http://issues.apache.org/bugzilla/show_bug.cgi?id=9206

私は代わりに、Doug Lea氏によるutil.concurrentパッケージをお勧めします。
http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/
この中にあるConcurrentHashMapおよびConcurrentReaderHashMapが
m-takaさんの要望に答えられるものだと思います。

ちなみに、このutil.concurrentパッケージには、他にも
マルチスレッドプログラミングを行なう上で有用なクラスが
多数収録されています。
しかも、その多くはJSR-166としてJDK1.5への追加も予定されています。
unibon
ぬし
会議室デビュー日: 2002/08/22
投稿数: 1532
お住まい・勤務地: 美人谷　　　　　　　　良回答(20pt)
投稿日時: 2003-06-08 09:07
unibon です。こんにちわ。

かなり初歩的な(便乗)質問になりますが、
同期化を試すために、そのためにはまずは HashMap のデフォルトのままで同期しないで使って、
なにか破綻する例を作り出したいと思っています。
そのため、つぎのようなサンプルコードを書いて動かしてみたのですが、
正常に動いてしまいます。
もくろみとしては、読み側(getter)のスレッドと書き側(putter)のスレッドが同時に動いて、
双方でランダムなキーを指定して読んだり(get)、書いたり(put)、して、
長く動かしていると、そのうちに put 中に get したり、get 中に put したりして、
破綻し、コード中に一箇所だけある System.out.println が表示されると思うのですが、
かなり(数分)待っても、なにも表示されず、黙々と正常に動いてしまうようです。
JDK 1.4.1 + Windows 98 の環境で試しました。

--- ここから SyncTester.java ---
コード:
import java.util.*;

public class SyncTester {

    public static void main(String[] args) {
        final int SIZE = 100000;
        final Random getterRandom = new Random(432987432987432L);
        final Random putterRandom = new Random(564165098897163L);
        final Map map = new HashMap(10, 0.1F);
        Runnable getterRunnable = new Runnable() {
            public void run() {
                while (true) {
                    int randomInt = getterRandom.nextInt(SIZE);
                    Integer key = new Integer(randomInt);
                    Object value = map.get(key);
                    if (value != null && !value.equals(key)) {
                        System.out.println("key = " + key + ", value = " + value);
                        throw new IllegalStateException();
                    }
                }
            }
        };
        Runnable putterRunnable = new Runnable() {
            public void run() {
                while (true) {
                    int randomInt = putterRandom.nextInt(SIZE);
                    Integer key = new Integer(randomInt);
                    Integer value = new Integer(randomInt);
                    map.put(key, value);
                }
            }
        };
        Thread getterThread = new Thread(getterRunnable);
        getterThread.start();
        Thread putterThread = new Thread(putterRunnable);
        putterThread.start();
    }
}

--- ここまで SyncTester.java ---
未記入
ぬし
会議室デビュー日: 2002/03/28
投稿数: 255
投稿日時: 2003-06-09 10:05
>同期化を試すために、そのためにはまずは HashMap のデフォルトのままで
>同期しないで使って、なにか破綻する例を作り出したいと思っています。

>JDK 1.4.1 + Windows 98 の環境で試しました。
まさかと思いますが，1CPUでやってませんか？

1CPU上では，そう滅多なことでは異常は発生しないと思います．
2CPU以上，ネイティブスレッドの環境にすべきです．
＃発生しないことが保証されているわけではないので，
＃バグであることには違いない．
m-taka
会議室デビュー日: 2003/05/27
投稿数: 8
投稿日時: 2003-06-09 10:19
引用:

yamasaさんの書き込み (2003-06-07 21:28) より:
yamasaです。

まずはパフォーマンスチューニングの鉄則ですが、必ず変更前後の
パフォーマンスを実際に測定し、比較するようにしましょう。

私も、HashTable/Map,synchronized{}のオーバヘッドについて
いろいろ測定しています。
その結果、今抱えている要件的には、HashTableで実装しても
問題はないだろうと判断しています。

引用:


で、話題になっているcommons-collectionsのFastHashMapですが、
はっきり言って私はお勧めしません。

m-takaさんの指摘された通り、マルチスレッド下でのsetFastメソッドの
呼び出しは安全ではありませんし、そもそもJavaのメモリモデルは
現在のFastHashMapの実装が正しく動作することを保証していません。
# 一応API仕様書では警告されていますが、修正する気はあるのやら…
# http://issues.apache.org/bugzilla/show_bug.cgi?id=9206

私も、仕様がはっきり明示されていれば良いのですが、ソースを見ないと
スレッドセーフかどうか分からないのでは、困ってしまいます。
（現行メモリモデルからの問題同様に）


引用:

私は代わりに、Doug Lea氏によるutil.concurrentパッケージをお勧めします。
http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/
この中にあるConcurrentHashMapおよびConcurrentReaderHashMapが
m-takaさんの要望に答えられるものだと思います。

はい、これは私も気に掛けていました。
ざっとソースも見てみましたが、このクラスは確実そうです。
やっぱり、手間を掛けてデザインしないとダメですね。

いろいろとご意見頂きありがとうございました。
確信を持てました。

unibon
ぬし
会議室デビュー日: 2002/08/22
投稿数: 1532
お住まい・勤務地: 美人谷　　　　　　　　良回答(20pt)
投稿日時: 2003-06-09 11:43
unibon です。こんにちわ。

引用:

悪夢を統べるものさんの書き込み (2003-06-09 10:05) より:
>JDK 1.4.1 + Windows 98 の環境で試しました。
まさかと思いますが，1CPUでやってませんか？

1CPUでやっていました。

引用:

悪夢を統べるものさんの書き込み (2003-06-09 10:05) より:
1CPU上では，そう滅多なことでは異常は発生しないと思います．
2CPU以上，ネイティブスレッドの環境にすべきです．

ありがとうございます。
さきほど Windows 2000 の 2CPU のコンピュータを使い、30分間ほど動かしてみました。
なお JDK のバージョンは環境の都合で 1.3.1 を使用しました。
しかし、1CPU + Windows 98 の時と同様に黙々と動いてしまいます。
なお、タスクマネージャでCPU使用率を見ると、
2つのCPUとも高い使用率で動いていることは確認しました。

そもそも HashMap で同期化していないと、どういうトラブルがいつ起きるのでしょうか。
そんなに稀にしか起きないものなのでしょうか。
私は、このあたりが良く分かっていません。
試したプログラムがそもそも違うのでしょうか。
それともこのプログラムで長く待てばいつかは同期化していないことによる矛盾が発生するのでしょうか。
m-taka
会議室デビュー日: 2003/05/27
投稿数: 8
投稿日時: 2003-06-09 13:13
引用:

unibonさんの書き込み (2003-06-09 11:43) より:
unibon です。こんにちわ。

そもそも HashMap で同期化していないと、どういうトラブルがいつ起きるのでしょうか。
そんなに稀にしか起きないものなのでしょうか。
私は、このあたりが良く分かっていません。
試したプログラムがそもそも違うのでしょうか。
それともこのプログラムで長く待てばいつかは同期化していないことによる矛盾が発生するのでしょうか。

unibonさん、こんにちは。
私も、もともとどこがスレッドセーフでないのかということから
始めたこのスレッドですが、Doug Lea氏によるutil.concurrentパッケージの
ConcurrentHashMapを見た感じからすると、
今のHashMapも構造的にはスレッドセーフかも知れません。
（ソースを見てる訳ではないのではっきりしませんが）
少なくともConcurrentHashMapの実装では、同期メカニズムが無かったとしても
getできた場合のvalueが異なるkeyのものであったりはしないと思います。
（古い値の可能性はあります）
ですから、現行JDKのHashMapの実装が、そのrehashメカニズムにおいて
ConcurrentHashMap同様と仮定するならば、unibonさんが実施されているテストでは
期待する結果は得られないかも知れません。

あと、もし構造的にスレッドセーフでない部分が存在したとしても、非常に
狭い範囲でしかないと思われますので、２スレッドの乱数ベースの環境では
再現は難しいかもしれまんね。


coasm
大ベテラン
会議室デビュー日: 2001/11/26
投稿数: 237
投稿日時: 2003-06-10 18:30
HashMapの実装だと、rehashとgetが競合した際に
「putしてあったはずのデータが見つからない（getがnullを返してくる）」
というタイプの不具合が起こる可能性があります。
（その場合も、もう一度getし直せば取れる可能性が大きい）

put同士の競合だと更に性質が悪くて、
「putしたはずの値が、Mapに格納されない」可能性があります。

いずれにしても、putしたのではない値がget出来てしまう可能性はないので、
unibonさんのサンプルでは検出されないでしょう。
yamasa
ベテラン
会議室デビュー日: 2003/02/15
投稿数: 80
投稿日時: 2003-06-10 18:37
yamasaです。
引用:
unibonさんの書き込み (2003-06-08 09:07) より:

同期化を試すために、そのためにはまずは HashMap のデフォルトのままで同期しないで使って、
なにか破綻する例を作り出したいと思っています。
そのため、つぎのようなサンプルコードを書いて動かしてみたのですが、
正常に動いてしまいます。

m-takaさんも指摘されていますが、現在のSun JDKの実装では
unibonさんのサンプルコードは正常に動くように見えるはずです。
# もちろん、たまたま実装がそうなっているだけで、API仕様は
# unibonさんのサンプルコードが正常に動くことを保証していません。

代わりにgetterRunnableを以下のように変更すると、
IllegalStateExceptionが投げられるようになると思います。
コード:
Runnable getterRunnable = new Runnable() {
  public void run() {
    while (true) {
      int randomInt = getterRandom.nextInt(SIZE);
      Integer key = new Integer(randomInt);
      if (map.containsKey(key)) {
        Object value = map.get(key);
        if (!key.equals(value)) {
          System.out.println("key = " + key + ", value = " + value);
          throw new IllegalStateException();
        }
      }
    }
  }
};

これでもまだ動き続けるようなら、
Object value = map.get(key);
の前に
Thread.yield();
を入れてみると、例外が発生する確率が上がるかもしれません。
«前のページへ 1|2|3 次のページへ»

スキルアップ／キャリアアップ（JOB@IT）