私はプロジェクトに取り組んでおり、実行時間の大幅な低下の原因を見つけようとしており、ロジックから最適化することができた単一のメソッドに絞り込みました。問題は、私の解決策には、コードの別のセクションの実行が非常に遅くなる参照の使用が含まれていることです...私が答えたい質問は、マップが参照である場合とは対照的に、内部ループの評価に時間がかかる理由ですローカル変数？
最適化前の古い方法は次のとおりです。
// old method: create an empty map, populate it
// and then assign it back to the path object later
map<int,float> screenline_usage;
for (int i=0; i<numCandidates; ++i)
{
// timing starts here.
map<int, float>& my_screenline_usage =
path->get_combined_screenline_usage(legnr, stop_id);
map<int, float>::iterator it = my_screenline_usage.begin();
for (; it != my_screenline_usage.end(); ++it)
screenline_usage[it->first] += usage * it->second;
// timing ends here, this block evaluated 4 million times for overall execution time of ~12 seconds
}
// This function call is evaluated 400k times for an overall execution time of ~126 seconds
path->set_zone_screenline_usage(access_mode, zone_id, screenline_usage);
// TOTAL EXECUTION TIME: 138 seconds.
最適化後の新しい方法:
// new method: get a reference to internal path mapping and populate it
map<int, float>& screenline_usage =
path->get_zone_screenline_usage(access_mode, zone_id);
screenline_usage.clear();
for (int i=0; i<numCandidates; ++i)
{
// timing starts here
map<int, float>& my_screenline_usage =
path->get_combined_screenline_usage(legnr, stop_id);
map<int, float>::iterator it = my_screenline_usage.begin();
for (; it != my_screenline_usage.end(); ++it)
screenline_usage[it->first] += usage * it->second;
// timing ends here, this block evaluated 4 million times for overall execution time of ~76 seconds
}
// New method... no need to assign back to path object (0 seconds execution :)
// TOTAL EXECUTION TIME: 76 seconds (62 second time saving) ... but should be able to do it in just 12 seconds if the use of reference didn't add so much time :(
そのコードから呼び出される関連するサブルーチンは次のとおりです。
// This is the really slow routine, due to the copy assignment used.
void set_zone_screenline_usage(int access_mode, int zone_id,
map<int,float>& screenline_usage)
{
m_container[access_mode][zone_id] = screenline_usage;
}
map<int,float>& get_zone_screenline_usage(int access_mode, int zone_id)
{
return m_container[access_mode][zone_id];
}
注: タイミング情報は、上記のコードが約 40 万回評価される 1 回の実行に関するものです。タイミングは、RDTSC タイム スタンプ カウンターにアクセスするために作成したいくつかのクラスを使用して行われます (はい、TSC はタイム スタンプ カウンターを意味します)。numCandidates の平均値は 10 で、screenline_usage マップに配置される要素の平均数は 25 です。
更新: まず、ここに関わってくれたすべての人に感謝します。最終的に、これは c++ 参照とはまったく関係がなく、キャッシュの一貫性に関係していると思います。上記の最適化されたコードを vector& とメンバー変数マップとして実装されたハッシュ関数に置き換えました
// newest method: get a reference to internal path mapping (as vector) and populate it
// map<int,int> m_linkNum_to_SlNum declared in header and populated in constructor.
vector<float>& screenline_usage = path->get_zone_screenline_usage(access_mode, zone_id);
for (int i=0; i<numCandidates; ++i)
{
// timing starts here
map<int, float>& my_screenline_usage =
path->get_combined_screenline_usage(legnr, stop_id);
map<int, float>::iterator it = my_screenline_usage.begin();
for (; it != my_screenline_usage.end(); ++it)
screenline_usage[m_linkNum_to_SlNum[it->first]] += usage * it->second;
// timing ends here, this block evaluated 4 million times for overall execution time of ~9 seconds
}
// Newest method... again no need to assign back to path object (0 seconds execution :)
// TOTAL EXECUTION TIME: just 9 seconds (129 second time saving) ... this is even better than using a locally constructed map which took 12 seconds in the inner loop :)
ここでは、ベクトルがローカルではなく連続したメモリ ブロックであり、ハッシュ関数 (m_linkNum_to_SlNum) がローカル メンバー変数であることを考えると、このアプローチはキャッシュに収まるコード/データにつながるように思えます。データを得るためにメイン メモリにアクセスする必要がないため、速度が大幅に向上します。これらの調査結果を踏まえた他の結論は大歓迎です。