How slow is boost::shared_ptr?

Hi,

i wrote a little single linked list test program to play with boost::shared_ptr which is new to me.

at first i implemented it just with plain c pointers and it worked as expected. then i exchanged them against boost::shared_ptr and it really slows down for operations on long lists. also the test program segfaulted in the middle of the calls to Element::~Element() after leaving scope of main, but only for longer lists (<99999) elements or so.

do i have some overlooked bug or is boost::shared_ptr just slow and or broken? I tested on gcc version 4.1.1 / boost 1.33.1-r1 / linux 2.6.19.

Code:

---

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <boost/shared_ptr.hpp>


using namespace std;
using namespace boost;


class Element
{
        shared_ptr<Element> mp_next;
        int        m_value;
public:
        ~Element()
        {
                printf("Element dtor\n");
        }
        Element(int i)
        {
                mp_next.reset();
                m_value = i;
        }
        shared_ptr<Element> next()
        {
                return mp_next;
        }
        void setNext(shared_ptr<Element> e)
        {
                mp_next = e;
        }
        int value()
        {
                return m_value;
        }
};

class List
{
        shared_ptr<Element> mp_start;
        shared_ptr<Element> mp_end;
public:
        ~List()
        {
                printf("List dtor\n");
        }
        List()
        {
                mp_start.reset();
                mp_end.reset();
        }
        void pushBack(int i)
        {
                shared_ptr<Element> ele(new Element(i));
                if(!mp_start)
                {
                        mp_start = ele;
                        mp_end = ele;
                        return;
                }
                mp_end->setNext(ele);
                mp_end = ele;
        }
        string print()
        {
                stringstream ss;
                ss << "from: ";
                (mp_start?ss<<mp_start->value():ss<<"NIL");
                ss << " to: ";
                (mp_end?ss<<mp_end->value():ss<<"NIL");
                ss<< endl;
                return ss.str();               
        }
        void reverse()
        {
                if(!mp_start || !mp_start->next()) return;
                mp_end = mp_start;
                shared_ptr<Element> pred;
                shared_ptr<Element> one (mp_start);
                shared_ptr<Element> two (mp_start);
                do
                {
                        two = two->next();
                        one->setNext(pred);
                        pred = one;
                        one = two;
                       
                }while(two->next());
                two->setNext(pred);
                mp_start = two;
        }
};

int main(void)
{
        shared_ptr<List> list(new List);
        for(long long i=0; i<99999; ++i)
        {
                list->pushBack(i);
        }
        cout << "list: " << list->print() << endl;
        list->reverse();
        cout << "reversed list: " << list->print() << endl;

}

---

gprof output:

Code:

---

Flat profile:

