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

From: bringiton bringiton (kneeride_at_[hidden])
Date: 2006-07-12 01:33:43

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