The Lazy Programmer

April 17, 2008

Benchmarking stack_array<T>

Filed under: C#,Programming — ferruccio @ 10:45 pm
Tags: , ,

In my last post I presented a stack_array template/macro combination that I use to create dynamically sized arrays on the stack. By allocating the space on the stack we get the dual benefits of not having to worry about freeing memory and better performance. I knew the performance had to be better, but how much better? Would I have been better off just using STL vectors?

I decided to do some empirical testing, so I put together a small benchmark. This benchmark runs two tests against four different array types.

The two tests are:

  1. The function is called in an environment where no heap allocations are taking place (outside of the array allocation, when applicable).
  2. The function is called in an environment where there is heavy heap allocation/deallocation going on, thereby fragmenting the heap.

And the four array types are:

  1. A fixed size C array of chars as a control.
  2. A stack_array<char>.
  3. A vector<char>.
  4. An explicitly allocated char*.

You can get the benchmark code here.

I ran the benchmark on a laptop with a 2GHz Pentium-M and got these results:

[test1] control: 3756 msec
[test1] stack array: 5518 msec
[test1] vector: 108696 msec
[test1] heap allocation: 23113 msec
------------------------------------
[test2] control: 44274 msec
[test2] stack array: 48289 msec
[test2] vector: 161001 msec
[test2] heap allocation: 67417 msec
------------------------------------

This benchmark tests the time it takes to create and destroy each type of array, nothing else. Well, the second test also measures the time it takes to do all the memory allocations and deallocation used to fragment memory. That is why each test run is started with a call to srand(1). This guarantees each test will use the exact same set of pseudo-random numbers.

Each test function is called 100 million times. This was necessary because of the sheer speed of today’s machines. I started with test runs of 10,000 and got results very close to zero for all tests. Until I tried at least one million iterations, the results seemed too close to each other for statistical comfort.

The stack_array times were comparable to the controls, which is what I expected. The only real surprise to me here was how badly the vector tests did in comparison with the direct heap allocation tests. I would have expected them to be a lot closer.

I think the stack_array is worth keeping around.

Advertisements

Blog at WordPress.com.

%d bloggers like this: