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

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 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users