/* KAI's version of Stepanov Benchmark -- Version 1.2

   Version 1.2 -- removed some special code for GNU systems that
		  GNU complained about without -O

To verify how efficiently C++ (and in particular STL) is compiled by
the present day compilers, I composed a little benchmark. It outputs
13 numbers. In the ideal world these numbers should be the same. In
the real world, however, ...

The final number printed by the benchmark is a geometric mean of the
performance degradation factors of individual tests. It claims to
represent the factor by which you will be punished by your
compiler if you attempt to use C++ data abstraction features. I call
this number "Abstraction Penalty."

As with any benchmark it is hard to prove such a claim; some people
told me that it does not represent typical C++ usage. It is, however,
a noteworthy fact that majority of the people who so object are
responsible for C++ compilers with disproportionatly large Abstraction
Penalty.

The structure of the benchmark is really quite simple. It adds 2000
doubles in an array 25000 times. It does it in 13 different ways that
introduce more and more abstract ways of doing it:

0 - uses simple Fortran-like for loop.
1 - 12 use STL style accumulate template function with plus function object.
1, 3, 5, 7 ,9, 11 use doubles.
2, 4, 6, 8, 10, 12 use Double - double wrapped in a class.
1, 2 - use regular pointers.
3, 4 - use pointers wrapped in a class.
5, 6 - use pointers wrapped in a reverse-iterator adaptor.
7, 8 - use wrapped pointers wrapped in a reverse-iterator adaptor.
9, 10 - use pointers wrapped in a reverse-iterator adaptor wrapped in a
  reverse-iterator adaptor.
11, 12 - use wrapped pointers wrapped in a reverse-iterator adaptor wrapped
  in a reverse-iterator adaptor.

All the operators on Double and different pointer-like classes are
declared inline. The only thing that is really measured is the penalty
for data abstraction. While templates are used, they do not cause any
performance degradation. They are used only to simplify the code.

Since many of you are interested in the C++ performance issues, I
decided to post the benchmark here. I would appreciate if you run it
and (if possible) send me the results indicating what you have
compiled it with (CPU, clock rate, compiler, optimization level). It
is self contained and written so that it could be compiled even with
those compilers that at present cannot compile STL at all.

It takes a fairly long time to run - on a really slow machine it might
take a full hour. (For those of you who want to run it faster - give
it a command line argument that specifies the number of
iterations. The default is 25000, but it gives an accurate predictions
even with 500 or a thousand.)


Alex Stepanov
stepanov@mti.sgi.com

*/


#include <stddef.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>

template <class T>
inline int operator!=(const T& x, const T& y) {
  return !(x == y);
}

struct Double {
  double value;
  Double() {}
  Double(const double& x) : value(x) {}
  operator double() { return value; }
};

inline Double operator+(const Double& x, const Double& y) {
  return Double(x.value + y.value);
}

struct double_pointer {
    double* current;
    double_pointer() {}
    double_pointer(double* x) : current(x) {}
    double& operator*() const { return *current; }
    double_pointer& operator++() {
	++current;
	return *this;
    }
    double_pointer operator++(int) {
	double_pointer tmp = *this;
	++*this;
	return tmp;
    }
    double_pointer& operator--() {
	--current;
	return *this;
    }
    double_pointer operator--(int) {
	double_pointer tmp = *this;
	--*this;
	return tmp;
    }
};


inline int operator==(const double_pointer& x,
		      const double_pointer& y) {
    return x.current == y.current;
}

struct Double_pointer {
    Double* current;
    Double_pointer() {}
    Double_pointer(Double* x) : current(x) {}
    Double& operator*() const { return *current; }
    Double_pointer& operator++() {
	++current;
	return *this;
    }
    Double_pointer operator++(int) {
	Double_pointer tmp = *this;
	++*this;
	return tmp;
    }
    Double_pointer& operator--() {
	--current;
	return *this;
    }
    Double_pointer operator--(int) {
	Double_pointer tmp = *this;
	--*this;
	return tmp;
    }
};


inline int operator==(const Double_pointer& x,
		       const Double_pointer& y) {
    return x.current == y.current;
}

template <class RandomAccessIterator, class T>
struct reverse_iterator {
    RandomAccessIterator current;
    reverse_iterator(RandomAccessIterator x) : current(x) {}
    T& operator*() const {
      RandomAccessIterator tmp = current;
      return *(--tmp);
    }
    reverse_iterator<RandomAccessIterator, T>& operator++() {
	--current;
	return *this;
    }
    reverse_iterator<RandomAccessIterator, T> operator++(int) {
      reverse_iterator<RandomAccessIterator, T> tmp = *this;
	++*this;
	return tmp;
    }
    reverse_iterator<RandomAccessIterator, T>& operator--() {
	++current;
	return *this;
    }
    reverse_iterator<RandomAccessIterator, T> operator--(int) {
      reverse_iterator<RandomAccessIterator, T> tmp = *this;
	--*this;
	return tmp;
    }
};

template <class RandomAccessIterator, class T>
inline int operator==(const reverse_iterator<RandomAccessIterator, T>& x,
		      const reverse_iterator<RandomAccessIterator, T>& y) {
    return x.current == y.current;
}

