.. _Optimization_Techniques:

コードの性能評価と改善方法
****************************************************

目的
======
    
画像処理は単位時間辺りに膨大な量の計算を扱うことになるため，正しい答えを得るというだけではなく高速に計算する必要があります．このチュートリアルでは

    * 自分が書いたコードの性能を計測する方法を学びます
    * 自分が書いたコードを改善する秘訣を学びます
    * 以下の関数の使い方を学びます : **cv2.getTickCount**, **cv2.getTickFrequency** etc.
    
OpenCVはさておき，実はPythonには処理時間の計測のためのモジュール **time** がありますさらに， **profile** というモジュールを使えば，各関数がコード内で何回使われたか，実行中に南海呼び出されたかといった詳細なレポートを取得できます．しかし，もしあなたがIPythonを使っているのであれば，もっとユーザフレンドリな形でこれら全ての機能が使えます．これらの内で重要なものを紹介します．興味がある人は **補足資料** に載っている資料を参照してください．

OpenCVの機能を使って性能を計測
==================================

**cv2.getTickCount** 関数は参照イベント後にクロック単位での時間(コンピュータがON状態になってからこの関数が呼ばれるまでの時間のようなもの)を返します．uそのため，ある関数を実行する前後でこの関数を呼べば，その関数の処理時間をクロック単位で知ることができます．

**cv2.getTickFrequency** 関数は単位時間あたりのクロック周波数を知るための関数です．処理速度を秒単位で知るためには，以下のようにします:
::

    e1 = cv2.getTickCount()
    # your code execution
    e2 = cv2.getTickCount()
    time = (e2 - e1)/ cv2.getTickFrequency()
    
以下の例ではカーネルサイズを5から49と変化させながら中央値フィルタを適用した時にかかる処理速度を表示します． (結果がどのようなものであるかは重要ではないので気にしないでください):
::

    img1 = cv2.imread('messi5.jpg')

    e1 = cv2.getTickCount()
    for i in xrange(5,49,2):
        img1 = cv2.medianBlur(img1,i)
    e2 = cv2.getTickCount()
    t = (e2 - e1)/cv2.getTickFrequency()
    print t
    
    # Result I got is 0.521107655 seconds
    
.. note::  ``time`` モジュールを使って同じことをするためには ``cv2.getTickCount`` の代わりに ``time.time()`` 関数を使います．


OpenCVのデフォルトでの最適化
================================

多くのOpenCVの関数はSSE2やAVXを使って最適化されていますが，中には最適化されていない関数もあります．もしも我々のシステムがこれらの最適化の機能をサポートしているのであれば利用するべきです(今現在使用されているプロセッサであれば大半はサポートしているはずです).最適化機能はデフォルトではコンパイル時に有効化されています．有効化されていればOpenCVは最適化されたコードを実行しますし，そうでなければ最適化されていないコードを実行することになります． **cv2.useOptimized()** 関数を使えば最適化が有効化されているか無効化されているか調べられ， **cv2.setUseOptimized()** 関数を使えば有効化もしくは無効化できます．というわけで，実際のコードを見てみましょう．
::

    # check if optimization is enabled
    In [5]: cv2.useOptimized()
    Out[5]: True

    In [6]: %timeit res = cv2.medianBlur(img,49)
    10 loops, best of 3: 34.9 ms per loop

    # Disable it
    In [7]: cv2.setUseOptimized(False)

    In [8]: cv2.useOptimized()
    Out[8]: False

    In [9]: %timeit res = cv2.medianBlur(img,49)
    10 loops, best of 3: 64.1 ms per loop


最適化が有効化されている場合，中央値フィルタの処理速度は無効化時に比べ2倍ほど速くなっています．関数の実装を見れば中央値フィルタがSIMD最適化されていることが分かるかと思います．この例が示すように，ライブラリの中身を変更すること無くコードの最上位からコード最適化を有効化ができるわけです(繰り返しますが，コードの最適化はデフォルトで有効化されています)．


IPythonの機能を使った性能の計測
============================================================

プログラミングをしていると，二つの似たような処理を実装したコードの性能を比較する機会があると思います．この目的を実現するために，IPythonは ``%timeit`` というコマンドを用意しています．このコマンドを実行すると，処理速度の計測を高精度に行うため，コードを数回実行します．ただし，この機能は主に1行の命令を計測する作業に向いています．

