トップ «前の日記(2009-09-05) 最新次の日記(2009-09-07)» 編集

日々の破片

2009-09-06

_ volatile、マルチスレッド、キャッシュコヒーレンス

The Art of Multiprocessor Programmingだが、1章と2章を何度も読み返しながら、なんでこんなに難しいんだろうか？と情けなくもあり、おもしろくもあり。わかるということと理解し切るということの相違だなぁ。

で、付録のハードウェアの基礎のところに、TASLockとTTASLockというのが出ていて、それを真似た実装をしてみていろいろ試してみると、どうも書いてあることとは結果が異なる。

TASLockは、TestAndSetなLockで、TTASLockは、Test-TestAndLockで、書いてあることを読むと、意味は同じ、コード量はTTASLockが多く、しかしパフォーマンスはTTASLockのほうが良い、ということになっている。

Javaで実装すると以下のようなコードになる（が、もちろん、現実には異なるコードとなるため、結果が異なるのだが、それに気づくまでえらく試行が必要だったというのが結論となる）。

import java.util.concurrent.atomic.AtomicBoolean;
public class LockBench {
    static AtomicBoolean abo = new AtomicBoolean();
    static void tasLock() {
        while (!abo.compareAndSet(false, true)) {} // tas
    }
    static void ttasLock() {
        while (true) {
            while (abo.get()) {} // test
            if (abo.compareAndSet(false, true)) { // tas
                return;
            }
        }
    }
    static void unlock() {
        abo.set(false);
    }
    static void runThreads(Thread[] ts) throws Exception {
        long start = System.currentTimeMillis();
        for (Thread t : ts) {
            t.start();
        }
        for (Thread t : ts) {
            t.join();
        }
        System.out.println(ts.length + " threads run in " + (System.currentTimeMillis() - start)
                           + " msecs");
        java.util.Arrays.fill(ts, null);
        System.gc();
    }
    interface Lock {
        void lock();
    }
    static class TestThread extends Thread {
        Lock lock;
        TestThread(Lock lk) {
            lock = lk;
        }
        public void run() {
            // (A) 初期化コード
            int x = 0;
            for (int i = 0; i < 1000000; i++) {
                lock.lock();
                // (B)何かおもしろいことを行う
                unlock();
            }
            // (c) 退出コード
        }
    }
    static void bench(int nthreads) throws Exception {
        Thread[] ts = new Thread[nthreads];
        for (int i = 0; i < nthreads; i++) {
            ts[i] = new TestThread(new Lock() {
                    public void lock() {
                        tasLock();
                    }
                });
        }
        runThreads(ts);  // TAS
        for (int i = 0; i < nthreads; i++) {
            ts[i] = new TestThread(new Lock() {
                    public void lock() {
                        ttasLock();
                    }
                });
        }
        runThreads(ts);  // TTAS
    }
    public static void main(String[] args) throws Exception {
        int nthreads = 4;
        if (args.length > 0) {
            nthreads = Integer.parseInt(args[0]);
        }
        for (int i = 0; i < 4; i++) {
            bench(nthreads);
        }
    }
}

上の、何もおもしろいことを行わない(A〜C)が空の場合、以下の結果を得た。NetBurst Xeon 2.8GHzのSMPでHyperThreadありの見かけ4CPUマシン。

c:\home\arton\test>java -cp . LockBench 1 2>nul:
1 threads run in 141 msecs
1 threads run in 131 msecs
1 threads run in 118 msecs
1 threads run in 113 msecs
1 threads run in 118 msecs
1 threads run in 116 msecs
1 threads run in 117 msecs
1 threads run in 113 msecs
--- 1スレッドだともしかするとTTASが速い？
c:\home\arton\test>java -cp . LockBench 4 2>nul:
4 threads run in 936 msecs
4 threads run in 944 msecs
4 threads run in 954 msecs
4 threads run in 967 msecs
4 threads run in 761 msecs
4 threads run in 962 msecs
4 threads run in 931 msecs
4 threads run in 972 msecs
--- 4スレッドだとTASのほうが速い？ （というか、1スレッドで4回回すほうが速いと思う）
c:\home\arton\test>java -cp . LockBench 8 2>nul:
8 threads run in 3924 msecs
8 threads run in 3596 msecs
8 threads run in 3671 msecs
8 threads run in 3815 msecs
8 threads run in 2465 msecs
8 threads run in 3601 msecs
8 threads run in 2924 msecs
8 threads run in 3330 msecs
--- 8スレッドだとTASのほうが速い？
c:\home\arton\test>java -cp . LockBench 16 2>nul:
16 threads run in 11665 msecs
16 threads run in 10544 msecs
16 threads run in 10480 msecs
16 threads run in 9087 msecs
16 threads run in 10105 msecs
16 threads run in 10281 msecs
16 threads run in 10493 msecs
16 threads run in 9325 msecs
--- 16スレッドだとTTASのほうが速い？

