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

From: Cory Nelson (phrosty_at_[hidden])
Date: 2006-07-12 02:16:56

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