#if 0

$ gcc-3.0 -Wall -mcpu=athlon -O3 -o cdrcoding cdrcoding.c && ( sync ; sleep 1; ./cdrcoding)
     cn: 1000000    500  1092734us
cc: 1000000    500  1692764us
ratio cc/cn: 154%.

cn: 500000   1000  1091401us
cc: 500000   1000  1770729us
ratio cc/cn: 162%.

cn: 250000   2000  1080452us
cc: 250000   2000  1668871us
ratio cc/cn: 154%.

cn: 100000   5000  1089640us
cc: 100000   5000  1669494us
ratio cc/cn: 153%.

cn:  50000  10000  1377414us
cc:  50000  10000  1661841us
ratio cc/cn: 120%.

cn:  33333  15000  1624156us
cc:  33333  15000  1664358us
ratio cc/cn: 102%.

cn:  25000  20000  1636328us
cc:  25000  20000  1710243us
ratio cc/cn: 104%.

cn:  16666  30000  1649876us
cc:  16666  30000  1738434us
ratio cc/cn: 105%.

cn:  12500  40000  4848137us
cc:  12500  40000  1697940us
ratio cc/cn: 35%.

cn:  10000  50000  7334477us
cc:  10000  50000  1742752us
ratio cc/cn: 23%.

cn:   5000 100000  7474957us
cc:   5000 100000  4129701us
ratio cc/cn: 55%.


$ cat /proc/cpuinfo
processor       : 0
vendor_id       : AuthenticAMD
cpu family      : 6
model           : 6
model name      : AMD Athlon(tm) XP 1600+
stepping        : 2
cpu MHz         : 1407.221
cache size      : 256 KB
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 1
wp              : yes
flags           : fpu vme de tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 mmx fxsr sse syscall mmxext 3dnowext 3dnow
bogomips        : 2804.94

#endif

#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>
#include <unistd.h>

char core [4000000];
char *freepointer = core;

char *alloc (int n)
{
  char *r = freepointer;
  freepointer+=n;
  return r;
}

void reset_core (void)
{
  freepointer = core;
}

/**********************************************************************************************/

#define CDR_NEXT 0
#define CDR_NIL  1

void *cc_consit (int n)
{
  int *q = (int*)alloc (sizeof (void*) * n);
  int i;
  for (i = 0; i < n; i++)
    q[i] = (i << 2) | CDR_NEXT;

  q[n-1] = ((n-1)<<2) | CDR_NIL;

  return (void*)q;
}

int cc_bench1 (void *x)
{
  int r = 0;
  
  while (x)
  {
    int car;
    void *cdr = 0;

    car = (int)(((void**)x)[0]);
    /*printf("%.8x %.8x\n", x,car);*/
    if ((car & 3) == CDR_NEXT)
      {
        car = car & ~3;
        cdr = ((void**)x) + 1;
      }
    else
      if ((car & 3) == CDR_NIL)
        {
          car = car & ~3;
          cdr = 0;
        }
    r+=car;
    x=cdr;
  }

  return r;
}

int cc_bench (int NLOOPS, int LLEN)
{
  void *x = cc_consit (LLEN);
  int i, z = 0;

  for (i = 0; i < NLOOPS; i++)
    z += cc_bench1 (x);

  return z;
}


/**********************************************************************************************/

struct cn {
  int car;
  void *cdr;
};

struct cn *cn_consit (int n)
{
  if (n == 0)
    return 0;
  else
    {
      struct cn *q = (struct cn *) alloc (sizeof (struct cn));
      q->car = (n-1) << 2;
      q->cdr = cn_consit (n-1);
      return q;
    }
}

int cn_bench1 (struct cn *x)
{
  int r = 0;
  
  while (x)
  {
    r += x->car;
    x = x->cdr;
  }

  return r;
}

int cn_bench (int NLOOPS, int LLEN)
{
  void *x = cn_consit (LLEN);
  int i, z = 0;

  for (i = 0; i < NLOOPS; i++)
    z += cn_bench1 (x);

  return z;
}

/**********************************************************************************************/

struct timeval base_tv;

long long now (void)
{
  struct timeval tv;
  gettimeofday (&tv, 0);
  tv.tv_sec -= base_tv.tv_sec;
  return ((long long)tv.tv_sec)*1000000LL + (long long)tv.tv_usec;
}

#define TOTAL (1000000 * 500)

int main (void)
{
  long long cn_t, cc_t, cn_z, cc_z;
  gettimeofday (&base_tv, 0);

  
#define B0(what,len)                                          \
  {                                                     \
    int n = TOTAL / len;                                \
    reset_core();                                       \
    what##_t  = now ();                                        \
    what##_z = what##_bench (n, len);                                  \
    what##_t = now () - what##_t;                                     \
    fprintf (stdout, #what": %6d %6d  %lldus\n", n, len, what##_t);     \
    sleep(1);                                           \
  }

#define B(len)                                                          \
  {                                                                     \
    B0(cn,len);                                                         \
    B0(cc,len);                                                         \
    fprintf (stdout, "ratio cc/cn: %d%%.\n", (int)((100*cc_t)/cn_t));   \
    fprintf (stdout,"\n");                                              \
  }
  
  B(500);
  B(1000);
  B(2000);
  B(5000);
  B(10000);
  B(15000);
  B(20000);
  B(30000);
  B(40000);
  B(50000);
  B(100000);

  return 0;
}