struct {
  double operator()(const double& x, const double& y) {return x + y; }
  Double operator()(const Double& x, const Double& y) {return x + y; }
} plus;


template <class Iterator, class Number>
Number accumulate(Iterator first, Iterator last, Number result) {
  while (first != last) result =  plus(result, *first++);
  return result;
}

#ifdef SMALL_PROBLEM_SIZE
int iterations = 10000;
#else
int iterations = 250000;
#endif
#define SIZE 2000

int current_test = 0;

double result_times[20];

/* This is an llvm hack to make the output not cause spurious diffs. */
#define STABILIZE(X) (X)*0.0000001

void summarize() {
  printf("\ntest      absolute   additions      ratio with\n");
  printf("number    time       per second     test0\n\n");
  int i;
  double millions = (double(SIZE) * iterations)/1000000.;
  for (i = 0; i < current_test; ++i)
    printf("%2i       %5.2fsec    %5.2fM         %.2f\n",
	   i,
	   STABILIZE(result_times[i]),
	   STABILIZE(millions/result_times[i]),
	   STABILIZE(result_times[i]/result_times[0]));
  double gmean_times = 0.;
  double total_absolute_times = 0.;  // sam added 12/05/95
  double gmean_rate = 0.;
  double gmean_ratio = 0.;
  for (i = 0; i < current_test; ++i) {
    total_absolute_times += result_times[i];  // sam added 12/05/95
    gmean_times += log(result_times[i]);
    gmean_rate  += log(millions/result_times[i]);
    gmean_ratio += log(result_times[i]/result_times[0]);
  } 
  printf("mean:    %5.2fsec    %5.2fM         %.2f\n",
	 STABILIZE(exp(gmean_times/current_test)),
	 STABILIZE(exp(gmean_rate/current_test)),
	 STABILIZE(exp(gmean_ratio/current_test)));
  printf("\nTotal absolute time: %.2f sec\n", STABILIZE(total_absolute_times));
  // sam added 12/05/95
  printf("\nAbstraction Penalty: %.2f\n\n", 
         STABILIZE(exp(gmean_ratio/current_test)));
}

clock_t start_time, end_time;

inline void start_timer() { start_time = clock(); }

inline double timer() {
  end_time = clock();
  return (end_time - start_time)/double(CLOCKS_PER_SEC);
}

const double init_value = 3.;


double data[SIZE];

Double Data[SIZE];

inline void check(double result) {
  if (result != SIZE * init_value) printf("test %i failed\n", current_test);
}

void test0(double* first, double* last) {
  start_timer();
  for(int i = 0; i < iterations; ++i) {
    double result = 0;
    for (int n = 0; n < last - first; ++n) result += first[n];
    check(result);
  }
  result_times[current_test++] = timer();
}


template <class Iterator, class T>
void test(Iterator first, Iterator last, T zero) {
  int i;
  start_timer();
  for(i = 0; i < iterations; ++i)
    check(double(accumulate(first, last, zero)));
  result_times[current_test++] = timer();
}

template <class Iterator, class T>
void fill(Iterator first, Iterator last, T value) {
  while (first != last) *first++ = value;
}


double d = 0.;
Double D = 0.;
typedef double* dp;
dp dpb = data;
dp dpe = data + SIZE;
typedef Double* Dp;
Dp Dpb = Data;
Dp Dpe = Data + SIZE;
typedef double_pointer dP;
dP dPb(dpb);
dP dPe(dpe);
typedef Double_pointer DP;
DP DPb(Dpb);
DP DPe(Dpe);
typedef reverse_iterator<dp, double> rdp;
rdp rdpb(dpe);
rdp rdpe(dpb);
typedef reverse_iterator<Dp, Double> rDp;
rDp rDpb(Dpe);
rDp rDpe(Dpb);
typedef reverse_iterator<dP, double> rdP;
rdP rdPb(dPe);
rdP rdPe(dPb);
typedef reverse_iterator<DP, Double> rDP;
rDP rDPb(DPe);
rDP rDPe(DPb);
typedef reverse_iterator<rdp, double> rrdp;
rrdp rrdpb(rdpe);
rrdp rrdpe(rdpb);
typedef reverse_iterator<rDp, Double> rrDp;
rrDp rrDpb(rDpe);
rrDp rrDpe(rDpb);
typedef reverse_iterator<rdP, double> rrdP;
rrdP rrdPb(rdPe);
rrdP rrdPe(rdPb);
typedef reverse_iterator<rDP, Double> rrDP;
rrDP rrDPb(rDPe);
rrDP rrDPe(rDPb);

int main(int argv, char** argc) {
  if (argv > 1) iterations = atoi(argc[1]);
  fill(dpb, dpe, double(init_value));
  fill(Dpb, Dpe, Double(init_value));
  test0(dpb, dpe);
  test(dpb, dpe, d);
  test(Dpb, Dpe, D);
  test(dPb, dPe, d);
  test(DPb, DPe, D);
  test(rdpb, rdpe, d);
  test(rDpb, rDpe, D);
  test(rdPb, rdPe, d);
  test(rDPb, rDPe, D);
  test(rrdpb, rrdpe, d);
  test(rrDpb, rrDpe, D);
  test(rrdPb, rrdPe, d);
  test(rrDPb, rrDPe, D);
  summarize();
  return 0;
}