Algorithm speed

This is a discussion on Algorithm speed within the C Programming forums, part of the General Programming Boards category; How can I clock the speed of a few algorithms I wrote? I wanna see which one's faster....

  1. #1
    Just one more wrong move. -KEN-'s Avatar
    Join Date
    Aug 2001
    Posts
    3,230

    Algorithm speed

    How can I clock the speed of a few algorithms I wrote? I wanna see which one's faster.

  2. #2
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Hmm, not sure, but maybe this...
    Code:
    #include <time.h>
    ...
    clock_t time1, time2;
    time1 = clock();
    algorithm();
    time2 = clock();
    printf("Algorithm took %d seconds.\n", (time2 - time1) / CLOCKS_PER_SEC);
    Two things. First, in retrospect, maybe representing the time as a float makes more sense. Second, I think that clock measures how much processor time your application is getting, which isn't neccisarily the same as how much time it actually takes, although if that is so, then it's a better representation of algorithm efficiency.

  3. #3
    train spotter
    Join Date
    Aug 2001
    Location
    near a computer
    Posts
    3,859
    Most timer functions are not very acurate as they have about the lowest priority of the windows messages.
    Don't depend on them too much, especially if your algorithms are close in speed.

  4. #4
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    Good question KEN. I don't know the answer either, yet there are obviously people who run these tests on a regular bases, or so they think.

    I think I found something. I'll post it later.
    Last edited by Troll_King; 10-23-2001 at 03:21 AM.

  5. #5
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    There is a section in the text 'Algorithms in C++' by Robert Sedgewick. I could type this out if you really want it. Let me know. It is 3 pages long. Infact, now I see that there is a whole chapter dedicated to this. I don't want to type that. Get the book.

    ISBN: 0201350883
    Last edited by Troll_King; 10-23-2001 at 03:32 AM.

  6. #6
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    you could probably do it with a couple of calls to QueryPerformanceCounter(). Dig out your msdn cds ken and look it up.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  7. #7
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,764
    The fastest clock going is the time stamp counter on pentium type processors (and I assume compatibles)

    It's a short asm sequence which will need to be adapted to your specific compiler.

    Here are a couple of examples to work from - the first is GCC, I don't know what the latter one is for.

    Code:
    #include <stdio.h>
    
    /*
     * This macro found on
     * http://www.c-for-dummies.com/compilers/djgpp_asm.html
     */
    #define RDTSC(llptr) ({ \
            __asm__ __volatile__ ( \
            ".byte 0x0f; .byte 0x31" \
            : "=A" (llptr) \
            : : "eax", "edx"); })
    
    int main ( ) {
        unsigned long long a, b;
        RDTSC(a);
        RDTSC(b);
        printf( "%lld -> %lld = %lld\n", a, b, b-a );
        return 0;
    }
    
    
    #include <stdio.h>
    
    unsigned long ReadChipTimer() {
        unsigned long x;
        _asm {
            rdtsc
            mov x, eax
        }
        return x;
    }
    
    int main(void) {
        unsigned long start, end;
        start = ReadChipTimer();
        end = ReadChipTimer();
        printf("Time = %u clock cycles ", end - start);
        return 0;
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  8. #8
    Just one more wrong move. -KEN-'s Avatar
    Join Date
    Aug 2001
    Posts
    3,230
    Thnaks, that ReadChipTimer function helped - the only problem is that it gives a different number each time...as would be expected, but at least the difference between the two speeds is always about equal.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Flight Simulator Wind Speed!!
    By Dilmerv in forum C++ Programming
    Replies: 6
    Last Post: 03-20-2006, 12:40 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

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