Thread: Testpad for itoa()

Originally Posted by cyberfish

In decreasing order of importance:

1. You really should use random numbers. You can even compare all answers with reference answers (from a slow, known correct implementation) if you want. This is a more systematic testing method.
2. itoa is a bad name. Some compilers have a function named itoa I believe.
3. You may want to pass the length of the buffer, along with the buffer, to the function, since the function has no way of finding that out. You can't just guarantee it will be larger than the longest answer either, since some implementations may use the buffer as scratch pad, and do clever things with it.
4. clock() measures different things on different platforms. For example, I don't remember which is which, but GCC's clock() measures CPU time on one platform, and wall time on another (Linux/Windows). They are only the same if the program takes 100% CPU all the time, and is the only process executing. There is no portable way to do accurate timing, but on Windows you can use GetSystemTimeAsFileTime. The rest of the world has gettimeofday.

There is more to the solution to issue 1 than you'd think though. If you use random numbers equally distributed over the entire range of an int then you'll get very few numbers close to 0 and as such might not test any one or two digit cases for example.
You can either test say -9999 to 9999 explicitly first (along with other specific cases like min and max), or you can generate the values from a different distribution such as normal distribution.

With number 3, in the real world it could be handled by documentation perhaps in the form of comments that the buffer must always have room for 15 characters (1 minus sign, 10 digits, 3 commas, 1 null terminator).

So x64 cut it down to 265 ms? Nice.

Originally Posted by iMalc

There is more to the solution to issue 1 than you'd think though. If you use random numbers equally distributed over the entire range of an int then you'll get very few numbers close to 0 and as such might not test any one or two digit cases for example.
You can either test say -9999 to 9999 explicitly first (along with other specific cases like min and max), or you can generate the values from a different distribution such as normal distribution.

With number 3, in the real world it could be handled by documentation perhaps in the form of comments that the buffer must always have room for 15 characters (1 minus sign, 10 digits, 3 commas, 1 null terminator).

Probably tests based on some range between -n to +n, plus the particular cases
like zero, int_min, int_max, plus a random serie of numbers in 3-4 different ranges
could be exaustive enough.

With number 3 I used the "always room for 15 characters" option.

@Elysia

So x64 cut it down to 265 ms? Nice.

Yes, X64 option is a bit faster even on my IA32 machine. :-)

Your real X64 machine should give an impressive 80-90 ms for
iMalc version. Did you test it?

And a last thing. Your version can spare some ms getting rid of
the bool neg altogheter. Without you have:

Code:

                    Testing version : Elysia
                 ------------------------------
 Testing on Intel Core 2 Duo E6600 2.4 Ghz IA32
 OS = Windows 7 Ultimate 64 bit  --  Compiler = Pelles C 6.00.4

 The value of num is: -1234567890

 The formatted value of num is: -1,234,567,890

 Elapsed time: 897 ms to perform 10,000,000 cycles
 -------------------------------------------------------

 handling 0 ---> 0
 handling 12 ---> 12
 handling 256 ---> 256
 handling 1000 --> 1,000
 handling 1000000 ---> 1,000,000
 handling 1000000000 ---> 1,000,000,000
 handling 2147483647 -> 2,147,483,647
 handling -2147483648 -> -2,147,483,648

Changing the appropriate code:

Code:

	if (num < 0)
	{
//		neg = true;
	        copy_to++;
		buffer[0] = '-';
		newnum = -num; // transform number to positive if negative
	}

Without inlining, I got 198 ms for iMalc's code.
When I forced it inline, the compiler was smart enough to optimize it all away, so 0 ms.

Code:

                    Testing version : Elysia
                 ------------------------------
 Testing on AMD Athlon II X2 250 (3 GHz)
 OS = Windows 7 Ultimate 64 bit  --  Compiler = Microsoft Visual Studio 2010

 The value of num is: 3734

 The formatted value of num is: 3,734

 Elapsed time: 355 ms to perform 10,000,000 cycles
 -------------------------------------------------------

 handling 0 ---> 0
 handling 12 ---> 12
 handling 256 ---> 256
 handling 1000 --> 1,000
 handling 1000000 ---> 1,000,000
 handling 1000000000 ---> 1,000,000,000
 handling 2147483647 -> 2,147,483,647
 handling -2147483648 -> -2,147,483,648
Press any key to continue . . .

That was iMalc's code. The compiler optimized away the function because it thought it didn't do anything worth while.
But you should understand that it's impossible to guarantee a deterministic time since we're using random numbers. You would have to have a pattern, such as x numbers of y length, etc.

Originally Posted by Elysia

That was iMalc's code. The compiler optimized away the function because it thought it didn't do anything worth while.

You mean that your X64 ultra-speed mega VS2010 has a slower
performance than mine?

Ok let's change the instruction:

Code:

srand(time(NULL));

with:

Code:

srand(0);

so we can test the same sequence of numbers all the time.

Originally Posted by frktons

You mean that your X64 ultra-speed mega VS2010 has a slower
performance than mine?

I have no idea where you got that from.

But it wouldn't surprise me if iMalc's code is faster. iMalc's code uses predicted paths to do as little work as necessary. But what's the most clever is the fact that there are no modulus operations. I have no idea how iMalc implemented it using minus and multiplication, though.

Originally Posted by frktons

I suspect it derives from a sentence I frequently heard from
a couple of guys, that sounds like:
Time to switch to a better compiler or the like. :-)

Still doesn't tell me from what context you got that from.

I won't be doing any more performance improvements now, though. At least not for a while.
Instead, I am going to sleep. Sweet sleep.