Approaches to optimize a small program (C++)

Imagine we have to work on the following problem (because it is our new assignment, our boss is obsessed with this problem, etc.):

We have a text file that’s a few hundred megabytes long. We knows that this text contains the word ‘fiona’ somewhere (its letters are written in lowercase letters), and we want to find its first occurrence in the text file. Suppose the text data is already loaded into the memory (because it is a part of a bigger system, that helps bad novelists to write better books) and all we need is a small C++ function that performs the search and returns the position of the fiona’s f. We need a fast and efficient solution. (Why? Our bigger system uses very much large text files, it loads brand new text files continiuously into the memory and we cannot control the creation of these text files because it belongs to an other system. But we want to replace every instance of the word ‘fiona’ with ‘agnes’, because we knew a Fiona once who had a really bad habit and we knew an Agnes who was a really nice girl. When the subroutine is fast enough, no one will know about our dirty little secrets.)

The easiest solution is really easy, every junior C++ programmer of the world (includes me) can code it in 10 minutes, check the following code:

/* ==== version 1 ==== the simple solution ==== */

inline bool match5( const char* big, const char* small )
{
  for ( int iii = 0; iii < 5; iii++ ) {
    if ( *(big + iii) != *(small + iii) )
       return false;
  }
  return true;
}

int find1( const char* big, const char* small, const int bound ) {
  for ( int iii = 0; iii < bound; iii++ ) {
    if ( match5(big + iii, small) ) return iii;
  }
}

...
int main() {
  ...
  find1(test, "fiona", 200000000);
  ...
}

(Note: It is the Boyer–Moore string search algorithm, so I’ve reinvented the wheel, but it is something like 2+2=4, so it doesn’t take much effort to reinvent it.) The function strstr is avaliable in <cstring>, however, it doesn’t work, the good old C function is not ready to process hundred of megabytes. But its re-implementation is simple and nice. The only question is: is there a faster and better algorithm, can we optimize this code? If we don’t like thinking we just take one of these optimization guides and we find out soon that we can optimize this code, for example, using short for loops is never efficient. So we rewrite this code and we get the second version:

/* ==== version 2 ==== traditional optimization ==== */

inline bool match5fast( const char* big, const char* small)
{
  if ( *big != *small )
    return false;
  if ( *(big + 1) != *(small + 1) )
    return false;
  if ( *(big + 2) != *(small + 2) )
    return false;
  if ( *(big + 3) != *(small + 3) )
    return false;
  if ( *(big + 4) != *(small + 4) )
    return false;
  return true;
}

int find2( const char* big, const char* small, const int bound ) {
  for ( int iii = 0; iii < bound; iii++ ) {
    if ( match5fast(big + iii, small) ) return iii;
  }
}

...
int main() {
  ...
  find2(test, "fiona", 200000000);
  ...
}

If we knew more about template metaprogramming, we could write this code in a more elegant way (using recursion), however, let the gentle reader imagine the situation of a junior programmer. If we follow the advice of Pete Isensee’s guide and we “measure, measure and measure” we will see that the second version is approximately 30 percent faster than the first version. It is cool. Could it be even faster? Of course we could use other good advices to rewrite some control structures in the code without the modification of the underlying algorithm. But suppose, we reached the point when this kind of optimizations is not helpful anymore. (It is not true, but please, suppose it.) Could we maybe improve the algorithm?

Maybe we could. The basic idea, that the algorithm, that we’ve used, is just too general. It works for such words like “ababa” or “retret” or “bbbbbbb” (which consist the same, repeated part), but we don’t really need this feature. The letters of ‘fiona’ are unique. We can use this fact, because it has important consequences.

  1. We don’t need always to read each letter of the text file. Suppose, we read the letter ‘e’ somewhere in the text file at the position x. What does it mean? It means that the fiona’s first f cannot be at x, but it cannot be also at the positions (x-4), (x-3), (x-2), (x-1). Why? Examine the figure below:
    fiona1When we find an ‘e’ at the position x, we know that the word ‘fiona’ cannot start at the position (x-2), because in this case, we would see ‘o’ instead of ‘e’ at the position x.
  2. If we find a letter of ‘fiona’ somewhere in the text, there is only one possible starting position that belongs to this letter. For example, if we find an ‘i’ at the position y, then there is only one possible starting position to the corresponding fiona: (y-1).

If we use these observations, we can construct a more intelligent algorithm to solve our problem, and it leads to the third version of the program. Here is its source code:

/* ==== version 3 ==== using better algorithm ==== */

