itoa'd you so?

Steve smorrey at gmail.com
Fri Sep 21 22:54:09 MDT 2007


How much function call overhead is this incurring?
Would it run faster if you took the digit function and just embedded
it directly into the itoa function?

On 9/21/07, Charles Curley <charlescurley at charlescurley.com> wrote:
> On Fri, Sep 21, 2007 at 08:37:11PM -0600, Levi Pearson wrote:
> > Charles Curley <charlescurley at charlescurley.com> writes:
> > >
> > > Have we beaten this thing into the ground yet?
> >
> > Not quite yet.  Try this one:
>
> I like it. A few points.
>
> * It is base ten only. My solution is much more general. Need base 36?
>   Recall that base 10 was not specified in the original problem. But
>   your method can be adapted at the cost of:
>
>   * expanding the lookup table,
>
>   * dividing by a variable instead of an inline constant, usually
>     slower.
>
>   Also, your lookup table is probably faster than my calculation.
>
> * You have a call to abs inside your main loop. I think I see why, but
>   would you safely speed things up by moving it outside?
>
> * Your reverse function is nice, but probably slower than strcat
>   because it uses an intermediate variable. But I think you can speed
>   it up considerably by only running for (strlen (s))/2 iterations. If
>   so, it probably would be better than my temporary buffer.
>
>   If the compiler will optimize the /2 into a right shift, you get rid
>   of a divide instruction. (Or, on most 16 bit processors, a divide
>   function.) Or do it yourself with (strlen (s))>>.
>
> * I replaced my while loop with a do ... while loop, and found (to no
>   great surprise) that it is slower. I didn't check, but I doubt it
>   saved any space because of the way do ... while loops usually
>   compile. That did let me get rid of the 0 special case, making
>   things more elegant. The same might apply here.
>
> I made a few other optimizations in my version.
>
> * I now initialize i to SIZE and decrement it. This gets rid of a
>   subtraction instruction inside the main loop.
>
> * I declared some variables to be register variables. That helps on
>   Intel architecture, which is so pathetically register poor. It might
>   or might not help on register rich processors because the compiler
>   might do it for you.
>
> * I declared the function digit inline. That helped. But it would make
>   for a smaller code size only if digit isn't used elsewhere. It could
>   be a useful routine for special cases like a hex dump.
>
> --------------------------------------------------
>
> /* We depend on a pure ASCII environment here. */
> inline char digit (int d)
> {
>     register char ret = '0' + d;
>
>     /* For bases greater than 10, skip from '9' to 'A' in the ASCII
>      * table. This may have been a trick your examiner was looking
>      * for. */
>     if (ret > '9') {
>         ret += 7;
>     }
>     return (ret);
> }
>
> char *itoa (int value, char *buffer)
> {
>     register int i = SIZE;
>
>     /* I have no way of knowing the size of the incoming buffer, so I
>      * have to build in a buffer, then copy into the given one. strcat
>      * is likely more efficient and faster than strncat, and probably
>      * coded in assembler. */
>     char tmp[SIZE+1];
>
>     tmp[SIZE] = 0;
>
>     /* For negative numbers, set the sign. Having done that, do
>      * the conversion as a positive number. */
>     if (value < 0) {
>         strcat (buffer, "-");
>         value = 0 - value;
>     }
>
>     do {
>         /* Since we are starting at the right end of the string, we
>          * fill our temporary buffer from the right. This is likely
>          * another trick the examiner wanted. */
>         tmp[--i] = digit (value%base);
>         value = value/base;
>     } while (value);
>
>     strcat (buffer, &tmp[i]);
> }
> --------------------------------------------------
>
> --
>
> Charles Curley                  /"\    ASCII Ribbon Campaign
> Looking for fine software       \ /    Respect for open standards
> and/or writing?                  X     No HTML/RTF in email
> http://www.charlescurley.com    / \    No M$ Word docs in email
>
> Key fingerprint = CE5C 6645 A45A 64E4 94C0  809C FFF6 4C48 4ECD DFDB
>
>
> /*
> PLUG: http://plug.org, #utah on irc.freenode.net
> Unsubscribe: http://plug.org/mailman/options/plug
> Don't fear the penguin.
> */
>
>



More information about the PLUG mailing list