RE: generic strncpy - off-by-one error

[Peter Kjellerstedt <peter.kjellerstedt@axis.com>]

[-- Attachment #1: Type: text/plain, Size: 6327 bytes --]

> -----Original Message-----
> From: Willy Tarreau [mailto:willy@w.ods.org] 
> Sent: Thursday, August 14, 2003 21:45
> To: Peter Kjellerstedt
> Cc: 'Timothy Miller'; linux-kernel mailing list
> Subject: Re: generic strncpy - off-by-one error
> 
> On Thu, Aug 14, 2003 at 11:34:50AM +0200, Peter Kjellerstedt wrote:
>  
> > char *strncpy(char *dest, const char *src, size_t count)
> > {
> > 	char *tmp = dest;
> > 
> > 	while (count) {
> > 		if (*src == '\0')
> > 			break;
> > 
> > 		*tmp++ = *src++;
> > 		count--;
> > 	}
> > 
> > 	while (count) {
> > 		*tmp++ = '\0';
> > 		count--;
> > 	}
> > 
> > 	return dest;
> > }
> > 
> > Moving the check for *src == '\0' into the first loop seems
> > to let the compiler reuse the object code a little better
> > (may depend on the optimizer). Also note that your version
> > of the second loop needs an explicit  comparison with -1,
> > whereas mine uses an implicit comparison with 0.
> 
> Well, if you're at this level of comparison, then I may object that
> 'count' is evaluated twice when jumping from one loop to the 
> other one.
> 
> *Algorithmically* speaking, the most optimal code should be :
> 
> char *strncpy(char *dest, const char *src, size_t count)
> {
>         char *tmp = dest;
>         if (unlikely(!count))
>                 goto end;
> loop1:
>         if ((*tmp = *src++) == '\0')
> 		goto next;
>         tmp++;
>         if (likely(--count))
> 		goto loop1;
> 	else
> 		goto end;
> loop2:
>         *tmp = '\0';
> next:
>         tmp++;
>         if (likely(--count))
> 		goto loop2;
> end:
>         return dest;
> }

I hope we do not opt to go with this version. :)