しかし、書かれている説明を読むと、この結果（ほとんどの場合TASが速く、TTASが逆転したとしても、顕著な差とはならない）は論理的に納得できない。

TASLockは、getAndSet(true)(引用者注- concurrentライブラリが提供するcompareAndSetと等しい機能を持つ仮想的なメソッド)をロックに適用するたびに相互接続を通じてメッセージを送信し、大量のトラフィックを引き起こす。SMPアーキテクチャでは、このトラフィックによって相互接続が飽和状態となり、すべてのスレッドを遅延させる。（中略）対照的に、ロックがビジー状態である間、TTASLockはスピンし、ロックのローカルキャッシュのコピーを読みとる。このため、相互接続トラフィックを生成せず、パフォーマンスに優れている。

説得的だ。

何が問題かは以下を試してわかった。

static volatile int total; // クラス変数として追加
static int dummy(int x) {
    return x * 2 + 1; // 適当な内容
}
(A) int x = 0;
(B) total += dummy(x++);
(C) System.err.println("total=" + total);

実行した結果は以下となった。

c:\home\arton\test>java -cp . LockBench 1 2>nul:
1 threads run in 206 msecs
1 threads run in 200 msecs
1 threads run in 181 msecs
1 threads run in 207 msecs
1 threads run in 180 msecs
1 threads run in 208 msecs
1 threads run in 180 msecs
1 threads run in 207 msecs
--- 元の結果より倍以上遅い。
c:\home\arton\test>java -cp . LockBench 4 2>nul:
4 threads run in 2406 msecs
4 threads run in 2754 msecs
4 threads run in 2342 msecs
4 threads run in 2672 msecs
4 threads run in 2120 msecs
4 threads run in 2723 msecs
4 threads run in 2306 msecs
4 threads run in 2744 msecs
--- 倍以上遅い。
c:\home\arton\test>java -cp . LockBench 8 2>nul:
8 threads run in 7621 msecs
8 threads run in 8384 msecs
8 threads run in 6943 msecs
8 threads run in 9046 msecs
8 threads run in 6904 msecs
8 threads run in 8987 msecs
8 threads run in 5915 msecs
8 threads run in 9320 msecs

付け加えた処理にはSystem.err.printlnというIO呼び出しがあるが、しかしこれは100万回ループの外なので大きな影響はない。したがって、これだけ遅くなる原因は、volatileなtotalへの代入にあると推測できる。

以下のように変えてみる。

static int dummy(int x) {
    return x * 2 + 1; // 適当な内容
}
(A) int x = 0;
(B) x += dummy(x++); // 多分、畳まれないとは思う
(C) System.err.println("total=" + x);

結果は以下となった。

c:\home\arton\test>java -cp . LockBench 8 2>nul:
8 threads run in 3600 msecs
8 threads run in 2548 msecs
8 threads run in 3083 msecs
8 threads run in 2835 msecs
8 threads run in 3974 msecs
8 threads run in 2866 msecs
8 threads run in 2836 msecs
8 threads run in 3057 msecs

そこで気づいた。

元の説明で、TASLockよりTTASLockが高速なのは、最初のTestで読みとる値をキャッシュとしているからだ。だが、AtomicBooleanのAPIとして考えた場合、getメソッドがキャッシュを返すはずがない。

確認してみる。

(jdk 1.6.0_16 AtomicBoolean.java)
    ……
    private volatile int value;
    ……
    public final boolean get() {
        return value != 0;
    }
    ……

なるほど。

いずれにしても、Javaの仕様からは、もしvolatileなしでvalueを宣言していたとしたら、メインメモリからの読み直しすら必要ない。最悪の場合、永遠に（JVM上の）キャッシュの読みとりになる可能性もあるわけで、この実装以外にはあり得ない話ではある。

それにしてもvolatile修飾子1つでこれだけパフォーマンスに影響を与えるというのは、頭ではわかっているようでもやってみないとわからないものだった。

The Art of Multiprocessor Programming 並行プログラミングの原理から実践まで(Maurice Herlihy)