Fibonacci BenchMark

fibo.cpp

#include "bench.h"

using SOURCE = u64;
using RESULT = u64;

SOURCE  src[ 10000 ];

constexpr   u32 SIZE = sizeof src / sizeof *src;

RESULT  dst0[ SIZE ], dst1[ SIZE ], dst2[ SIZE ], dst3[ SIZE ], dst4[ SIZE ],
        dst5[ SIZE ], dst6[ SIZE ], dst7[ SIZE ];

//----- Init -------------------------------------------------------------------
#include <stdlib.h>
#include <string.h>

void prepare( void* result )
{
    memcpy(result, src, sizeof src);
}

bool compare( void* result, void* answer, u32 bytes)
{
    return memcmp(result, answer, bytes) == 0;
}

//----- Factorial --------------------------------------------------------------
constexpr u64 N = 30;

namespace loop
{
    u64 fibonacci(u64 n)
    {
        u64 n1 = 0;
        u64 n2 = 1;
        u64 value;

        if (n == 0)
            return n1;
        if (n == 1)
            return n2;

        for( u64 i=2; i <= n; i++ )
        {
            value = n1 + n2;

            n1 = n2;
            n2 = value;
        }
        return value;
    }

    void run(void* result) { *(u64*)result = fibonacci(N); }
}

namespace d_loop
{
    u64 value[N+1];
    u64 fibonacci(u64 n)
    {
        value[0] = 0;
        value[1] = 1;

        for ( u64 i = 2; i <= n; i++ )
            value[i] = value[i-1] + value[i-2];

        return value[n];
    }

    void run(void* result) { *(u64 *)result = fibonacci(N); }
}

namespace recur
{
    u64 fibonacci(u64 n)
    {
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;

        return fibonacci(n-1) + fibonacci(n-2);
    }

    void run(void* result) { *(u64*)result = fibonacci(N); }
}

namespace t_recur
{
    u64 fibonacci(u64 n, u64 n1 = 0, u64 n2 = 1)
    {
        if (n == 0)
            return n1;
        if (n == 1)
            return n2;

        return fibonacci(n-1, n2, n1+n2);
    }

    void run(void* result) { *(u64*)result = fibonacci(N); }
}

namespace m_recur
{
    u64 value[N+1];
    u64 fibonacci(u64 n)
    {
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;

        if (value[n] != 0)
            return value[n];

        value[n] = fibonacci(n-1) + fibonacci(n-2);
        return value[n];
    }

    void run(void* result) { *(u64*)result = fibonacci(N); }
}

namespace tm_recur
{
    u64 value[N+1];
    u64 fibonacci(u64 n, u64 n1 = 0, u64 n2 = 1)
    {
        if (n == 0)
            return n1;
        if (n == 1)
            return n2;

        if (value[n] != 0)
            return value[n];

        value[n] = fibonacci(n-1, n2, n1+n2);
        return value[n];
    }

    void run(void* result) { *(u64*)result = fibonacci(N); }
}

namespace tmp
{
    template <u64 n> struct fibonacci
    {
        enum: u64 { value = fibonacci<n - 1>::value + fibonacci<n - 2>::value };
    };
    template <> struct fibonacci<0> { enum: u64 { value = 0 }; };
    template <> struct fibonacci<1> { enum: u64 { value = 1 }; };

    void run(void* result) { *(u64*)result = fibonacci<N>::value; }
}


//----- Main -------------------------------------------------------------------
int main()
{
  for (int i = 0; i < 10000; ++i)
    src[i] = rand() * rand();

  BENCH bench("Fibbonacci N: 30", 10000, prepare, compare);
  bench.solution(loop::run, dst0, sizeof dst0);
  bench.add( FUN(    loop::run), dst1 );
  bench.add( FUN(  d_loop::run), dst2 );
  bench.add( FUN(   recur::run), dst3 );
  bench.add( FUN( t_recur::run), dst4 );
  bench.add( FUN( m_recur::run), dst5 );
  bench.add( FUN(tm_recur::run), dst6 );
  bench.add( FUN(     tmp::run), dst7 );
  bench.run();
  return 0;
}

Benchmark Result

https://black7375.tumblr.com/post/189662254015