例えば，以下に示す加算処理の内，どの処理が良い処理でしょうか． ``x = 5; y = x**2``, ``x = 5; y = x*x``, ``x = np.uint8([5]); y = x*x`` or ``y = np.square(x)`` ? IPython上で ``%timeit`` コマンドを使えば比較が容易にできます．
::

    In [10]: x = 5

    In [11]: %timeit y=x**2
    10000000 loops, best of 3: 73 ns per loop

    In [12]: %timeit y=x*x
    10000000 loops, best of 3: 58.3 ns per loop

    In [15]: z = np.uint8([5])

    In [17]: %timeit y=z*z
    1000000 loops, best of 3: 1.25 us per loop

    In [19]: %timeit y=np.square(z)
    1000000 loops, best of 3: 1.16 us per loop

この結果を見ると, ``x = 5 ; y = x*x`` の処理が最速で，Numpyに比べて20倍ほど高速であることが分かります．配列の作成も処理速度に含めると100倍も速くなっていることが分かります．すごいと思いませんか？  *(Numpyの開発チームは，この兼に関して処理の高速化を行っています)*

.. note:: Pythonのスカラー計算はNumpyのスカラー計算より高速なので，1,2要素を含む処理であればPythonのスカラー計算を使うほうがNumpyの配列を使って計算するより高速に処理ができます．Numpyは配列のサイズが大きくなった時に使うと良いでしょう．
    
もう一つの例を示します．この例では **cv2.countNonZero()** 関数と **np.count_nonzero()** 関数のを同じ画像に対して適用した時の性能の差を比較史ます．
::

    In [35]: %timeit z = cv2.countNonZero(img)
    100000 loops, best of 3: 15.8 us per loop

    In [36]: %timeit z = np.count_nonzero(img)
    1000 loops, best of 3: 370 us per loop
           
結果が示すように，OpenCVの関数の方が25倍ほど高速です．

.. note:: 一般的にOpenCVの関数はNumpyの関数より高速に実行されるため，同一の処理であればOpenCVを使った方が良いでしょう．ただし例外が有ります．コピーではなくデータの値を見る時はNumpyの方が高速に処理ができます．

      
IPythonの更なるマジックコマンド
=======================================

上で紹介した ``%timeit`` 以外にも，性能計測やプロファイリング，メモリ計測などに便利なマジックコマンドがあります．これらのマジックコマンドについては公式ドキュメントによくまとめられているので，ここではドキュメントへのリンクを載せるだけにします．興味がある人は，リンク先のドキュメントに目を通してみてください．

パフォーマンスの最適化技術
=====================================

PythonとNumpyの最大限の性能を引き出すための技術が幾つかあります．ここでは関連性のある技術のみ紹介し，重要なソースへのリンクを載せます．ここで述べるべき大事な点は，アルゴリズムを実装する時は，まず初めに単純な実装を試すということです．処理のボトルネックを見つけたりコードを最適化するのは，アルゴリズムが正しく動作することを確認してからです．

    #. Pythonを使うのであれば，可能な限りループの使用を避けましょう．特に二重/三重ループやそれ以上の多重ループは処理速度が極端に遅くなってしまうため避けるべきです．
    #. アルゴリズムやコードはできる限りベクトル化しましょう．なぜなら，NumpyとOpenCVはvectorの処理に対して性能を発揮するように最適化されているからです．
    #. キャッシュコヒーレンス(cache coherence)を利用する．データがメモリ/キャッシュ上でどのように配置されるか考えながら処理をする．
    #. 不必要な配列のコピーはせずに，データの参照を試す．配列のコピーは重い処理の一つです．
    
上記の点を全て意識したとしてもあなたの書いたコードの処理速度が遅い，もしくは大きなループの使用が避けられないのであれば，ループ処理を高速に行うCythonのようなライブラリの使用を検討したほうが良いでしょう．

補足資料
======================

1. `Pythonの最適化技術(英語) <http://wiki.python.org/moin/PythonSpeed/PerformanceTips>`_
2. Scipy講義資料(英語) - `Advanced Numpy <http://scipy-lectures.github.io/advanced/advanced_numpy/index.html#advanced-numpy>`_
3. `IPythonの時間計測，プロファイリング機能 <http://pynash.org/2013/03/06/timing-and-profiling.html>`_


課題
============