[ruby][java] JRuby ã®ä¸¦åˆ—å®Ÿè¡Œã§ãƒ¡ã‚½ãƒƒãƒ‰ã®è¿½åŠ ã®å®Ÿè£…æ–¹æ³•

某所にて、 JRuby のスレッドは本当に並列で走る(global interpreter lock は使っていない)という話を聞きました。Ruby (大文字で始まるので言語のほうね) では、define_method とか動的な仕組みがいろいろとあるので、実装は大変なんじゃなかろうか、と思い、 JRuby のソースを久し振りに眺めてみることにしました。
メソッドの追加と、それと対になるメソッド呼び出し(探索)だけに注目しているので、ほんの一部しか目を通していません。注目するところは、以下の 2 点のみです。

1. メソッド追加時に取得するロックはなにか
2. メソッド呼び出し(探索)時にロックを取得するのか、するなら頻度とロックの種類

This is a community wiki dedicated to JRuby, an implementation of the Ruby programming language atop the Java Virtual Machine (JVM).

JRuby: Wiki: Home ― Project Kenai

対象バージョン: 1.4.0

追い掛けやすそうなメソッド追加側

Emacs で rgrep define_method 。RubyModule#define_method が出てきたので、これで間違いなさそう。おおざっぱにまとめると、

• module 単位で token をもって型を世代管理している (型の名前と token の組で識別)
• メソッド追加時には、module 単位のロックを取得
• そのロックを持った中で、
  • メソッドの Map を更新して
  • メソッド探索用のキャッシュを更新する
    • この時は、グローバルなキャッシュを取って
    • 更新で影響を受ける型オブジェクトに対する token を更新している

以下、コード読んだときの走り書き。