Each sample counts as 0.01 seconds.
  %  cumulative  self              self    total         
 time  seconds  seconds    calls  ms/call  ms/call  name   
 50.00      0.01    0.01  119986    0.00    0.00  boost::detail::atomic_exchange_and_add(int*, int)
 25.00      0.01    0.01  109986    0.00    0.00  boost::detail::sp_counted_base::release()
 25.00      0.02    0.01    10000    0.00    0.00  boost::detail::sp_counted_base::weak_release()
  0.00      0.02    0.00    99986    0.00    0.00  boost::detail::sp_counted_base::add_ref_copy()
  0.00      0.02    0.00    99986    0.00    0.00  boost::detail::atomic_increment(int*)
  0.00      0.02    0.00    69999    0.00    0.00  boost::detail::shared_count::~shared_count()
  0.00      0.02    0.00    69998    0.00    0.00  boost::shared_ptr<Element>::~shared_ptr()
  0.00      0.02    0.00    59993    0.00    0.00  boost::shared_ptr<Element>::operator=(boost::shared_ptr<Element> const&)
  0.00      0.02    0.00    59993    0.00    0.00  boost::detail::shared_count::operator=(boost::detail::shared_count const&)
  0.00      0.02    0.00    39998    0.00    0.00  boost::shared_ptr<Element>::operator->() const
  0.00      0.02    0.00    39996    0.00    0.00  boost::shared_ptr<Element>::shared_ptr(boost::shared_ptr<Element> const&)
  0.00      0.02    0.00    39996    0.00    0.00  boost::detail::shared_count::shared_count(boost::detail::shared_count const&)
  0.00      0.02    0.00    20003    0.00    0.00  boost::shared_ptr<Element>::shared_ptr()
  0.00      0.02    0.00    20003    0.00    0.00  boost::detail::shared_count::shared_count()
  0.00      0.02    0.00    19997    0.00    0.00  Element::next()
  0.00      0.02    0.00    19997    0.00    0.00  Element::setNext(boost::shared_ptr<Element>)
  0.00      0.02    0.00    10002    0.00    0.00  boost::shared_ptr<List>::operator->() const
  0.00      0.02    0.00    10002    0.00    0.00  boost::shared_ptr<Element>::operator Element* boost::shared_ptr<Element>::*() const
  0.00      0.02    0.00    10001    0.00    0.00  boost::shared_ptr<Element>::swap(boost::shared_ptr<Element>&)
  0.00      0.02    0.00    10001    0.00    0.00  boost::shared_ptr<Element>::reset()
  0.00      0.02    0.00    10001    0.00    0.00  boost::detail::shared_count::swap(boost::detail::shared_count&)
  0.00      0.02    0.00    10001    0.00    0.00  boost::shared_ptr<Element>::operator!() const
  0.00      0.02    0.00    10001    0.00    0.00  void std::swap<Element*>(Element*&, Element*&)
  0.00      0.02    0.00    10000    0.00    0.00  boost::detail::sp_counted_base::destroy()
  0.00      0.02    0.00    10000    0.00    0.00  boost::detail::sp_counted_base::sp_counted_base()
  0.00      0.02    0.00    10000    0.00    0.00  boost::detail::sp_counted_base::~sp_counted_base()
  0.00      0.02    0.00    10000    0.00    0.00  boost::detail::sp_enable_shared_from_this(boost::detail::shared_count const&, ...)
  0.00      0.02    0.00    9999    0.00    0.00  List::pushBack(int)
  0.00      0.02    0.00    9999    0.00    0.00  boost::shared_ptr<Element>::shared_ptr<Element>(Element*)
  0.00      0.02    0.00    9999    0.00    0.00  void boost::checked_delete<Element>(Element*)
  0.00      0.02    0.00    9999    0.00    0.00  boost::detail::shared_count::shared_count<Element>(Element*)
  0.00      0.02    0.00    9999    0.00    0.00  boost::detail::sp_counted_impl_p<Element>::dispose()
  0.00      0.02    0.00    9999    0.00    0.00  boost::detail::sp_counted_impl_p<Element>::sp_counted_impl_p(Element*)
  0.00      0.02    0.00    9999    0.00    0.00  boost::detail::sp_counted_impl_p<Element>::~sp_counted_impl_p()
  0.00      0.02    0.00    9999    0.00    0.00  Element::Element(int)
  0.00      0.02    0.00    9999    0.00    0.00  Element::~Element()
  0.00      0.02    0.00        4    0.00    0.00  Element::value()
  0.00      0.02    0.00        2    0.00    0.00  List::print()
  0.00      0.02    0.00        2    0.00    0.00  std::operator|(std::_Ios_Openmode, std::_Ios_Openmode)
  0.00      0.02    0.00        1    0.00    0.00  global constructors keyed to main
  0.00      0.02    0.00        1    0.00    0.00  __static_initialization_and_destruction_0(int, int)
  0.00      0.02    0.00        1    0.00    11.51  List::reverse()
  0.00      0.02    0.00        1    0.00    0.00  List::List()
  0.00      0.02    0.00        1    0.00    0.00  List::~List()
  0.00      0.02    0.00        1    0.00    0.00  boost::shared_ptr<List>::shared_ptr<List>(List*)
  0.00      0.02    0.00        1    0.00    0.00  boost::shared_ptr<List>::~shared_ptr()
  0.00      0.02    0.00        1    0.00    0.00  void boost::checked_delete<List>(List*)
  0.00      0.02    0.00        1    0.00    0.00  boost::detail::shared_count::shared_count<List>(List*)
  0.00      0.02    0.00        1    0.00    0.00  boost::detail::sp_counted_impl_p<List>::dispose()
  0.00      0.02    0.00        1    0.00    0.00  boost::detail::sp_counted_impl_p<List>::sp_counted_impl_p(List*)
  0.00      0.02    0.00        1    0.00    0.00  boost::detail::sp_counted_impl_p<List>::~sp_counted_impl_p()

