Thread: A little optimization challenge.

Originally Posted by Hodor

... do you no agree that the order of evaluation of vowels can make a huge difference? Your code makes the order irrelevant of course but, in general, I think that stuff like this makes a difference.

Of course, more 'e's than 'u's in english. Stuff like that?

The suggestion of avoiding branches is a good one. But not at the cost of using an "instruction" slower then a possible penalty of a single clock cycle if the conditional branch is not taken, due to statically branch prediction algorithm implemented on the processor. That suggestion of using MUL (which have latency of 4 clock cycles on x86) instead of a single conditional branch (which maybe has a penalty of a single clock cycle) is not very smart to make this "always avoid branches" a rule.

I believe, as you do, to focus on macro optimizations is a good thing, but I believe in "micro" optimizations as well. That's why I measure the clock cycles spent in my codes. That's not an exact science, since a function can spend more cycles than it was measured: Too many side effects (cache misses, page faults, interrupts, task switching, ...), but it is a way to get a general idea of how my codes are performing, in comparison to another code.

Also, to use some obfuscated "trick", sometimes, leads to problems. Such as those about using bitwise AND and ORs, instead of logical ones (not because it is wrong, it isn't - The == operator has precedence over ANDs and ORs, bitwise or logical - the problem is the defeating of "short circuits", or, putting another way, "sequence points"). But, sometimes, they are useful... Always depends on analysis, and we should not make them a "rule".

[]s
Fred

PS: I don't know what's going on with you, Hodor, and awsdert and, really, don't care... Sorry.

Here's my entry:

Code:

puts("There are 2357034 consonants and 1433891 vowels in the Complete Works of William Shakespeare");

My optimisation was working smarter, not harder and leveraging the work of others.
My solution is also fortified with the domain-specific knowledge that if Shakespeare indeed does rise as a zombie, he will be more occupied with trying to eat the brains of those attributing his works to Francis Bacon than with the thought of renaming Titania to Cheryl and so completely discombobulating the letter count of this hitherto static file.

About 15x faster than the reference code...

Code:

/***********************************************
* charcount.c : count chars and vowels in a file
***********************************************/
#include <stdio.h>
#include <stdint.h>
#include <ctype.h>
#include <sys/time.h>


char fname[] = "t8.shakespeare.txt";


int isVowel(int c) {
  c = tolower(c);
  return (c == 'a') || (c == 'e') || (c == 'i') || (c == 'o') || (c == 'u');
}


int isConsonant(int c) {
  if(isVowel(c)) return 0;
  return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}




static unsigned char buffer[16*1024];
static uint64_t lookupTable1[256];
static uint64_t lookupTable2[256*256];


static void tableSetup(void) {
   // Table for checking one character at a time
   // isConstonant in the low bit
   // isVowel in bit 32 
   for(int i = 0; i < 256; i++) {
      lookupTable1[i]  = isVowel(i) ? (1LL<<32) : 0;
      lookupTable1[i] += isConsonant(i) ? 1 : 0;
   }


   // Table for checking two characters at a time
   // isConstonant in the low bit
   // isVowel in bit 32 
   for(int i = 0; i < 256*256; i++) {
      lookupTable2[i]  = isVowel(i&0xFF) ? (1LL<<32) : 0;
      lookupTable2[i] += isConsonant(i&0xFF) ? 1 : 0;
      lookupTable2[i] += isVowel(i>>8) ? (1LL<<32) : 0;
      lookupTable2[i] += isConsonant(i>>8) ? 1 : 0;
   }
}


int main(int argc, char *argv[]) {
   struct timeval start, end;
   uint32_t conCount = 0, vowelCount = 0; 
   uint64_t total = 0;
   gettimeofday(&start, NULL);




   FILE *f = fopen(fname,"r");
   if(f == NULL) {
      printf("Unable to open %s\n",fname);
      printf("\n");
      printf("Please download the test file from \n");
      printf("https://ocw.mit.edu/ans7870/6/6.006/s08/lecturenotes/files/t8.shakespeare.txt\n");
      return 0;
   }


   //============== Start of code ==========
   tableSetup();


   int chars_read = fread(buffer,1,sizeof(buffer),f);
   while(chars_read > 0) {
      unsigned char *b = buffer;
      while( chars_read >= 8) {
         uint16_t *b2 = (uint16_t *)b;
         total  += lookupTable2[b2[0]]; 
         total  += lookupTable2[b2[1]]; 
         total  += lookupTable2[b2[2]]; 
         total  += lookupTable2[b2[3]]; 
         total  += lookupTable2[b2[4]]; 
         total  += lookupTable2[b2[5]]; 
         total  += lookupTable2[b2[6]]; 
         total  += lookupTable2[b2[7]]; 
         b          += 16;
         chars_read -= 16;
      }
      while( chars_read > 0) {
         total  += lookupTable1[b[0]]; 
         b++;
         chars_read--;
      }
      chars_read = fread(buffer,1,sizeof(buffer),f);
   }
   conCount   = total;
   vowelCount = total>>32;
   // ========== End of code ==========
   fclose(f);


   gettimeofday(&end, NULL);


   printf("There are %i consonants and %i vowels in the complete works of William Shakespeare\n",conCount, vowelCount);
   printf("Time taken = %li microseconds\n", (long int)(end.tv_sec-start.tv_sec)*1000000+(end.tv_usec-start.tv_usec));
   return 0;
}

Found a little shortcut in my table setup code, so it's now 16x faster. Updated function below.

Code:

static void tableSetup(void) {
   // Table for checking one character at a time
   // isConsonant in the low bit
   // isVowel in bit 32 
   for(int i = 0; i < 256; i++) {
      lookupTable1[i]  = isVowel(i) ? (1LL<<32) : 0;
      lookupTable1[i] += isConsonant(i) ? 1 : 0;
   }


   // Table for checking two characters at a time
   // isConstonant in the low bit
   // isVowel in bit 32 
   for(int i = 0; i < 256*256; i++) {
      lookupTable2[i] = lookupTable1[i&0xFF] + lookupTable1[i>>8];
   }
}