2014年1月3日金曜日

OpenCV2: cv::MatConstIterator::operator++()さんが笑えない遅さなのでreinterpret_castします

OpenCV2でcv::Matに画像をロードして、そのすべての要素を走査したいって、よくあるニーズだと思います。

仮に、640×480×CV_U8C3のcv::Matとしてimageがあるとしましょう。その全てのピクセル要素を順に走査して何か処理を行う必要があるとします。すると、

[コード例1: OpenCV2曰く高速な要素アクセス方法(OpenCV2のcv::MatIterator_)]

auto i = image.begin<cv::Point3_<uint8_t>>();
const auto e = image.end<cv::Point3_<uint8_t>>();
while(i != e)
{
  (*i).x = 255;
  ++i;
}

とかなるわけです。iなどに取得されているイテレーターはOpenCV2のcv::MatIterator_テンプレート型で、これはOpenCV2曰く「高速な要素アクセス」なのだそうです。


ところが、実際にこれを「高速な要素アクセス」だって信じて使ってみてさしあげると笑えないのです。激おそぷんぷんドリームです。

どのくらい遅いのかは比較対象を挙げてから語る事にします。

[コード例2: reinterpret_cast<cv::Point3_<uint8_t>*>(image.data)]

auto p = reinterpret_cast<cv::Point3_<uint8_t>*>(image.data);
const auto e = p + image.cols * image.rows;
while(p < e)
{
  p->x = 255;
  ++p;
}

はい、まったくユーザーにとっては同じ事を、ポインターで書いてみました。

[比較: コード例1 vs. コード例2]


286フレームの短いビデオのフレーム全てについて、上記のコード例1とコード例2の部分コードの処理時間を計測、算術平均と標準偏差を計算してみました。
  • clang++-3.2 -O0
    • result 1: ave=5081.24[us], stdev=2582.33[us]
    • result 2: ave=1083.91[us], stdev=814.675[us]
  • clang++-3.2 -O3 -march=native
    • result 1: ave=2255.26[us], stdev=663.584[us]
    • result 2: ave=277.688[us], stdev=178.963[us]
  • g++-4.8.1 -O0
    • result 1: ave=7704.684[us], stdev=3778.59[us]
    • result 2: ave=834.556[us], stdev=676.846[us]
  • g++-4.8.1 -O3 -march=native
    • result 1: ave=1707.22[us], stdev=880.224[us]
    • result 2: ave=151.472[us], stdev=111.854[us]

CPU: Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz
MEM: 16GB DDR3
OS: Linux Mint 16 KDE

こんな具合でした。cv::MatConstIterator::operator++()さん遅すぎです。

リアルタイム処理や低性能なマシンでの実行を考える場合は、ユーザーコードでreinterpret_castしてデータアクセスする事まで考えないとOpenCV2は使い物にならないかも。

通常、イテレーターによるアクセスが重大なオーバーヘッドを伴ってくれてユーザーコードでreinterpret_castでポインターを直接触るなんてまともなC++のライブラリーではありえない事なんだけど、これはとても罠な感じです。

蛇足として、OpenCV2のcv::Matのbegin/endの設計ではrange-based-forにも使えませんし、今回のcv::MatIterator_もオーバーヘッドの事もそうですし、operator->()が無いなど、C++のstdライブラリーを参考にしている様で実はまったくそんな事は無いだなんて、OpenCVのcv::Mat周りには罠がたくさんありすぎです。

[追記1: data領域の連続性について]

通常は画像を扱うcv::Matでは連続していると前提を置いても問題無いでしょう。
あ、寝る前に一言付け加えておこうかな。cv::Matのdataは連続しているとは限らないとか言われるかもしんないけど、std::list<cv::Point3_<uint8_t>>を同様にイテレーター走査を書くのと同じくらい遅いんじゃないかな。std::listは完全に双方向連結リストでポインターによって接続された完全に不連続な領域の要素群、cv::Matは連続領域に確保された一部不連続かもしれない要素群だから、つまりだからOpenCV2のデータ構造と要素アクセスって設計・実装したのどこの誰っていうレベルじゃないかしら、となるわけ。
[追記2: おまけ、std::listとか併せて実験用そーすぜんぶ]

で、起きてから実際にstd::list<cv::Point3_<uint8_t>>で同様の評価も書いてみました。ついでにstd::forward_list(これはメモリー消費的に若干有利なだけのlistです)、std::vectorも併せてベンチマーク用にソースをちょっと綺麗にまとめてみました。
これで測った結果はこちら↓
[追記3: コメントでのご指摘「OpenCVがリリースビルドになっていないのでは?」について]

どうやらそんな事はありませんで、ご指摘は間違いのようです。

この環境では、

/usr/share/OpenCV/OpenCVConfig.cmake

にcmakeのfind_package用の定義ファイルがあります。

このcmakeの定義ファイルの中身を確認してみると、CMAKE_BUILD_TYPE変数がDebugにマッチした場合にはOpenCV_LIBS変数にOpenCV_LIBS_DBG変数とOpenCV_EXTRA_LIBS_DBG変数がセットされ、それ以外の場合にはOpenCV_LIBS変数にはOpenCV_LIBS_OPT変数とOpenCV_EXTRA_LIBS_OPT変数がセットされます。

ご指摘への対応その1として、念の為、CMakeLists.txtにて直接、target_link_librariesに${OpenCV_LIBS_OPT}を定義した上でビルドして確認してみましたが、結果は変わりません。

