Thread: A little optimization challenge.

  1. #16
    Registered User
    Join Date
    Feb 2019
    Posts
    767
    Quote Originally Posted by Hodor View Post
    ... 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?

  2. #17
    Registered User
    Join Date
    Feb 2019
    Posts
    767
    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.

  3. #18
    'Allo, 'Allo, Allo
    Join Date
    Apr 2008
    Posts
    628
    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.

  4. #19
    Registered User
    Join Date
    Sep 2020
    Posts
    140
    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;
    }

  5. #20
    Registered User
    Join Date
    Sep 2020
    Posts
    140
    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];
       }
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need optimization
    By sc7 in forum C++ Programming
    Replies: 22
    Last Post: 11-10-2018, 11:11 AM
  2. Optimization challenge
    By Zacariaz in forum C Programming
    Replies: 1
    Last Post: 06-02-2015, 11:00 AM
  3. Optimization
    By lach in forum C Programming
    Replies: 4
    Last Post: 03-18-2006, 12:08 PM
  4. optimization
    By krithi in forum C Programming
    Replies: 9
    Last Post: 01-19-2003, 10:52 AM
  5. IDE optimization
    By Traveller in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 07-04-2002, 02:01 AM

Tags for this Thread