Verwenden von Lambda anstelle eines Funktionsobjekts, schlechte Leistung

Question

Mein Problem ist ziemlich einfach, ich möchte Lambda's auf die gleiche Weise verwenden, ich kann einen Funktor als 'Komparator' verwenden, lassen Sie mich ein wenig besser erklären. Ich habe zwei große Strukturen, beide haben ihre eigene Implementierung von operator<, und ich habe auch eine useless Klasse (das ist nur der Name der Klasse im Kontext dieser Frage), die die zwei struct verwenden, sieht alles so aus:

struct be_less 
{ 
    //A lot of stuff 
    int val; 
    be_less(int p_v):val(p_v){} 
    bool operator<(const be_less& p_other) const 
    { 
     return val < p_other.val; 
    } 
}; 

struct be_more 
{ 
    //A lot of stuff 
    int val; 
    be_more(int p_v):val(p_v){} 
    bool operator<(const be_more& p_other) const 
    { 
     return val > p_other.val; 
    } 
}; 

class useless 
{ 
    priority_queue<be_less> less_q; 
    priority_queue<be_more> more_q; 
public: 
    useless(const vector<int>& p_data) 
    { 
     for(auto elem:p_data) 
     { 
      less_q.emplace(elem); 
      more_q.emplace(elem); 
     } 
    } 
}; 

Ich mag whould die Duplizierung in den beiden struct ist die einfachste Idee ist, machen die Struktur eine Vorlage aus und bieten zwei Funktors zu tun, um den Vergleich Job entfernen:

template<typename Comp> 
struct be_all 
{ 
    //Lot of stuff, better do not duplicate 
    int val; 
    be_all(int p_v):val{p_v}{} 
    bool operator<(const be_all<Comp>& p_other) const 
    { 
     return Comp()(val,p_other.val); 
    } 
}; 

class comp_less 
{ 
public: 
    bool operator()(int p_first, 
        int p_second) 
    { 
     return p_first < p_second; 
    } 
}; 

class comp_more 
{ 
public: 
    bool operator()(int p_first, 
        int p_second) 
    { 
     return p_first > p_second; 
    } 
}; 

typedef be_all<comp_less> all_less; 
typedef be_all<comp_more> all_more; 

class useless 
{ 
    priority_queue<all_less> less_q; 
    priority_queue<all_more> more_q; 
public: 
    useless(const vector<int>& p_data) 
    { 
     for(auto elem:p_data) 
     { 
      less_q.emplace(elem); 
      more_q.emplace(elem); 
     } 
    } 
}; 

diese Arbeit ziemlich gut jetzt habe ich keine doppelung im struct code zum preis von zwei zusätzlichen funktionsobjekten. Bitte beachten Sie, dass ich die Implementierung von operator< sehr vereinfacht habe, der hipotetische Real-Code viel mehr, als nur zwei Ints zu vergleichen.

Dann über i dachte, wie die gleiche Sache zu tun Lambda mit (nur als ein Experiment) .Der einzige funktionierende Lösung ich in der Lage war zu implementieren ist:

template<typename Comp> 
struct be_all 
{ 
    int val; 
    function<bool(int,int)> Comparator; 
    be_all(Comp p_comp,int p_v): 
     Comparator(move(p_comp)), 
     val{p_v} 
    {} 
    bool operator<(const be_all& p_other) const 
    { 
     return Comparator(val, p_other.val); 
    } 
}; 

auto be_less = [](int p_first, 
      int p_second) 
{ 
    return p_first < p_second; 
}; 

auto be_more = [](int p_first, 
      int p_second) 
{ 
    return p_first > p_second; 
}; 

typedef be_all<decltype(be_less)> all_less; 
typedef be_all<decltype(be_more)> all_more; 

class useless 
{ 
    priority_queue<all_less> less_q; 
    priority_queue<all_more> more_q; 
public: 
    useless(const vector<int>& p_data) 
    { 
     for(auto elem:p_data) 
     { 
      less_q.emplace(be_less,elem); 
      more_q.emplace(be_more,elem); 
     } 
    } 
}; 

Diese Implementierung nicht nur ein neues Mitglied hinzufügen zu den Daten, die struct enthalten, aber auch eine sehr schlechte Performance haben, habe ich einen kleinen Test vorbereitet, in dem ich eine Instanz für all die nutzlose Klasse erstelle, die ich euch hier zeige, jedes Mal wenn ich den Konstruktor mit einem Vektor voller 2 Millionen füttere Ganzzahlen, die Ergebnisse sind die folgenden:

