Blog
詰めバリアント技術を用いて高速並行カウンターを作ってみる
こんにちは、CA ProFit-Xのフックです。
今の時代、コンピューターのCPUといえば 間違いなくマルチコアのCPUであります。マルチコアCPUが普及したことがきっかけでプログラミングモデルも根本的に変わっています。高いパフォーマンスのアプリを作るために、マルチコアCPUで色々なプログラミングモデル・技術が誕生しています。一方、マルチコアCPUでプログラミングする際に、リソースの衝突(contention)が発生しやすくなってしまうので、衝突が減らせることが大事です。
今回は詰めバリアント(英語: Padded Variant)技術を使ってシンプルな高速並行カウンターを作り方を紹介させていただきたいと思います。
volatileで並行性保証
|
1 2 3 |
class Counter { @volatile var value: Long = 0 } |
上記のコードでは簡単なアトミックカウンターを定義しています。Counterクラスにはvolatile変数のvalueがあります。
volatileアノテーションはJava 5から提供されており、volatile変数はスレッド・セーフにコードを実行するために使用されます。
スレッドではvolatile変数を読み込み・書み込み時に、(コア別のL1キャッシュではなく) 必ずシェアキャッシュ(CPU L2、L3キャッシュ 又は メインメモリー)で操作することになります。
別のコアにあるスレッドから同じvolatile変数の値を読み込む場合と同じ値になり、並行性的なカウンターが保証できます。
Counterの更新パフォーマンス
Counterインスタンスの並行性が保証できますが、更新速度はどうでしょう。下記のケースで検討してみました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
package com.example object Main extends App { val ITERATIONS = 100000000 def updatesDuration = { val counter1, counter2 = new Counter updateValueOfCounters( new Runnable { override def run = { (1 to ITERATIONS).foreach(_ => counter1.value += 1) } }, new Runnable { override def run = { (1 to ITERATIONS).foreach(_ => counter2.value += 1) } } ) } def updateValueOfCounters(updateTask1: Runnable, updateTask2: Runnable): Long = { val start: Long = System.currentTimeMillis val t1 = new Thread(updateTask1) val t2 = new Thread(updateTask2) t1.start t2.start t1.join t2.join System.currentTimeMillis - start } } |
2つのCounterインスタンスcounter 1、counter 2を定義して、別のスレッドでそれぞれインスタンスのvalueを更新します。
並行的にcounter 1、counter 2のvalueの更新速度を下記のコードで確認します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
package com.example object Main extends App { ... (1 to 5).foreach { i => println(s"${getOrdinalStr(i)} time:") println(s"Updating 100 million times of counters took: ${updatesDuration} ms") println("") } private def getOrdinalStr(i: Int) = { val suffix = i match { case 1 => "st" case 2 => "nd" case 3 => "rd" case _ => "th" } s"$i$suffix" } } |
実行:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
$ sbt > run [info] Running com.example.Main [info] 1st time: [info] Updating 100M times of counters took: 661 ms [info] [info] 2nd time: [info] Updating 100M times of counters took: 594 ms [info] [info] 3rd time: [info] Updating 100M times of counters took: 4621 ms [info] [info] 4th time: [info] Updating 100M times of counters took: 4895 ms [info] [info] 5th time: [info] Updating 100M times of counters took: 4067 ms |
実行結果によって、3回目から更新速度が数倍ぐらい落ちてしまうことが分かりました。
どうしてこの結果になってしまうのか?次の節で説明します。
キャッシュ行の長さ
キャッシュ行の長さ(英語: cache line size)はCPUキャッシュ上の1行の容量であり、x86アーキテクチャのCPUではキャッシュ行のサイズは64バイトです。
CPUのキャッシュ長さは下記のコマンドで確認できます。
Macの場合:
|
1 2 3 |
$ sysctl -a | grep -e '\(cachelinesize\|cache.linesize\)' hw.cachelinesize: 64 machdep.cpu.cache.linesize: 64 |
Linuxの場合:
|
1 2 3 4 5 |
$ getconf LEVEL1_DCACHE_LINESIZE 64 # or $ cat /proc/cpuinfo | grep cache_alignment cache_alignment : 64 |
JOLツール
jol(Java Object Layout)は、Javaのオブジェクトがどのようにメモリ上にレイアウトされるのか確認できるツールです。
Scalaでjolを使えるようにするため、下記のコードのようにbuild.sbtに追加します
|
1 |
libraryDependencies += "org.openjdk.jol" % "jol-core" % "0.6" |
実装したCounterのオブジェクトのレイアウトを確認しましょう。
|
1 2 3 4 5 6 7 8 9 10 |
$ sbt > console scala> println(org.openjdk.jol.info.ClassLayout.parseClass(classOf[com.example.Counter]).toPrintable) com.example.Counter object internals: OFFSET SIZE TYPE DESCRIPTION VALUE 0 12 (object header) N/A 12 4 (alignment/padding gap) N/A 16 8 long Counter.value N/A Instance size: 24 bytes Space losses: 4 bytes internal + 0 bytes external = 4 bytes total |
ということは1つのCounterのインスタンスはメモリ上に24バイトの領域を確保していることがわかります。
キャッシュ行の衝突問題 (False sharing問題)
上記の確認したキャッシュ行の長さ及びCounterのインスタンスサイズにおける２つのCounterインスタンスのvalueが、1つのキャッシュ行に放置されることがあります (以下の画像のように)。
その場合、仮に
- コア0にあるスレッドはcounter 1のvalueを書き込む
- 並行でコア1にあるスレッドはcounter 2のvalueを書き込むときは、キャッシュ行が ‘dirty’としてマークされるようになる。
- 次に、コア0にあるスレッドは*counter 1*の*value*を読み込もうとするとき、キャッシュ行が消毒(sanitize)できるまで待つ。言い換えると、キャッシュ行の衝突が発生してしまいました。
そのため、counter 1及びcounter 2のvalueへの書き込み速度に影響してしまいます。
詰めバリアントを利用してキャッシュ行の衝突を解決
詰めバリアントはvolatile変数を詰め物に挟むようにする技術であり、2つのCounterインスタンスのvalueが絶対に別のキャッシュ行に放置されるようにします。
それに従い、別のCounterインスタンスのvalueに書き込むとき、別のキャッシュ行に操作することになるため、衝突が減らせます。
コードは下記です
|
1 2 3 4 5 |
class PaddedCounter { @volatile private var p0, p1, p2, p3, p4, p5, p6: Long = 0 // padding variants @volatile var value: Long = 0 @volatile private var q0, q1, q2, q3, q4, q5, q6: Long = 0 // padding variants } |
JOLツールでPaddedCounterインスタンスのオブジェクトレイアウトを確認してみます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
$ sbt > console scala> println(org.openjdk.jol.info.ClassLayout.parseClass(classOf[com.example.PaddedCounter]).toPrintable) [info] com.example.PaddedCounter object internals: [info] OFFSET SIZE TYPE DESCRIPTION VALUE [info] 0 12 (object header) N/A [info] 12 4 (alignment/padding gap) N/A [info] 16 8 long PaddedCounter.p0 N/A [info] 24 8 long PaddedCounter.p1 N/A [info] 32 8 long PaddedCounter.p2 N/A [info] 40 8 long PaddedCounter.p3 N/A [info] 48 8 long PaddedCounter.p4 N/A [info] 56 8 long PaddedCounter.p5 N/A [info] 64 8 long PaddedCounter.p6 N/A [info] 72 8 long PaddedCounter.value N/A [info] 80 8 long PaddedCounter.q0 N/A [info] 88 8 long PaddedCounter.q1 N/A [info] 96 8 long PaddedCounter.q2 N/A [info] 104 8 long PaddedCounter.q3 N/A [info] 112 8 long PaddedCounter.q4 N/A [info] 120 8 long PaddedCounter.q5 N/A [info] 128 8 long PaddedCounter.q6 N/A [info] Instance size: 136 bytes [info] Space losses: 4 bytes internal + 0 bytes external = 4 bytes total |
オブジェクトレイアウト結果によって、1つのPaddedCounterインスタンスがメモリ上に136バイトレイアウトされて、value変数が56バイトのp*変数と56バイトのq*変数に挟まれました。
どんな放置方法でも2つPaddedCounterインスタンスのvalueが別のキャッシュ行に放置されるので、キャッシュ行の衝突が減らせるようになりました。
CounterとPaddedCounterの更新パフォーマンス
では作ったCounterとPaddedCounterの更新速度を確認しましょう。
まとめるコード:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
package com.example class Counter { @volatile var value: Long = 0 } class PaddedCounter { @volatile private var p0, p1, p2, p3, p4, p5, p6: Long = 0 // padding variants @volatile var value: Long = 0 @volatile private var q0, q1, q2, q3, q4, q5, q6: Long = 0 // padding variants } object Main extends App { val ITERATIONS = 100000000 def updatesDuration = { val counter1, counter2 = new Counter updateValueOfCounters( new Runnable { override def run = { (1 to ITERATIONS).foreach(_ => counter1.value += 1) } }, new Runnable { override def run = { (1 to ITERATIONS).foreach(_ => counter2.value += 1) } } ) } def paddedUpdatesDuration = { val counter1, counter2 = new PaddedCounter updateValueOfCounters( new Runnable { override def run = { (1 to ITERATIONS).foreach(_ => counter1.value += 1) } }, new Runnable { override def run = { (1 to ITERATIONS).foreach(_ => counter2.value += 1) } } ) } (1 to 5).foreach { i => println(s"${getOrdinalStr(i)} time:") println(s"Updating 100 million times of counters took: ${updatesDuration} ms") println(s"Updating 100 million times of padded counters took: ${paddedUpdatesDuration} ms") println("") } def updateValueOfCounters(updateTask1: Runnable, updateTask2: Runnable): Long = { val start: Long = System.currentTimeMillis val t1 = new Thread(updateTask1) val t2 = new Thread(updateTask2) t1.start t2.start t1.join t2.join System.currentTimeMillis - start } private def getOrdinalStr(i: Int) = { val suffix = i match { case 1 => "st" case 2 => "nd" case 3 => "rd" case _ => "th" } s"$i$suffix" } } |
実行:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
$ sbt > run [info] Running com.example.Main [info] 1st time: [info] Updating 100 million times of counters took: 738 ms [info] Updating 100 million times of padded counters took: 1150 ms [info] [info] 2nd time: [info] Updating 100 million times of counters took: 3709 ms [info] Updating 100 million times of padded counters took: 1431 ms [info] [info] 3rd time: [info] Updating 100 million times of counters took: 6064 ms [info] Updating 100 million times of padded counters took: 1425 ms [info] [info] 4th time: [info] Updating 100 million times of counters took: 4306 ms [info] Updating 100 million times of padded counters took: 1533 ms [info] [info] 5th time: [info] Updating 100 million times of counters took: 4630 ms [info] Updating 100 million times of padded counters took: 1406 ms |
1回目の実行ではCounterのほうが更新速度が早いですが、
2回目からキャッシュ行の衝突が発生してしまうため、上記のCounterパフォーマンスを確認する結果と同様に更新速度が数倍落ちてしまいました。
PaddedCounterの更新速度は安定的に1500 ms程かかることが分かりました。
まとめ
今回は詰めバリアント技術を使ってとてもシンプルなPaddedCounterを作ってみました。 マルチコアCPUで共通のvolatile変数を使用する場合よりもPaddedCounterの更新速度が早く、並行性を守ることができます。
詰めバリアント技術はJava 8から提供されているjava.util.concurrent.atomic.{LongAdder,DoubleAdder,…}などの親クラスStrip64にあるCellクラス またはContendedアノテーションで使われています。
詳細は下記のリンクになります。
長い記事ですが、読んでいただきありがとうございます。ｍ(＿ ＿)ｍ
Author
