master mind by c++; part8 profiling( valgrind, gdb )

今回やること

• プログラムの実行速度計測の追加
• プログラムのプロファイリング( valgrind & gdb )

実行速度計測について

プログラムの今後の最適化のために, 実行速度のプロファイルを取りたいと思います. そこで, どういった実行速度を測るか? ですが, コード一覧(S)から秘密コードを1つ選択し, その秘密コードについて

1. 探索回数が何回必要だったか
2. 計算時間をどれほど要したか

を, 全てのコード一覧に対して計測し, その統計情報を出力することにします.

計測コード

int main(
      int argc,
      char *argv[]
      )
{
   Config config = getConfig(argc, argv);
   std::cout << config.str() << std::endl;

   if ( config.interactive )
   {
      runInteractive(config);
   }
   else
   {
      runTest(config);  // 計測テスト用
   }

   return 0;
}

/**
 * @fn void runInteractive(Config &config)
 * @brief 全てのsecret codeに対する計測
 * @param[in] config
 */
void runTest(
      Config &config
      )
{
   CodeList S;
   allCodeGenerator(config, S);

   std::vector<int> countTable(S.size());
   std::vector<double> timeTable(S.size());

   int i = 0;
   for ( auto secret : S )
   {
      // test code
      config.setSecret(secret);  // 秘密コードを設定
      CodeList testS = S;

      int count = 0;

      auto start = std::chrono::system_clock::now(); // 計測開始時間
      while( testS.size() > 1 )
      {
         count++;
         auto guess = policy(testS, testS);  // G <- S
         trial(testS, guess, config);        // update S
      }
      auto end = std::chrono::system_clock::now();  // 計測終了時間

      assert( testS[0] == secret );
      double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(
            end-start).count();  //処理に要した時間をミリ秒に変換
      countTable[i] = count;
      timeTable[i] = elapsed;
      i++;
   }

   // output statistics
   auto getMax = [&](auto &v){ return *std::max_element(v.cbegin(), v.cend()); };
   auto getSum = [&](auto &v){ return std::accumulate(v.cbegin(), v.cend(), 0.0); };
   auto getAve = [&](auto &v){ return getSum(v) / v.size(); };
   int maxCount         = getMax(countTable);
   double averageCount  = getAve(countTable);
   double totalTime     = getSum(timeTable);
   double averageTime   = getAve(timeTable);
   std::cout
      << "Log,num colors,num pins,max count,average count,total time,average time"
      << std::endl;
   std::cout
      << "log"
      << "," << config.nColors   << "," << config.nPins
      << "," << maxCount         << "," << averageCount
      << "," << totalTime        << "," << averageTime
      << std::endl;
}

mainの処理を時間計測で挟みます. 速度の計測は#include <chrono>で行っています.

高速化オプションの追加

ということで, 早速簡単にできるコンパイル時の高速化オプションで実行時間を測ってみます.

• 高速化オプションなし

target_compile_options(
  mastermind PUBLIC
  -Wall
  )

• -O3 あり

target_compile_options(
  mastermind PUBLIC
  -Wall
  -O3
  )

nColors	nPins	duplicate	total time [msec] -O3なし	total time [msec] -O3あり
5	4	true	457	0
6	4	true	2539	2
7	4	true	9872	1138
6	5	true	105397	21444

-O3をつけるだけでかなり早くなりましたね.

プロファイル

Valgrind

せっかくなので, Dockerで構築した仮想環境上でvalgrindを使ってプロファイルを取ります. (Dockerについて master mind by c++; part5 Docker - サブロウ丸 )
(macだとvalgrindのinstallに失敗したため)

$ docker run -v $(pwd):/mnt -it master_mind

でコンテナイメージを起動します. -v オプションはマウントに関する設定で, このオプションによりDocker上とローカルでのファイルの受け渡しが簡単にできるようになります. 実際/mntに行くと $(pwd) 現在のディレクトリが見れるようになっているはずです.
マウントする理由としては図を作成して確認する作業はDocker外でやった方がやりやすいため, 図のデータ集めはDockerでやって, それ以外はローカルでやるという感じですね.

target_compile_options(
  mastermind PUBLIC
  -Wall
  # -O3
  -g
  )

コンパイルオプションに -g を追加しておきます.

$ valgrind --tool=callgrind --callgrind-out-file=./callgrind.out ./bin/mastermind 4 4 --test

でコールグラフデータ./callgrind.outを取得して,

$ cp callgrind.out /mnt/

で/mnt/以下におきます. すると $(pwd) にcallgrind.outが追加されていることが確認できます.

あとは, pip install gprof2dot で必要なものをinstallした後で

$ gprof2dot -f callgrind ./callgrind.out | dot -Tpdf -o report.pdf

でコールグラフの可視化を確認できます.

こんな感じの. やたらアイテムの横幅が大きいです. -s オプションをつけると 関数とテンプレート引数の情報が取り除かれてスッキリします.

$ gprof2dot -f callgrind ./callgrind.out -s | dot -Tpdf -o report.pdf

これらを用いて, 計算時間が多くかかっているボトルネックを特定して, その箇所から優先的に対処していきます.
対処方法は, 実装を見直す( ポインタを効率的に導入する ) や 処理自体のアルゴリズムを変える, 並列化などで高速化を図るなどでしょうか.

