Wednesday 5 March 2008

c++ benchmark: list or vector?

In games programming, it's likely to have a collection of objects you want to draw to the screen. In some cases, the number of items in such a collection can be quite high.

I wondered if there's an efficient option between using std::list or std::vector, and I did a benchmark to see it myself.


Scenario 1: Insert n items, traverse n times.

when n=100, there isn't a huge difference but list is better. For vector it's between 15ms and 78ms, and for list it's between 15ms and 62ms.
When I calculate the average of rates, I can see that list is ~%11 faster.

when n=300, I can't see a clear winner. For vector it's between 200ms and 310ms, and for list it's between 203ms and 343ms.
According to the average of rates, vector is ~%3 faster.

Here's the source for this benchmark:http://pastebin.com/f41f684cb



Scenario 2: Insert n items, traverse n times and replace %20 of items on every iteration whilst traversing.


when n=100, mostly list wins. For vector it's between 170msms and 250ms, and for list it's between 172ms and 190ms.
List is ~%5 faster on average.

when n=200, list is always the winner. For vector it's between 1360ms and 1531ms, and for list it's between 1297ms and 1422ms.
List is ~%7 faster.

Here's the source for this benchmark:http://pastebin.com/f522f7e6b


Conclusion

If the number of items in your world are around 300 or more, and you don't perform so many insert&remove operations, pick vector. Otherwise, pick list.

I think the reason behind the truth that vector can't deal with continuous insert&remove operations is that it has to relocate remaining elements in the array when you delete one of them. For list, it's far more easy because it's implemented as a linked-list which means it's just about modifying two pointers to remove an element.

On the other hand, I think the reason why the list beats vector for 100 items is about the allocation strategy that vector uses. I don't know exactly how MS implemented this in standard library, but it's generally something like doubling the allocated memory everytime it's completely consumed. If it starts with a number like 5, to reach 100 it must be doubled 5 times, and everytime it looks for a bigger chunk of memory. The memory management has to find a continuous part in the memory for it. And after 100, to reach 300 it hast to be doubled just twice.