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

From: Boris Breidenbach (Boris.Breidenbach_at_[hidden])
Date: 2006-07-12 04:18:45

You can check how a vector's capacity changes, while pushing back new elements:

    unsigned int capacity=0;
    std::vector<int> vec;
    
    for (unsigned int i=0; i<10000; ++i)
    {
        vec.push_back(i);
        if (vec.capacity()!=capacity)
        {
            capacity=vec.capacity();
            std::cout << capacity << std::endl;
        }
    }
 
output:

1
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384

so it doubles its size whenever it hit its boundary. That's probably why building
a vector is faster.

On Wed, Jul 12, 2006 at 03:33:43PM +1000, bringiton bringiton 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.
> >
> > The test builds a list by inserting to end. And then removes all items
> > from the front until size == 0.  (note: removing from index [0] should
> > provide worst case linear complexity for vector)
> >
> > Here are my finding for containers of size 64, 256 and 1024. first
> > result uses vector, 2nd uses list. i ran the test in release mode in
> > ms vc++ 6.
> >
> > Test build/remove 64
> > 0.062
> > 0.234
> > Test build/remove 256
> > 0.422
> > 0.938
> > Test build/remove 1024
> > 5.844
> > 3.75
> >
> > - 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++)
> >
> > For those curious, here is my code. feel free to pick at it ;)
> >
> > void TestVectBuildDelete(int redoCount, int listSize)
> > {
> >        boost::timer t;
> >        for (int i = 0; i < redoCount; i++) {
> >                // build the list
> >                std::vector<int> vect;
> >                for (int j = 0; j < listSize; j++) {
> >                        vect.push_back(j);
> >                        //vect.insert(vect.begin(), j); //.push_front(j);
> >                }
> >                // remove all elements in list
> >                while (!vect.empty()) {
> >                        vect.erase(vect.begin());
> >                }
> >        }
> >        std::cout << t.elapsed() << std::endl;
> > }
> >
> > void TestListBuildDelete(int redoCount, int listSize)
> > {
> >        boost::timer t;
> >        for (int i = 0; i < redoCount; i++) {
> >                // build the list
> >                std::list<int> vect;
> >                for (int j = 0; j < listSize; j++) {
> >                        vect.push_back(j);
> >                }
> >                // remove all elements in list
> >                while (!vect.empty()) {
> >                        vect.pop_front();
> >                }
> >        }
> >        std::cout << t.elapsed() << std::endl;
> > }
> >
> > void Test()
> > {
> >        std::cout << "Test build/remove 64" << std::endl;
> >        TestVectBuildDelete(10000, 64);
> >        TestListBuildDelete(10000, 64);
> >
> >        std::cout << "Test build/remove 256" << std::endl;
> >        TestVectBuildDelete(10000, 256);
> >        TestListBuildDelete(10000, 256);
> >
> >        std::cout << "Test build/remove 1024" << std::endl;
> >        TestVectBuildDelete(10000, 1024);
> >        TestListBuildDelete(10000, 1024);
> > }
> >
> 
> 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?
> 
> *NB sorry this is boost related. but i found it interesting ;)
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users