🚀 go-pugleaf

I timed the attached program on a number of platforms to compare the
relative performance of their system library versions of atoi() and
sprintf(str,"%d",i) against a hand-coded C version.  In most cases, it
was easy to beat the system library-- perhaps losing some generality,
but I'm surprised how much better the simple hand-coded C version does
on some platforms.  This generality shouldn't cost you more than a
factor of 2, should it?

OS & MACHINE		USER TIMES 	RATIO
======================	==============	=====
IRIX 5.3, SGI Indy       6.23 / 10.84	.574
FreeBSD 2.0.5, Pent.90	10.13 / 30.14	.336
OSF1 3.2, DEC-ALPHA300X 13.0  / 22.7	.572
LINUX 1.2.11, Pentium90 13.4  /180.3	.074
AIX 3.2.5, PowerPC-41T  17.4  / 19.7	.883
ULTRIX 4.2, DEC-MIPS    28.8  /	69.0	.417
SUNOS 4.1.2, SPARC-10	45.0  / 51.2	.878
SUNOS 4.1.2, SPARC-2    126.2 / 84.4	1.50
				^^^^
				^^^^ system library atoi()/sprintf()
			^^^^
			^^^^ hand-coded C versions  gcc -O3


Someone (aorenste@sunspot.tiac.net) has since posted a version of
the program which beats socks off the system library implementations.
(I'll attach his routines too.)  Which platform would you rather have?


OS & MACHINE		USER TIMES 	RATIO
======================	==============	=====
IRIX 5.3, SGI Indy       3.68 / 10.84	.339
LINUX 1.2.11, Pentium90	 4.6  /180.3	.025
OSF1 3.2, DEC-ALPHA300X	 5.9  / 22.7	.259	
SUNOS 4.1.2, SPARC-10	 8.3  / 51.2	.162
AIX 3.2.5, PowerPC-41T	18.5  / 19.7	.939
ULTRIX 4.2, DEC-MIPS	20.0  /	69.0	.289


(Could someone please re-run the Linux / Pentium 90 timing?  
Our library probably wasn't configured right.)

-George

PS: Strange but true, Pentium90s makes a high pitched whine when I run 
certain CPU-bound jobs, e.g. testing the library 'a.out -10000000'
Any idea why?   It can be quite earritating.

----------------------------------------------------------------
graduate student, Computer Science & Engineering, Univ. of Washington













/****************************************************************
# begin Makefile

a.out:
        gcc -O3 contest.c 

test:   a.out
        time  a.out  10000
        time  a.out -10000

your:   a.out
        time  a.out  1000000

lib:    a.out
        time  a.out -1000000

contest: a.out
        echo "This may take around 5 minutes..."
        time  a.out  1000000
        time  a.out -1000000
        echo "Divide the first user time by the second."

# end Makefile 
#
# Here's a csh alias for extracting & using Makefiles stored inside .c files: 
# Usage: inmake contest.c [make options]
#
# alias inmake awk "'/begin Makefile/,/end Makefile/{print}' \!:1 \
#       >/tmp/InMakefile.$$; make -f /tmp/InMakefile.$$ \!:2*"
****************************************************************/


#include <stdio.h>
#include <stdlib.h>

extern int  fast_atoi(char *string);    /* fast atoi() */

extern int  fast_itoa(char *buf, int i); /* fast sprintf(buf,"%d",i); */


int  main( int argc, char *argv[])
{
  char buf[80];
  int i,j;
  int N = 10000;                /* # of iterations / 2 */
  if (argc > 1)  N = atoi(argv[1]);

  /* test your code a bit */
  if (fast_atoi("2147483647") != 2147483647)  exit(1);
  if (fast_atoi(" 0")         != 0)           exit(1);
  if (fast_atoi("00123")      != 123)         exit(1);
  if (fast_atoi("-2147483647")!= -2147483647) exit(1);
  
  if (N < 0) {                  /* negative --> time library code */
    N = -N;
    for (i = -N; i < N; i++) {
      sprintf( buf, "%d", i);
      j = atoi(buf);
      if (i != j)  exit(1);     /* error (unlikely in library code) */
    }
  }
  else {                        /* positive --> time your code */
    for (i = -N; i < N; i++) {
      fast_itoa( buf, i);
      j = fast_atoi(buf);
      if (i != j)  exit(1);     /* error */
    }
  }
  return 0;
}


int  fast_atoi(char *string)    /* fast version of atoi() */
{ 
    int number=0;
    char negative=0;

    while (*string==32) string++;  /* skip leading spaces */
    if (*string=='-')              /* negative ? */
        {negative=1;string++;}
    else
        negative=0;

    while (isdigit(*string))
    {
        number*=10;
        number+=(*string)-48;       /* make char to int and add to number */
        string++;
    }
    if (negative) number=-number;
    return number;
} 


int  fast_itoa(char *buf, int i) /* fast version of sprintf(buf,"%d",i); */
{ 
    int nr_written=0;
    char tmp[40];
    char *pointer;
    pointer=tmp;
    *pointer++=0;

    if (i<0)
    {
        i=-i;
        *buf++='-';
        nr_written++;
    }

    while (i)
    {
        nr_written++;
        *pointer++=(i%10)+48;
        i/=10;
    }
    pointer--;

    while (*buf++=*pointer--);    /* copy number (reversed) from tmp to buf */
    return nr_written;
}













And Aaron's faster code:

/* fast_itoa & fast_atoi by Aaron Orenstein (aorenste@sunspot.tiac.net) */
/* Given to the public domain */

#include <ctype.h>

/* WARNING: Assuming 32-bit ints */

/* ------------------------------------------------------------------------ */

int  fast_atoi(register char *string)	/* fast version of atoi() */
{ 
  register int total=0;
  int neg=0;

  while(isspace(*string)) string++;
  if(*string=='-')
    {
      neg=1;
      string++;
    }

  while(isdigit(*string))
    total=(total*10)+*string++-'0';

  if(neg)
    return -total;
  else
    return total;
} 

/* ------------------------------------------------------------------------ */

#define DECODE_N(n) \
 decode1##n: \
  if(i<5##n) \
    if(i<3##n) \
      if(i<2##n) \
        if(i<1##n) \
          *ptr++='0'; \
        else \
	  { *ptr++='1'; i-=1##n; } \
      else			/* 2##n <= i < 3##n */ \
	{ *ptr++='2'; i-=2##n; } \
    else			/* 3##n <= i < 5##n */ \
      if(i<4##n) \
	{ *ptr++='3'; i-=3##n; } \
      else			/* 4##n <= i < 5##n */ \
	{ *ptr++='4'; i-=4##n; } \
  else				/* i>=5##n */ \
    if(i<7##n) \
      if(i<6##n) \
	{ *ptr++='5'; i-=5##n; } \
      else			/* 6##n <= i < 7##n */ \
	{ *ptr++='6'; i-=6##n; } \
    else			/* 7##n <= i < 10##n */ \
      if(i<9##n) \
	if(i<8##n)	 \
	  { *ptr++='7'; i-=7##n; } \
	else			/* 8##n <= i < 9##n */ \
	  { *ptr++='8'; i-=8##n; } \
      else			/* 9##n <= i < 10##n */ \
	{ *ptr++='9'; i-=9##n; }

/* fast version of sprintf(buf,"%d",i); */
int  fast_itoa(char *buf, register int i)
{ 
  register char *ptr=buf;
  register int place=9;

  if(i==0)
    {
      *ptr++='0';
      *ptr=0;
      return 1;
    }

  if(i<0)
    {
      *ptr++='-';
      i=-i;
    }

  if(i<10) goto decode1;
  if(i<100) goto decode10;
  if(i<1000) goto decode100;
  if(i<10000) goto decode1000;
  if(i<100000) goto decode10000;
  if(i<1000000) goto decode100000;
  if(i<10000000) goto decode1000000;
  if(i<100000000) goto decode10000000;
  if(i<1000000000) goto decode100000000;

  if(i<2000000000)
    { *ptr++='1'; i-=1000000000; }
  else				/* 2000000000 <= i < 2147483648 */
    { *ptr++='2'; i-=2000000000; }

  DECODE_N(00000000)
  DECODE_N(0000000)
  DECODE_N(000000)
  DECODE_N(00000)
  DECODE_N(0000)
  DECODE_N(000)
  DECODE_N(00)
  DECODE_N(0)

 decode1:
  *ptr++=i+'0';

 done:
  *ptr=0;
  return ptr-buf;
}