---

here is version with plain pointers.no segfaults and fast as the wind:

Code:

---

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <boost/shared_ptr.hpp>


using namespace std;
using namespace boost;

long long num=0;

class Element
{
        Element* mp_next;
        int        m_value;
public:
        ~Element()
        {
                printf("Element dtor %lld\n",num++);
        }
        Element(int i)
        {
                mp_next=NULL;
                m_value = i;
        }
        Element* next()
        {
                return mp_next;
        }
        void setNext(Element* e)
        {
                mp_next = e;
        }
        int value()
        {
                return m_value;
        }
};

class List
{
        Element* mp_start;
        Element* mp_end;
public:
        ~List()
        {
                printf("List dtor\n");
                for(Element* e=mp_start; e;)
                {
                        Element* f = e;
                        e=e->next();
                        delete f;
                }
        }
        List()
        {
                mp_start=NULL;
                mp_end=NULL;
        }
        void pushBack(int i)
        {
                Element* ele(new Element(i));
                if(!mp_start)
                {
                        mp_start = ele;
                        mp_end = ele;
                        return;
                }
                mp_end->setNext(ele);
                mp_end = ele;
        }
        string print()
        {
                stringstream ss;
                ss << "from: ";
                (mp_start?ss<<mp_start->value():ss<<"NIL");
                ss << " to: ";
                (mp_end?ss<<mp_end->value():ss<<"NIL");
                ss<< endl;
                return ss.str();               
        }
        void reverse()
        {
                if(!mp_start || !mp_start->next()) return;
                mp_end = mp_start;
                Element* pred=NULL;
                Element* one =mp_start;
                Element* two (mp_start);
                do
                {
                        two = two->next();
                        one->setNext(pred);
                        pred = one;
                        one = two;
                       
                }while(two->next());
                two->setNext(pred);
                mp_start = two;
        }
};

int main(void)
{
        List* list(new List);
        for(long long i=0; i<99999; ++i)
        {
                list->pushBack(i);
        }
        cout << "list: " << list->print() << endl;
        list->reverse();
        cout << "reversed list: " << list->print() << endl;
        delete list;
}

---

and the gprof:

Code:

---

Flat profile:

Each sample counts as 0.01 seconds.
  %  cumulative  self              self    total         
 time  seconds  seconds    calls  ms/call  ms/call  name   
100.00      0.01    0.01        1    10.00    10.00  List::~List()
  0.00      0.01    0.00  299996    0.00    0.00  Element::next()
  0.00      0.01    0.00  199997    0.00    0.00  Element::setNext(Element*)
  0.00      0.01    0.00    99999    0.00    0.00  List::pushBack(int)
  0.00      0.01    0.00    99999    0.00    0.00  Element::Element(int)
  0.00      0.01    0.00    99999    0.00    0.00  Element::~Element()
  0.00      0.01    0.00        4    0.00    0.00  Element::value()
  0.00      0.01    0.00        2    0.00    0.00  List::print()
  0.00      0.01    0.00        2    0.00    0.00  std::operator|(std::_Ios_Openmode, std::_Ios_Openmode)
  0.00      0.01    0.00        1    0.00    0.00  global constructors keyed to num
  0.00      0.01    0.00        1    0.00    0.00  __static_initialization_and_destruction_0(int, int)
  0.00      0.01    0.00        1    0.00    0.00  List::reverse()
  0.00      0.01    0.00        1    0.00    0.00  List::List()

---

I found out it crashes always after about 65400 calls to Element:~Element() or not, if there are less than 65400 list members. strange...

EDIT: and after about 174426 calls if I build without debugging symbols.

I very much doubt that boost::shared_ptr is buggy - it's used far too much.

Whatever may be the reason for the crash, I know however that using boost::shared_ptr is simply wrong in your code. There is no question of ownership here.

shared_ptr has a noticeable performance impact on acquiring and releasing one - it comes from the reference counting. However, in such cases where this is a prime occupation, shared_ptr very likely is not the right choice anyway.