gprof

gprofはプロファイリング用のツールです. (参考: gprofを使いこなす - minus9d's diary) gprofを使うためには, コンパイル時に-pgオプションをつける必要があります.

target_compile_optionsとtarget_link_optionsにそれぞれ -pgオプションを追加します ( ついでに-gオプションもつけています).

src/CMakeLists.txt

add_executable(
  mastermind
  main.cpp
  )

target_include_directories(
  mastermind PUBLIC
  ${PROJECT_SOURCE_DIR}/source/argparse/include
  )

target_compile_options(
  mastermind PUBLIC
  -Wall
  # -O3
  -pg -g  # 追加!!
  )

target_compile_features(
  mastermind PUBLIC
  cxx_std_17
  )

target_link_options( # 追加!!
  mastermind PUBLIC
  -pg -g
  )

上記のCMakeLists.txtでコンパイル(cmake)を行った後

$ ./bin/mastermind 4 4 --test

のように, バイリナを実行すると, gmon.out というファイルが生成されているので

$ gprof ./bin/mastermind gmon.out

でプロファイル結果が表示されます.

Cmake, Debug, Release

ところで, いちいちファイルを書き換えてコンパイル時のオプションを変更するのは面倒ですね. Cmakeでは大きくDebug, Release, MinSizeRel(最小サイズリリース), RelWithDebInfo(デバッグ情報を加えたリリース) によってコンパイル時のオプションを管理できるので, それを使ってみます. ( 参考: CMakeの使い方（その２） #C++ - Qiita )

コンパル時は cmake .. -DCMAKE_BUILD_TYPE=Debug のように指定します.
下記の場合は, Releaseのときは -O3, Debugのときは-O0 -g -pgがコンパイルオプションとして追加されます.

src/CmakeLists.txt

add_executable(
  mastermind
  main.cpp
  )

target_include_directories(
  mastermind PUBLIC
  ${PROJECT_SOURCE_DIR}/source/argparse/include
  )

target_compile_options(
  mastermind PUBLIC
  -Wall
  $<$<CONFIG:Release>:-O3>  # 追加!!
  $<$<CONFIG:Debug>:-O0 -g -pg> # 追加!!
  )

target_compile_features(
  mastermind PUBLIC
  cxx_std_17
  )

target_link_options(
  mastermind PUBLIC
  $<$<CONFIG:Debug>:-O0 -g -pg> # 追加!!
)

ちなみに $<<condition>:<value>>の形の文法はGenerator Expressionsというもので, if文の役割を果たすものです. (参考: CMake: Generator Expressions #AdventCalendar - Qiita )

しかし, CMAKE_BUILD_TYPEのデフォルトは空白になっていました. ( Releaseかと思ってた; 環境によって違うのかも? ) デフォルト値を設定したい場合は下記をルートの./CMakeLists.txtに加えます.

cmake_minimum_required(VERSION 3.1)
project(MasterMind CXX)

# setting of CMAKE_BUILD_TYPE
if(NOT CMAKE_BUILD_TYPE)
  set(CMAKE_BUILD_TYPE "Release")
endif(NOT CMAKE_BUILD_TYPE)
message("Generated with build types: ${CMAKE_BUILD_TYPE}")

# setting of CMAKE_RUNTIME_OUTPUT_DIRECTORY
if(NOT CMAKE_RUNTIME_OUTPUT_DIRECTORY )
  set(CMAKE_RUNTIME_OUTPUT_DIRECTORY ${PROJECT_SOURCE_DIR}/bin)
endif(NOT CMAKE_RUNTIME_OUTPUT_DIRECTORY)
message("Binaries will be generaed in: ${CMAKE_RUNTIME_OUTPUT_DIRECTORY}")

add_subdirectory(src)
add_subdirectory(test)

実行時に, メッセージが表示されます.

-- The CXX compiler identification is AppleClang 12.0.5.12050022
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /Library/Developer/CommandLineTools/usr/bin/c++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
Generated with build types: Release     # ここ
Binaries will be generaed in: /xxx/master_mind_cpp/bin　　# ここ
-- Configuring done
-- Generating done
-- Build files have been written to: /xxx/master_mind_cpp/build

まとめ

• プログラム内に計測用コードを挿入して, 最適化オプションの有無による測定を行いました.
• valgrind, gprof2dotを用いてコールグラフを作成しました.
• gprofが使用できるようにcmakeを書き換えました
• cmakeにCMAKE_BUILD_TYPEを導入しました.

コード

• 作業前コード, 作業前タグ
• 作業後コード, 作業後タグ
• 差分

参考

• C++でフリープラットフォームな時間計測 #C++ - Qiita
• プロファイラの比較（＋簡単な使い方） #C - Qiita
• https://githubja.com/jrfonseca/gprof2dot
• gprofを使いこなす - minus9d's diary
• CMakeの使い方（その２） #C++ - Qiita
• https://musicscience37.gitlab.io/til/development/cmake/output_directories_in_build.html
• CMake: Generator Expressions #AdventCalendar - Qiita

他の記事

• 次の記事
• 前の記事
• 一覧 mastermind カテゴリーの記事一覧 - サブロウ丸