竹内関数を使って分散並列言語Swiftのオーバーヘッドを見てみる

竹内関数は関数呼出のオーバーヘッドのベンチマークやメモ化の例題としてよく挙げられます。

では分散処理言語で竹内関数を実装してみましょう。

分散処理言語では、多数の計算資源へ多数のタスクを良い感じに割り当てて分散処理する、といった事にフォーカスしてデザインされています。「良い感じ」というのには、対象となる処理の特性やネットワークの特性などによって様々なゴールがあるので、まあ色々です。

で、ちょうど、良い感じの分散処理スクリプト言語のSwiftが見つかったのでこれでやってみます。

Swiftではプロシージャ単位で良い感じに分散処理されます。竹内関数をプロシージャとして実装すると、全然良くない感じになるので、分散処理のオーバーヘッドがベンチマークができるはずです。

では実装してみます。プロシージャ名をtとして実装します。Swiftでは名前付の多値引数と多値返値が扱えます。返値はreturn文で返すのではなく返値の変数に代入します。変数への代入は1度しかできない点にも注意です。（よくある事です。）

tarai.swift

(int result) t (int x, int y, int z) {
    if(x <= y) {
        result = y;
    } else {
        result = t(
            t(x-1, y, z),
            t(y-1, z, x),
            t(z-1, x, y)
        );
    }
}
trace(t(8, 4, 0));

そして実行します。

time ./bin/swift tarai.swift
Swift 0.94.1 swift-r7114 cog-r3803

RunID: 20140604-1607-h5vkatrb
Progress:  time: Wed, 04 Jun 2014 16:07:21 +0900
SwiftScript trace: 8
Final status: Wed, 04 Jun 2014 16:07:28 +0900

real    0m11.067s
user    0m18.387s
sys 0m1.284s

　　　＿人人人人＿
　　　＞　11秒　＜
　　　￣Y^Y^Y￣

おそらく12605回のタスク割当とプロシージャ呼出と沢山のメッセージ交換が起こったのでしょう。おつかれさまです。

ちなみにRubyでも実行してみます。

tarai.rb

def t(x,y,z)
  if x <= y
    y
  else
    t(t(x-1, y, z), t(y-1, z, x), t(z-1, x, y))
  end
end
puts t(8, 4, 0)

えい。

$ time ruby tarai.rb 
8

real    0m0.037s
user    0m0.029s
sys 0m0.007s

0.037秒でした。

ということで、この手のたぐいのプログラミング言語では、無意識に再帰呼出をすると悲しみの海が広がるので注意しましょう。