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

12 Jul 2006


      On 7/12/06, Cory Nelson  wrote:
...
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
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users
ok results change when i use a larger object. clearly the list is faster

Test build/remove 64
0.812
0.531
Test build/remove 256
8.688
2.016
Test build/remove 1024
126.487
11.032

the object i used:

class SmallObject {
public:
	SmallObject() {
		v = 0;
		s = "hello";
	}
	int v;
	std::string s;
};