On the performance of forward (linear) iterators of std::vector and std::list

The Experiment

I've been wondering for a while; when iterating linearly over an ordered collection of values; what's faster, an std::list or an std::vector. Today I set up the following C++ experiment:

	#include <list>
	#include <vector>
	#include <cmath>
	#include <iostream>
	#include "univhac.h"
	int pow(int num, int exp)
	{
	int rv = 1;
	for(int i = 0; i < exp; i++)
	{
	rv *= num;
	}
	return rv;
	}
	template<typename T>
	void g(T)
	{
	// do nothing
	}
	template<typename STORAGE>
	void test()
	{
	Univhac timer;
	for(size_t arraySizeExp = 0; arraySizeExp < 18; arraySizeExp++)
	{
	const int size = pow(2, arraySizeExp);
	timer.reset();
	STORAGE stor(size);
	const int factor = 5000;
	for(int j = 0; j < factor; j++)
	{
	for(typename STORAGE::iterator it = stor.begin();
	it != stor.end();
	++it)
	{
	g<typename STORAGE::value_type>(*it);
	}
	}
	std::cout << arraySizeExp << " " << timer.poll()/factor << std::endl;
	}
	}
	int main(int argc, char **argv)
	{
	test<std::list<int> >();
	test<std::vector<int> >();
	test<std::list<int> >();
	test<std::vector<int> >();
	return 0;
	}

view raw main.cpp hosted with ❤ by GitHub

(univhac.h is an extremely minor project of mine which can be found on http://univhac.googlecode.com/svn/trunk/univhac.h).

I'm only using the last two runs, the first two runs are just to warm up the cache.

The Result

This is with time on the y-axis and the 2-logarithm of the size linear access was tested on on the x-axis. The little disturbances for x < 10 are measurement errors and not repeatable.

Conclusion

Although std::list is slightly faster than std::vector for linear access, the difference on my laptop is maybe 1-2%. So, when all you care about is speed, and all you need is linear access, it really doesn't matter if you pick an std::list or an std::vector. I'd probably go for an std::vector, in case I ever need random access. Now, memory usage is another story, more on that later...