A dead heat?  I’m such a stinker.  And some wondered why I did such unusual math in the test body, with no squaring and so forth.  I admit it, I rigged the fight.  But why?  Let’s look at the numbers because they’re very cool.

 

First, when reading the chart you should know that the amount of “work” done in each of the samples is fixed.  This is to say that when I did the timing I varied the number of iterations inversely with the size of the problem so that the total amount of summing was fixed.  I did this deliberately so that times would be comparable across all runs.

 

OK, looking at the graph, we can see that for sizes up to 2^14 Test2 is the clear winner.  Why is this?  Well, for those sizes in both cases all the data was fitting in my processors L2 cache, which means there was no additional time overhead associated with using the memory and so all that happens when cache the z value is that we save time.

 

It’s important to note just how nearly-flat the time is here in both cases.  Even though the smaller size arrays are doing many more allocations there is only a barely measurable speedup going from allocations of size 16 bytes to 32, 64, and so forth.  By the flatness of both graphs you can see that the amortized cost of allocating memory and collecting memory varies with the number of bytes allocated, which is fixed, and not with the number of allocations, which is going down geometrically. 

 

As the size approaches 2^14 you can see the time going up gradually in both cases, corresponding to the cache becoming fully loaded and the necessary cache misses to get the cache primed.

 

At 2^15 the interesting things start to happen.  This is if you like the shining moment for Test1 – both algorithms took a big hit going to 32k entries in the array but Test1 is still getting a substantial number of cache hits while Test2 is now paying a hefty penalty for more misses.

 

At 2^16, which is the problem as given, Test1 is still getting enough extra cache hits to break even with the math.

 

And now we come to the most interesting phenomenon – at size 2^17 Test2 is back in the lead, and it won’t look back for a long time.   Why?  Well at this point, on my machine anyway, the data is too big for the cache in BOTH algorithms.  Neither is getting a substantial number of cache hits and so the distance between them is reverting to the previous savings of some double-precision math.

 

The real failing of the answers I got to this problem was here, the reason I couldn’t give anyone full marks was that despite notions that memory would soon dominate, nobody predicted that for larger sizes the cache would stop being a factor. 

 

Again moving up to sizes 2^23 you can see that the graph is still very flat.  Remember the x-axis is logarithmic. With each new data point doubling the size of the array if I were to plot the graph in non-log scale you’d see a nearly flat line for almost all the graph and a very sharp almost vertical line at the extreme left near zero.

 

But even as I say it’s nearly flat, we can see that the green line for Test2 is growing a lot faster than the red Test1 line.  What is going on here?

 

Well what’s happening now is that as the test arrays are increasing in size they are requiring greater and greater percentages of the machines overall memory.  That doesn’t come so easily, and in fact the next level of the memory hierarchy starts to play a factor – to find the necessary physical memory the operating system is having to page out some data pages that were serving other processes, incurring some significant overhead.  Ultimately, at size 2^23 Test1’s more frugal algorithm starts winning again.

 

 

What do we learn from all of this?

 

Very often I’m shown new and potentially better algorithms along with a micro-benchmark that indicates how vastly superior the new algorithm is.  These have to be taken with a good deal of salt, and you yourself should be very careful about how much weight you put in your own isolated measurements.

 

Had you been shown a benchmark for Test1 and Test2 with some number of iterations and data-size in which either was shown to be decidedly better, you would only have been seeing a part of the puzzle.  The truth is there’s a real horse-race here.

 

Looking at the big picture you can more readily appreciate the demand that the algorithms are making on system resources to achieve their throughput.  And in fact, if these algorithms were running as part of a larger system Test2 would have a much greater collateral impact on the overall system even though when run in isolation it is faster for many more data sizes.

 

It’s vital to measure code in the manner in which it will be used, and not (only) in isolation.

 

Analyzing two functions with random numbers at their core may seem strange but there are many algorithms which either randomize their inputs, or deal with input that is nearly random in the first place – though perhaps not as evenly distributed randomness as this example.

 

And having seen all this data which do I recommend?

 

The performance architects of the CLR are again united in their opinion: Test1 is the winner.  The benchmarks show that it is in the neighborhood of 13% slower in the worst of times and consistently uses 1/3 less data.  We felt that when used in the context of a larger program the additional throughput was not worth the resource consumption.  Overall performance was more likely to benefit from the frugalness of Test1 than the caching of Test2.