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()