Testpad for itoa()

This is a discussion on Testpad for itoa() within the C Programming forums, part of the General Programming Boards category; Originally Posted by cyberfish In decreasing order of importance: 1. You really should use random numbers. You can even compare ...

  1. #31
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by cyberfish View Post
    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).
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  2. #32
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,537
    So x64 cut it down to 265 ms? Nice.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #33
    Registered User
    Join Date
    Jun 2010
    Posts
    182
    Quote Originally Posted by iMalc View Post
    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
    	}
    Last edited by frktons; 07-09-2010 at 05:07 PM.

  4. #34
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,537
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  5. #35
    Registered User
    Join Date
    Jun 2010
    Posts
    182
    Quote Originally Posted by Elysia View Post
    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.
    I have still some doubts about what the compiler does
    when the performance changes so much, only testing the
    function with random generated numbers can give me a
    realistic idea.

  6. #36
    Registered User
    Join Date
    Jun 2010
    Posts
    182
    OK, I added the random generation for the numbers to
    format, so now we can see if the optimization miracle of
    modern compiler is a real one or a fake version.

    Attached the source for testing iMalc's function with the
    modified testpad.

    Let me know what results do you get.

    Mine are:
    Code:
                        Testing version : iMalc
                     ------------------------------
     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: 938786183
    
     The formatted value of num is: 938,786,183
    
     Elapsed time: 328 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
    And yours?
    Attached Files Attached Files

  7. #37
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,537
    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 . . .
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #38
    Registered User
    Join Date
    Jun 2010
    Posts
    182
    Your version is slower than mine?
    Oh ! you didn't test iMalc's version, but yours.
    What about the "0 ms"?

  9. #39
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,537
    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.
    Last edited by Elysia; 07-09-2010 at 06:24 PM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  10. #40
    Registered User
    Join Date
    Jun 2010
    Posts
    182
    Quote Originally Posted by Elysia View Post
    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.
    Last edited by frktons; 07-09-2010 at 06:30 PM.

  11. #41
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,537
    Quote Originally Posted by frktons View Post
    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.
    Last edited by Elysia; 07-09-2010 at 06:33 PM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #42
    Registered User
    Join Date
    Jun 2010
    Posts
    182
    Quote Originally Posted by Elysia View Post
    I have no idea where you got that from.
    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. :-)

    By the way we can solve the performance gap test doing:

    Code:
     srand(0);
    and we test the same sequence of numbers all the time.

  13. #43
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,537
    Quote Originally Posted by frktons View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  14. #44
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,656
    Quote Originally Posted by frktons View Post
    So far I'm still waiting for the working versions of:
    - whiteflags - not sure
    I have shown you a similar unit test (the main function) to your test pad. If you can't get it to work with your code, I can't help you unless you're specific. But with the version I posted here, all you need to do is invoke foo. O_o

  15. #45
    Registered User
    Join Date
    Jun 2010
    Posts
    182
    Quote Originally Posted by whiteflags View Post
    I have shown you a similar unit test (the main function) to your test pad. If you can't get it to work with your code, I can't help you unless you're specific. But with the version I posted here, all you need to do is invoke foo. O_o
    Thanks for your explanation, I'll try again, maybe I get it working
    on my testpad.

Page 3 of 7 FirstFirst 1234567 LastLast
Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21