ちょっとプログラムが遅すぎるのでプロファイラを使った。
# https://stackoverflow.com/questions/30553417/how-to-find-hot-spot-in-a-c-or-c-program gcc test.cpp -pg -o test ./test gprof -b -A -p -q test gmon.out > prof.txt
遅かった理由
- その1: Eigen::SparseMatrixをNxN行列分reserveしており疎行列の意味をなしていなかった。
SpMat.reserve(Eigen::VectorXi::Constant(nrow, x))
で解決した。Eigenはデフォルトで列優先、xは各列あたりの要素数の予想より少し多い値を使う。→これだけでメモリ確保はホットスポットではなくなった。 - その2: 無頓着にハッシュマップ(
std::unordered_map
)に対してfind
やoperator[]
でのアクセスを繰り返していた。→find
してからoperator[]
を呼ぶのは止めたがそもそも標準ライブラリの実装はそれほど速くない模様。オーダーが異なるコンテナがあるわけではなさそう。(最速のハッシュテーブルを求めて - Qiita)