背景

RubyのQueueクラスの説明に、これはスレッドセーフだと書いてあったので検証してみました。

スレッドセーフとは

自分でも正確な意味を理解していなかったので調べてみました。スレッドセーフとはアプリケーションをマルチスレッドで動作させても問題がないこと

スレッドアンセーフだとどうなるか

たとえばマルチスレッドで実行したときに、複数スレッドから同一の変数に変更が発生してデータが消えたり意図しない値になってしまうこと（レースコンディションという）

つまり仮説!

ArrayとQueueを用意し、100スレッドで複数のワーカーで同時にpopさせて並列計算するとQueueでは正しい結果が出力されるが、Arrayではレースコンディションが発生し、計算結果がズレる..はず

仕様

1..10000000の値を合計する。結果が50000005000000となれば正しい
レースコンディションが発生すれば同じ値をpopさせるので合計結果がズレるはず。

実験1.Queueで計算してみる

queue_calc.rb

t_start = Time.now.instance_eval { self.to_i * 1000 + (usec/1000) }

# 定数
scope = Array((1..1000000))
result = []

# キューに詰める
q = Queue.new
scope.each { |i| q.push(i) }

threads = (1..100).map {|i|
  Thread.new {
    v = 0
    until q.empty?
      _v = q.pop(true) rescue nil
      if _v
        v += _v
      end
    end
    result.push(v)
  }
}

# スレッド実行
threads.each {|t| t.join }

# 実行結果
puts "----------------------------"
p "SUM:" << result.inject(:+).to_s
t_end = Time.now.instance_eval { self.to_i * 1000 + (usec/1000) }
puts "----------------------------"
puts "TotalTime:" << (t_end - t_start).to_s << "ms"


>>ruby queue_calc.rb
>>----------------------------
>>"SUM:500000500000"
>>----------------------------

Queueはスレッドセーフな実装なので計算結果が正しいのは想定通り

実験2 Arrayで計算する

array_calc.rb

t_start = Time.now.instance_eval { self.to_i * 1000 + (usec/1000) }

# 定数
scope = Array((1..10000000))
result = []

threads = (1..100).map {|i|
  Thread.new {
    v = 0
    ct = 0
    while scope.length != 0
      _v = scope.pop
      if _v != nil
        v += _v
        ct += 1
      end
    end
    result.push(v)
  }
}

# スレッド実行
threads.each {|t| t.join }

# 実行結果
puts "----------------------------"
p "SUM:" << result.inject(:+).to_s
t_end = Time.now.instance_eval { self.to_i * 1000 + (usec/1000) }
puts "----------------------------"
puts "TotalTime:" << (t_end - t_start).to_s << "ms"

>>ruby array_calc.rb
>>----------------------------
>>"SUM:500000500000"
>>----------------------------

Arrayで100並列で計算しても正しい結果になってしまいました。レースコンディションが発生しないのは何故か調べてみました。

Arrayでレースコンディションが発生しなかった理由

理由は、並列計算できてなかったのが理由でした。

puts result
>>[50000005000000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

1つ目のワーカースレッドで全ての計算を行っています。これじゃあマルチスレッド処理になっていません。仕方ないのでsleep入れて対応します。またQueueでの実験も再試験しました。

array_calc.rb

threads = (1..100).map {|i|
  Thread.new {
    v = 0
    ct = 0
    while scope.length != 0
      _v = scope.pop
      if _v != nil
        v += _v
        ct += 1
      end
      if ct > 100000
        sleep(1)
      end
    end
    result.push(v)
  }
}

>>ruby array_calc2.rb
>>----------------------------
[13216789115, 464460844562, 454460644561, 444460444560, 434460244559, 424100840966, 414100640965, 404100440964, 394100240963, 379277692739, 369277492738, 359277292737, 349277092736, 332264922616, 322264722615, 312264522614, 302264322613, 288077380745, 278077180744, 268076980743, 258076780742, 243093430910, 233093230909, 223093030908, 213092830907, 199613496115, 189613296114, 179613096113, 169612896112, 159446294447, 149446094446, 139445894445, 197074996334, 407863022799, 314092177398, 478392140651, 526659269754, 430045407647, 273701758583, 995010809978, 359479778322, 985010609976, 975010409974, 965010209972, 358424247418, 945009772941, 925009372937, 955009972943, 935009572939, 358537400003, 904157935235, 894157735233, 884157535231, 914158135237, 872868589635, 87296979921, 852868125930, 842867925928, 221237519762, 818829433766, 808829233764, 798829033762, 828829633768, 257786915697, 785853174122, 775852974120, 765852774118, 755852574116, 157679610696, 740050557963, 730050357961, 720050157959, 710049957957, 151580756651, 692967736966, 672967336962, 682967536964, 662967136960, 102750352146, 647011512195, 637011312193, 627011112191, 617010912189, 41381924337, 603524378988, 593524178986, 583523978984, 26006560063, 16006360062, 573523545238, 557841344477, 547841144475, 170246459886, 537840944473, 527840744471, 862867694706, 511543081494, 501542881492, 491542681490, 481542481488]
"SUM:50000005000000"
----------------------------
TotalTime:3670ms

実行時間は1秒劣化しましたが複数のワーカーでちゃんと計算できていることが確認できました。しかし、計算結果は正しいまま。なーぜーだー
Arrayがスレッドセーフであるならば、Queueを利用する意味がないことになってしまいます。

色々調べてみた結果

ArrayもQueueもレースコンディションが発生しなかった。なぜか。そもそもRubyは次のような実装になってるみたいです。なーんだ
ネイティブスレッドを用いて実装されていますが、現在の実装では Ruby VM は Giant VM lock (GVL)を有しており、同時に実行されるネイティブスレッドは常にひとつです。

参考: Ruby拡張モジュールマルチスレッドでの性能向上

でも納得いかない

マルチスレッドとはなんだったのか...Queueを利用する意味はあるのか
Ruby3.0くらいには改善するのでしょうか？
なお検証はruby 2.2.3p173 (2015-08-18 revision 51636) [x86_64-darwin13]で行いました。

【Ruby】ArrayとQueueがスレッドセーフか検証してみた

背景