Recursive, iterative and tail-recursive performance test for X86 (with factorial)

gistfile1.c

/*
 * Test for recursive, tail-recursive and iterative functions
 * solving the same problem (factorial) to test execution speed
 * on an X86 processor.
 *
 * Found: 
 *   http://mpathirage.com/recursion-non-recursion-and-tail-recursion-test/
 *
 * Cleaned up by Toby DiPasquale <[email protected]>
 *
 * Compile with:
 *   gcc -W -Wall -O2 facttest.c -o facttest
 *
 */
#include <stdio.h>

/*
 * Recursive implementation of the factorial function.
 */
static int rfact(int n)
{
    if (0 == n) {
        return 1;
    }
    return n * rfact(n - 1);
}

/*
 * Iterative implementation of the factorial function.
 */
static int ifact(int n)
{
    int result = 1;
    
    if (0 == n) {
        return 1;
    }
    while (n > 0) {
        result *= n;
        n--;
    }
    return result;
}

/*
 * Tail-recursive helper function for tfact().
 */
static int tfact_aux(int n, int acc)
{
    return (0 == n) ? acc : tfact_aux(acc * n, n - 1);
}

/*
 * Tail-recursive implementation of the factorial function.
 */
static int tfact(int n)
{
    return tfact_aux(n, 1);
}

/*
 * Function to retrieve value from hardware clock timer on X86 CPUs.
 */
static unsigned long long int rdtsc()
{
    unsigned long long int x;
    
    __asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
    return x;
}

#define METER(func, str)                            \
{                                                   \
    int count;                                      \
    unsigned long long c0, cputime;                 \
                                                    \
    c0 = rdtsc();                                   \
    for (count = 0; count < 10000000; count++) {    \
        func;                                       \
    }                                               \
    cputime = rdtsc() - c0;                         \
    printf(str " " # func ":  %Lu\n", cputime);     \
}

int main(void)
{
    METER(ifact(5), "[iterative]");
    METER(rfact(5), "[recursive]");
    METER(tfact(5), "[tail-recursive]");
    printf("possible measurement error (+/-): %Lu\n", rdtsc() - rdtsc());
    return 0;
}