Ich habe eine einzige Codezeile, die 25% - 30% der Laufzeit meiner Anwendung beansprucht. Es ist ein Kleiner-als-Komparator für ein std :: set (das set wird mit einem Rot-Schwarz-Baum implementiert). Es wird ungefähr 180 Millionen Mal innerhalb von 28 Sekunden aufgerufen.

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;
        }
    }
};

Die Einträge sollten nach Kosten sortiert sein und, wenn die Kosten gleich sind, nach ihrer ID. Ich habe viele Einfügungen für jede Extraktion des Minimums. Ich habe überlegt, Fibonacci-Heaps zu verwenden, aber mir wurde gesagt, dass sie theoretisch nett sind, aber unter hohen Konstanten leiden und ziemlich kompliziert zu implementieren sind. Und da sich insert in O (log (n)) befindet, ist die Laufzeiterhöhung mit großem n nahezu konstant. Ich denke es ist in Ordnung, am Set festzuhalten.

Um die Leistung zu verbessern, habe ich versucht, es in verschiedenen Formen auszudrücken:

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);

Sogar das:

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;

Aber der Compiler scheint schon schlau genug zu sein, weil ich die Laufzeit nicht verbessern konnte.

Ich habe auch über SSE nachgedacht, aber dieses Problem ist für SSE wirklich nicht sehr zutreffend ...

Die Montage sieht ungefähr so ​​aus:

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

Ich habe ein sehr kleines bisschen Erfahrung mit Assemblersprache, aber nicht wirklich viel.

Ich dachte, es wäre der beste (einzige?) Punkt, um etwas Leistung herauszuholen, aber ist es die Mühe wirklich wert? Können Sie Verknüpfungen sehen, die einige Zyklen sparen könnten?

Die Plattform, auf der der Code ausgeführt wird, ist ein Ubuntu 12 mit gcc 4.6 (-stl = c ++ 0x) auf einem Intel-Computer mit vielen Kernen. Es sind nur die Bibliotheken boost, openmp und tbb verfügbar. Der 30-Sekunden-Benchmark wurde mit meinem 4 Jahre alten Laptop (Core 2 Duo) durchgeführt.

Ich stecke wirklich in dieser Sache fest, sie scheint so einfach zu sein, nimmt aber so viel Zeit in Anspruch. Seit Tagen zerbreche ich meinen Kopf und denke darüber nach, wie ich diese Linie verbessern könnte ...

Können Sie mir einen Vorschlag machen, wie Sie diesen Teil verbessern können, oder ist er bereits von seiner besten Seite?

EDIT 1: Nachdem ich Jerrys Vorschlag verwendet hatte, erreichte ich eine Geschwindigkeit von ~ 4,5 Sekunden. EDIT 2: Nach dem Versuch, Fibonacci-Haufen zu steigern, ging der Vergleich auf 174 Mio Aufrufe der Funktion less than über.