はい
java-ja
February 24, 2011
145 messages
ConcurrentHashMapにSetを格納したいんだが、こんなコードでどうかなぁ?https://gist.github.com/842027
<pre>ConcurrentHashMapにSetを格納したいんだが、こんなコードでどうかなぁ?https://gist.github.com/842027</pre>
気持ち的には、internalAddやremoveで使ってるsynchronizedブロックを消したい。後、java6以降限定でおk。
<pre>気持ち的には、internalAddやremoveで使ってるsynchronizedブロックを消したい。後、java6以降限定でおk。</pre>
っつうか、何か人がスゲェ勢いでofflineになっていくんですが、気のせいですか?被害妄想ですか?
<pre>っつうか、何か人がスゲェ勢いでofflineになっていくんですが、気のせいですか?被害妄想ですか?</pre>
うちの上司が最近Javaのメモリモデルにハマってるから、何かコメントしてくれるかもしれんぜ。
<pre>うちの上司が最近Javaのメモリモデルにハマってるから、何かコメントしてくれるかもしれんぜ。</pre>
private final Map<String, Object> map = new ConcurrentHashMap<String, Object>();
<pre>private final Map<String, Object> map = new ConcurrentHashMap<String, Object>();</pre>
final LockFree lf = new LockFree();だから、大丈夫だった。
<pre>final LockFree lf = new LockFree();だから、大丈夫だった。</pre>
LockFree lf = new LockFree(); lf.add(...); だと、LockFreeのmapの初期化安全性がないけど、lf に finalついているから大丈夫か。
<pre>LockFree lf = new LockFree(); lf.add(...); だと、LockFreeのmapの初期化安全性がないけど、lf に finalついているから大丈夫か。</pre>
というのも、ashigeru の 受け売りだが、JSR-133の仕様をほとんどよんだところ、しんどかったw
<pre>というのも、ashigeru の 受け売りだが、JSR-133の仕様をほとんどよんだところ、しんどかったw</pre>
LockFreeのインスタンスは、同期的に生成されるので、初期化安全性は多分いらない感じだけども、付けた所で使い方が変わる訳で無し、付けておくます。
<pre>LockFreeのインスタンスは、同期的に生成されるので、初期化安全性は多分いらない感じだけども、付けた所で使い方が変わる訳で無し、付けておくます。</pre>
LockFree lf = new LockFree(); // map = new ConcurrentHashMap() // Normal Store
//
lf.add(...); //Set<Entry> current = this.map.get(key); // Normal Load
上記処理は、Normal Store, Normal Loadなどの Can Reorderは禁止されていないので、命令が順序変更される場合がある。
なので、 mapが観測できない場合がある。でも、ほとんど再現しないと思う。
対策はフィールドにfinalを付ける。
public class LockFree {
final ConcurrentMap<String, Set<Entry>> map = new ConcurrentHashMap<String, Set<Entry>>();
そしたら、スレッドから見える。
JSR-133でfinalはNormal扱いだけど、リオーダーを制限している。http://www.javareading.com/bof/cookbook-J20060917.html#finalFields
「言語仕様 17.5 finalフィールドのセマンティックス」
<pre>LockFree lf = new LockFree(); // map = new ConcurrentHashMap() // Normal Store // lf.add(...); //Set<Entry> current = this.map.get(key); // Normal Load 上記処理は、Normal Store, Normal Loadなどの Can Reorderは禁止されていないので、命令が順序変更される場合がある。 なので、 mapが観測できない場合がある。でも、ほとんど再現しないと思う。 対策はフィールドにfinalを付ける。 public class LockFree { final ConcurrentMap<String, Set<Entry>> map = new ConcurrentHashMap<String, Set<Entry>>(); そしたら、スレッドから見える。 JSR-133でfinalはNormal扱いだけど、リオーダーを制限している。http://www.javareading.com/bof/cookbook-J20060917.html#finalFields 「言語仕様 17.5 finalフィールドのセマンティックス」</pre>
俺なら Entry の String member に null 渡されたら hashcode とか equals とか compareTo とかで ヌルポでちゃうから、 LockFree の add で最初に値のチェック入れるか、hashcode とかのメソッドを nullsafe にするかなぁ
<pre>俺なら Entry の String member に null 渡されたら hashcode とか equals とか compareTo とかで ヌルポでちゃうから、 LockFree の add で最初に値のチェック入れるか、hashcode とかのメソッドを nullsafe にするかなぁ</pre>
keyに対してまだ何も値が無い状態で、24行目に複数のスレッドが入った場合、後から入ったスレッドがaddしたConcurrentSkipListSetが優先されるように見えるんだが、俺の勘違い?
<pre>keyに対してまだ何も値が無い状態で、24行目に複数のスレッドが入った場合、後から入ったスレッドがaddしたConcurrentSkipListSetが優先されるように見えるんだが、俺の勘違い?</pre>
putIfAbsentはatomicなので、その場合、最初のSetは普通にputされて戻り値がnull。二つ目のスレッドでは、既にputされているSetが返ってくるので、internalAddに処理が遷移する。
<pre>putIfAbsentはatomicなので、その場合、最初のSetは普通にputされて戻り値がnull。二つ目のスレッドでは、既にputされているSetが返ってくるので、internalAddに処理が遷移する。</pre>
あ、今コード読んで理解した。2つめのスレッドはbreakしないのか。戯れ言だった忘れてくれ
<pre>あ、今コード読んで理解した。2つめのスレッドはbreakしないのか。戯れ言だった忘れてくれ</pre>
今作ってるブツは物凄い量の処理を捌きたいので、後でボトルネックになると分かっている事は最初から潰しておきたい感じ。
<pre>今作ってるブツは物凄い量の処理を捌きたいので、後でボトルネックになると分かっている事は最初から潰しておきたい感じ。</pre>
後は、知的好奇心を満たす為。Lockして良いのは小学生までだよね、と言いたかったが、Setを同期しているので、言えなくて哀しい。
<pre>後は、知的好奇心を満たす為。Lockして良いのは小学生までだよね、と言いたかったが、Setを同期しているので、言えなくて哀しい。</pre>
そのためにプログラムの同期化設計が複雑になるのはどうかと思うけど、トレードオフかなーとか、勝手につぶやくw
<pre>そのためにプログラムの同期化設計が複雑になるのはどうかと思うけど、トレードオフかなーとか、勝手につぶやくw</pre>
なるほ。勉強になる。何処まで同期するスコープを狭くできるかのチキンレースな気がしてきた。モヒモヒしてない俺には近寄りがたい
<pre>なるほ。勉強になる。何処まで同期するスコープを狭くできるかのチキンレースな気がしてきた。モヒモヒしてない俺には近寄りがたい</pre>
internalAddがバグっとるがな…。set#addは重複するエントリがある場合、戻り値falseになるがな…。
<pre>internalAddがバグっとるがな…。set#addは重複するエントリがある場合、戻り値falseになるがな…。</pre>
setがisEmpty == trueだと何もセットしないでfalse返すのは何故なのか追ってる。
<pre>setがisEmpty == trueだと何もセットしないでfalse返すのは何故なのか追ってる。</pre>
<pre>http://www.javareading.com/bof/cookbook-J20060917.html#reorderings の 表見てもらえる?</pre>
public void add(String key, String value) {
Entry newentry = new Entry(value);
for (;;) {
Set<Entry> current = this.map.get(key); // Normal Load
if (current == null) {
Set<Entry> newone = new ConcurrentSkipListSet<Entry>();
newone.add(newentry);
Set<Entry> previous = this.map.putIfAbsent(key, newone); // Normal Load
if ((previous == null) || internalAdd(previous, newentry)) {
break;
}
} else {
if (internalAdd(current, newentry)) { // MonitorEnter
break;
}
}
}
}
<pre>public void add(String key, String value) { Entry newentry = new Entry(value); for (;;) { Set<Entry> current = this.map.get(key); // Normal Load if (current == null) { Set<Entry> newone = new ConcurrentSkipListSet<Entry>(); newone.add(newentry); Set<Entry> previous = this.map.putIfAbsent(key, newone); // Normal Load if ((previous == null) || internalAdd(previous, newentry)) { break; } } else { if (internalAdd(current, newentry)) { // MonitorEnter break; } } } } </pre>
Normal Load, MonitorEnter の組み合わせは、命令がリオーダーされる場合がある。
<pre>Normal Load, MonitorEnter の組み合わせは、命令がリオーダーされる場合がある。</pre>
リオーダーだから、順番が変わる場合がある。map.getが、internalAddの前に来る場合がある
<pre>リオーダーだから、順番が変わる場合がある。map.getが、internalAddの前に来る場合がある</pre>
mapをfinalにすれば、初期化安全性があるけど、この場合リオーダー食らうきがしてならない。
<pre>mapをfinalにすれば、初期化安全性があるけど、この場合リオーダー食らうきがしてならない。</pre>
んー気になったのはどっちかというと、スレッドの順序に関係なく先勝ちでSetに対して値が入ればよいのであれば、とにかくadd()読んじゃえば先に勝った方の値が入るんじゃないの?というあたり。同期化してるならなおのこと。
<pre>んー気になったのはどっちかというと、スレッドの順序に関係なく先勝ちでSetに対して値が入ればよいのであれば、とにかくadd()読んじゃえば先に勝った方の値が入るんじゃないの?というあたり。同期化してるならなおのこと。</pre>
あとinternalAddってprivateメソッドだし、引数はConcurrentSkipListSetを前提として良いような気もした。
<pre>あとinternalAddってprivateメソッドだし、引数はConcurrentSkipListSetを前提として良いような気もした。</pre>
ああ、これ途中で他のスレッドから挿入された場合はもう一回ループしたい、ということなんか。
<pre>ああ、これ途中で他のスレッドから挿入された場合はもう一回ループしたい、ということなんか。</pre>
でもsynchronizedしてるのでSetの中身は保証されるし、putIfAbsentはアトミックでスレッド安全だし、原稿コードでは起きないような気がする。
<pre>でもsynchronizedしてるのでSetの中身は保証されるし、putIfAbsentはアトミックでスレッド安全だし、原稿コードでは起きないような気がする。</pre>
あのリンク先の話って、複数スレッドが同じものを見ていてしかもそれにはロックもvolatileもかかってないケースの話かと。
<pre>あのリンク先の話って、複数スレッドが同じものを見ていてしかもそれにはロックもvolatileもかかってないケースの話かと。</pre>
ん?current変数と同じポインタは、ロックされていないから、複数のスレッドが見るよ。
<pre>ん?current変数と同じポインタは、ロックされていないから、複数のスレッドが見るよ。</pre>
map.get()したとき、値が取れなかったとしても、もしかしたら他のスレッドがput()し終わってるのだけど、現スレッドには見えてないだけって可能性があるって話かな。
<pre>map.get()したとき、値が取れなかったとしても、もしかしたら他のスレッドがput()し終わってるのだけど、現スレッドには見えてないだけって可能性があるって話かな。</pre>
同期なしのHashMapだとあり得そう。ConcurrentHashMapだとどうなんかな。
<pre>同期なしのHashMapだとあり得そう。ConcurrentHashMapだとどうなんかな。</pre>
ConcurrentSkipListSetって、実装的に、スレッド間の操作の前後関係は保証されるんだろうか。
<pre>ConcurrentSkipListSetって、実装的に、スレッド間の操作の前後関係は保証されるんだろうか。</pre>
mapがfinalで保証されるのは、final変数の可視性だけのように思う。Mapの中身じゃなくて。
<pre>mapがfinalで保証されるのは、final変数の可視性だけのように思う。Mapの中身じゃなくて。</pre>
繰り返すけど、このLockFreeオブジェクト自体は動機的に生成されるから、コンストラクタの処理が完全に終了するよりも前に、LockFree#addやLockFree#removeが呼出される事は無いのぜ。
<pre>繰り返すけど、このLockFreeオブジェクト自体は動機的に生成されるから、コンストラクタの処理が完全に終了するよりも前に、LockFree#addやLockFree#removeが呼出される事は無いのぜ。</pre>
if (set.isEmpty()) { ってところは、ここに入る直前にremoveによってSetがclearされてることを想定しているように思うのだけど、
<pre>if (set.isEmpty()) { ってところは、ここに入る直前にremoveによってSetがclearされてることを想定しているように思うのだけど、</pre>
空の場合は、既にmapからremove済みのエントリである為、単にsetにaddするとaddしたEntryが亜空間に消える。
<pre>空の場合は、既にmapからremove済みのエントリである為、単にsetにaddするとaddしたEntryが亜空間に消える。</pre>
current = map#get() ~ if(current==null) のelseブロックが、投機的な最適化によって、順序が入れ替わる可能性について考えているのだけど
<pre>current = map#get() ~ if(current==null) のelseブロックが、投機的な最適化によって、順序が入れ替わる可能性について考えているのだけど</pre>
複数スレッドから共有メモリがどう見えるかって話なんだろうし、これって「何らかの方法で同期しない限り保証されない」「volatile使うと表の条件で保証されるよ」という話のように解釈しているが…
<pre>複数スレッドから共有メモリがどう見えるかって話なんだろうし、これって「何らかの方法で同期しない限り保証されない」「volatile使うと表の条件で保証されるよ」という話のように解釈しているが…</pre>
表を見ると、normal xxx が絡むととりあえず保証されませんよ、という図になってる。
<pre>表を見ると、normal xxx が絡むととりあえず保証されませんよ、という図になってる。</pre>
currentに関して言えば、これはローカル変数なのでスレッドそれぞれ固有になるので、可視性とかあまり関係ない気が。
<pre>currentに関して言えば、これはローカル変数なのでスレッドそれぞれ固有になるので、可視性とかあまり関係ない気が。</pre>
変更内容の結果が問題なんじゃなくて、投機的なReorderingによって、結果が変わってしまう可能性がある事が問題。
<pre>変更内容の結果が問題なんじゃなくて、投機的なReorderingによって、結果が変わってしまう可能性がある事が問題。</pre>
でも、internalAddはcurrent変数を引数に取るのだからやはり、投機的な最適化を行うコンパイラであったとしても、順序を入れ替えたり出来んだろう。
<pre>でも、internalAddはcurrent変数を引数に取るのだからやはり、投機的な最適化を行うコンパイラであったとしても、順序を入れ替えたり出来んだろう。</pre>
<pre>http://www.google.com/codesearch/p?hl=ja#GLh8vwsjDqs/trunk/src/mapred/org/apache/hadoop/mapred/IndexCache.java&q=%5C.%5Cs*putIfAbsent%5Cs*%5C(%20lang:java%20license:apache&l=90</pre>
ConcurrentMapのエントリに触る時は、synchronizedするしか無いのかもしれぬ。
<pre>ConcurrentMapのエントリに触る時は、synchronizedするしか無いのかもしれぬ。</pre>
LockFree#getで取ったIterable経由でSetが空っぽになるまでremoveすると、LockFree#addが適切に動作しなくなる事に気付いたのでなおした。https://gist.github.com/842027
<pre>LockFree#getで取ったIterable経由でSetが空っぽになるまでremoveすると、LockFree#addが適切に動作しなくなる事に気付いたのでなおした。https://gist.github.com/842027</pre>




