fannkuch-redux C++ g++ program | Computer Language Benchmarks Game

performance measurements

Each table row shows performance measurements for this C++ g++ program with a particular command-line input value N.

N	CPU secs	Elapsed secs	Memory KB	Code B	≈ CPU Load
10	0.32	0.10	?	1059	80% 82% 100% 70%
11	3.98	1.03	1,108	1059	97% 100% 94% 98%
12	54.86	14.03	1,144	1059	100% 97% 97% 98%

Read the ↓ make, command line, and program output logs to see how this program was run.

Read fannkuch-redux benchmark to see what this program should do.

notes

gcc (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3

fannkuch-redux C++ g++ program source code

/* The Computer Language Benchmarks Game
   http://benchmarksgame.alioth.debian.org/

   contributed by Branimir Maksimovic
   first permutation algo taken from Miroslav Rubanets program
*/
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <future>
#include <unistd.h>

typedef unsigned char int_t;

void rotate(int_t* p, int n)
{
   int_t tmp = p[0];
   for(int i = 0; i < n; ++i)p[i]=p[i+1];
   p[n] = tmp;
}

void next_permutation(int_t* beg, int n, int_t* c)
{
   int i = 1;
   while(i<n)
   {
      rotate(beg,i);
      if(c[i]>=i)c[i++]=0;
      else break;
   }
   ++c[i];
}

class Perm{
public:
struct P{
   int_t p[16];
};
Perm(unsigned n)
: cnt {0},n(n),permcount(0)
{
   fact[0]=1;
   for(unsigned i=1;i<n+1;++i)
   {
      fact[i]=fact[i-1]*i;
   }
}
P get(int idx)
{ 
    char pp[16]={};
    permcount = idx;
    int_t i = 0;
    std::generate(perm.p,perm.p+n,[&i](){return ++i;});
    for ( unsigned i=n-1; i>0; --i ) {
        unsigned d = idx / fact[i];
        cnt[i] = d;
        idx = idx % fact[i];
        std::copy( &perm.p[0], &perm.p[i+1], &pp[0] );
        for (unsigned j=0; j<=i; ++j ){
         perm.p[j] = j+d <= i ? pp[j+d] : pp[j+d-i-1];
      }
    }
   return perm;
}
P next()
{
   next_permutation(perm.p,n,cnt);
   ++permcount;
   return perm;
}
unsigned count()const { return permcount; }
unsigned max()const { return fact[n]; }
private:
   int_t cnt[16];
   unsigned fact[16],n,permcount;
   P perm;
};

struct Result{
   int checksum;
   int maxflips;
};

Result work(Perm perm,unsigned n,unsigned max)
{
   Result r={0};
   Perm::P p = perm.get(n);
   for(; perm.count()<max;p=perm.next())
   {
      int flips = 0;
      while(p.p[0] != 1)
      {
         std::reverse(p.p,p.p+p.p[0]);
         ++flips;
      }
      r.checksum += (perm.count()%2 == 0)?flips:-flips;
      r.maxflips = std::max(r.maxflips,flips);
   }
   return r;
}

Result fannkuch(int n)
{
   Result tmp = {0};
   Perm perm(n);
   
   unsigned N = sysconf(_SC_NPROCESSORS_ONLN);
   std::future<Result> ft[N];
   
   unsigned k = perm.max()/N;
   unsigned j = 0;
   for(unsigned i = 0 ; i < N;++i,j+=k)
   {
      unsigned max = i<N-1?j+k:perm.max();
      ft[i] = std::async(std::launch::async,work,perm,j,max);
   }
   for(unsigned i = 0; i < N; ++i)
   {
      auto r = ft[i].get();
      tmp.checksum += r.checksum;
      tmp.maxflips = std::max(tmp.maxflips,r.maxflips);
   }
   return tmp;
}

int main(int argc, char** argv)
{
   int n = 7;
   if(argc > 1)n = atoi(argv[1]);
   if(n < 3 || n > 12)
   {
      printf("n should be between [3 and 12]\n");
      return 0;
   }
   Result r = fannkuch(n);
   printf("%d\nPfannkuchen(%d) = %d\n",r.checksum,n,r.maxflips);
}

make, command-line, and program output logs

Thu, 31 Jan 2013 21:39:12 GMT

MAKE:
/usr/bin/g++ -c -pipe -O3 -fomit-frame-pointer -march=native  -std=c++0x fannkuchredux.c++ -o fannkuchredux.c++.o &&  \
        /usr/bin/g++ fannkuchredux.c++.o -o fannkuchredux.gpp_run -lpthread 
rm fannkuchredux.c++
1.95s to complete and log all make actions

COMMAND LINE:
./fannkuchredux.gpp_run 12

PROGRAM OUTPUT:
3968050
Pfannkuchen(12) = 65

Home Conclusions License Play

x64 Ubuntu : Intel® Q6600® quad-coreComputer Language Benchmarks Game [[ Play ]]

performance measurements

notes

fannkuch-redux C++ g++ program source code

make, command-line, and program output logs

x64 Ubuntu : Intel® Q6600® quad-core
Computer Language Benchmarks Game [[ Play ]]