inline bool isLetterOfFiona( char chr ) {
 switch ( chr ) {
   case 'f':
   case 'i':
   case 'o':
   case 'n':
   case 'a':
     return true;
   default:
     return false;
 }
}

inline char relativeDistanceOfFionasEnding( const char chr ) {
  switch ( chr ) {
    case 'f': return 4;
    case 'i': return 3;
    case 'o': return 2;
    case 'n': return 1;
    case 'a': return 0;
    default : exit(-1);
  }
}

int find3( const char* big, const int bound ) {
  for (int iii = 0; iii < bound; ) {
    char letter = *(big + iii + 4);
    if ( isLetterOfFiona( letter ) ) {
      char pl = relativeDistanceOfFionasEnding( letter );
      int jjj = iii + pl;
      if ( match5fast(big + jjj, "fiona") )
        return jjj;
      else
        iii += pl;
    }
    iii += 5;
  }
}

...
int main() {
  ...
  find3(test, 200000000);
  ...
}

If we compare the speed of the second and third versions, we will experience that the third version is also 30 percent faster than the second version, so it is about 70 percent faster than the first version. Is it beautiful? In one hand, it is, we wanted to have some speed-up and we’ve done it, yippee ki-ay. In other hand, the last algorithm isn’t flexible anymore. The algorithm of the first version was (more or less) a general algorithm, the second algorithm is more specific and the third algorithm is a very specifical one, if you want to search an other word like ‘rosalinda’, you have to rewrite almost the whole program. Of course even the first version is not a totally general solution because it uses the function match5(), but I’m sure you feel that it is much much more general than the third version.

So, the third version is 70 percent faster than the first, but it wasn’t enough to me. I still wanted to make it faster and I’ve been thought for days how could I still optimize it. I couldn’t sleep. I couldn’t eat. And after than, all of sudden, I had a brand new idea: if the compiler uses five ifs (or compares/jumps) to code the function isLetterOfFiona(), maybe I could write instead of this switch-case something more cool. I’ve implemented the following function:

/* ==== version 4 ==== almost identical to the version 3, but it uses a different isLetterOfFiona() function ==== */

...
inline bool isLetterOfFionaUltrafast( unsigned char chr ) {
  chr ^= 0x60;
  return ( chr < 16? (0xc242 >> chr) & 1 : false );
}
...

I was so proud, because it is so cool. Do you like it? There is a simple idea behind it, we use a lookup table, and we don’t store this lookup table in an array, we code it into just one single unsigned short integer. We can do it, because our table contains in this case less or equal than sixteen boolean values. (Note: We could write it into a more general version with subtraction and 32 bit integers, because there are only 26 lower-case letters in the English alphabet.) I was especially proud because I invented my own magic number which is related to fiona. There is only one small problem: the fourth version is slower than the third, and it spoiled my day. A quick benchmarking showed that it is about 2% slower than the third version. What does it mean? First, the compiler generates a small and nice lookup table automatically, and second, it is more efficient than my version.

Optimization is like motorsport, it is hard to quit at the top, and overdoing optimization is a quite dangerous. The resulting code can be less general, more specific, it is likely harder to maintain and there is no guarantee that our great ideas lead to a better version, only benchmarking can decide whether an idea is useful or not. But the greatest danger is wasting time, optimization can be a great temptation, we have to learn to resist.

***

Small remarks about benchmarking. Because I wanted to compare the speeds of the different versions, I’ve used a subroutine that generates random English letters and the distribution of the generated letters is corresponding to English letter frequency. With this function I’ve created 200 megabytes long text inputs, I’ve removed the occurrences  of ‘fiona’ from it and I’ve placed the word ‘fiona’ at the end. I believe this method produces such text inputs that behaves very similar like real English texts.

double frequency[25] =
{0.08167,
 0.01492,
 ...};

inline char randLetter() {
  double rv = rand() * 1.0 / RAND_MAX;
  char act = 'a';
  double sum = frequency[0];
  while ( act < 'z' && sum < rv ) {
    act++;
    sum += frequency[ act - 'a' ];
  }
  return act;
}

(If you want to know, why we don’t like Fiona, please, watch the movie EuroTrip and/or listen the song Scotty doesn’t know.)

Advertisements

About vrichard86

I'm Richard and I'm an enthusiastic coder. I want to be better and I think a professional journal is a great self improvement tool. Welcome to my blog, to my hq, to my home on the web!
This entry was posted in C++ and tagged , , , , , , , . Bookmark the permalink.