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

On 7/11/06, 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.

...

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

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?

Accessing the heap for every list edit can take significantly more time than the memcpy a vector<int> might do when you delete from the front of a small vector. Try making the list use a allocator from boost::pool, I bet you will see much better results! -- Cory Nelson http://www.int64.org