Thread: How to test algorithms?

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    51

    How to test algorithms?

    Hello,

    I am in the process of writing functions and such, but I need to know how efficient different algorithms are. Disassembling these functions just tells me the assembly code used, but I don't know how many cycles are being invested per instruction/function. Is there a easy way to figure out how efficent sections of my code is? I'm using Eclipse and gcc. Thanks.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    You can use gprof to profile your code. It is part of the GCC toolchain. Of course, you would not be determining how efficient the algorithms are in general mathematical terms, but how well your implementations of those algorithms perform with the given input.

    EDIT:
    Actually, gprof might not be part of the GCC toolchain, but it is included with the MinGW port of GCC by default, so it might be. In any case it, or a version of it, is part of the GNU project.
    Last edited by laserlight; 01-02-2009 at 11:22 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    3 options:
    1. You can study the code and try and work out the big-oh-notation of the algorithms.
    2. You can write a test harness program to utilise and time the algorithms.
    3. You can post the code here for everyone to tear apart, do the above two things for themselves and tell you how good or crappy the bits are.
    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"

  4. #4
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    Lots of test data and a stop watch.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by esbo View Post
    Lots of test data and a stop watch.
    Well, surely "clock()" or "time()" is nearly always better than a stopwatch - particularly if you intend to make minor adjustments and want to see if it's going in the right or the wrong direction. To get good precision on a stopwatch, you need something that runs for several seconds (10+ seconds, I'd say), and changes need to be at least half a second to a second before they can be noticed. Using the correct in-program timing mechanism will give much more precise timing, and repeatability should be in the tenths of a second over a couple of seconds of runtime unless the machine is very heavily loaded with other work.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by someprogr View Post
    Hello,

    I am in the process of writing functions and such, but I need to know how efficient different algorithms are. Disassembling these functions just tells me the assembly code used, but I don't know how many cycles are being invested per instruction/function. Is there a easy way to figure out how efficent sections of my code is? I'm using Eclipse and gcc. Thanks.
    Both AMD and Intel do publish cycle timings for each instruction in their respective "optimization" documents. However, modern processors are very difficult to determine the exact timing of an instruction or set of instructions [1] - there are only two realistic possibilities:
    - Empirical testing of the function. Give it some data that is representative of the real world data you may expect it to work on, and time the whole function.
    - Simulation of the entire processor - this is slow, but will give EXACT information on how long each step takes. AMD's CodeAnalyst is able to perform this sort of work.


    [1] Because modern processors do stuff that makes it terribly hard to know exactly what is going on in any code but the most trivial:
    • execute instructions out of order,
    • splits instructions to several micro-ops (or whatever the respective processor calls them),
    • register renaming which changes the dependancy path (it allows a R1 to still be used for some calculation, and yet R1 being used as a target for another instruction that is later on in the sequence can be executed before the first R1 using instruction is finished)
    • memory accesses can take several dozen cycles
    • speculative execution - instructions are executed based on "we think this will happen, so let's do the next steps".
    • branch/return prediction - processor will base it's idea of what to do next on the way that the code has flowed previously in a particular piece of code.

    All of these things make predicting how long an arbitrary piece of code will take to execute, given a particular piece of data, awfully tricky.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Integer Emulation
    By Elysia in forum C++ Programming
    Replies: 31
    Last Post: 03-18-2008, 01:03 PM
  2. My C++ test is COMING!!...
    By [Z-D] in forum C++ Programming
    Replies: 52
    Last Post: 12-01-2006, 08:02 PM
  3. undefined reference
    By 3saul in forum Linux Programming
    Replies: 12
    Last Post: 08-23-2006, 05:28 PM
  4. C++ Operator Overloading help
    By Bartosz in forum C++ Programming
    Replies: 2
    Last Post: 08-17-2005, 12:55 PM
  5. MSVC Template Constructor/Assignment Errors
    By LuckY in forum Windows Programming
    Replies: 3
    Last Post: 07-22-2005, 02:57 PM