RubyModule.java
  L. 1348
    @JRubyMethod(name = "define_method", frame = true, visibility = PRIVATE,
                 reads = VISIBILITY)
    public IRubyObject define_method(ThreadContext context, IRubyObject arg0,
                                     Block block) {
        Ruby runtime = context.getRuntime();
        ...
        RuntimeHelpers.addInstanceMethod(this, name, newMethod,
                           context.getPreviousVisibility(), context, runtime);
  L.  885 addMethod
  L.  895 addMethodInternal
        synchronized(getMethods()) {
            addMethodAtBootTimeOnly(name, method);
            // -> methods#put している
            invalidateCacheDescendants();
            // -> 
            // 1. generation の更新 (token を new Object() で上書き)
            // 2. getRuntime().getHierarchyLock() のロック(グローバル)を持って
            //    includingHierarchy.invalidateCacheDescendants();
        }
  L.  369 getMethods
    methods の getter
    L. 199 private final Map<String, DynamicMethod> methods =
                   new ConcurrentHashMap<String, DynamicMethod>(4, 0.9f, 1);

RuntimeHelpers (org.jruby.javasupport.util)
  L. 1398 addInstanceMethod 
    L. 1403 call addModuleMethod
      L. 1409 addModuleMethod
        L. 1410
          containingClass.getSingletonClass().addMethod(name, new WrapperMethod(
            containingClass.getSingletonClass(), method, Visibility.PUBLIC));
          // containingClass: RubyModule

メソッド呼び出し(探索)側

org.jruby.runtime.Callsite からの型ツリーが呼び出し側っぽい。
ザッとまとめ。

• 基本はロックを取らない。
• ときどき(0xFF + 1 = 256)、synchronized をかけてスレッドワーキングメモリを追い出す。
• token を調べて、古かったら真面目にメソッドを探索する(親なども追い掛ける)。

走り書き。

CashingCallsite.java
  L. 63 call
    L. 64 callAndGetClass
      ThreadContext#callThreadPoll (L.502) // 0xFF 回ごとには synchronized する
    L. 66 CacheEntry#typeOK
      // キャッシュの有効性確認
    L. 69 cacheAndCall
      L. 274 selfType.searchWithCache // selfType: RubyClass
      L. 277 callMethodmissing
      L. 280 method.call  // method: DynamicMethod

RubyModule
  L. 962 searchWithCache
    L. 963 cacheHit // メソッドキャッシュから名前で引いて token を当てる
      取れたらそれを return
    L. 969 取れないときは、階層を上に探索して、キャッシュして返す
      L. 967 - 968 この処理へのコメント
        // we grab serial number first; the worst that will happen is we cache a later
        // update with an earlier serial number, which would just flush anyway
        // 訳: 先にシリアルナンバー(token)を取る。最悪でも、キャッシュされたメソッドに
        //     対する token が古くなるが、それはあとで捨てられるだけである。

実際に動かしてみる

1. ロック競合がほとんで無いであろう fibonacchi を one thread, two threads で計算
2. 同じクラスの同じメソッドを define/undefine
3. 同じクラスの違うメソッドを define/undefine
4. 違うクラスのメソッドを define/undefine

コードは gist

difine_method_bench.rb

gist: 235787 - GitHub

環境

% sw_vers
ProductName:    Mac OS X
ProductVersion: 10.6.2
BuildVersion:   10C540

% system_profiler SPHardwareDataType | grep Processor
      Processor Name: Intel Core 2 Duo
      Processor Speed: 2.2 GHz
      Number Of Processors: 1

% ï¿£/local/jruby-1.4.0/bin/jruby --version
jruby 1.4.0 (ruby 1.8.7 patchlevel 174) (2009-11-02 69fbfa3)
  (Java HotSpot(TM) 64-Bit Server VM 1.6.0_15) [x86_64-java]

結果
2 -> 3 -> 4 の順で実行時間が短くなっていることが分かる。上のソース読みと整合性は取れている。ただし、完全には説明できているわけではない。

% ï¿£/local/jruby-1.4.0/bin/jruby define_method_bench.rb 38 2000000
Almost no lock contention (calculate Fibonacchi sequence)
                user     system      total        real
1 thread  (0) 12.088000   0.000000  12.088000 ( 12.038000)
2 threads (0) 14.528000   0.000000  14.528000 ( 14.528000)
1 thread  (1) 12.234000   0.000000  12.234000 ( 12.235000)
2 threads (1) 17.308000   0.000000  17.308000 ( 17.308000)
1 thread  (2) 12.030000   0.000000  12.030000 ( 12.031000)
2 threads (2) 15.870000   0.000000  15.870000 ( 15.870000)
1 thread  (3) 12.298000   0.000000  12.298000 ( 12.298000)
2 threads (3) 15.762000   0.000000  15.762000 ( 15.762000)

Add/remove the SAME method for the SAME class object
                user     system      total        real
1 thread  (0)  4.203000   0.000000   4.203000 (  4.202000)
2 threads (0)  7.575000   0.000000   7.575000 (  7.575000)
1 thread  (1)  3.629000   0.000000   3.629000 (  3.629000)
2 threads (1)  7.204000   0.000000   7.204000 (  7.205000)
1 thread  (2)  3.545000   0.000000   3.545000 (  3.545000)
2 threads (2)  7.292000   0.000000   7.292000 (  7.291000)
1 thread  (3)  3.684000   0.000000   3.684000 (  3.684000)
2 threads (3)  7.060000   0.000000   7.060000 (  7.060000)

Add/remove different methods for the SAME class object
                user     system      total        real
1 thread  (0)  3.758000   0.000000   3.758000 (  3.758000)
2 threads (0)  5.774000   0.000000   5.774000 (  5.774000)
1 thread  (1)  3.840000   0.000000   3.840000 (  3.840000)
2 threads (1)  5.938000   0.000000   5.938000 (  5.938000)
1 thread  (2)  3.709000   0.000000   3.709000 (  3.709000)
2 threads (2)  5.482000   0.000000   5.482000 (  5.483000)
1 thread  (3)  3.749000   0.000000   3.749000 (  3.749000)
2 threads (3)  5.614000   0.000000   5.614000 (  5.613000)

Add/remove different methods for different class objects
                user     system      total        real
1 thread  (0)  3.805000   0.000000   3.805000 (  3.805000)
2 threads (0)  5.156000   0.000000   5.156000 (  5.156000)
1 thread  (1)  3.662000   0.000000   3.662000 (  3.662000)
2 threads (1)  4.900000   0.000000   4.900000 (  4.900000)
1 thread  (2)  3.656000   0.000000   3.656000 (  3.656000)
2 threads (2)  4.611000   0.000000   4.611000 (  4.611000)
1 thread  (3)  3.735000   0.000000   3.735000 (  3.735000)
2 threads (3)  4.800000   0.000000   4.800000 (  4.800000)

補足

Java 仮想マシンの仕様で、 synchronized (修飾子 or ブロック)による、スレッドのワーキングメモリとメインメモリの同期要求に関しては、結城さんの本にに説明があって、すごく分かりやすい(本文じゃなくてコラムかアペンディックスだったかも)。
Amazon.co.jp： 増補改訂版 Java言語で学ぶデザインパターン入門 マルチスレッド編: 結城 浩: 本

ダグ・リー先生のページにしっかりとした説明がある。

In essence, releasing a lock forces a flush of all writes from
working memory employed by the thread, and acquiring a lock
forces a (re)load of the values of accessible fields. While lock
actions provide exclusion only for the operations performed
within a synchronized method or block, these memory effects are
defined to cover all fields used by the thread performing the
action.

Note the double meaning of synchronized: it deals with locks that
permit higher-level synchronization protocols, while at the same
time dealing with the memory system (sometimes via low-level
memory barrier machine instructions) to keep value
representations in synch across threads. This reflects one way in
which concurrent programming bears more similarity to distributed
programming than to sequential programming. The latter sense of
synchronized may be viewed as a mechanism by which a method
running in one thread indicates that it is willing to send and/or
receive changes to variables to and from methods running in other
threads. From this point of view, using locks and passing
messages might be seen merely as syntactic variants of each
other.

Synchronization and the Java Memory Model