狠狠撸

狠狠撸Share a Scribd company logo

闯补惫补でトランザクショナルメモリを使う

?Download as PPT, PDF?
?
Kenji Kazumura
Kenji Kazumura

JJUG CCC 2014 Spring #ccc_r27のスライド @kkzr

Convert to study guideBETA

Transform any presentation into a summarized study guide, highlighting the most important points and key insights.

1 of 57
Downloaded 53 times
Copyright 2014 FUJITSU LIMITED Java でトランザクショナルメモ リを使う 2014.5.18 数村　憲治 JJUG CCC 2014 Spring
目次 ? JavaVM におけるロックの進化 ? トランザクショナルメモリ（ TM ）とは ? Haswell でのトランザクショナルメモリ ? Java でトランザクショナルメモリを使う ? JDK8/9 の動向 ? まとめ 2 Copyright 2014 FUJITSU LIMITED
3 Copyright 2014 FUJITSU LIMITED JavaVM ロック機構の進化 第一世代 ヘビーロック 第二世代 シンロック 第三世代 バイアスロック 第四世代 ？？？ JDK1.0-1.2 JDK1.3.1 HotSpot VM JDK5.0 HotSpot VM
競合と共有（定義） ? ロック競合とは ?複数のスレッドが同時 に同じロックを取る ? ロック共有とは ?複数のスレッドが同じ ロックを使用する 4 Copyright 2014 FUJITSU LIMITED スレッド A スレッド B ロック X 獲得 ロック X 待ち ロック X の競合 ロック競合している例 共有しているが競合していない例 スレッド A スレッド B ロック X 獲得 ロック X 解放 ロック X 獲得 CS 実 行 CS 実 行 CS 実 行
競合と共有（定義） ? データ競合とは ?複数のスレッドが同じ データにアクセスする こと、あるいは、アク セスするためのロック 競合 5 Copyright 2014 FUJITSU LIMITED synchronized(array) { array[1] = 2; } synchronized(array) { array[2] = 4; } スレッド A スレッド B ロック競合しているが データ競合していないコード例 ロック競合しているが データ競合していない例 スレッド A スレッド B ロック X 獲得 ロック X 待ち ロックの競合 アクセス Y アクセス Z ロック X 解放 ロック X 獲得 データ競合なし CS 実 行 CS 実 行
ヘビーロック ? OS のロック関数 (pthread_mutex_lock/unlock 等 ) を使用 ? 実装が簡単なため、初期の JVM で使用 ? オブジェクト毎に mutex を作成?保持する 必要がある 6 Copyright 2014 FUJITSU LIMITED 管理ヘッダ mutex Java オブジェクト mutex_t if(obj->mutex == null) { obj->mutex = malloc(…); … } pthread_mutex_lock(&obj->mutex); 本来の オブジェクト データ synchornize の実装例
シンロック ? ほとんどのロックは競合してない ? CAS(Compare and Swap) で十分 ? マルチコア?メニーコア CPU では、 CAS の コストはバカにならない 7 Copyright 2014 FUJITSU LIMITED ロック ビット Java オブジェクト 管理ヘッダ mov 0, %R2 ld [ ロックビット ], %R1 cas [ ロックビット ], %R1, %R2 cmp %R1, %R2 jne ヘビーロック 通常処理 0: ロック 1: アンロック シンロック実装例
バイアスロック ? ほとんどのロックは共有されていない ?特定のスレッド使うならロックする必要はない ? 最初（バイアスされていない時）だけ CAS ? そのあとは Load ＆ Compare 8 Copyright 2014 FUJITSU LIMITED ld [ バイアス情報 ], %R1 cmp %R1, 自分自身のスレッド jne バイアス無効処理 通常処理 バイアスされている場合の 実装例 StringBuffer sb = new StringBuffer(); sb.append( abc”);“ sb.append( def”);“ String str = sb.toString(); return str; バイアスロックの有効例
java.util.concurrent パッケージ ? JDK5.0 から導入 ? synchronize より柔軟なロック 9 Copyright 2014 FUJITSU LIMITED import java.util.concurrent.locks.ReentrantLock; ReentrantLock lock = new ReentrantLock(); … public void m() { lock.lock(); try { // クリティカルセクションの実行 } finally { lock.unlock(); } tryLock() isLocked() getOwner() 使用例 便利な API (ReentrantLock) 便利なクラス ReadWriteLock Semaphore AtomicInteger
目次 ? JavaVM におけるロックの進化 ? トランザクショナルメモリ（ TM ）とは ? Haswell でのトランザクショナルメモリ ? Java でトランザクショナルメモリを使う ? JDK8/9 の動向 ? まとめ 10 Copyright 2014 FUJITSU LIMITED
トランザクショナルメモリとは ? 楽観的ロック ? とりあえず、ロックはしない ? 実行しているうちに、データ競合があった ら、それまでの実行結果を破棄（ アボート ）して、最初の状態にもどる（ロールバッ ク） ? 最後までデータ競合がなければ、結果を確 定する（コミット） 11 Copyright 2014 FUJITSU LIMITED
悲観的ロックと楽観的ロック 12 Copyright 2014 FUJITSU LIMITED 楽観的ロック 非観的ロック スレッド１ スレッド 2 スレッド 3 スレッド 4 ロック ロック ロック ロック クリティカルセクションの実行はシリアライズ スレッド１ スレッド 2 スレッド 3 スレッド 4 　　　 　　　 　　　 　　　 ロ ッ ク な し クリティカルセクションの実行は並行
HTM と STM ? トランザクショナルメモリ（ TM ）をハー ドで実現するのを HTM 、ソフトで実現する のを STM と呼ぶ。 ? HTM の実装例 ?IBM System z (zEC12) ?Intel Haswell Microarchitecture ? STM の実装例 ?Scala ?Haskell 13 Copyright 2014 FUJITSU LIMITED
目次 ? JavaVM におけるロックの進化 ? トランザクショナルメモリ（ TM ）とは ? Haswell でのトランザクショナルメモリ ? Java でトランザクショナルメモリを使う ? JDK8/9 の動向 ? まとめ 14 Copyright 2014 FUJITSU LIMITED
TSX ? Intel? Transactional Synchronization Extension ?Intel アーキテクチャでの HTM 実装 ?Haswell で利用可能 ?HLE と RTM の２種類 ? Hardware Lock Elision ?従来 (mutex) 方式と互換インタフェース ? Restricted Transaction Memory ?新しいインタフェース 15 Copyright 2014 FUJITSU LIMITED
HLE ? 従来の mutex_lock/mutex_unlock の形式で そのまま置き換えられる ? アボートしたら、自動的にリトライ 16 Copyright 2014 FUJITSU LIMITED mov $1, %eax RETRY: xacquire xchg mutex, %eax test %eax, %eax jne RETRY xrelease mov $0, mutex mutex_lock(&mutex); mutex_unlock(&mutex); クリティカルセクションの 実行 クリティカルセクションの実 行 従来 (mutex) HLE
GCC4.8 から HLE サポート 17 Copyright 2014 FUJITSU LIMITED #include <immintrin.h> void lock_hle_gcc(int mutex) {* while (__atomic_exchange_n(mutex, 1, __ATOMIC_ACQUIRE|__ATOMIC_HLE_ACQUIRE)) _mm_pause(); } void unlock_hle_gcc(int mutex) {* __atomic_clear(mutex, __ATOMIC_RELEASE|__ATOMIC_HLE_RELEASE); } 以下のような関数を自分で用意する（ fallback なし） int mutex = 0; void func() { lock_hle_gcc(&mutex); // クリティカルセクションの実行 unlock_hle_gcc(&mutex); クリティカルセクションを 上記 2 関数で挟む
GCC4.8 から HLE をサポート 18 Copyright 2014 FUJITSU LIMITED 0000000000000000 <lock_hle_gcc>: 0: ba 01 00 00 00 mov $0x1,%edx 5: eb 0b jmp 12 <lock_hle_gcc+0x12> 7: 66 0f 1f 84 00 00 00 nopw 0x0(%rax,%rax,1) 10: f3 90 pause 12: 89 d0 mov %edx,%eax 14: f2 87 07 xacquire xchg %eax,(%rdi) 17: 85 c0 test %eax,%eax 19: 75 f5 jne 10 <lock_hle_gcc+0x10> 1b: f3 c3 repz retq 1d: 0f 1f 00 nopl (%rax) 0000000000000020 <unlock_hle_gcc>: 20: f3 c6 07 00 xrelease movb $0x0,(%rdi) 24: c3 retq ディスアセンブルするには、新しい objdump(binutils) が必要
RTM ? アボートした時のハンドラ―を自分で書く必 要あり 19 Copyright 2014 FUJITSU LIMITED RETRY: xbegin FAIL cmp mutex, $0 jz OK FAIL: # goto RETRY or SLOWPATH SLOWPATH: # original code OK: ret cmp mutex, $0 jne SLOWPATH xend ret SLOWPATH: # original code ロックコード アンロックコード
いつアボートするか ? トランザクションが長い ? I/O が入る ? OS によるスレッドコンテキストスイッチ ? 特殊な命令を実行 (CPUID/XABORT) ? ネストが深すぎる ? L1 キャッシュラインの競合 20 Copyright 2014 FUJITSU LIMITED
Haswell のキャッシュ ? L1 Instruction Cache 32KB 8-way ? L1 Data Cache 32KB 8-way ?コアごと ( スレッドで共有 ) ? L2 Unified Cache 256KB 8-way ?コアごと ( スレッドで共有 ) ? キャッシュライン 64B 21 Copyright 2014 FUJITSU LIMITED 64 バイト 64 バイト 64 バイト 64 バイト L1 Data Cache 64 個 8-way
キャッシュラインの競合 ? TSX では、 L1 キャッシュラインでデータ競 合を検出 22 Copyright 2014 FUJITSU LIMITED xbegin FAIL mov (0x1000), %eax xend スレッド A xbegin FAIL mov %eax, (0x1010) xend スレッド B 0x1000 0x1010 0x1004 0x1008 0x1040 アドレス 同 一 キ ャ ッ シ ュ ラ イ ン 競合
目次 ? JavaVM におけるロックの進化 ? トランザクショナルメモリ（ TM ）とは ? Haswell でのトランザクショナルメモリ ? Java でトランザクショナルメモリを使う ? JDK8/9 の動向 ? まとめ 23 Copyright 2014 FUJITSU LIMITED
Java での実装案 ? synchronize の実装として使う ? API として提供 ? 特定ライブラリでの実装 24 Copyright 2014 FUJITSU LIMITED
synchronize の実装 ? アプリの修正が不要 ? 個別に指定できない ?競合あるところは TM は向いていないので、従 来実装を使いたい ?競合のないところは、 TM 実装を使いたい ? 実装するのがたいへん ?JVM （ HotSpot ）の中でかなりの部分に影響 25 Copyright 2014 FUJITSU LIMITED
API として提供 ? アプリ修正が必要 ? 選択的に使用可能 ? 使う側がどういう場合に TM が向いている か理解している必要あり ? 使用方法は ReentrantLock と同じ ? 実装は syhchronize ほどではないが、比較的 たいへん。 26 Copyright 2014 FUJITSU LIMITED
特定ライブラリでの実装 ? アプリ修正は不要 ? 使いたいところで使えない ? 例 java.util.HashMap/ArrayList/LinkedList 27 Copyright 2014 FUJITSU LIMITED table HashMap Entry テーブル Key Value Key Value
API 方式での実装 28 Copyright 2014 FUJITSU LIMITED public final class HTM { private ByteBuffer data; private long mutex_addr; public HTM() { data = ByteBuffer.allocateDirect(64); mutex_addr = nativeAddress(data); } public void lock() { lockRTM(mutex_addr); } public void unlock() { unlockRTM(mutex_addr); } static private native void lockRTM(long addr); static private native void unlockRTM(long addr); 使用方法 HTM htm = new HTM(); htm.lock(); // クリティカル // セクションの実行 htm.unlock();
HTM クラスの構造 29 Copyright 2014 FUJITSU LIMITED ByteBuffer data HTM 64 バイト long mutex_addr Java ヒープ C ヒープ DirectByteBuffer ??? long address allocateDirect(64) mutex
ネイティブメソッド (C) 30 Copyright 2014 FUJITSU LIMITED #include <jni.h> void java_htm_lock_rtm(jlong); void java_htm_unlock_rtm(jlong); JNIEXPORT void JNICALL Java_HTM_lockRTM(JNIEnv *env, jclass kl, jlong add) { java_htm_lock_rtm(add); } JNIEXPORT void JNICALL Java_HTM_unlockRTM(JNIEnv *env, jclass kl, jlong add) { java_htm_unlock_rtm(add); }
ネイティブメソッド (asm) 31 Copyright 2014 FUJITSU LIMITED # void java_htm_lock_rtm(jlong) java_htm_lock_rtm: movl $10, %ecx #retry count .RETRY: xbegin .FAIL cmpl $0, (%rdi) jz .OK xabort $0xfe .FAIL: pause dec %ecx cmpl $0, %ecx jz .SLOWPATH jmp .RETRY .SLOWPATH: xor %edx, %edx inc %edx xor %eax, %eax lock cmpxchgl %edx, (%rdi) jne .SLOWPATH .OK: ret # void java_htm_unlock_rtm(jlong) java_htm_unlock_rtm: cmpl $0, (%rdi) jz .END movl $0, (%rdi) ret .END: xend ret
データ競合なしプログラム ? 本来ロックを取る必要のないプログラムで のベンチマーク ? 一定量 (500,000,000 回 ) スレッドローカル な変数をインクリメントする ? スレッド数を１から８まで増やす ? 各スレッドに均等な処理量を分割する ? 各スレッドの処理時間の平均を求める ? 「排他なし」、「 synchronized 」、　　　 「 ReentrantLock 」「 HTM 」の４パターン 32 Copyright 2014 FUJITSU LIMITED
データ競合なしプログラム 33 Copyright 2014 FUJITSU LIMITED class LockNone extends Test { LockNone(long amount) { this.amount = amount; } void doIt() { count++; } } abstract class Test implements Runnable { long count; long time; long amount; public void run() { count = 0; long start = System.currentTimeMillis(); while (count < amount) { doIt(); } long end = System.currentTimeMillis(); time = (end-start); } } 排他なし
データ競合なしプログラム 34 Copyright 2014 FUJITSU LIMITED class LockSync extends Test { Object lock; LockSync(long amount, Object lock) { this.amount = amount; this.lock = lock; } void doIt() { synchronized (lock) { count++; } } } synchronized 使用
データ競合なしプログラム 35 Copyright 2014 FUJITSU LIMITED class LockConc extends Test { ReentrantLock lock; LockConc(long amount, ReentrantLock lock) { this.amount = amount; this.lock = lock; } void doIt() { lock.lock(); count++; lock.unlock(); } } ReentrantLock 使用
データ競合なしプログラム 36 Copyright 2014 FUJITSU LIMITED class LockRTM extends Test { HTM htm; LockRTM(long amount, HTM htm) { this.amount = amount; this.htm = htm; } void doIt() { htm.lock(); count++; htm.unlock(); } } HTM 使用
データ競合なし（結果） 37 Copyright 2014 FUJITSU LIMITED １スレッドあたりの平均処理時間 JDK1.7.0_51 Intel Xeon E3-1270 v3 3.5GHz Red Hat Enterprise Linux Server release 6.5 (Santiago)
ネイティブメソッド呼出し ? ネイティブメソッドの呼び出しはコストが 高い ? 性能高速化のために、 Java でかけるコード を C にしても、速くなるとは限らない 38 Copyright 2014 FUJITSU LIMITED Java メソッド ネイティブ メソッドスタブ コード 直接呼べない
スタブコード (unlockRTM) 39 Copyright 2014 FUJITSU LIMITED Decoding compiled method 0x00007f12dd05ebd0: Code: [Disassembling for mach='i386:x86-64'] [Entry Point] # {method} 'unlockRTM' '(J)V' in 'HTM' # parm0: rsi:rsi = long # [sp+0x50] (sp of caller) 0x00007f12dd05ed60: mov 0x8(%rsi),%r10d 0x00007f12dd05ed64: cmp %r10,%rax 0x00007f12dd05ed67: je 0x00007f12dd05ed78 0x00007f12dd05ed6d: jmpq 0x00007f12dd037960 ; {runtime_call} 0x00007f12dd05ed72: nopw 0x0(%rax,%rax,1) [Verified Entry Point] 0x00007f12dd05ed78: mov %eax,-0x14000(%rsp) 0x00007f12dd05ed7f: push %rbp 0x00007f12dd05ed80: mov %rsp,%rbp 0x00007f12dd05ed83: sub $0x40,%rsp 0x00007f12dd05ed87: mov %rsi,%rdx 0x00007f12dd05ed8a: movabs $0xdff84370,%r14 ; {oop(a 'java/lang/Class' = 'HTM')} 0x00007f12dd05ed94: mov %r14,0x30(%rsp) 0x00007f12dd05ed99: lea 0x30(%rsp),%r14 0x00007f12dd05ed9e: mov %r14,%rsi ; OopMap{[48]=Oop off=65} 0x00007f12dd05eda1: movabs $0x7f12dd05eda1,%r10 ; {section_word} 0x00007f12dd05edab: mov %r10,0x1c0(%r15) 0x00007f12dd05edb2: mov %rsp,0x1b8(%r15) 0x00007f12dd05edb9: cmpb $0x0,0x8ef495a(%rip) # 0x00007f12e5f5371a ; {external_word} 0x00007f12dd05edc0: je 0x00007f12dd05edfa 0x00007f12dd05edc6: push %rsi 0x00007f12dd05edc7: push %rdx 0x00007f12dd05edc8: movabs $0xdafd0040,%rsi ; {oop({method} 'unlockRTM' '(J)V' in 'HTM')} 0x00007f12dd05edd2: mov %r15,%rdi 0x00007f12dd05edd5: test $0xf,%esp 0x00007f12dd05eddb: je 0x00007f12dd05edf3 0x00007f12dd05ede1: sub $0x8,%rsp 0x00007f12dd05ede5: callq 0x00007f12e59c4230 ; {runtime_call} 0x00007f12dd05edea: add $0x8,%rsp 0x00007f12dd05edee: jmpq 0x00007f12dd05edf8 0x00007f12dd05edf3: callq 0x00007f12e59c4230 ; {runtime_call} 0x00007f12dd05edf8: pop %rdx 0x00007f12dd05edf9: pop %rsi 0x00007f12dd05edfa: lea 0x1d8(%r15),%rdi 0x00007f12dd05ee01: movl $0x4,0x250(%r15) 0x00007f12dd05ee0c: callq 0x00007f12da7ef660 ; {runtime_call} 0x00007f12dd05ee11: vzeroupper 0x00007f12dd05ee14: movl $0x5,0x250(%r15) 0x00007f12dd05ee1f: mov %r15d,%ecx 0x00007f12dd05ee22: shr $0x4,%ecx 0x00007f12dd05ee25: and $0xffc,%ecx 0x00007f12dd05ee2b: movabs $0x7f12e61ac000,%r10 ; {external_word} 0x00007f12dd05ee35: mov %ecx,(%r10,%rcx,1) 0x00007f12dd05ee39: cmpl $0x0,0x8efd83d(%rip) # 0x00007f12e5f5c680 ; {external_word} 0x00007f12dd05ee43: jne 0x00007f12dd05ee57 0x00007f12dd05ee49: cmpl $0x0,0x30(%r15) 0x00007f12dd05ee51: je 0x00007f12dd05ee74 0x00007f12dd05ee57: mov %r15,%rdi 0x00007f12dd05ee5a: mov %rsp,%r12 0x00007f12dd05ee5d: sub $0x0,%rsp 0x00007f12dd05ee61: and $0xfffffffffffffff0,%rsp 0x00007f12dd05ee65: callq 0x00007f12e5a655a0 ; {runtime_call} 0x00007f12dd05ee6a: mov %r12,%rsp 0x00007f12dd05ee6d: mov 0x8ed8f3c(%rip),%r12 # 0x00007f12e5f37db0 ; {external_word} 0x00007f12dd05ee74: movl $0x8,0x250(%r15) 0x00007f12dd05ee7f: cmpl $0x1,0x27c(%r15) 0x00007f12dd05ee8a: je 0x00007f12dd05ef13 0x00007f12dd05ee90: cmpb $0x0,0x8ef4883(%rip) # 0x00007f12e5f5371a ; {external_word} 0x00007f12dd05ee97: je 0x00007f12dd05eecd 0x00007f12dd05ee9d: movabs $0xdafd0040,%rsi ; {oop({method} 'unlockRTM' '(J)V' in 'HTM')} 0x00007f12dd05eea7: mov %r15,%rdi 0x00007f12dd05eeaa: test $0xf,%esp 0x00007f12dd05eeb0: je 0x00007f12dd05eec8 0x00007f12dd05eeb6: sub $0x8,%rsp 0x00007f12dd05eeba: callq 0x00007f12e59c4380 ; {runtime_call} 0x00007f12dd05eebf: add $0x8,%rsp 0x00007f12dd05eec3: jmpq 0x00007f12dd05eecd 0x00007f12dd05eec8: callq 0x00007f12e59c4380 ; {runtime_call} 0x00007f12dd05eecd: movabs $0x0,%r10 0x00007f12dd05eed7: mov %r10,0x1b8(%r15) 0x00007f12dd05eede: movabs $0x0,%r10 0x00007f12dd05eee8: mov %r10,0x1c0(%r15) 0x00007f12dd05eeef: mov 0x38(%r15),%rcx 0x00007f12dd05eef3: movq $0x0,0x100(%rcx) 0x00007f12dd05eefe: leaveq 0x00007f12dd05eeff: cmpq $0x0,0x8(%r15) 0x00007f12dd05ef07: jne 0x00007f12dd05ef0e 0x00007f12dd05ef0d: retq 0x00007f12dd05ef0e: jmpq Stub::forward exception ; {runtime_call} 0x00007f12dd05ef13: mov %rsp,%r12 0x00007f12dd05ef16: sub $0x0,%rsp 0x00007f12dd05ef1a: and $0xfffffffffffffff0,%rsp 0x00007f12dd05ef1e: callq 0x00007f12e59c3600 ; {runtime_call} 0x00007f12dd05ef23: mov %r12,%rsp 0x00007f12dd05ef26: mov 0x8ed8e83(%rip),%r12 # 0x00007f12e5f37db0 ; {external_word} 0x00007f12dd05ef2d: jmpq 0x00007f12dd05ee90 0x00007f12dd05ef32: hlt
JIT コードを disassemble ? hsdis-amd64.so の場所を LD_LIBRARY_PATH に ? -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly 40 Copyright 2014 FUJITSU LIMITED
native intrinsic ? ネイティブメソッドを JIT が翻訳したコード のように扱う ? インライン展開することで、スタブが不要 41 Copyright 2014 FUJITSU LIMITED Java ソース C ソース .class .so/.dll 翻訳 コード javac C コンパイラ jit スタブ経由の 呼出し 同等コード アセンブラ 翻訳 コード 取込み
intrinsic コード (lock) 42 Copyright 2014 FUJITSU LIMITED instruct htm_lock_rtm( memory adr, rax_RegI result, rcx_RegI tmp) %{ match(HtmRtmLock adr); ins_encode %{ Label retry, fail, ok, slowpath; __ movl($tmp$$Register, 10); __ bind(retry); __ xbegin(fail); __ cmpl($adr$$Address, 0); __ jccb(Assembler::equal, ok); __ xabort(0xfe); __ bind(fail); __ pause(); __ decrementl($tmp$$Register); __ cmpl($tmp$$Register, 0); __ jccb(Assembler::equal, slowpath); __ jmp(retry); __ bind(slowpath); __ movl($tmp$$Register, 1); __ movl($result$$Register, 0); __ lock(); __ cmpxchgl($tmp$$Register, $adr$$Address); __ jccb(Assembler::notEqual, slowpath); __ bind(ok); hotspot/src/cpu/x86/vm/x86_64.ad
intrinsic コード (unlock) 43 Copyright 2014 FUJITSU LIMITED instruct htm_unlock_rtm(memory adr, rax_RegI result) %{ match(HtmRtmUnlock adr); ins_encode %{ Label end, done; __ cmpl($adr$$Address, 0); __ jccb(Assembler::equal, end); __ movl($adr$$Address, 0); __ jmp(done); __ bind(end); __ xend(); __ bind(done); hotspot/src/cpu/x86/vm/x86_64.ad
データ競合なし（結果） 44 Copyright 2014 FUJITSU LIMITED １スレッドあたりの平均処理時間 JDK1.7.0_51 Intel Xeon E3-1270 v3 3.5GHz Red Hat Enterprise Linux Server release 6.5 (Santiago)
データ競合あるかもプログラム ? ArrayList アクセス時にロックを取るプログ ラムでのベンチマーク ? 全部で一定回数 (100,000,000 回 ) 、 ArrayList の連続した２要素を入れ替 える ? 入れ替える場所はランダムに決める ? 配列要素は十分大きい ? スレッド数を１から８まで増やす ? 各スレッドに均等な処理量を分割する ? 各スレッドの処理時間の平均を求める45 Copyright 2014 FUJITSU LIMITED
データ競合あるかもプログラム 46 Copyright 2014 FUJITSU LIMITED static long AMOUNT = 100_000_000L; static int ARRAY_SIZE = 131_072; static ArrayList<Object> alist = new ArrayList<>(ARRAY_SIZE); abstract class Test implements Runnable { long count; long time; long amount; long seed; public void run() { count = 0; long start = System.currentTimeMillis(); while (count < amount) { int n1 = nextInt(ARRAY_SIZE); int n2 = n1+1; if (n2 == ARRAY_SIZE) n2 -= 2; doIt(n1, n2); count++; } long end = System.currentTimeMillis(); time = (end-start); } void swap(int n1, int n2) { Object o1 = alist.get(n1); Object o2 = alist.get(n2); alist.set(n1, o2); alist.set(n2, o1); } int nextInt(int n) { long nextseed = (seed * 0x5deece66dL + 0xbL) & ((1L << 48) - 1); long rnd31 = nextseed >>> (48-31); seed = nextseed; return (int) ((n * rnd31) >> 31); }
データ競合あるかもプログラム 47 Copyright 2014 FUJITSU LIMITED void doIt(int n1, int n2) { synchronized (lock) { swap(n1, n2); } } void doIt(int n1, int n2) { lock.lock(); try { swap(n1, n2); } finally { lock.unlock(); } } void doIt(int n1, int n2) { swap(n1, n2); } void doIt(int n1, int n2) { htm.lock(); try { swap(n1, n2); } finally { htm.unlock(); } } 排他なし HTM synchronized ReentrantLock
データ競合あるかも（結果） 48 Copyright 2014 FUJITSU LIMITED １スレッドあたりの平均処理時間 JDK1.7.0_51 Intel Xeon E3-1270 v3 3.5GHz Red Hat Enterprise Linux Server release 6.5 (Santiago)
目次 ? JavaVM におけるロックの進化 ? トランザクショナルメモリ（ TM ）とは ? Haswell でのトランザクショナルメモリ ? Java でトランザクショナルメモリを使う ? JDK8/9 の動向 ? まとめ 49 Copyright 2014 FUJITSU LIMITED
JDK8/9 の動向 ? -XX:+UseRTMLocking ?https://bugs.openjdk.net/browse/JDK-8031320 ? synchronize の実装として使用 ?メソッド毎に有効?無効を指定する仕組みはあ りそう ? バイアスロックとは排他関係 ? 性能は？ 50 Copyright 2014 FUJITSU LIMITED
データ競合なし (JDK9) 51 Copyright 2014 FUJITSU LIMITED １スレッドあたりの平均処理時間
目次 ? JavaVM におけるロックの進化 ? トランザクショナルメモリ（ TM ）とは ? Haswell でのトランザクショナルメモリ ? Java でトランザクショナルメモリを使う ? JDK8/9 の動向 ? まとめ 52 Copyright 2014 FUJITSU LIMITED
Java で TM が有効なケース ? ロック共有しているが、ロック競合がない ?バイアスロックが不向きなパターン ? ロック競合はあるが、データ競合がない ?本来プログラム的にはロックの必要がなく、安 心のためだけにロックを入れている ? ロック競合はあるが、ほとんどデータ競合 せず、たまに競合する場合がある ?ArrayList のパターン 53 Copyright 2014 FUJITSU LIMITED
Java で TM の効果ないケー ス ? ロック競合がほとんど起きていない ? ロック期間が長い ?バッファ枯渇やコンテキストスイッチ ? ロック中に IO あり ?デバッグは難しい ? ロック中に GC あり ? 共有しないロックを何度も使う ?バイアスロックがよい 54 Copyright 2014 FUJITSU LIMITED
Q&A 55 Copyright 2014 FUJITSU LIMITED
56 Copyright 2014 FUJITSU LIMITED Java は、 Oracle Corporation およびその子会社、関連会社の米国および その他の国おける登録商標です。 本ドキュメントに記載されている、社名、商品名等は各社の商標または 登録商標である場合があります。 その他の記載されている、商標および登録商標については、 一般に各社の商標または登録商標です。
57 Copyright 2010 FUJITSU LIMITED

More Related Content

闯补惫补でトランザクショナルメモリを使う

  • 1. Copyright 2014 FUJITSU LIMITED Java でトランザクショナルメモ リを使う 2014.5.18 数村　憲治 JJUG CCC 2014 Spring
  • 2. 目次 ? JavaVM におけるロックの進化 ? トランザクショナルメモリ（ TM ）とは ? Haswell でのトランザクショナルメモリ ? Java でトランザクショナルメモリを使う ? JDK8/9 の動向 ? まとめ 2 Copyright 2014 FUJITSU LIMITED
  • 3. 3 Copyright 2014 FUJITSU LIMITED JavaVM ロック機構の進化 第一世代 ヘビーロック 第二世代 シンロック 第三世代 バイアスロック 第四世代 ？？？ JDK1.0-1.2 JDK1.3.1 HotSpot VM JDK5.0 HotSpot VM
  • 4. 競合と共有（定義） ? ロック競合とは ?複数のスレッドが同時 に同じロックを取る ? ロック共有とは ?複数のスレッドが同じ ロックを使用する 4 Copyright 2014 FUJITSU LIMITED スレッド A スレッド B ロック X 獲得 ロック X 待ち ロック X の競合 ロック競合している例 共有しているが競合していない例 スレッド A スレッド B ロック X 獲得 ロック X 解放 ロック X 獲得 CS 実 行 CS 実 行 CS 実 行
  • 5. 競合と共有（定義） ? データ競合とは ?複数のスレッドが同じ データにアクセスする こと、あるいは、アク セスするためのロック 競合 5 Copyright 2014 FUJITSU LIMITED synchronized(array) { array[1] = 2; } synchronized(array) { array[2] = 4; } スレッド A スレッド B ロック競合しているが データ競合していないコード例 ロック競合しているが データ競合していない例 スレッド A スレッド B ロック X 獲得 ロック X 待ち ロックの競合 アクセス Y アクセス Z ロック X 解放 ロック X 獲得 データ競合なし CS 実 行 CS 実 行
  • 6. ヘビーロック ? OS のロック関数 (pthread_mutex_lock/unlock 等 ) を使用 ? 実装が簡単なため、初期の JVM で使用 ? オブジェクト毎に mutex を作成?保持する 必要がある 6 Copyright 2014 FUJITSU LIMITED 管理ヘッダ mutex Java オブジェクト mutex_t if(obj->mutex == null) { obj->mutex = malloc(…); … } pthread_mutex_lock(&obj->mutex); 本来の オブジェクト データ synchornize の実装例
  • 7. シンロック ? ほとんどのロックは競合してない ? CAS(Compare and Swap) で十分 ? マルチコア?メニーコア CPU では、 CAS の コストはバカにならない 7 Copyright 2014 FUJITSU LIMITED ロック ビット Java オブジェクト 管理ヘッダ mov 0, %R2 ld [ ロックビット ], %R1 cas [ ロックビット ], %R1, %R2 cmp %R1, %R2 jne ヘビーロック 通常処理 0: ロック 1: アンロック シンロック実装例
  • 8. バイアスロック ? ほとんどのロックは共有されていない ?特定のスレッド使うならロックする必要はない ? 最初（バイアスされていない時）だけ CAS ? そのあとは Load ＆ Compare 8 Copyright 2014 FUJITSU LIMITED ld [ バイアス情報 ], %R1 cmp %R1, 自分自身のスレッド jne バイアス無効処理 通常処理 バイアスされている場合の 実装例 StringBuffer sb = new StringBuffer(); sb.append( abc”);“ sb.append( def”);“ String str = sb.toString(); return str; バイアスロックの有効例
  • 9. java.util.concurrent パッケージ ? JDK5.0 から導入 ? synchronize より柔軟なロック 9 Copyright 2014 FUJITSU LIMITED import java.util.concurrent.locks.ReentrantLock; ReentrantLock lock = new ReentrantLock(); … public void m() { lock.lock(); try { // クリティカルセクションの実行 } finally { lock.unlock(); } tryLock() isLocked() getOwner() 使用例 便利な API (ReentrantLock) 便利なクラス ReadWriteLock Semaphore AtomicInteger
  • 10. 目次 ? JavaVM におけるロックの進化 ? トランザクショナルメモリ（ TM ）とは ? Haswell でのトランザクショナルメモリ ? Java でトランザクショナルメモリを使う ? JDK8/9 の動向 ? まとめ 10 Copyright 2014 FUJITSU LIMITED
  • 11. トランザクショナルメモリとは ? 楽観的ロック ? とりあえず、ロックはしない ? 実行しているうちに、データ競合があった ら、それまでの実行結果を破棄（ アボート ）して、最初の状態にもどる（ロールバッ ク） ? 最後までデータ競合がなければ、結果を確 定する（コミット） 11 Copyright 2014 FUJITSU LIMITED
  • 12. 悲観的ロックと楽観的ロック 12 Copyright 2014 FUJITSU LIMITED 楽観的ロック 非観的ロック スレッド１ スレッド 2 スレッド 3 スレッド 4 ロック ロック ロック ロック クリティカルセクションの実行はシリアライズ スレッド１ スレッド 2 スレッド 3 スレッド 4 　　　 　　　 　　　 　　　 ロ ッ ク な し クリティカルセクションの実行は並行
  • 13. HTM と STM ? トランザクショナルメモリ（ TM ）をハー ドで実現するのを HTM 、ソフトで実現する のを STM と呼ぶ。 ? HTM の実装例 ?IBM System z (zEC12) ?Intel Haswell Microarchitecture ? STM の実装例 ?Scala ?Haskell 13 Copyright 2014 FUJITSU LIMITED
  • 14. 目次 ? JavaVM におけるロックの進化 ? トランザクショナルメモリ（ TM ）とは ? Haswell でのトランザクショナルメモリ ? Java でトランザクショナルメモリを使う ? JDK8/9 の動向 ? まとめ 14 Copyright 2014 FUJITSU LIMITED
  • 15. TSX ? Intel? Transactional Synchronization Extension ?Intel アーキテクチャでの HTM 実装 ?Haswell で利用可能 ?HLE と RTM の２種類 ? Hardware Lock Elision ?従来 (mutex) 方式と互換インタフェース ? Restricted Transaction Memory ?新しいインタフェース 15 Copyright 2014 FUJITSU LIMITED
  • 16. HLE ? 従来の mutex_lock/mutex_unlock の形式で そのまま置き換えられる ? アボートしたら、自動的にリトライ 16 Copyright 2014 FUJITSU LIMITED mov $1, %eax RETRY: xacquire xchg mutex, %eax test %eax, %eax jne RETRY xrelease mov $0, mutex mutex_lock(&mutex); mutex_unlock(&mutex); クリティカルセクションの 実行 クリティカルセクションの実 行 従来 (mutex) HLE
  • 17. GCC4.8 から HLE サポート 17 Copyright 2014 FUJITSU LIMITED #include <immintrin.h> void lock_hle_gcc(int mutex) {* while (__atomic_exchange_n(mutex, 1, __ATOMIC_ACQUIRE|__ATOMIC_HLE_ACQUIRE)) _mm_pause(); } void unlock_hle_gcc(int mutex) {* __atomic_clear(mutex, __ATOMIC_RELEASE|__ATOMIC_HLE_RELEASE); } 以下のような関数を自分で用意する（ fallback なし） int mutex = 0; void func() { lock_hle_gcc(&mutex); // クリティカルセクションの実行 unlock_hle_gcc(&mutex); クリティカルセクションを 上記 2 関数で挟む
  • 18. GCC4.8 から HLE をサポート 18 Copyright 2014 FUJITSU LIMITED 0000000000000000 <lock_hle_gcc>: 0: ba 01 00 00 00 mov $0x1,%edx 5: eb 0b jmp 12 <lock_hle_gcc+0x12> 7: 66 0f 1f 84 00 00 00 nopw 0x0(%rax,%rax,1) 10: f3 90 pause 12: 89 d0 mov %edx,%eax 14: f2 87 07 xacquire xchg %eax,(%rdi) 17: 85 c0 test %eax,%eax 19: 75 f5 jne 10 <lock_hle_gcc+0x10> 1b: f3 c3 repz retq 1d: 0f 1f 00 nopl (%rax) 0000000000000020 <unlock_hle_gcc>: 20: f3 c6 07 00 xrelease movb $0x0,(%rdi) 24: c3 retq ディスアセンブルするには、新しい objdump(binutils) が必要
  • 19. RTM ? アボートした時のハンドラ―を自分で書く必 要あり 19 Copyright 2014 FUJITSU LIMITED RETRY: xbegin FAIL cmp mutex, $0 jz OK FAIL: # goto RETRY or SLOWPATH SLOWPATH: # original code OK: ret cmp mutex, $0 jne SLOWPATH xend ret SLOWPATH: # original code ロックコード アンロックコード
  • 20. いつアボートするか ? トランザクションが長い ? I/O が入る ? OS によるスレッドコンテキストスイッチ ? 特殊な命令を実行 (CPUID/XABORT) ? ネストが深すぎる ? L1 キャッシュラインの競合 20 Copyright 2014 FUJITSU LIMITED
  • 21. Haswell のキャッシュ ? L1 Instruction Cache 32KB 8-way ? L1 Data Cache 32KB 8-way ?コアごと ( スレッドで共有 ) ? L2 Unified Cache 256KB 8-way ?コアごと ( スレッドで共有 ) ? キャッシュライン 64B 21 Copyright 2014 FUJITSU LIMITED 64 バイト 64 バイト 64 バイト 64 バイト L1 Data Cache 64 個 8-way
  • 22. キャッシュラインの競合 ? TSX では、 L1 キャッシュラインでデータ競 合を検出 22 Copyright 2014 FUJITSU LIMITED xbegin FAIL mov (0x1000), %eax xend スレッド A xbegin FAIL mov %eax, (0x1010) xend スレッド B 0x1000 0x1010 0x1004 0x1008 0x1040 アドレス 同 一 キ ャ ッ シ ュ ラ イ ン 競合
  • 23. 目次 ? JavaVM におけるロックの進化 ? トランザクショナルメモリ（ TM ）とは ? Haswell でのトランザクショナルメモリ ? Java でトランザクショナルメモリを使う ? JDK8/9 の動向 ? まとめ 23 Copyright 2014 FUJITSU LIMITED
  • 24. Java での実装案 ? synchronize の実装として使う ? API として提供 ? 特定ライブラリでの実装 24 Copyright 2014 FUJITSU LIMITED
  • 25. synchronize の実装 ? アプリの修正が不要 ? 個別に指定できない ?競合あるところは TM は向いていないので、従 来実装を使いたい ?競合のないところは、 TM 実装を使いたい ? 実装するのがたいへん ?JVM （ HotSpot ）の中でかなりの部分に影響 25 Copyright 2014 FUJITSU LIMITED
  • 26. API として提供 ? アプリ修正が必要 ? 選択的に使用可能 ? 使う側がどういう場合に TM が向いている か理解している必要あり ? 使用方法は ReentrantLock と同じ ? 実装は syhchronize ほどではないが、比較的 たいへん。 26 Copyright 2014 FUJITSU LIMITED
  • 27. 特定ライブラリでの実装 ? アプリ修正は不要 ? 使いたいところで使えない ? 例 java.util.HashMap/ArrayList/LinkedList 27 Copyright 2014 FUJITSU LIMITED table HashMap Entry テーブル Key Value Key Value
  • 28. API 方式での実装 28 Copyright 2014 FUJITSU LIMITED public final class HTM { private ByteBuffer data; private long mutex_addr; public HTM() { data = ByteBuffer.allocateDirect(64); mutex_addr = nativeAddress(data); } public void lock() { lockRTM(mutex_addr); } public void unlock() { unlockRTM(mutex_addr); } static private native void lockRTM(long addr); static private native void unlockRTM(long addr); 使用方法 HTM htm = new HTM(); htm.lock(); // クリティカル // セクションの実行 htm.unlock();
  • 29. HTM クラスの構造 29 Copyright 2014 FUJITSU LIMITED ByteBuffer data HTM 64 バイト long mutex_addr Java ヒープ C ヒープ DirectByteBuffer ??? long address allocateDirect(64) mutex
  • 30. ネイティブメソッド (C) 30 Copyright 2014 FUJITSU LIMITED #include <jni.h> void java_htm_lock_rtm(jlong); void java_htm_unlock_rtm(jlong); JNIEXPORT void JNICALL Java_HTM_lockRTM(JNIEnv *env, jclass kl, jlong add) { java_htm_lock_rtm(add); } JNIEXPORT void JNICALL Java_HTM_unlockRTM(JNIEnv *env, jclass kl, jlong add) { java_htm_unlock_rtm(add); }
  • 31. ネイティブメソッド (asm) 31 Copyright 2014 FUJITSU LIMITED # void java_htm_lock_rtm(jlong) java_htm_lock_rtm: movl $10, %ecx #retry count .RETRY: xbegin .FAIL cmpl $0, (%rdi) jz .OK xabort $0xfe .FAIL: pause dec %ecx cmpl $0, %ecx jz .SLOWPATH jmp .RETRY .SLOWPATH: xor %edx, %edx inc %edx xor %eax, %eax lock cmpxchgl %edx, (%rdi) jne .SLOWPATH .OK: ret # void java_htm_unlock_rtm(jlong) java_htm_unlock_rtm: cmpl $0, (%rdi) jz .END movl $0, (%rdi) ret .END: xend ret
  • 32. データ競合なしプログラム ? 本来ロックを取る必要のないプログラムで のベンチマーク ? 一定量 (500,000,000 回 ) スレッドローカル な変数をインクリメントする ? スレッド数を１から８まで増やす ? 各スレッドに均等な処理量を分割する ? 各スレッドの処理時間の平均を求める ? 「排他なし」、「 synchronized 」、　　　 「 ReentrantLock 」「 HTM 」の４パターン 32 Copyright 2014 FUJITSU LIMITED
  • 33. データ競合なしプログラム 33 Copyright 2014 FUJITSU LIMITED class LockNone extends Test { LockNone(long amount) { this.amount = amount; } void doIt() { count++; } } abstract class Test implements Runnable { long count; long time; long amount; public void run() { count = 0; long start = System.currentTimeMillis(); while (count < amount) { doIt(); } long end = System.currentTimeMillis(); time = (end-start); } } 排他なし
  • 34. データ競合なしプログラム 34 Copyright 2014 FUJITSU LIMITED class LockSync extends Test { Object lock; LockSync(long amount, Object lock) { this.amount = amount; this.lock = lock; } void doIt() { synchronized (lock) { count++; } } } synchronized 使用
  • 35. データ競合なしプログラム 35 Copyright 2014 FUJITSU LIMITED class LockConc extends Test { ReentrantLock lock; LockConc(long amount, ReentrantLock lock) { this.amount = amount; this.lock = lock; } void doIt() { lock.lock(); count++; lock.unlock(); } } ReentrantLock 使用
  • 36. データ競合なしプログラム 36 Copyright 2014 FUJITSU LIMITED class LockRTM extends Test { HTM htm; LockRTM(long amount, HTM htm) { this.amount = amount; this.htm = htm; } void doIt() { htm.lock(); count++; htm.unlock(); } } HTM 使用
  • 37. データ競合なし（結果） 37 Copyright 2014 FUJITSU LIMITED １スレッドあたりの平均処理時間 JDK1.7.0_51 Intel Xeon E3-1270 v3 3.5GHz Red Hat Enterprise Linux Server release 6.5 (Santiago)
  • 38. ネイティブメソッド呼出し ? ネイティブメソッドの呼び出しはコストが 高い ? 性能高速化のために、 Java でかけるコード を C にしても、速くなるとは限らない 38 Copyright 2014 FUJITSU LIMITED Java メソッド ネイティブ メソッドスタブ コード 直接呼べない
  • 39. スタブコード (unlockRTM) 39 Copyright 2014 FUJITSU LIMITED Decoding compiled method 0x00007f12dd05ebd0: Code: [Disassembling for mach='i386:x86-64'] [Entry Point] # {method} 'unlockRTM' '(J)V' in 'HTM' # parm0: rsi:rsi = long # [sp+0x50] (sp of caller) 0x00007f12dd05ed60: mov 0x8(%rsi),%r10d 0x00007f12dd05ed64: cmp %r10,%rax 0x00007f12dd05ed67: je 0x00007f12dd05ed78 0x00007f12dd05ed6d: jmpq 0x00007f12dd037960 ; {runtime_call} 0x00007f12dd05ed72: nopw 0x0(%rax,%rax,1) [Verified Entry Point] 0x00007f12dd05ed78: mov %eax,-0x14000(%rsp) 0x00007f12dd05ed7f: push %rbp 0x00007f12dd05ed80: mov %rsp,%rbp 0x00007f12dd05ed83: sub $0x40,%rsp 0x00007f12dd05ed87: mov %rsi,%rdx 0x00007f12dd05ed8a: movabs $0xdff84370,%r14 ; {oop(a 'java/lang/Class' = 'HTM')} 0x00007f12dd05ed94: mov %r14,0x30(%rsp) 0x00007f12dd05ed99: lea 0x30(%rsp),%r14 0x00007f12dd05ed9e: mov %r14,%rsi ; OopMap{[48]=Oop off=65} 0x00007f12dd05eda1: movabs $0x7f12dd05eda1,%r10 ; {section_word} 0x00007f12dd05edab: mov %r10,0x1c0(%r15) 0x00007f12dd05edb2: mov %rsp,0x1b8(%r15) 0x00007f12dd05edb9: cmpb $0x0,0x8ef495a(%rip) # 0x00007f12e5f5371a ; {external_word} 0x00007f12dd05edc0: je 0x00007f12dd05edfa 0x00007f12dd05edc6: push %rsi 0x00007f12dd05edc7: push %rdx 0x00007f12dd05edc8: movabs $0xdafd0040,%rsi ; {oop({method} 'unlockRTM' '(J)V' in 'HTM')} 0x00007f12dd05edd2: mov %r15,%rdi 0x00007f12dd05edd5: test $0xf,%esp 0x00007f12dd05eddb: je 0x00007f12dd05edf3 0x00007f12dd05ede1: sub $0x8,%rsp 0x00007f12dd05ede5: callq 0x00007f12e59c4230 ; {runtime_call} 0x00007f12dd05edea: add $0x8,%rsp 0x00007f12dd05edee: jmpq 0x00007f12dd05edf8 0x00007f12dd05edf3: callq 0x00007f12e59c4230 ; {runtime_call} 0x00007f12dd05edf8: pop %rdx 0x00007f12dd05edf9: pop %rsi 0x00007f12dd05edfa: lea 0x1d8(%r15),%rdi 0x00007f12dd05ee01: movl $0x4,0x250(%r15) 0x00007f12dd05ee0c: callq 0x00007f12da7ef660 ; {runtime_call} 0x00007f12dd05ee11: vzeroupper 0x00007f12dd05ee14: movl $0x5,0x250(%r15) 0x00007f12dd05ee1f: mov %r15d,%ecx 0x00007f12dd05ee22: shr $0x4,%ecx 0x00007f12dd05ee25: and $0xffc,%ecx 0x00007f12dd05ee2b: movabs $0x7f12e61ac000,%r10 ; {external_word} 0x00007f12dd05ee35: mov %ecx,(%r10,%rcx,1) 0x00007f12dd05ee39: cmpl $0x0,0x8efd83d(%rip) # 0x00007f12e5f5c680 ; {external_word} 0x00007f12dd05ee43: jne 0x00007f12dd05ee57 0x00007f12dd05ee49: cmpl $0x0,0x30(%r15) 0x00007f12dd05ee51: je 0x00007f12dd05ee74 0x00007f12dd05ee57: mov %r15,%rdi 0x00007f12dd05ee5a: mov %rsp,%r12 0x00007f12dd05ee5d: sub $0x0,%rsp 0x00007f12dd05ee61: and $0xfffffffffffffff0,%rsp 0x00007f12dd05ee65: callq 0x00007f12e5a655a0 ; {runtime_call} 0x00007f12dd05ee6a: mov %r12,%rsp 0x00007f12dd05ee6d: mov 0x8ed8f3c(%rip),%r12 # 0x00007f12e5f37db0 ; {external_word} 0x00007f12dd05ee74: movl $0x8,0x250(%r15) 0x00007f12dd05ee7f: cmpl $0x1,0x27c(%r15) 0x00007f12dd05ee8a: je 0x00007f12dd05ef13 0x00007f12dd05ee90: cmpb $0x0,0x8ef4883(%rip) # 0x00007f12e5f5371a ; {external_word} 0x00007f12dd05ee97: je 0x00007f12dd05eecd 0x00007f12dd05ee9d: movabs $0xdafd0040,%rsi ; {oop({method} 'unlockRTM' '(J)V' in 'HTM')} 0x00007f12dd05eea7: mov %r15,%rdi 0x00007f12dd05eeaa: test $0xf,%esp 0x00007f12dd05eeb0: je 0x00007f12dd05eec8 0x00007f12dd05eeb6: sub $0x8,%rsp 0x00007f12dd05eeba: callq 0x00007f12e59c4380 ; {runtime_call} 0x00007f12dd05eebf: add $0x8,%rsp 0x00007f12dd05eec3: jmpq 0x00007f12dd05eecd 0x00007f12dd05eec8: callq 0x00007f12e59c4380 ; {runtime_call} 0x00007f12dd05eecd: movabs $0x0,%r10 0x00007f12dd05eed7: mov %r10,0x1b8(%r15) 0x00007f12dd05eede: movabs $0x0,%r10 0x00007f12dd05eee8: mov %r10,0x1c0(%r15) 0x00007f12dd05eeef: mov 0x38(%r15),%rcx 0x00007f12dd05eef3: movq $0x0,0x100(%rcx) 0x00007f12dd05eefe: leaveq 0x00007f12dd05eeff: cmpq $0x0,0x8(%r15) 0x00007f12dd05ef07: jne 0x00007f12dd05ef0e 0x00007f12dd05ef0d: retq 0x00007f12dd05ef0e: jmpq Stub::forward exception ; {runtime_call} 0x00007f12dd05ef13: mov %rsp,%r12 0x00007f12dd05ef16: sub $0x0,%rsp 0x00007f12dd05ef1a: and $0xfffffffffffffff0,%rsp 0x00007f12dd05ef1e: callq 0x00007f12e59c3600 ; {runtime_call} 0x00007f12dd05ef23: mov %r12,%rsp 0x00007f12dd05ef26: mov 0x8ed8e83(%rip),%r12 # 0x00007f12e5f37db0 ; {external_word} 0x00007f12dd05ef2d: jmpq 0x00007f12dd05ee90 0x00007f12dd05ef32: hlt
  • 40. JIT コードを disassemble ? hsdis-amd64.so の場所を LD_LIBRARY_PATH に ? -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly 40 Copyright 2014 FUJITSU LIMITED
  • 41. native intrinsic ? ネイティブメソッドを JIT が翻訳したコード のように扱う ? インライン展開することで、スタブが不要 41 Copyright 2014 FUJITSU LIMITED Java ソース C ソース .class .so/.dll 翻訳 コード javac C コンパイラ jit スタブ経由の 呼出し 同等コード アセンブラ 翻訳 コード 取込み
  • 42. intrinsic コード (lock) 42 Copyright 2014 FUJITSU LIMITED instruct htm_lock_rtm( memory adr, rax_RegI result, rcx_RegI tmp) %{ match(HtmRtmLock adr); ins_encode %{ Label retry, fail, ok, slowpath; __ movl($tmp$$Register, 10); __ bind(retry); __ xbegin(fail); __ cmpl($adr$$Address, 0); __ jccb(Assembler::equal, ok); __ xabort(0xfe); __ bind(fail); __ pause(); __ decrementl($tmp$$Register); __ cmpl($tmp$$Register, 0); __ jccb(Assembler::equal, slowpath); __ jmp(retry); __ bind(slowpath); __ movl($tmp$$Register, 1); __ movl($result$$Register, 0); __ lock(); __ cmpxchgl($tmp$$Register, $adr$$Address); __ jccb(Assembler::notEqual, slowpath); __ bind(ok); hotspot/src/cpu/x86/vm/x86_64.ad
  • 43. intrinsic コード (unlock) 43 Copyright 2014 FUJITSU LIMITED instruct htm_unlock_rtm(memory adr, rax_RegI result) %{ match(HtmRtmUnlock adr); ins_encode %{ Label end, done; __ cmpl($adr$$Address, 0); __ jccb(Assembler::equal, end); __ movl($adr$$Address, 0); __ jmp(done); __ bind(end); __ xend(); __ bind(done); hotspot/src/cpu/x86/vm/x86_64.ad
  • 44. データ競合なし（結果） 44 Copyright 2014 FUJITSU LIMITED １スレッドあたりの平均処理時間 JDK1.7.0_51 Intel Xeon E3-1270 v3 3.5GHz Red Hat Enterprise Linux Server release 6.5 (Santiago)
  • 45. データ競合あるかもプログラム ? ArrayList アクセス時にロックを取るプログ ラムでのベンチマーク ? 全部で一定回数 (100,000,000 回 ) 、 ArrayList の連続した２要素を入れ替 える ? 入れ替える場所はランダムに決める ? 配列要素は十分大きい ? スレッド数を１から８まで増やす ? 各スレッドに均等な処理量を分割する ? 各スレッドの処理時間の平均を求める45 Copyright 2014 FUJITSU LIMITED
  • 46. データ競合あるかもプログラム 46 Copyright 2014 FUJITSU LIMITED static long AMOUNT = 100_000_000L; static int ARRAY_SIZE = 131_072; static ArrayList<Object> alist = new ArrayList<>(ARRAY_SIZE); abstract class Test implements Runnable { long count; long time; long amount; long seed; public void run() { count = 0; long start = System.currentTimeMillis(); while (count < amount) { int n1 = nextInt(ARRAY_SIZE); int n2 = n1+1; if (n2 == ARRAY_SIZE) n2 -= 2; doIt(n1, n2); count++; } long end = System.currentTimeMillis(); time = (end-start); } void swap(int n1, int n2) { Object o1 = alist.get(n1); Object o2 = alist.get(n2); alist.set(n1, o2); alist.set(n2, o1); } int nextInt(int n) { long nextseed = (seed * 0x5deece66dL + 0xbL) & ((1L << 48) - 1); long rnd31 = nextseed >>> (48-31); seed = nextseed; return (int) ((n * rnd31) >> 31); }
  • 47. データ競合あるかもプログラム 47 Copyright 2014 FUJITSU LIMITED void doIt(int n1, int n2) { synchronized (lock) { swap(n1, n2); } } void doIt(int n1, int n2) { lock.lock(); try { swap(n1, n2); } finally { lock.unlock(); } } void doIt(int n1, int n2) { swap(n1, n2); } void doIt(int n1, int n2) { htm.lock(); try { swap(n1, n2); } finally { htm.unlock(); } } 排他なし HTM synchronized ReentrantLock
  • 48. データ競合あるかも（結果） 48 Copyright 2014 FUJITSU LIMITED １スレッドあたりの平均処理時間 JDK1.7.0_51 Intel Xeon E3-1270 v3 3.5GHz Red Hat Enterprise Linux Server release 6.5 (Santiago)
  • 49. 目次 ? JavaVM におけるロックの進化 ? トランザクショナルメモリ（ TM ）とは ? Haswell でのトランザクショナルメモリ ? Java でトランザクショナルメモリを使う ? JDK8/9 の動向 ? まとめ 49 Copyright 2014 FUJITSU LIMITED
  • 50. JDK8/9 の動向 ? -XX:+UseRTMLocking ?https://bugs.openjdk.net/browse/JDK-8031320 ? synchronize の実装として使用 ?メソッド毎に有効?無効を指定する仕組みはあ りそう ? バイアスロックとは排他関係 ? 性能は？ 50 Copyright 2014 FUJITSU LIMITED
  • 51. データ競合なし (JDK9) 51 Copyright 2014 FUJITSU LIMITED １スレッドあたりの平均処理時間
  • 52. 目次 ? JavaVM におけるロックの進化 ? トランザクショナルメモリ（ TM ）とは ? Haswell でのトランザクショナルメモリ ? Java でトランザクショナルメモリを使う ? JDK8/9 の動向 ? まとめ 52 Copyright 2014 FUJITSU LIMITED
  • 53. Java で TM が有効なケース ? ロック共有しているが、ロック競合がない ?バイアスロックが不向きなパターン ? ロック競合はあるが、データ競合がない ?本来プログラム的にはロックの必要がなく、安 心のためだけにロックを入れている ? ロック競合はあるが、ほとんどデータ競合 せず、たまに競合する場合がある ?ArrayList のパターン 53 Copyright 2014 FUJITSU LIMITED
  • 54. Java で TM の効果ないケー ス ? ロック競合がほとんど起きていない ? ロック期間が長い ?バッファ枯渇やコンテキストスイッチ ? ロック中に IO あり ?デバッグは難しい ? ロック中に GC あり ? 共有しないロックを何度も使う ?バイアスロックがよい 54 Copyright 2014 FUJITSU LIMITED
  • 55. Q&A 55 Copyright 2014 FUJITSU LIMITED
  • 56. 56 Copyright 2014 FUJITSU LIMITED Java は、 Oracle Corporation およびその子会社、関連会社の米国および その他の国おける登録商標です。 本ドキュメントに記載されている、社名、商品名等は各社の商標または 登録商標である場合があります。 その他の記載されている、商標および登録商標については、 一般に各社の商標または登録商標です。
  • 57. 57 Copyright 2010 FUJITSU LIMITED