> (sorry for those who hate gotos). Look at it : no test is 
> performed twice, no byte is read nor written twice in any 
> case. The assembly code produced is optimal on x86 (well, 
> in fact we could delete exactly one conditionnal jump because 
> the compiler doesn't know how to reuse them for several tests).
> 16 inlinable instructions (= excluding function in/out) which 
> can be executed 2 at a time if your CPU has 2 pipelines. about
> 3 cycles/copied byte, 2 cycles/filled byte.

It does not give optimal code for CRIS for the second loop.
It can easily be fixed by combining loop2 and next (which
will cause tmp to be assigned twice when changing loop),
but I know this was not the intent of this exercise.

> Unfortunately, it fools branch predictors and prefetch 
> mechanisms found in today's processors, so it results in 
> slower code than yours (at least on athlon and P3). Perhaps 
> it would be fast on older processors, I don't know.
> 
> All that demonstrates that whatever your efforts in helping 
> the optimizer, the only meaningful result is the benchmark. 
> Number of bytes and speculations on the reusability of 
> information between lines of codes are not what makes our
> programs fast anymore :-(

It was easier some years ago, wasn't it? ;)

> > Testing on the CRIS architecture, your version is 24 instructions,
> > whereas mine is 18. For comparison, Eric's one is 12 and the
> > currently used implementation is 26 (when corrected for the
> > off-by-one error by comparing with > 1 rather than != 0 in the
> > second loop).
> 
> Just out of curiosity, can the CRIS architecture execute 
> multiple instructions per cycle ? have you tried to determine 

No it cannot. :( Our ETRAX 100LX processor which uses the
CRIS architecture is a 100 MIPS processor without most of
today's fancy processor optimizations like multiple instructions,
branch prediction etc. It is designed for embedded products.

> the dependencies between the instructions ? Did you time the 
> different functions ? (yours is rather fast on x86 BTW).

No I didn't, but I have done it now.

I made a program that called the respective strncpy() 
implementation a number of times copying a 100 byte string
into a 1000 byte buffer. For each function I tested with
copying 50, 100, 200 and 1000 bytes. I have attached the 
source to this mail if anyone wants to make sure I did not
screw up the benchmarking too much... ;)

This table shows the times in seconds to call each function
500,000 times for CRIS:

                   50         100         200        1000
Original        3.123906    6.138616    9.146204   33.323051  
Eric's          2.602632    5.105367    9.637701   45.910798  
Timothy's       3.125003    6.128571    9.147905   33.325337  
My first        2.868396    5.626149    8.138134   28.276760  
My second (for) 2.622412    5.129988    7.636364   27.786745  
Algorithmic     2.597808    5.119332    7.627300   27.785999  

Going by these numbers, Eric's version is a good candidate 
for the copying phase, but loses out badly when it comes to
the filling. The best versions here seem to be my version
with the for loops and your algorithmic version which both
give almost identical numbers (but look below for more on
the algorithmic version).

This table shows the times in seconds to call each function
20,000,000 times for my P4 2.53GHz:

                   50         100         200        1000
Original        2.900444    5.475311    9.095701   37.462796  
Eric's          2.988404    5.637352    9.576857   37.580639  
Timothy's       2.929508    5.534824    9.157147   36.836899  
My first        2.951068    5.511169    8.321381   29.669017  
My second (for) 2.921675    5.531486    8.296728   28.940855  
Algorithmic     3.911937    7.343235   12.699275   54.288284  

The interesting thing here is that the original code wins
the copying phase. But the numbers for the copying phase for
the first five versions are so similar, that I doubt one can 
say one is better than the other. However, when it comes to
the filling phase my versions are back in the lead. These 
numbers also shows very clearly what you stated above about
branch predictions, as the algorithmic version loses out
badly here.

All these numbers taken together, I would say that my version
with the for loops seems to be the overall winner. :)

> To conclude, I would say that if we want to implement really 
> fast low-level primitives such as str*, mem*, ... there's 
> nothing better than assembly associated with benchmarks on 
> different CPU architectures and models.
> 
> But I don't know if strncpy() is used enough to justify that...

I agree

> Regards,
> Willy

//Peter


[-- Attachment #2: testa.c --]
[-- Type: application/octet-stream, Size: 5293 bytes --]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <sys/types.h>

#include <sys/time.h>

char *strncpy0(char *dest, const char *src, size_t count)
{
  char *tmp = dest;

  while (count-- && (*tmp++ = *src++) != '\0')
    /* nothing */;

  return dest;
}

char *strncpy0a(char *dest, const char *src, size_t count)
{
  char *tmp = dest;

  while (count && (*dest++ = *src++) != '\0')
    count--;

  while (count > 1)
  {
    *dest++ = 0;
    count--;
  }

  return tmp;
}

char *strncpy0b(char *dest, const char *src, size_t count)
{
  char *tmp = dest;

  while (count && (*tmp++ = *src++) != '\0')
    count--;

  while (count > 1)
  {
    *tmp++ = 0;
    count--;
  }

  return dest;
}

char *strncpy0x(char *dest, const char *src, size_t count)
{
  char *tmp = dest;

  while (count)
  {
    if (!(*tmp = *src++))
      break;
    tmp++;

    count--;
  }

  return dest;
}

char *strncpy1(char *dest, const char *src, size_t count)
{
  char *tmp = dest;

  while (count)
  {
    if ((*tmp = *src))
      src++;
    tmp++;

    count--;
  }

  return dest;
}

char *strncpy1x(char *dest, const char *src, size_t count)
{
  char *tmp = dest;

  for (; count; count--)
  {
    if ((*tmp = *src))
      src++;
    tmp++;
  }

  return dest;
}

char *strncpy2(char *dest, const char *src, size_t count)
{
  char *tmp = dest;

  while (count--)
  {
    if ((*tmp++ = *src))
      src++;
  }

  return dest;
}

char *strncpy3(char *dest, const char *src, size_t count)
{
   if (count)
   {
      char *tmp = dest;

      while (1)
      {
         *tmp = *src;
         if (*src)
           src++;
         tmp++;
         if (!count--)
           break;
      }
   }

   return dest;
}

char *strncpy4(char *dest, const char *src, size_t count)
{
   if (count)
   {
      char *tmp = dest;

      do
      {
         if ((*tmp = *src))
           ++src;
         ++tmp;
      } while (--count);
   }

   return dest;
}

char *strncpy5(char *dest, const char *src, size_t count)
{
  char *tmp = dest;

  while (count && *src)
  {
    count--;
    *tmp++ = *src++;
  }

  while (count--)
  {
    *tmp++ = 0;
  }

  return dest;
}

char *strncpy5w(char *dest, const char *src, size_t count)
{
  char *tmp = dest;

  while (count)
  {
    if (*src == '\0')
      break;

    *tmp++ = *src++;
    count--;
  }

  while (count)
  {
    *tmp++ = 0;
    count--;
  }

  return dest;
}

char *strncpy5x(char *dest, const char *src, size_t count)
{
  char *tmp = dest;

  while (count)
  {
    count--;
    if (!(*tmp++ = *src++))
      break;
  }

  while (count)
  {
    count--;
    *tmp++ = 0;
  }

  return dest;
}

char *strncpy5y(char *dest, const char *src, size_t count)
{
  char *tmp = dest;

  for (; count && *src; count--)
    *tmp++ = *src++;

  for (; count; count--)
    *tmp++ = '\0';

  return dest;
}

#define likely(x)    __builtin_expect(!!(x),1)
#define unlikely(x)  __builtin_expect(!!(x),0)

char *strncpy6(char *dest, const char *src, size_t count)
{
  char *tmp = dest;

  if (unlikely(!count))
    goto end;

loop1:
  if ((*tmp = *src++) == '\0')
    goto next;
  tmp++;
  if (likely(--count))
    goto loop1;
  else
    goto end;

loop2:
  *tmp = '\0';
next:
  tmp++;
  if (likely(--count))
    goto loop2;

end:
  return dest;
}

char *strncpy6x(char *dest, const char *src, size_t count)
{
  char *tmp = dest;

  if (unlikely(!count))
    goto end;

loop1:
  if ((*tmp = *src++) == '\0')
    goto loop2;
  tmp++;
  if (likely(--count))
    goto loop1;
  else
    goto end;

loop2:
  *tmp++ = '\0';
  if (likely(--count))
    goto loop2;

end:
  return dest;
}

void time_it(char *(*func)(char *dest, const char *src, size_t count),
             size_t size)
{
  struct timeval start;
  struct timeval end;
  long sec, usec;
  static char *string = "asdl hfaslkfh alksjfh laksjh lkajsdflkasflksdf ljhfljshf laksflaksfhlaksjhflaksfh lakshf lkds hflsd";
  static char buffer[1000];
#ifdef __CRIS__
  int count = 500000;
#else
  int count = 20000000;
#endif

  if (size > sizeof buffer)
  {
    fprintf(stderr, "Buffer too small!\n");
    exit(1);
  }

  gettimeofday(&start, NULL);

  while (count)
  {
    func(buffer, string, size);
    count--;
  }

  gettimeofday(&end, NULL);

  sec = end.tv_sec - start.tv_sec;
  if ((usec = end.tv_usec - start.tv_usec) < 0)
  {
    sec--;
    usec += 1000000;
  }

  printf("%3ld.%06ld  ", sec, usec);
  fflush(stdout);
}

void do_it(const char *name,
           char *(*func)(char *dest, const char *src, size_t count))
{
  printf("%-12s  ", name);
  fflush(stdout);
  time_it(func, 50);
  time_it(func, 100);
  time_it(func, 200);
  time_it(func, 1000);
  printf("\n");
}

#define TIME_IT(func) time_it(#func, func)

int main(int argc, char* argv[])
{
  do_it("Original", strncpy0a);
  do_it("Eric's", strncpy1);
  do_it("Timothy's", strncpy5);
  do_it("My first", strncpy5x);
  do_it("For loops", strncpy5y);
  do_it("Algorithmic", strncpy6);

  exit(0);
}