ownership control is not the only application of shared_ptr. its second use is the prevention of leaking resources. to quote from

http://www.boost.org/libs/smart_ptr/...#BestPractices

Quote:

---

Best Practices

A simple guideline that nearly eliminates the possibility of memory leaks is: always use a named smart pointer variable to hold the result of new. Every occurence of the new keyword in the code should have the form:

shared_ptr<T> p(new Y);

It is, of course, acceptable to use another smart pointer in place of shared_ptr above; having T and Y be the same type, or passing arguments to Y's constructor is also OK.

If you observe this guideline, it naturally follows that you will have no explicit deletes; try/catch constructs will be rare.

---

Maybe someone who has installed boost could compile the first listing and check for a segfault for big values in the main loop so I know if my setup or my brain fails :)

I'm very well aware of that, but this point does not apply to low-level data structures like a linked list.

My 2 cents...
Yes, boost::shared_ptr is dog slow.

The real cost comes from the fact that the assignment operator incurs extra cost due to reference counting. Allocation/Deallocation is slightly more expensive, but you only do that about 10,000 times each in this program.
Shared_ptr's relatively expensive operator=() and copy constructor are being called 100,000 times, and -that- is what's killing your program.

Also, you are running thread-safe shared_ptrs. The following is a mutex lock.

Code:

---

50.00      0.01    0.01  119986    0.00    0.00  boost::detail::atomic_exchange_and_add(int*, int)

---

Try undefining BOOST_HAS_THREADS and tell us how it runs.

It's not a mutex lock. It's just the atomic decrement-and-check-if-needs-destruction operation. It's what saves shared_ptr from having to do full mutex locks.

I wonder at something else: why does the call even register? It should be inlined.

Have you tried a simple method for timing fully optimized builds of the two versions?

of course it seg faults, you have a stack overflow! I don't think you've really grasped how a shared_ptr works.

when you call ~Element, it calls ~Element on it's mp_next which calls ~Element on it's mp_next which calls ~Element on it's mp_next which calls ~Element on it's mp_next which calls ~Element on it's mp_next which calls ~Element on it's mp_next which calls ~Element on it's mp_next which calls.... get the picture?

A shared_ptr is totally inappropriate for this. In fact, using any smart pointer to implement a linked list is conceptually wrong. A smart pointers sole reason for existence is manage object lifetime. Ownership control is merely a by-product of this. The nodes in a linked list are managed by the list. Even the boost ptr_list class just wraps a std::list<void*>.

Thanks all for the enlightenment.

Quote:

---

Have you tried a simple method for timing fully optimized builds of the two versions?

---

A very simple one: staring at my watch :) what would you suggest, clock_gettime?

Quote:

---

I don't think you've really grasped how a shared_ptr works.

---

That is absolutely true :) but I'm working on it.

Quote:

---

A shared_ptr is totally inappropriate for this. In fact, using any smart pointer to implement a linked list is conceptually wrong.

---

Ok I understood what you mean. It's bad style to let shared_ptr control the life time of a linked list element because it's the job of the list operations. So one question remains: why does the boost people confuse (beginners like me) with statements like the quoted one above ("put every result of new in an smart ptr..."). If I trust someone I usually take such advices literally.

Quote:

---

So one question remains: why does the boost people confuse (beginners like me) with statements like the quoted one above ("put every result of new in an smart ptr..."). If I trust someone I usually take such advices literally.

---

My guess is that they also expect you to use existing containers such as std::list instead of writing your own. It is, after all, only a guideline.

Quote:

---

Originally Posted by laserlight

My guess is that they also expect you to use existing containers such as std::list instead of writing your own.

---

Of course I use them. But sometimes I like to experiment with to find out how things work internaly.

Another question entered my mind over night. Consider this:

Code:

---

void pushBack // Add new Element to list
{
    Element* e = new Element(int i); // construct object and allocate memory
                                                        // and assign it to raw pointer
  <prepare list for insertion>;  // throws exception
  <insert new Element>;    // this never happens
}

// mem leak

---

With using a smart pointer cleanup happens automaticaly after exception. but what to do without?

Prepare the list first, then allocate the Element.