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

From: bringiton bringiton (kneeride_at_[hidden])
Date: 2006-07-12 02:45:16

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