1行のコードがあり、アプリケーションの実行時間の25％〜30％を消費します。これは、std :: setのコンパレータよりも小さいです（セットは赤黒木で実装されます）。28秒以内に約1億8000万回呼び出されます。
struct Entry {
const float _cost;
const long _id;
// some other vars
Entry(float cost, float id) : _cost(cost), _id(id) {
}
};
template<class T>
struct lt_entry: public binary_function <T, T, bool>
{
bool operator()(const T &l, const T &r) const
{
// Most readable shape
if(l._cost != r._cost) {
return r._cost < l._cost;
} else {
return l._id < r._id;
}
}
};
エントリはコストで並べ替える必要があり、コストがIDで同じかどうかを確認します。最小値の抽出ごとに多くの挿入があります。フィボナッチヒープの使用を考えましたが、理論的には優れていると言われていますが、定数が高く、実装がかなり複雑です。また、挿入はO（log（n））にあるため、nが大きい場合、実行時の増加はほぼ一定です。だから、セットにこだわっても大丈夫だと思います。
パフォーマンスを向上させるために、さまざまな形で表現しようとしました。
return l._cost < r._cost || r._cost > l._cost || l._id < r._id;
return l._cost < r._cost || (l._cost == r._cost && l._id < r._id);
これでも：
typedef union {
float _f;
int _i;
} flint;
//...
flint diff;
diff._f = (l._cost - r._cost);
return (diff._i && diff._i >> 31) || l._id < r._id;
しかし、私はランタイムを改善することができなかったので、コンパイラーはすでに十分に賢いようです。
私もSSEについて考えましたが、この問題は実際にはSSEにはあまり当てはまりません...
アセンブリは次のようになります。
movss (%rbx),%xmm1
mov $0x1,%r8d
movss 0x20(%rdx),%xmm0
ucomiss %xmm1,%xmm0
ja 0x410600 <_ZNSt8_Rb_tree[..]+96>
ucomiss %xmm0,%xmm1
jp 0x4105fd <_ZNSt8_Rb_[..]_+93>
jne 0x4105fd <_ZNSt8_Rb_[..]_+93>
mov 0x28(%rdx),%rax
cmp %rax,0x8(%rbx)
jb 0x410600 <_ZNSt8_Rb_[..]_+96>
xor %r8d,%r8d
私はアセンブリ言語についてほんの少しの経験がありますが、それほど多くはありません。
パフォーマンスを絞り出すのが（唯一？）最良のポイントだと思いましたが、本当に努力する価値はありますか？いくつかのサイクルを節約できるショートカットを見つけることができますか？
コードが実行されるプラットフォームは、メニーコアIntelマシン上のgcc 4.6（-stl = c ++ 0x）を備えたubuntu12です。使用可能なライブラリは、boost、openmp、およびtbbのみです。30秒のベンチマークは、4年前のラップトップ（コア2デュオ）で実行されました。
私は本当にこれに固執しています、それはとても単純に見えますが、それだけの時間がかかります。どうすればこのラインを改善できるかを考えて何日も頭を悩ませてきました...
この部分を改善する方法を教えていただけますか、それともすでに最高の状態ですか？
編集1：ジェリーズの提案を使用した後、私は約4.5秒のスピードアップを達成しました。編集2：ブーストフィボナッチヒープを試した後、比較は未満関数への174Mio呼び出しに行きました。