[Boost-users] vector vs list speed test

From: bringiton bringiton (kneeride_at_[hidden])
Date: 2006-07-12 00:48:37

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