1. dauert 48ms zu e Xecute den Konstruktor der ersten nutzlos Klasse
2. 228ms ist die zweite nutzlos Klasse (functor)
3. nimmt 557ms die dritte nutzlos Klasse (Lambda)

eindeutig den Preis i für den entfernten zahlen zu erstellen die Vervielfältigung ist sehr hoch, und im ursprünglichen Code ist die Vervielfältigung immer noch vorhanden. Bitte beachten Sie, wie schlecht ist die Leistung der dritten Implementierung, zehnmal langsamer als die ursprüngliche, ich glaubte, dass der Grund für die dritte Implementierung langsamer als die zweite war wegen der zusätzlichen Parameter im Konstruktor be_all ... aber:

Eigentlich gibt es auch einen vierten Fall, wo ich immer noch das Lambda verwendet, aber ich werde das Comparator Mitglied befreien und des zusätzlichen Parameters in be_all, ist der Code, die folgenden:

template<typename Comp> 
struct be_all 
{ 
    int val; 
    be_all(int p_v):val{p_v} 
    {} 
    bool operator<(const be_all& p_other) const 
    { 
     return Comp(val, p_other.val); 
    } 
}; 

bool be_less = [](int p_first, 
      int p_second) 
{ 
    return p_first < p_second; 
}; 

bool be_more = [](int p_first, 
      int p_second) 
{ 
    return p_first > p_second; 
}; 

typedef be_all<decltype(be_less)> all_less; 
typedef be_all<decltype(be_more)> all_more; 

class useless 
{ 
    priority_queue<all_less> less_q; 
    priority_queue<all_more> more_q; 
public: 
    useless(const vector<int>& p_data) 
    { 
     for(auto elem:p_data) 
     { 
      less_q.emplace(elem); 
      more_q.emplace(elem); 
     } 
    } 
}; 

Wenn ich entfernen auto aus dem Lambda und verwenden bool stattdessen den Code Build, auch wenn ichverwendein operator<.

Was mir sehr seltsam ist, dass diese vierte Implementierung (Lambda ohne Comparator Mitglied) ist sogar langsamer als die andere, am Ende der durchschnittliche Leistung ich in der Lage war zu registrieren ist die folgende:

1. 48ms
2. 228ms
3. 557ms
4. 698ms

Warum die Funktors sind in diesem Szenario so viel schneller als Lambdas? Ich hatte erwartet, dass Lambdas mindestens so gut abschneidet wie der normale Funktor, kann jemand von euch bitte kommentieren? Und gibt es irgendeinen technischen Grund, warum die vierte Implementierung langsamer ist als die dritte?

PS:

Die compilator ich benutze ist g ++ 4.8.2 mit O3. In meinem Test erstellen i für jede useless Klasse einer Instanz und mit chrono i aufgrund der erforderlichen Zeit in Anspruch nehmen:

namespace benchmark 
{ 
    template<typename T> 
    long run() 
    { 
     auto start=chrono::high_resolution_clock::now(); 
     T t(data::plenty_of_data); 
     auto stop=chrono::high_resolution_clock::now(); 
     return chrono::duration_cast<chrono::milliseconds>(stop-start).count(); 
    } 
} 

und:

cout<<"Bad code: "<<benchmark::run<bad_code::useless>()<<"ms\n"; 
cout<<"Bad code2: "<<benchmark::run<bad_code2::useless>()<<"ms\n"; 
cout<<"Bad code3: "<<benchmark::run<bad_code3::useless>()<<"ms\n"; 
cout<<"Bad code4: "<<benchmark::run<bad_code4::useless>()<<"ms\n"; 

Der Satz von Eingang ganzen Zahlen ist für alle gleich, plenty_of_data ist ein Vektor voller 2 Millionen Interger.

Vielen Dank für Ihre Zeit

Answer 1

Sie vergleichen nicht die Laufzeit eines Lambda und einem Funktor. Stattdessen zeigen die Zahlen den Unterschied bei der Verwendung eines Funktors und eines std::function an. Und std::function<R(Args...)>, zum Beispiel, kann jede Callable speichern, die die Signatur R(Args...) erfüllt. Dies geschieht durch Typ-Löschung. Der Unterschied, den Sie sehen, ergibt sich aus dem Overhead eines virtuellen Anrufs in std::function::operator(). Die libc++ Implementierung (3.5) hat beispielsweise eine Basisklasse template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes> __base mit einer virtual operator(). std::function speichert eine __base<...>*. Jedes Mal, wenn Sie eine std::function mit einer aufrufbaren F erstellen, wird ein Objekt vom Typ template<class F, class _Alloc, class R, class ...Args> class __func erstellt, das von __base<...> erbt und die virtuelle operator() überschreibt.