lock-freeを考える - 生涯未熟

考える発端となったのは以下の記事。

stackimpact.com

GoのPerformance Turningに関する記事なのだが、気になる項目が。

Favor lock-free algorithms

ふむ🤔

冬のLock free祭り safe from Kumazaki Hiroki

www.slideshare.net

ほう？🤔

MutexやSemaphoreで排他制御を行なうのではなく、CASなどを使ったlock-freeを実装した方が良いらしい。

CAS

値の書き換えが想定通りのものなら、実際に書き換えを行なう。
書き換えが出来るまで、何度でも繰り返す。
→ 但し、問題もある（ex. ABA問題

上記のCASは有限のステップ数で処理が完了しないため、lock-freeではあるがwait-freeではない。

Goの場合はどうやるの？

Goの場合、atomicパッケージにCAS実装がある。

atomic - The Go Programming Language

package main

import (
  "sync"
  "fmt"
)

var (
  balance int32 = 100
  wg = sync.WaitGroup{}
)

func main() {
  // expect: balance = 55
  var i int32
  for i = 0; i < 10; i++ {
    wg.Add(1)
    go withdraw(i)
  }
  wg.Wait()
  fmt.Println(balance)
}

func withdraw(amount int32) {
  balance = balance - amount
  wg.Done()
}

しかし、この方法だと当たり前だがgoroutineの処理タイミングによって全く違った値が算出される。そこで、以下のようにCASを用いる。

package main

import (
  "sync"
  "fmt"
  "sync/atomic"
)

var (
  balance int32 = 100
  wg = sync.WaitGroup{}
)

func main() {
  // expect: balance = 55
  var i int32
  for i = 0; i < 10; i++ {
    wg.Add(1)
    go withdraw(i)
  }
  wg.Wait()
  fmt.Println(balance)
}

func withdraw(amount int32) {
  for {
    if atomic.CompareAndSwapInt32(&balance, balance, balance - amount) {
      break
    }
  }
  wg.Done()
}

すると、想定した55の値が常に算出される。

Mutexの中身は・・・

結局、CASを使っていたりする。

// Fast path: grab unlocked mutex.
if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
  if race.Enabled {
    race.Acquire(unsafe.Pointer(m))
  }
  return
}

パフォーマンスの差異

実際にパフォーマンスに違いは出るのだろうか？ベンチマークを取ってみる。

old: use Mutex
new: use CAS

benchmark         old ns/op     new ns/op     delta
BenchmarkDo-4     4028          3670          -8.89%
BenchmarkDo-4     4000          3683          -7.93%
BenchmarkDo-4     4014          2934          -26.91%
BenchmarkDo-4     3516          3043          -13.45%
BenchmarkDo-4     2759          3660          +32.66%
BenchmarkDo-4     4030          2883          -28.46%
BenchmarkDo-4     4025          3802          -5.54%
BenchmarkDo-4     4027          3358          -16.61%
BenchmarkDo-4     4046          3602          -10.97%
BenchmarkDo-4     3749          3363          -10.30%

全体的に早くはなっているが、たまに致命的に遅くなる。

さて、実行するgoroutineの数を増やすとどうなるのだろうか？

1000

benchmark         old ns/op     new ns/op     delta
BenchmarkDo-4     271236        266445        -1.77%
BenchmarkDo-4     275415        267188        -2.99%
BenchmarkDo-4     269019        269459        +0.16%
BenchmarkDo-4     272291        271073        -0.45%
BenchmarkDo-4     273410        269671        -1.37%

10000

benchmark         old ns/op     new ns/op     delta
BenchmarkDo-4     2782914       2831663       +1.75%
BenchmarkDo-4     2712926       2936499       +8.24%
BenchmarkDo-4     2748464       2891509       +5.20%
BenchmarkDo-4     2810436       2844462       +1.21%
BenchmarkDo-4     2738268       2875502       +5.01%

む？なんか段々とMutexに負けてるぞ🤔
何故だ・・・

結局どうすりゃいいのか？

多大なコア数を持つCPUでないと、CASなどのlock-freeの効果は薄そう。
以下のリンク先にも書いてあるが、実際に80coreで動かした場合にMutexがボトルネックになったようである。
そういう時にはlock-freeを使う意味が出てきそう。

texlution.com