Page 1 of 2 12 Last
  • Jump to page:
    #1
  1. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,672
    Rep Power
    4273

    POTW June 2nd 2006


    Puzzle of the Week June 2nd 2006

    A programmer decides to write a program that receives data from some source and appends it to the end of a char buffer as the data is received. This is a fairly common programming occurrence (for instance, receive some data from a socket and put it in a buffer). In our simplified case, we simply generate a set of pseudo random numbers and append to the buffer.
    Code:
    #include <stdio.h>
    #include <time.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define  BIG_BUF    65536
    
    int main(void)
    {
        int i;
        char tmp[20];
        char big_buf[BIG_BUF];
    
        srand(time(NULL));
    
        for (i = 0; i < 200; i++) {
            /* Do something to receive some input into tmp */
            sprintf(tmp, "%d|", rand());
    
            /* Now append this to the buffer */
            strncat(big_buf, tmp, BIG_BUF);
        }
        /* Do something with big_buf */
        printf("%s\n", big_buf);
    
        return 0;
    }
    Questions:
    1. What are some of the inefficiences of the above code.
    2. What would you do to remove the inefficiences.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Aug 2005
    Posts
    580
    Rep Power
    98
    The function strncat() concatenates at most count characters of str2 onto str1, adding a null termination. The resulting string is returned.
    your example will possibly overflow bigbuf.
    To prevent this you could
    Code:
    #include <stdio.h>
    #include <time.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define  BIG_BUF    65536
    
    int main(void)
    {
        int i;
        char tmp[20];
        char big_buf[BIG_BUF];
    
        int sz_left = BIG_BUF;
        srand(time(NULL));
    
        for (i = 0; i < 10000 && sz_left > 0; i++) {
            /* Do something to receive some input into tmp */
            int n;
            sprintf(tmp, "%d|%n", rand(),&n);
            sz_left -= n;
            /* Now append this to the buffer */
            strncat(big_buf, tmp, sz_left);
        }
        /* Do something with big_buf */
        printf("%s\n", big_buf);
    
        return 0;
    }
    But I guess that is not what you call inefficient.
    To make it more efficient you could update the pointer where you want to write to with the number of bytes written.
    e.g.
    Code:
        char * ptr = big_buf;
        
        for (i = 0; i < 10000 && sz_left > 0; i++) {
            /* Do something to receive some input into tmp */
            int n;
            sprintf(tmp, "%d|%n", rand(),&n);
            sz_left -= n;
            /* Now append this to the buffer */
            strncat(ptr, tmp, sz_left);
            ptr += n;
        }
    This is not tested but I guess you get the idea.
    Kurt
    Last edited by ZuK; June 2nd, 2006 at 02:39 PM.
  4. #3
  5. No Profile Picture
    Closet coder
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Feb 2005
    Location
    Plantation, FL <---south florida
    Posts
    1,431
    Rep Power
    154
    EDIT: i suck :P
    Last edited by nattylife; June 2nd, 2006 at 02:57 PM.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Aug 2005
    Posts
    580
    Rep Power
    98
    Originally Posted by nattylife
    1 thing i notice, strncat fills the remaining chars of the destination string with null characters. since this string was declared rather largely in the beginning, every iteration is going to fill BIG_BUF-n characters (where n is the size of the concat'd string thus far) with nulls that were already previously set on the previous iteration.
    Does strncat() do that ?. Thought only strncpy() fills the buffer with '\0'
    Kurt
  8. #5
  9. No Profile Picture
    Closet coder
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Feb 2005
    Location
    Plantation, FL <---south florida
    Posts
    1,431
    Rep Power
    154
    Originally Posted by ZuK
    Does strncat() do that ?. Thought only strncpy() fills the buffer with '\0'
    Kurt
    yes you are right, i got them confused :o
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2004
    Posts
    287
    Rep Power
    15
    1. What are some of the inefficiences of the above code.

    The strcat isnt required?

    Code:
    	int i;
    	char big_buf[BIG_BUF];
    	int pos=0,n=0;
    
    	_set_printf_count_output(1);
    
    	srand(time(NULL));
    
    	for (i = 0; i < 200; i++, pos+=n) {
    		/* Do something to receive some input into tmp */
    		sprintf(big_buf+pos, "%d|%n", rand(),&n);
    	}
    	/* Do something with big_buf */
    	printf("%s\n", big_buf);

    Comments on this post

    • peenie agrees : Good call with the %n.
  12. #7
  13. No Profile Picture
    ......@.........
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Jun 2004
    Posts
    1,345
    Rep Power
    56
    To optimize code:
    1. run a profiler
    2. locate the bottleneck
    3. generally changing the algorithm is the best first attack.

    I made changes to the base code so it took long enough for differences to be perceptible :)
    Code:
    #include <stdio.h>
    #include <time.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define  BIG_BUF    256000
    
    int main(void)
    {
    	int i=0;
    	FILE *out=fopen("/dev/null","w");
    	char tmp[20]={0x0};
    	char big_buf[BIG_BUF]={0x0};   
    	
    	srand(time(NULL));
    
    	for (i = 0; i < 20000; i++) {
    		/* Do something to receive some input into tmp */
    		sprintf(tmp, "%d|", rand());
    
    		/* Now append this to the buffer */
    		strncat(big_buf, tmp, BIG_BUF);
    	}
    	/* Do something with big_buf */
    	fprintf(out,"%s\n", big_buf);
    
    	return 0;
    }
    The profile for this (UNIX):
    potw.c

    %Time Seconds Cumsecs #Calls msec/call Name

    92.9 1.18 1.18 __strncat20
    2.4 0.03 1.21 20002 0.00 _doprnt
    1.6 0.02 1.23 1 20.00 main
    1.6 0.02 1.25 $$mulI
    0.8 0.01 1.26 20000 0.00 _strncat
    0.8 0.01 1.27 20000 0.00 rand
    0.0 0.00 1.27 20001 0.00 _sprintf
    0.0 0.00 1.27 14 0.00 _write
    0.0 0.00 1.27 6 0.00 __errno
    0.0 0.00 1.27 4 0.00 __thread_mutex_lock
    0.0 0.00 1.27 4 0.00 __thread_mutex_unlock
    0.0 0.00 1.27 3 0.00 sbrk
    0.0 0.00 1.27 2 0.00 _getenv
    0.0 0.00 1.27 2 0.00 open
    0.0 0.00 1.27 1 0.00 ___exit
    0.0 0.00 1.27 1 0.00 __findbuf
    0.0 0.00 1.27 1 0.00 __fwrite_unlocked
    0.0 0.00 1.27 1 0.00 __syscall_err
    0.0 0.00 1.27 1 0.00 _bufsync
    0.0 0.00 1.27 1 0.00 _findiop
    0.0 0.00 1.27 1 0.00 _fopen
    0.0 0.00 1.27 1 0.00 _fprintf
    0.0 0.00 1.27 1 0.00 _monitor
    0.0 0.00 1.27 1 0.00 _start
    0.0 0.00 1.27 1 0.00 _wrtchk
    0.0 0.00 1.27 1 0.00 creat64
    0.0 0.00 1.27 1 0.00 isatty
    0.0 0.00 1.27 1 0.00 malloc
    0.0 0.00 1.27 1 0.00 memmove
    0.0 0.00 1.27 1 0.00 srand
    0.0 0.00 1.27 1 0.00 sysconf
    The bottleneck is _strncat20 a library call.
  14. #8
  15. No Profile Picture
    ......@.........
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Jun 2004
    Posts
    1,345
    Rep Power
    56
    Next, change the algorithm. Note: this algorithm can overflow, but will not as written with a biiig buffer.
    Code:
    #include <stdio.h>
    #include <time.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define  BIG_BUF    256000
    
    int main(void)
    {
    	int i=0;
    	FILE *out=fopen("/dev/null","w");
    	char tmp[20]={0x0};
    	char big_buf[BIG_BUF]={0x0};   
        char *p=big_buf;    
        char *q=NULL;	
    
    	srand(time(NULL));
    
    	for (i = 0; i < 20000; i++) {
    		/* Do something to receive some input into tmp */
    		sprintf(tmp, "%d|", rand());
    
    		/* Now append this to the buffer */
    		for(q=tmp;*q;q++)
    		{
    			*p++=*q++;
    		}
    	}
    	/* Do something with big_buf */
    	fprintf(out,"%s\n", big_buf);
    
    	return 0;
    }
    Profile:
    Code:
    potw2.c   
     %Time Seconds Cumsecs  #Calls   msec/call  Name
    
      71.4    0.05    0.05   20002        0.00  _doprnt
      14.3    0.01    0.06       1       10.00  main
       3.6    0.00    0.06       1        2.50  srand
       0.0    0.00    0.06   20001        0.00  sprintf
       0.0    0.00    0.06   20000        0.00  _rand
       0.0    0.00    0.06       8        0.00  write
       0.0    0.00    0.06       6        0.00  __errno
       0.0    0.00    0.06       4        0.00  __thread_mutex_lock
       0.0    0.00    0.06       4        0.00  __thread_mutex_unlock
       0.0    0.00    0.06       3        0.00  sbrk
       0.0    0.00    0.06       2        0.00  _getenv
       0.0    0.00    0.06       2        0.00  open
       0.0    0.00    0.06       1        0.00  ___exit
       0.0    0.00    0.06       1        0.00  __findbuf
       0.0    0.00    0.06       1        0.00  __fwrite_unlocked
       0.0    0.00    0.06       1        0.00  __syscall_err
       0.0    0.00    0.06       1        0.00  _bufsync
       0.0    0.00    0.06       1        0.00  _findiop
       0.0    0.00    0.06       1        0.00  _fopen
       0.0    0.00    0.06       1        0.00  _monitor
       0.0    0.00    0.06       1        0.00  _start
       0.0    0.00    0.06       1        0.00  _wrtchk
       0.0    0.00    0.06       1        0.00  creat64
       0.0    0.00    0.06       1        0.00  fprintf
       0.0    0.00    0.06       1        0.00  isatty
       0.0    0.00    0.06       1        0.00  malloc
       0.0    0.00    0.06       1        0.00  memmove
       0.0    0.00    0.06       1        0.00  sysconf
    The runtime on this is now 20+ times faster:
    1.27 seconds vs .06 seconds.

    The lost time = algorithm change.
    Last edited by jim mcnamara; June 2nd, 2006 at 03:47 PM.
  16. #9
  17. No Profile Picture
    ......@.........
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Jun 2004
    Posts
    1,345
    Rep Power
    56
    Last comment:
    optimizing is cool. Most of the time this coolness is misguided. Only optimize when there is a reason, cool is NOT one of those reasons.

    You'll also notice that the code does have a potential overflow because there is no bounds checking, except that 20000 outputs from rand() with a '|' appended can never exceed 120000 bytes (RAND_MAX is 32767, five digits, plus one for the pipe=6 * 20000). I oversized the buffer bigtime. In some environments this is bad.
  18. #10
  19. Super User
    Devshed Novice (500 - 999 posts)

    Join Date
    Sep 2004
    Posts
    648
    Rep Power
    76
    I think everyone has pretty much already nailed it, but I'll have a go anyway.

    The real inefficiency comes from knowing how strncat works. Internally, it finds the length of the string manually, so it knows where to append the source string. Here is the strncat source from the Linux kernel version 2.1:

    Code:
    char * strncat(char *dest, const char *src, size_t count)
         {
          char *tmp = dest;
    
          if (count) {
         
    while (*dest) dest++;
    while ((*dest++ = *src++)) {
    if (--count == 0) {
    *dest = '\0';
    break; }
    } } return tmp; }
    Each time you call strncat within the loop, it has to recalculate the current length of the string in the large buffer to know where to append the source buffer at. The solution, as mentioned before, is to use a pointer to the end of the destiation string.

    Besides the potential buffer overflow, your code snippet, even with Zuk's changes, won't always work unless you first initialize big_buf to 0.
  20. #11
  21. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Jan 2004
    Location
    Constant Limbo
    Posts
    989
    Rep Power
    364
    I may be way off here, but I'm assuming that the '|' separator is for future parsing, so based on that I remove the character buffers altogether and deal with the original data.

    Code:
    #include <stdlib.h>
    #include <time.h>
    
    #define IN_SZ 200
    
    int main (void)
    {
       int i = 0;
       int buf[IN_SZ];
    
       srand(time(NULL));
    
       while (i < IN_SZ)
          buf[i++] = rand();
    
       /* do something with buf */
    
       return 0;
    }
    If you needed to deal with characters rather than numbers later on, you could do the sprinting then and save yourself a run with sscanf.

    [edit] Oops. After a re-read of the original problem, the random numbers were just to represent incomming data. So, in _this_ case it works, but for the intended application - prolly not :D
    Last edited by L7Sqr; June 2nd, 2006 at 04:14 PM.
    True happiness is not getting what you want, it's wanting what you've already got.

    My Blog
  22. #12
  23. Wiser? Not exactly.
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    May 2001
    Location
    Bonita Springs, FL
    Posts
    5,970
    Rep Power
    4035
    Originally Posted by jim mcnamara
    except that 20000 outputs from rand() with a '|' appended can never exceed 120000 bytes (RAND_MAX is 32767, five digits, plus one for the pipe=6 * 20000). I oversized the buffer bigtime. In some environments this is bad.
    Note, RAND_MAX isn't always 32767, or even five digits for that matter. It depends on the compiler. GCC for instance (on my system anyway) has a RAND_MAX of 2147483647, which is 10 digits.

    11 * 20000 = 220,000

    Still happens to be less than your buffer, but not by so much now. Another compiler could probably go bigger and thus actually overflow.

    The ideal way to solve the strncat problem and still maintain speed is to do as was said above, and keep a pointer which points at the terminating \0 character. Then the function doesn't have to search for the null each call, it's already there. Combine that with the change where you monitor how much of the buffer is still available and use that as the length argument to strncat and you solve both the speed problem and the overflow problem.

    Code:
    #include <stdio.h>
    #include <time.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define  BIG_BUF    65536
    
    int main(void)
    {
            int i, n;
            char tmp[20];
            char big_buf[BIG_BUF];
            int buf_rem=BIG_BUF;
            char *buf_start=big_buf;
    
            srand(time(NULL));
    
            for (i = 0; i < 2000; i++) {
                    /* Do something to receive some input into tmp */
                    n=sprintf(tmp, "%d|", rand());
    
                    /* Now append this to the buffer */
                    strncat(buf_start, tmp, buf_rem);
                    buf_start += n;
                    buf_rem -= n;
            }
            /* Do something with big_buf */
            printf("%s\n", big_buf);
    
            return 0;
    }
    Last edited by kicken; June 2nd, 2006 at 08:58 PM.
    Recycle your old CD's, don't just trash them



    If I helped you out, show some love with some reputation, or tip with Bitcoins to 1N645HfYf63UbcvxajLKiSKpYHAq2Zxud
  24. #13
  25. Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Apr 2004
    Posts
    1,676
    Rep Power
    134
    Jim: Have you got an strlcat to compare with your algorithm change? I'm curious how a pseudo-standard possibly hand-optimized assembly version of an strlcat (if available) might compare, since they are fairly similar.
    Any advertisement triggered by IntelliTxt in this post is not endorsed by the author of this post.
  26. #14
  27. I kept my Swingline stapler
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2004
    Location
    Northern California
    Posts
    254
    Rep Power
    130
    In some environments it can be bad to declare large amounts of data on the stack.
    Code:
    char big_buf[BIG_BUF];
    In these environments it would be better to use the new keyword or malloc function to place these large "chunks" of data on the heap.
    Code:
    char* big_buff = (char*) malloc(sizeof(char)*BIG_BUF);
    // check if malloc succeeded
    // free the memory you allocated when you are done with it
    If memory is a constraint, but speed or efficiency is not, then you might be better off using a data structure that can grow as needed as opposed to an array. Then you can increase its size as you add the data that is input to it.
  28. #15
  29. Google Relay Server
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Oct 2003
    Location
    Oh christ I don't even know any more.
    Posts
    1,812
    Rep Power
    439
    Code:
    #include <stdio.h>
    #include <time.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define  BIG_BUF    65536
    
    // problems:
    //   1. stability: strncats number argument is the max number of source chars
    //      to copy, which won't prevent overflow in big_buf.
    //   2. stability: it is assumed that rand() will return a number that is less
    //      than 10^19 and greater than -10^18, otherwise tmp will overflow.
    //   2. inefficiency: strncat will rescan big_buf to find the end every time,
    //      which is silly because you can easily keep track of the string on the
    //      fly.
    //   3. inefficiency: sprintf is probably not -that- slow, but its also not
    //      necessarily that fast. we already know that we are converting from an
    //      int so using a powerful function like sprintf may be overkill. but on
    //      the other hand, sprintf gets the job done and conveniently returns the
    //      string length.
    //   4. inefficiency: while allocating big_buf on the stack is virtually a
    //      free operation (since you just need to increment the stack pointer a
    //      few extra bytes), accessing it is slightly slower than having a
    //      statically allocated buffer. in most cases, having a static big_buf
    //      means the compiler knows the address at compile_time, while having it
    //      non-static on the stack means the address is not available until
    //      runtime. that means the address must be computed from the stack
    //      pointer every time it is accessed. note: making it static means that
    //      the function is no longer reentrant or threadsafe. we'll assume that
    //      is ok. this is stupid and nitpicky and negligible (and might not
    //      make any difference on newer processors) but whatever.
    
    int main(void)
    {
    
      int i;
      static char big_buf[BIG_BUF], *pos, *end;
    
      srand(time(NULL));
      pos = big_buf;
      end = big_buf + BIG_BUF - 1;
    
      for (i = 0; i < 200 && pos <= end; ++ i) {
    
        /* write string and store end position in npos. it is easy to calculate
         * the number of bytes remaining to prevent buffer overflows. we'll write
         * to the current string position. */
        pos += snprintf(pos, end - pos + 1, "%i|", rand());
    
      }
    
      /* this is necessary since snprintf() won't terminate the string if the
       * buffer was too small. use *end since we know its in big_buf, and
       * also since the string will already be terminated properly if snprintf
       * succeeded the whole way. */
      *end = 0;
    
      /* do something with big_buf. */
      printf("%s\n", big_buf);
    
      return 0;
    
    }
    Answers to questions are in code comments. Note that at no point does the code ever search for a null in the buffer string, which strcat/strncat will always do regardless of whether or not the null is the first character (you may know this, but strcat doesn't).

    One additional point to answer question #2:

    While I didn't do this above, a much faster integer -> string algorithm, implemented in assembler, can be found here:

    http://www.df.lth.se/~john_e/gems/gem003e.html

    Using that will speed things up even more. You'd modify that algorithm to not go beyond the buffer by always comparing edi to the end, or by decrementing and testing a counter. I didn't use it because I had trouble porting that to C and keeping it portable (got hung up on the quads) and also I figure pointing out that it exists and where I would use it is just as good as actually doing it for this puzzle, right? ;)

    But in looking at the other posts it seems like animatronic at least got it before me, and its much slicker with the %n, although it doesn't have the overrun protection.
    Last edited by peenie; June 10th, 2006 at 06:25 PM.
    OMG RAVER CHICKS!!
    On a related note: C/C++ Programming Tutorials


    "Science is based on reality staying the same, and Nature ignores what humans vote upon." -- Bill Beaty
    "Three litres of sherry up the butt can only be described as astounding." -- Darwin Awards
Page 1 of 2 12 Last
  • Jump to page:

IMN logo majestic logo threadwatch logo seochat tools logo