PyUblasとBoost.Pythonを使ったDTWの実装

Python C++

PyUblasを試すために, 今回は距離関数の一つであるDTW(Dynamic Time Warping)を実装する.

DTWの説明は余所で読んでもらうとして, まあ２つの長さが異なるベクトルx,y の距離をO(|x|×|y|)で計算するアルゴリズムだと思ってもらえばいい. 今回はパフォーマンスにも着目するため, 比較対称としてmlpyのDTW関数を用いた.
Pythonで単純に書くと次のようになる.

def dtw(x,y):
    n = len(x)
    m = len(y)
    cost = zeros((n,m))

    cost[0,0] = abs(x[0] - y[0])
    for i in range(1,n):
        cost[i,0] = cost[i-1,0] + abs(x[i]-y[0])
    for i in range(1,m):
        cost[0,i] = cost[0,i-1] + abs(x[0]-y[i])

    for i in range(1,n):
        for j in range(1,m):
            cost[i,j] = min(cost[i-1,j],cost[i,j-1],cost[i-1,j-1]) + abs(x[i] - y[j])

    return cost[n-1,m-1]

ただ, これは非常に遅い. 長さ16のベクトル同士の比較を10000回するだけで6.3秒かかる.

そこで, Boost.Pythonを用いてC++で実装することで高速化する. 全部は掲載しないが, メインのループは次のようになっている.

 for(int i = 1;i <= n;i++,ite_x++){
    numpy_vector<double>::const_iterator ite_y = y.begin();
    
    for(int j = 1;j <= m;j++,ite_y++){
      costs[i][j] = min(min(costs[i-1][j],costs[i-1][j-1]),costs[i][j-1]) + euc(*ite_x,*ite_y);
    }
  }

numpy_vectorはPyUblasで提供されているvectorである. これはindexでのアクセスが遅いとあったので(以前の日記を参照), Iteratorを用いてアクセスしている.

これによる高速化がどの程度かを調べるため最初のPythonで実装したもの, mlpy, Boost.Pythonで実装したもの, 3つのパフォーマンスを計測した. 長さ16のベクトル同士で100万回距離を計測している. また, コンパイルは-O2オプションを用いて行なっている.

手法 実行時間(s)
PurePython たくさん
mlpy 10.8s
Boost.Python 10.4s

mlpyよりちょっと速い！ mlpyはCythonを使って実装しているように見える.

もっと速く！

更にBoost.Pythonを高速化するためにoprofileを用いたパフォーマンス分析を行なった. 計測は次のように行なっている.

sudo opcontrol --reset
sudo opcontrol --start
計測対象プログラム
sudo opcontrol --shutdown
opreport -tl1

ただし, コンパイルオプションで-gをつけているためパフォーマンスは大幅に悪化している. この計測結果は次のようになった.

samples % app name symbol name
434030 10.0486 extra_distance.so boost::python::handle<_object>::get() const
384109 8.8929 extra_distance.so pyublas::numpy_array::begin() const
310042 7.1781 no-vmlinux /no-vmlinux
268411 6.2142 extra_distance.so pyublas::numpy_array::ndim() const
248274 5.7480 extra_distance.so pyublas::numpy_array::stride(long) const
203019 4.7003 extra_distance.so pyublas::numpy_array::dim(long) const

これを見る限り, numpy_vectorの値へのアクセスに大きなコストがかかっている. そこで, Pythonから受け取った際にnumpy_vectorをboost::numeric::ublas::vectorに変換し, それに対して処理を行うように変更した.

その結果のパフォーマンスは

手法 実行時間(s)
PurePython たくさん
mlpy 10.8s
Boost.Python 10.4s
変換する奴 2.7s

と大幅に向上した.

まとめ

PyUblasのvectorの要素へのアクセスは例えiteratorであっても遅い. まずiteratorの取得が結構めんどいっぽいし. これはメモリコピーが不要という利点を上回るものであり, 要素へのアクセスが多いような操作では, 一度boost::numericのvectorに変換した方がよい.

実験結果で注意しなければいけないのは, mlpyにおいてCythonで実装されたDTWよりもBoost.Pythonを適切に用いたDTWの方が速いように見えるのは, Cythonのせいでは無い.
現在, Boost側のDTW関数は, A,BとC, Dを渡すと, (A,B)(A,D)(B,C)(B,D)の間の距離を返すような仕様になっている. 一方, mlpyでは一つずつしかベクトルを渡せないため, 上の例ではAを２回型変換する必要がある. このことが, 大きなオーバーヘッドを産んでいるため, ちゃんとフェアな実験をしなおさなくてはならない.

もう一つ注意したいのは, contiguousであることが保証されているnumeric_matrixを使うという手だ. これは, メモリコピーの必要無く素早い処理が書けるのでは無いだろうか. これも試したい.

追記: 残念ながらnumpy_matrixとnumpy_vectorのパフォーマンスはさほど変わらなかった.