vs2015上的stl列表性能不佳,同时删除包含迭代器到列表中自身位置的节点

Question

我只是存储一个节点列表,每个节点都包含一个指向它在列表中的位置的迭代器.然后我对插入和删除std列表和提升列表的节点进行基准测试.

包括

#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

帮助函数打印插入或删除的平均持续时间

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清单

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

提升清单

struct node_boost
{
    boost::container::list<boost::shared_ptr<node_boost>>::iterator iter;
};

void measure_list_insert_boost(boost::container::list<boost::shared_ptr<node_boost>>& l)
{
    const size_t count = ONE_MILLION;
    size_t i = 0;



    auto begin = std::chrono::high_resolution_clock::now();
    for (; i < count; ++i)
    {
        boost::shared_ptr<node_boost> temp = boost::make_shared<node_boost>();
        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_boost  ", total / i);
}

void measure_list_delete_boost(boost::container::list<boost::shared_ptr<node_boost>>& l)
{
    const size_t count = ONE_MILLION;
    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_boost  ", total / i);
    //std::cout << l.size() << std::endl;
}

主要

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

我只是存储一个节点列表,每个节点都包含一个指向它在列表中的位置的迭代器.

上述代码的输出是:

measure_list_insert_std:4830纳米

measure_list_delete_std:431.624微秒

measure_list_insert_boost:4462纳米

measure_list_delete_boost:4248纳秒

如果node不包含"iterator"元素,那么一切正常,所有输出大致相似.为什么在VS2015列表实现中出现这个问题？

Answer 1

运行代码以测试性能时,请始终使用优化标志.我有同样的问题,为什么emplace_back比push_back更快？,所以你不是第一个面对这一点.

在IDE上,对于基准测试,您必须使用Release模式,但仍然使用(总是可靠的)终端,并且应该记住g ++的优化标志.