また、対応その2として、


を参考にgithubから入手した現在最新のHEAD( 1c3bfae2121f689535ab1a17284f40f5d64e0927 )を用いソースコードから-O3最適化付きでリリースビルドし、ソースのincludeファイル群及びビルドした最新のlibファイル群を用いて、評価用のcv-osoiプロジェクトを最適化ビルドし、間違いの無いようにLD_LIBRARY_PATHにて明示的にリンクライブラリーも指示して実行てみましたが、結果はまったく変わりません。

ちなみに、記事本文ではOpenCV-2.4を用いていましたが、最新版HEADでは開発版のOpenCV-3.0として、OpenCV-2.4では不満を覚える部分が多かったC++対応のいい加減さについても、少しは改善している様です。

例えば、CV_CAP_PROP_FRAME_COUNTは基本的には未定義となり、cv::CAP_PROP_FRAME_COUTが使用可能になっていたり、など。

・・・蛇足となりますが、opencvのリポジトリーはduを見るに592MBもあり入手にも時間がかかります。このビルドはcmakeに対応しているので難しい事はありませんが、全部で1072個のビルドタスクが必要で高性能な計算機でもそれなりに時間もかかりました。

ご意見を頂ける事は大変嬉しいのですが、できれば少しでも検証されてからご指摘を頂けると助かります。ご指摘ありがとうございました。

5 件のコメント:

  1. OpenCVがリリースビルドになっていないのでは?

    返信削除
  2. OpenCV の要素イテレータ、確かに遅いですよね。
    個人的に依然計測した単純な例では、1桁以上の差があることもあり、
    愕然とした記憶があります。

    http://evemedia.org/tetra/2012/10/21/opencv_pixel_access2


    >通常は画像を扱うcv::Matでは連続していると前提を置いても問題無いでしょう。

    cv::Mat::clone でコピーしておくと安全だった気がします。

    これの対応のために iterator のインクリメントにかなり冗長な処理(分岐含む)が入っているので(…にしても遅すぎる気がしないでもないですが、)どこの誰っていうレベルではないかと。

    あと、この場合、std::list のデフォルトアロケーターは連続したメモリを確保した上で、L2 or L3 キャッシュ上に存在しているはずですので、
    リンクリストとはいえそれほどパフォーマンスは悪くないはずです。

    でも遅すぎますね。OpenCV。


    全要素をイテレートする必要がある場合、cv::Mat::isContinus が true であればそのまま、
    false であれば、 cv::Mat::clone() でコピー(と同時にメモリ配置が連続化される)した上で、上記の例のようなポインタアクセスする方法が最速と思われます。


    重箱の隅ですが、ここまでループがタイトだと、主記憶へアクセスする際のレイテンシが馬鹿にならないようです。
    手元の環境では、cv_iterator と native_pointer について評価する順番を変更し、
    先に native_pointer を評価したところ、
    cv_iterator の評価値が 1500μs 程度 → 1300μs 程度になりました。

    frames に入っている全データの合計が L3 キャッシュサイズを超えると影響がありそうです。
    参考まで。

    しかし、遅いですね……
    イテレータ使うだけでフレームレート 1kHz 以下が確定とは……

    返信削除
  3. ええ、今回は省略していますが、実用上はclone/isContinuousを入れるべきですね(*´ω`*)

    std::listがキャッシュに乗っているであろう点もそうですね。ただ、そこは本件の記事の本質ではないので、今回は気にしないことにさせて下さい。

    また、L3キャッシュ周りのご指摘についてもありがとうございます。

    実際にはビデオファイルから読み込む事よりも、カメラからのキャプチャーによるリアルタイム処理でOpenCVを使う事が多いと思います。今回のサンプルの様な無茶なframesへの読み込み部分は完全な手抜きで、実用上はバッファーを確保する際も数十フレームから、せいぜい数秒分のバッファーを扱う事が多く、今回の手抜きコードではご指摘の通りL3キャッシュ周りで実用上とは誤差が生じてしまいますね。

    OpenCV3に少しだけ期待する事にします。少しだけ。

    返信削除
  4. すみません、
    > 蛇足として、OpenCV2のcv::Matのbegin/endの設計ではrange-based-forにも使えませんし
    について補足です。


    cv::Mat はピクセルの型を動的な値として持っているため(内部で型推論 + コンパイル時型決定されている訳ではない)ので、静的型付けの C++ 上でコードを書く際にはどうしても begin/end に型を教えてやる必要があります。

    at / ptr も同様です。

    OpenCV は型が決定している場合のクラスとして、
    cv::Mat_<_Tp> クラスが用意されており、 このクラスに対して begin/end を呼び出すと、
    cv::Mat::begin<_Tp> / cv::Mat::end<_Tp> が呼び出されます。
    テンプレート引数が不要なので、 range-based-for も利用可能です。

    この例で言うと、

    for (auto &p : cv::Mat_>(frame)) {
    p.x = 255;
    }

    で range-based-for ループが使えるようになります。
    極端なパフォーマンス劣化を抑えた上で、
    型を : の左側に書けるようにすることは、
    現在の C++ の仕様の範囲内ではほぼ不可能です。

    返信削除
  5. へー、v::Mat_<_Tp>なんてあったんですねー。まったく存在に気付けていませんでした!
    教えていただいてありがとうございます(*´ω`*)

    返信削除