Optimization for the sake of optimization...

I haven't had the time to post anything new lately, mostly because I've been very busy on an old project that regained my interest. I've also had a two week vacation, during which I have started to revive my C++ knowledge, also in light of the same project (more about it later).

While doing some small C++ exercises and examples to get my feeling for the language back, I fell for an age-old trap: over-optimization...

Here's the situation: suppose you have an array with lots and lots of integers, and you want to find out which the minimum and maximum values are in said array. In itself this is a very simple homework-type task: choose a high minimum, choose a low maximum, loop throughout the array, and each time you find a value surpassing an extremity, alter it and move on.

In code, this would look like the following:

#include <iostream>
using namespace std;

int main()
{
  const int ARRAY_SIZE = 1000;

  int values [ARRAY_SIZE];

  int minimum = INT_MAX;
  int maximum = INT_MIN;

  // initialize array to random values
  srand((unsigned int) time(NULL));
  for (int i = 0; i < ARRAY_SIZE; i++)
  {
    values[i] = rand();
  }

  // find minimum / maximum values
  for (int i = 0; i < ARRAY_SIZE; i++)
  {
    if (values[i] < minimum)
    {
      minimum = values[i];
    }

    if (values[i] > maximum)
    {
      maximum = values[i];
    }
  }

  cout << "Minimum : " << minimum << endl;
  cout << "Maximum : " << maximum << endl;
}

Those two "if" statements bothered me for some reason, though... I figured there should be a way to do the same, but shorter, so I rewrote that part using the C++ ternary operator.

// find minimum / maximum values
for (int i = 0; i < ARRAY_SIZE; i++)
{
  maximum = (values[i] > maximum) ? values[i] : maximum;
  minimum = (values[i] < minimum) ? values[i] : minimum;
}

And then it dawned on me - why on earth would I check the minimum/maximum myself? Why not simply use the already existing functions in math.h? Never one to re-invent the wheel, I altered the above to:

#include <math.h>
...
// find minimum / maximum values
for (int i = 0; i < ARRAY_SIZE; i++)
{
  maximum = max(values[i], maximum);
  minimum = min(values[i], minimum);
}

Much nicer - but is it faster? Since I got a bit carried away optimizing this part, I decided to time the three different solutions. The following code was used to get an average time based on a bigger array, and over a lot of iterations of the three code snippets:

#include <iostream>
#include <math.h>
#include <windows.h>
using namespace std;

int main()
{
  const int ITERATIONS = 1000;
  const int ARRAY_SIZE = 500000;

  int values [ARRAY_SIZE];

  int minimum = INT_MAX;
  int maximum = INT_MIN;

  int delta;
  int deltas;
  float resultDelta;

  // initialize array to random values
  srand((unsigned int) time(NULL));
  for (int i = 0; i < ARRAY_SIZE; i++)
  {
    values[i] = rand();
  }

  // time the "if" method
  deltas = 0;
  for (int j = 0; j < ITERATIONS; j++)
  {
    delta = GetTickCount();

    // find minimum / maximum values
    for (int i = 0; i < ARRAY_SIZE; i++)
    {
      if (values[i] < minimum)
      {
        minimum = values[i];
      }

      if (values[i] > maximum)
      {
        maximum = values[i];
      }
    }

    deltas += (GetTickCount() - delta);
  }
  resultDelta = (float) deltas / (float) ITERATIONS;
  cout << "Delta (if)     : " << resultDelta << "ms" << endl;

  // time the "ternary operator" method
  deltas = 0;
  for (int j = 0; j < ITERATIONS; j++)
  {
    delta = GetTickCount();

    // find minimum / maximum values
    for (int i = 0; i < ARRAY_SIZE; i++)
    {
      maximum = (values[i] > maximum) ? values[i] : maximum;
      minimum = (values[i] < minimum) ? values[i] : minimum;
    }

    deltas += (GetTickCount() - delta);
  }
  resultDelta = (float) deltas / (float) ITERATIONS;
  cout << "Delta (ternary): " << resultDelta << "ms" << endl;

  // time the "math function" method
  deltas = 0;
  for (int j = 0; j < ITERATIONS; j++)
  {
    delta = GetTickCount();

    // find minimum / maximum values
    for (int i = 0; i < ARRAY_SIZE; i++)
    {
      maximum = max(values[i], maximum);
      minimum = min(values[i], minimum);
    }

    deltas += (GetTickCount() - delta);
  }
  resultDelta = (float) deltas / (float) ITERATIONS;
  cout << "Delta (math)   : " << resultDelta << "ms" << endl;
}

Unfortunately, as it turns out, my efforts were wasted. Both solutions I considered an optimization (code-wise), turned out to be slower than the original snippet.

When you think about it, it is logical that the "if" statement is the fastest solution: after all, if the condition is false, no assignment is done. Since assignments are heavier statements for a CPU than conditional checks, this explains the time difference between the first method and the two later snippets. Besides, the further you progress in the loop, the less likely the chance of a lower minimum or a higher maximum - further more reducing the number of assignments.

All things considered, Donald Knuth was right in the first place: "premature optimization is the root of all evil".