Schlechte Leistung der STL-Liste auf vs2015 beim Löschen von Knoten, die Iterator zu self-Position in der Liste enthalten

Question

Ich bin einfach speichern eine Liste von Knoten und jeder Knoten enthält einen Iterator auf seine Position in der Liste zeigt.Dann Benchmark-Zeit genommen Einfügen und Löschen von Knoten für die Standardliste und die Boostliste.

Inklusive

#include <iostream> 
#include <memory> 
#include <list> 
#include <chrono>  
#include "boost/container/list.hpp" 
#include "boost/shared_ptr.hpp" 
#include "boost/make_shared.hpp" 

#define ONE_BILLION    1000000000 
#define ONE_HUNDRED_MILLION  100000000 
#define TEN_MILLION    10000000 
#define ONE_MILLION    1000000 
#define ONE_HUNDRED_THOUSAND 100000 
#define TEN_THOUSAND   10000 

Helper Funktion durchschnittliche Dauer des Einsatzes drucken oder

void print_duration(std::ostream &out, const std::string& str, const std::chrono::high_resolution_clock::duration &d) 
{ 
    out << str << ": "; 

    if (d < std::chrono::microseconds(10)) 
     out << std::chrono::duration_cast<std::chrono::duration<float, std::nano>>(d).count() << " nano s"; 
    else if (d < std::chrono::milliseconds(10)) 
     out << std::chrono::duration_cast<std::chrono::duration<float, std::micro>>(d).count() << " micro s"; 
    else if (d < std::chrono::seconds(10)) 
     out << std::chrono::duration_cast<std::chrono::duration<float, std::milli>>(d).count() << " milli s"; 
    else if (d < std::chrono::minutes(10)) 
     out << std::chrono::duration_cast<std::chrono::duration<float>>(d).count() << " s"; 

    out << std::endl; 
} 

STL Liste

struct node 
{ 
    std::list<std::shared_ptr<node>>::iterator iter; 
}; 

void measure_list_insert_std(std::list<std::shared_ptr<node>>& l) 
{ 
    const size_t count = TEN_THOUSAND; 
    size_t i = 0; 



    auto begin = std::chrono::high_resolution_clock::now(); 
    for (; i < count; ++i) 
    { 
     std::shared_ptr<node> temp = std::make_shared<node>(); 
     l.push_back(temp); 
     temp->iter = --l.end(); 
    } 

    std::chrono::high_resolution_clock::duration total = std::chrono::high_resolution_clock::now() - begin; 
    print_duration(std::cout, "measure_list_insert_std ", total/i); 
} 

void measure_list_delete_std(std::list<std::shared_ptr<node>>& l) 
{ 
    const size_t count = TEN_THOUSAND; 
    size_t i = 0; 

    auto begin = std::chrono::high_resolution_clock::now(); 
    for (; i < count; ++i) 
    { 
     //std::list<std::shared_ptr<node>>::iterator it = (l.front())->iter; 
     l.erase((l.front())->iter); 
     //l.pop_back(); 
     //std::cout << l.size() << std::endl; 
    } 

    std::chrono::high_resolution_clock::duration total = std::chrono::high_resolution_clock::now() - begin; 
    print_duration(std::cout, "measure_list_delete_std ", total/i); 
    //std::cout << l.size() << std::endl; 
} 

Boost-Liste

löschen

Haupt

int main() 
{ 
    std::list < std::shared_ptr<node>> l; 

    measure_list_insert_std(l); 
    measure_list_delete_std(l); 

    boost::container::list<boost::shared_ptr<node_boost>> l2; 
    measure_list_insert_boost(l2); 
    measure_list_delete_boost(l2); 

    return 0; 
} 

Ich bin einfach eine Liste von Knoten zu speichern und jeder Knoten enthält einen Iterator auf seine Position in der Liste zeigt.

Ausgang für obigen Code ist:

measure_list_insert_std: 4830 Nano s

measure_list_delete_std: 431,624 micro s

measure_list_insert_boost: 4462 Nano s

measure_list_delete_boost: 4248 Nano s

Wenn der Knoten das Element "Iterator" nicht enthält, ist alles normal und alles Ausgaben sind in etwa ähnlich.Warum in VS2015 Implementation der Liste ist dieses Problem aufgetreten ??

Answer 1

Beim Ausführen von Code zum Testen der Leistung immer verwenden Sie Optimierungsflags. Ich hatte das gleiche Problem mit Why emplace_back is faster than push_back?, also sind Sie nicht die ersten, die das Gesicht haben.

Auf einer IDE, für Benchmarking, haben Sie die Release-Modus, aber immer noch die (immer zuverlässig) Terminal nutzen und die Optimierungsflags von g++ zum Beispiel in den Sinn kommen sollte.