Boost logo

Boost Users :

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net