64-bit Lock-free queue implementation

by syoyo

http://lucille.atso-net.jp/svn/angelina/algo/lock-free/

[EN] Here’s my implementation of

Simon Doherty, Maurice Herlihy, Victor Luchangco and Mark Moir,
Bringing practical lock-free synchronization to 64-bit applications.
PODC 2004. pp. 31–39.
http://www.cs.brown.edu/research/projects/transactional_memory.html


[JP]

64-bit 対応な lock-free queue を実装してみました。

この論文の特徴は、

o 64-bit 対応
o スレッド数をあらかじめ知らなくても OK (population-oblivious)
o O(m+n) のメモリ領域しか使わない(m = LL/SC でアクセスが必要な変数の数, n = スレッド数)

な lock-free queue アルゴリズムの提案です。これらすべてを実現するのは、この論文のアルゴリズムが初らしい。論文には疑似コードが豊富でだいたいそのまま実装もできちゃうのがいい(CAS のインラインアセンブラ実装で手こずりましたが)。

lock-free アルゴリズム

lock-free とは、ロックを必要としないで同期処理を行うアルゴリズムです。

http://ja.wikipedia.org/wiki/Lock-freeとWait-freeアルゴリズム

nyaxt 先生の日記でこの言葉を知りましたが、
10 年以上前からずっと研究されてきた仕組みなんですね。

スレッド間での同期や排他処理などには、
ミューテックスとかで排他区間を実現するくらいしか知らなかったので、
ちょっと目から鱗でした。

今は linux やら windows などのカーネルでも、この lock-free なアルゴリズムが使われています。

lock-free に関係の深いものとして、wait-free アルゴリズムというのもあります(wikipedia 参照)。

web で調べた限りではあまりよい説明が無かったのですが、
要は、通常のロックベースだと、誰かがロックを取っている間は
他のスレッドは資源にアクセスできないので、(最悪無制限に)待たざるを得ないのですが、
wait-free であれば、最大でも待ちはスレッド数に比例するが、
有限時間内に自分に資源が回ってくる、という感じでしょうか。

既存のロックベースのアルゴリズムは、
while とかでループをまわして資源がとれるまで待ちますが、
しかし wait-free だからと言って、
そのような while でループを回すという仕組みが無くなるというわけではないようです。

ループで回る回数がロックベースに比べると少なくなったり、
無制限にループしてしまう(デッドロック)ということが起きなくなるという感じのようです。

アトミック命令

さて、実際に lock-free アルゴリズムを実現するには、アトミック命令と呼ばれる、
特定のメモリ位置を不可分(atomic)に操作する命令が必要になります。

アトミック命令には、CAS(Compare and Swap) もしくは
LL/SC(Load-Linked/Store-Conditional)命令があります。
x86 では、CAS のみがサポートされ、LL/SC 命令はサポートされていませんが、
通常 LL/SC は CAS で実装することが可能です。

アトミック命令といっても、プロセッサによってそのサポートには細かい違いがあり、
たとえば一度に不可分に操作できるバイト数などに違いがあります。

また、アトミック命令は、Java などではそれらのインターフェイスが提供されていますが、
C 言語ではインラインアセンブラを使って呼び出す必要があります。

今回の実装では、64-bit 環境における 64-bit 幅の CAS 命令が必要です。
x86-64 な環境では、64-bit 幅の CAS 命令は、cmpxchgq 命令が用意されています。

static inline uint64_t cmpxchg64(void *ptr, uint64_t oldv, uint64_t newv)
{
        uint64_t out;

        uint64_t v = *((uint64_t *)ptr);

        // newline after `lock' for the work around of apple's gas(?) bug.
        __asm__ __volatile__(
                "lock\\n cmpxchgq %2,%1"
                : "=a" (out), "+m" (*(volatile uint64_t *)ptr)
                : "q" (newv), "0" (oldv)
                : "cc");

        return out;
}

Intel Mac の場合、コンパイラのバグらしきもののせいで、
lock の後には newline が必要になります。
(二行に分けて書くのが問題ないかも)

cmpchg8b 命令も 64-bit 幅の CAS 命令で、これは 32-bit 環境でサポートされています。
atomic_ops ライブラリ [1] より。

static inline int
cas64(volatile double_var_t *addr, unsigned long old1, unsigned long old2,
     unsigned long new1, unsigned long new2)
{
  char result;
  __asm__ __volatile__("lock\\n cmpxchg8b %0; setz %1"
                       : "=m"(*addr), "=q"(result)
                       : "m"(*addr), "d" (old1), "a" (old2),
                         "c" (new1), "b" (new2) : "memory");
  return (int) result;
}

ただ、このコード、Linux ではうまくいくのですが、
Intel Mac のコンパイラだと BREG に割当てられないとか変なエラーがでてコンパイルできません。
うーん、インラインアセンブラをしっかり勉強しないとかな。

その他、x86_64 環境では、cmpxchg16b という 128-bit 幅のアトミック命令があります。
(AMD64 環境では、最近になりサポートされたようです [2] )
他プロセッサでのアトミック命令を扱うコードは、atomic_ops [1] などが参考になります。

パフォーマンス

通常のロックベースのキュー(リポジトリの TowLockConcurrentQueue/ にある)と、
今回の 64-bit clean な lock-free キューの実装とのパフォーマンスを比較してみました。

result.png
horizontal: # of threads. vertical: time(secs).

横軸がスレッド数で、縦軸が処理時間(秒)です。
ロックベース(pthread_mutex 使用)では、2 スレッド以上でガクンと処理時間がかかっています。

測定のプログラムはキューの処理中に malloc/free を呼んでいたりするので、あまり fair な
パフォーマンス測定プログラムではないと思います。

pthread_mutex を利用したロックベースの手法も、スレッド数が増えていく割には
処理時間が O(n^2) とかで増えて行く訳ではないので、単純に pthread_mutex コールの
オーバヘッドの差だけなのかもしれません。

それでも絶対的な処理時間は lock-free が短いので利用価値はある、と言えそうです。

キュー構造とレンダラ

マルチスレッド対応(MT safe)なキュー構造は、現状の lucille ではあまりプログラムが高度にスレッド化もされているわけではないので、利用部分は今のところないと思います。

しかし、kilauea の解説をみると MT safe キューは至る所で使われたとあります。
これからのマルチコア時代に、1 CPU 内の中で kilauea のような複雑なスレッドレンダリング処理を行うことを考えると、MT safe なキュー構造の必要性が大きいと思います。

そういう訳で、今回の lock-free queue の実装に至りました。

ただ、NVIDIA の cuda や Intel の 80 cores プロセッサをみると、
スレッドへの仕事の割り振りやスレッド間の同期とかはコンパイラが
うまーく処理してくれそうな雰囲気がします。
なので、いずれ lock-free なアルゴリズム(に限らず並列プログラムも?)を
ユーザが実装するというのは必要無くなっていくのかもしれませんね…

[1] The atomic_ops project
[2] http://www.marbacka.net/asm64/arkiv/amd64_em64t_difference.html

Advertisements