Poor performance of stl list on vs2015 while deleting nodes which contain iterator to self's position in list

Question

I am simply storing a list of nodes and each node contains an iterator pointing to its position in the list.Then I am benchmarking time taken to insert and delete nodes for std list and boost list.

Includes

#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 function to print average duration of insert or delete

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 list

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 list

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

Main

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

I am simply storing a list of nodes and each node contains an iterator pointing to its position in the list.

Output for above code is:

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

If node does not contain the "iterator" element then everything is normal and all outputs are roughly similar.Why in VS2015 implemetation of list is this problem occuring ??

Why are you also involving std::shared_ptr vs boost::shared_ptr? — LogicStuff
MSVC debug mode will check iterators, which explains why this unusual case is particularly slow. — MSalters

gsamaras gsamaras · Accepted Answer · 2016-07-29T22:39:53

When running code to test performance, always use optimization flags. I had the same issue with Why emplace_back is faster than push_back?, so you are not the first to face that.

On an IDE, for benchmarking , you have to use the Release mode, but still using the (always reliable) terminal and the optimization flags of g++ for example should come in mind.

Poor performance of stl list on vs2015 while deleting nodes which contain iterator to self's position in list

1 Answers