Re: [Boost-users] vector vs list speed test

From: bringiton bringiton (kneeride_at_[hidden])
Date: 2006-07-12 02:47:29

On 7/12/06, bringiton bringiton <kneeride_at_[hidden]> wrote:
> On 7/12/06, Cory Nelson <phrosty_at_[hidden]> wrote:
> > On 7/11/06, bringiton bringiton <kneeride_at_[hidden]> wrote:
> > > On 7/12/06, bringiton bringiton <kneeride_at_[hidden]> wrote:
> > > > I'm just wondering what your thoughts are on my findings.
> > > >
> > > > I need a container that meets the following:
> > > > - forward iteration only
> > > > - insert to end only
> > > > - no random access
> > > > - delete from any position
> > > > - average size of list will be 64 items
> > > >
> > > > I would first say use list over vector. because no random access and
> > > > delete from any position. I ran some performance tests, which proved
> > > > otherwise.
> >
> > > > - it seems vector is best for smaller lists. even at 256 items, the
> > > > vector is twice as fast at building at contant time and deleting and
> > > > worst case linear time.
> > > > - is this strange behaviour? is my test correct or do i have a bug?
> > > > - i am also curious to how this runs on other compilers (esp later
> > > > version of ms vc++)
> > >
> > > I've done some more tests. It seems building a list is significantly
> > > slower that building a vector.  (This is were the discrepancy is
> > > coming from).  can anyone suggest why this is so?  is the
> > > list<T>::push_back bottleneck due to memory allocation for each node?
> >
> > Accessing the heap for every list edit can take significantly more
> > time than the memcpy a vector<int> might do when you delete from the
> > front of a small vector.  Try making the list use a allocator from
> > boost::pool, I bet you will see much better results!
> >
> >
> > --
> > Cory Nelson
> > http://www.int64.org
> > _______________________________________________
> > Boost-users mailing list
> > Boost-users_at_[hidden]
> > http://lists.boost.org/mailman/listinfo.cgi/boost-users
> >
>
>
> ok results change when i use a larger object. clearly the list is faster
>
> Test build/remove 64
> 0.812
> 0.531
> Test build/remove 256
> 8.688
> 2.016
> Test build/remove 1024
> 126.487
> 11.032
>
> the object i used:
>
> class SmallObject {
> public:
>        SmallObject() {
>                v = 0;
>                s = "hello";
>        }
>        int v;
>        std::string s;
> };
>

however, i only plan on using small datatypes. for anything large, i
will use pointers or shared_ptr<T>

so the results for the larger object is not very relevant to my needs