Thread: making programms faster

  1. #16
    Registered User joed's Avatar
    Join Date
    Mar 2004
    Posts
    59
    There's not much point in using goto, not for performance anyway. It can be used to simplify life in rare cases. Eliminating unnecessary function calls or heavy math in loops is the best place to start. Example:

    This fills a 64x64 block using a function:
    Code:
        for(y = 0; y < 64; y++)
            for(x = 0; x < 64; x++)
                plot(dest, x, y, color);
    This increments a pointer instead:
    Code:
        int *p = dest;
    
        for(y = 0; y < 64; y++)
            for(x = 0; x < 64; x++)
                *p++ = color;
    The important part is the inner X loop; updating the pointer's position (for clipping, etc) in the Y loop only incurs a small performance hit. Even if plot() were inlined, this is still faster, since the pixel offset isn't recalculated every time.

  2. #17
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    Actually, in that case, it could be optimized farther to this:
    Code:
      int *p = dest;
      y = 63;
    
      while( y-- )
      {
    
        x = 63;
        while( x-- )
          *p++ = color;
    
      }
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  3. #18
    .
    Join Date
    Nov 2003
    Posts
    307
    Quote Originally Posted by Bubba
    You guys are insane. Never use goto. You mean to tell me that with everything that is available in C++ and C all you can do is resort to a goto as your solution.

    Gimme a break.
    Bubba -

    Tell that to Peter Berg - wrote the strstr() function for Linux.
    His algorithm is the fastest one known, AFAIK. There are times when goto is used. Take this and rewrite it so it's just as fast without goto - this is a copy of the code.
    I'm not saying it's good/bad code but the requirements were: C only, no asm, and as fast as possible
    Code:
    char *
    old_strstr (const char *phaystack, const char *pneedle)
    {
      register const unsigned char *haystack, *needle;
      register chartype b, c;
    
      haystack = (const unsigned char *) phaystack;
      needle = (const unsigned char *) pneedle;
    
      b = *needle;
      if (b != '\0')
        {
          haystack--;				/* possible ANSI violation */
          do
    	{
    	  c = *++haystack;
    	  if (c == '\0')
    	    goto ret0;
    	}
          while (c != b);
    
          c = *++needle;
          if (c == '\0')
    	goto foundneedle;
          ++needle;
          goto jin;
    
          for (;;)
            {
              register chartype a;
    	  register const unsigned char *rhaystack, *rneedle;
    
    	  do
    	    {
    	      a = *++haystack;
    	      if (a == '\0')
    		goto ret0;
    	      if (a == b)
    		break;
    	      a = *++haystack;
    	      if (a == '\0')
    		goto ret0;
    shloop:;    }
              while (a != b);
    
    jin:	  a = *++haystack;
    	  if (a == '\0')
    	    goto ret0;
    
    	  if (a != c)
    	    goto shloop;
    
    	  rhaystack = haystack-- + 1;
    	  rneedle = needle;
    	  a = *rneedle;
    
    	  if (*rhaystack == a)
    	    do
    	      {
    		if (a == '\0')
    		  goto foundneedle;
    		++rhaystack;
    		a = *++needle;
    		if (*rhaystack != a)
    		  break;
    		if (a == '\0')
    		  goto foundneedle;
    		++rhaystack;
    		a = *++needle;
    	      }
    	    while (*rhaystack == a);
    
    	  needle = rneedle;		   /* took the register-poor approach */
    
    	  if (a == '\0')
    	    break;
            }
        }
    foundneedle:
      return (char*) haystack;
    ret0:
      return 0;
    }

  4. #19
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by jim mcnamara
    Bubba -

    Tell that to Peter Berg - wrote the strstr() function for Linux.
    GOTO is part of the language. Some people feel that there are circumstances where it is appropriate to use this. If you have to ask, "Is it OK to use GOTO in my program," my answer would probably be, "probably not."

    If you were getting ready to climb into the cockpit of a fighter jet on the deck of an aircraft carrier with the engine running and you asked, "Is it OK to push the throttle control all the way to the bulkhead", I would probably say, "probably not."

    I'm guessing Peter Berg didn't have to ask.

    Regards,

    Dave

  5. #20
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Quote Originally Posted by jim mcnamara
    Take this and rewrite it so it's just as fast without goto
    Code:
    #include <stdio.h>
    #include <string.h>
    #include <time.h>
    
    typedef char chartype;
    
    char *
    old_strstr (const char *phaystack, const char *pneedle)
    {
      register const unsigned char *haystack, *needle;
      register chartype b, c;
    
      haystack = (const unsigned char *) phaystack;
      needle = (const unsigned char *) pneedle;
    
      b = *needle;
      if (b != '\0')
        {
          haystack--;				/* possible ANSI violation */
          do
    	{
    	  c = *++haystack;
    	  if (c == '\0')
    	    goto ret0;
    	}
          while (c != b);
    
          c = *++needle;
          if (c == '\0')
    	goto foundneedle;
          ++needle;
          goto jin;
    
          for (;;)
            {
              register chartype a;
    	  register const unsigned char *rhaystack, *rneedle;
    
    	  do
    	    {
    	      a = *++haystack;
    	      if (a == '\0')
    		goto ret0;
    	      if (a == b)
    		break;
    	      a = *++haystack;
    	      if (a == '\0')
    		goto ret0;
    shloop:;    }
              while (a != b);
    
    jin:	  a = *++haystack;
    	  if (a == '\0')
    	    goto ret0;
    
    	  if (a != c)
    	    goto shloop;
    
    	  rhaystack = haystack-- + 1;
    	  rneedle = needle;
    	  a = *rneedle;
    
    	  if (*rhaystack == a)
    	    do
    	      {
    		if (a == '\0')
    		  goto foundneedle;
    		++rhaystack;
    		a = *++needle;
    		if (*rhaystack != a)
    		  break;
    		if (a == '\0')
    		  goto foundneedle;
    		++rhaystack;
    		a = *++needle;
    	      }
    	    while (*rhaystack == a);
    
    	  needle = rneedle;		   /* took the register-poor approach */
    
    	  if (a == '\0')
    	    break;
            }
        }
    foundneedle:
      return (char*) haystack;
    ret0:
      return 0;
    }
    
    char *my_strstr(const char *haystack, const char *needle)
    {
       if ( !*needle )
       {
          return (char*)haystack;
       }
       for ( ; *haystack; ++haystack )
       {
          if ( *haystack == *needle )
          {
             const char *h = haystack, *n = needle;
             for ( ; *h && *n; ++h, ++n )
             {
                if ( *h != *n )
                {
                   break;
                }
             }
             if ( !*n )
             {
                return (char*)haystack;
             }
          }
       }
       return 0;
    }
    
    int main(void)
    {
       const char text[] = "The quick brown fox jumps over the lazy dog.";
       const char word[] = "fox";
       char *(*function[])(const char *, const char *) = {old_strstr, my_strstr, strstr};
       size_t j;
       for ( j = 0; j < sizeof function / sizeof *function; ++j )
       {
          char *found;
          int i;
          double elapsed;
          clock_t start = clock();
          for ( i = 0; i < 10000000; ++i )
          {
             found = function[j](text, word);
          }
          elapsed  = clock() - start;
          elapsed /= CLOCKS_PER_SEC;
          printf("elapsed = %g\n", elapsed);
          if ( found )
          {
             puts(found);
          }
       }
       return 0;
    }
    
    /* Borland 5.5
    elapsed = 2.013
    fox jumps over the lazy dog.
    elapsed = 1.362
    fox jumps over the lazy dog.
    elapsed = 1.192
    fox jumps over the lazy dog.
    */
    
    /* MSVC6
    elapsed = 3.284
    fox jumps over the lazy dog.
    elapsed = 2.764
    fox jumps over the lazy dog.
    elapsed = 0.862
    fox jumps over the lazy dog.
    */
    
    /* Dev-C++
    elapsed = 1.792
    fox jumps over the lazy dog.
    elapsed = 1.583
    fox jumps over the lazy dog.
    elapsed = 0.811
    fox jumps over the lazy dog.
    */
    The optimizations that are made for a particular system may not necessarily be optimal everywhere.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  6. #21
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Ok you guys use goto. I won't. There is no debate here.

  7. #22
    .
    Join Date
    Nov 2003
    Posts
    307
    Dave - you're correct. The code can't work as the best of all possible choices everywhere.
    Caching. pipelining and other gotchas get in the way of the best intentions.

    But the Gnu people are stuck with using only C to develop over a huge range of platforms.
    Maybe you don't know but there is Linux-390 for IBM mainframes. ugh. IMO.

    I was just reacting to Bubba's comment. I think I've used goto about twice in 20 years.
    The strstr algorithm example is extreme. But every Linux box is using it. Why don't you
    improve it? I already worked on memchr....

  8. #23
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Quote Originally Posted by jim mcnamara
    I was just reacting to Bubba's comment. I think I've used goto about twice in 20 years.
    Don't get me wrong, I am in favor of the measured use of goto. I'm not one to throw a tool when it does exactly what I want it to do when I want it do it. I used it several times on a recent project for exactly that reason.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  9. #24
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934

    Lightbulb

    Touché Dave_Sinkula!!!

    Maybe you haven't convinced everyone, but you certainly have convinced me. When I first saw that code, I was very much in awe. After seeing your test results, I'm no longer so awed by it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Java is 1000 times faster than c++ on my computer???
    By darin722 in forum C++ Programming
    Replies: 16
    Last Post: 06-13-2009, 12:48 AM
  2. Faster bitwise operator
    By Yarin in forum C++ Programming
    Replies: 18
    Last Post: 04-29-2009, 01:56 PM
  3. which among the following two for loops is faster?
    By vapanchamukhi in forum C Programming
    Replies: 11
    Last Post: 02-12-2009, 03:32 AM
  4. Replies: 2
    Last Post: 11-26-2001, 04:05 PM
  5. Floating point faster than fixed-point
    By VirtualAce in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 11-08-2001, 11:34 PM