stepanov_abstraction.cpp

/*
    Copyright 2007-2008 Adobe Systems Incorporated
    Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
    or a copy at http://stlab.adobe.com/licenses.html )


Goal:  examine any change in performance when adding abstraction to simple data types
	in other words:  what happens when adding {} around a type.


Assumptions:
	
	1) A value wrapped in a struct or class should not perform worse than a raw value
	
	2) A value recursively wrapped in a struct or class should not perform worse than the raw value


History:
	Alex Stepanov created the abstraction penalty benchmark. 
	Recently, Alex suggested that I take ownership of his benchmark and extend it.
	
	The original accumulation tests used to show large penalties for using abstraction,
	but compilers have improved.  I have added three sorting tests with non-trivial
	value and pointer usage that show some compilers still have more
	opportunities for optimization.
	
	Chris Cox
	February 2008

*/

#include <cstddef>
#include <cstdio>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include "benchmark_results.h"
#include "benchmark_timer.h"
#include "benchmark_algorithms.h"

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

// a value wrapped in a struct, recursively

template <typename T>
struct ValueWrapper {
	T value;
	ValueWrapper() {}
	template<typename TT>
		inline operator TT () const { return (TT)value; }
	template<typename TT>
		ValueWrapper(const TT& x) : value(x) {}
	T& operator*() const { return *value; }
};

template <typename T>
inline ValueWrapper<T> operator+(const ValueWrapper<T>& x, const ValueWrapper<T>& y) {
	return ValueWrapper<T>(x.value + y.value);
}

template <typename T>
inline bool operator<(const ValueWrapper<T>& x, const ValueWrapper<T>& y) {
	return (x.value < y.value);
}

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

typedef ValueWrapper<double>	DoubleValueWrapper;
typedef ValueWrapper< ValueWrapper< ValueWrapper< ValueWrapper< ValueWrapper< ValueWrapper< ValueWrapper< ValueWrapper< ValueWrapper< ValueWrapper<double> > > > > > > > > >	DoubleValueWrapper10;

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

// a pointer wrapped in a struct, aka an iterator

template<typename T>
struct PointerWrapper {
	T* current;
	PointerWrapper() {}
	PointerWrapper(T* x) : current(x) {}
	T& operator*() const { return *current; }
};

// really a distance between pointers, which must return ptrdiff_t
// because (ptr - ptr) --> ptrdiff_t
template <typename T>
inline ptrdiff_t operator-(PointerWrapper<T>& xx, PointerWrapper<T>& yy) {
	return (ptrdiff_t)( xx.current - yy.current );
}

template <typename T>
inline PointerWrapper<T>& operator++(PointerWrapper<T> &xx) {
	++xx.current;
	return xx;
}

template <typename T>
inline PointerWrapper<T>& operator--(PointerWrapper<T> &xx) {
	--xx.current;
	return xx;
}

template <typename T>
inline PointerWrapper<T> operator++(PointerWrapper<T> &xx, int) {
	PointerWrapper<T> tmp = xx;
	++xx;
	return tmp;
}

template <typename T>
inline PointerWrapper<T> operator--(PointerWrapper<T> &xx, int) {
	PointerWrapper<T> tmp = xx;
	--xx;
	return tmp;
}

template <typename T>
inline PointerWrapper<T> operator-(PointerWrapper<T> &xx, ptrdiff_t inc) {
	PointerWrapper<T> tmp = xx;
	tmp.current -= inc;
	return tmp;
}

template <typename T>
inline PointerWrapper<T> operator+(PointerWrapper<T> &xx, ptrdiff_t inc) {
	PointerWrapper<T> tmp = xx;
	tmp.current += inc;
	return tmp;
}

template <typename T>
inline PointerWrapper<T>& operator+=(PointerWrapper<T> &xx, ptrdiff_t inc) {
	xx.current += inc;
	return xx;
}

template <typename T>
inline PointerWrapper<T>& operator-=(PointerWrapper<T> &xx, ptrdiff_t inc) {
	xx.current -= inc;
	return xx;
}

template <typename T>
inline bool operator<(const PointerWrapper<T>& x, const PointerWrapper<T>& y) {
	return (x.current < y.current);
}

template <typename T>
inline bool operator==(const PointerWrapper<T>& x, const PointerWrapper<T>& y) {
	return (x.current == y.current);
}

template <typename T>
inline bool operator!=(const PointerWrapper<T>& x, const PointerWrapper<T>& y) {
	return (x.current != y.current);
}

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

typedef PointerWrapper<double> double_pointer;
typedef PointerWrapper<DoubleValueWrapper> doubleValueWrapper_pointer;
typedef PointerWrapper<DoubleValueWrapper10> doubleValueWrapper10_pointer;

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

// this constant may need to be adjusted to give reasonable minimum times
// For best results, times should be about 1.0 seconds for the minimum test run
int iterations = 2000000;

// 2000 items, or about 16k of data
// this is intended to remain within the L2 cache of most common CPUs
const int SIZE = 2000;

// initial value for filling our arrays, may be changed from the command line
double init_value = 3.0;

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

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

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

template <typename Iterator>
void verify_sorted(Iterator first, Iterator last) {
	if (!is_sorted(first,last))
		printf("sort test %i failed\n", current_test);
}

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

template <typename Iterator, typename T>
void test_accumulate(Iterator first, Iterator last, T zero, const char *label) {
  int i;
  
  start_timer();
  
  for(i = 0; i < iterations; ++i)
	check_sum( double( accumulate(first, last, zero) ) );
	
  record_result( timer(), label );
}

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

template <typename Iterator, typename T>
void test_insertion_sort(Iterator firstSource, Iterator lastSource, Iterator firstDest,
						Iterator lastDest, T zero, const char *label) {
	int i;

	start_timer();

	for(i = 0; i < iterations; ++i) {
		::copy(firstSource, lastSource, firstDest);
		insertionSort< Iterator, T>( firstDest, lastDest );
		verify_sorted( firstDest, lastDest );
	}
	
	record_result( timer(), label );
}

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

template <typename Iterator, typename T>
void test_quicksort(Iterator firstSource, Iterator lastSource, Iterator firstDest,
					Iterator lastDest, T zero, const char *label) {
	int i;

	start_timer();

	for(i = 0; i < iterations; ++i) {
		::copy(firstSource, lastSource, firstDest);
		quicksort< Iterator, T>( firstDest, lastDest );
		verify_sorted( firstDest, lastDest );
	}
	
	record_result( timer(), label );
}

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

template <typename Iterator, typename T>
void test_heap_sort(Iterator firstSource, Iterator lastSource, Iterator firstDest,
					Iterator lastDest, T zero, const char *label) {
	int i;

	start_timer();

	for(i = 0; i < iterations; ++i) {
		::copy(firstSource, lastSource, firstDest);
		heapsort< Iterator, T>( firstDest, lastDest );
		verify_sorted( firstDest, lastDest );
	}
	
	record_result( timer(), label );
}

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

// our global arrays of numbers to be summed

double data[SIZE];
DoubleValueWrapper VData[SIZE];
DoubleValueWrapper10 V10Data[SIZE];

double dataMaster[SIZE];
DoubleValueWrapper VDataMaster[SIZE];
DoubleValueWrapper10 V10DataMaster[SIZE];

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

// declaration of our iterator types and begin/end pairs
typedef double* dp;
dp dpb = data;
dp dpe = data + SIZE;
dp dMpb = dataMaster;
dp dMpe = dataMaster + SIZE;

typedef DoubleValueWrapper* DVp;
DVp DVpb = VData;
DVp DVpe = VData + SIZE;
DVp DVMpb = VDataMaster;
DVp DVMpe = VDataMaster + SIZE;

typedef DoubleValueWrapper10* DV10p;
DV10p DV10pb = V10Data;
DV10p DV10pe = V10Data + SIZE;
DV10p DV10Mpb = V10DataMaster;
DV10p DV10Mpe = V10DataMaster + SIZE;

typedef double_pointer dP;
dP dPb(dpb);
dP dPe(dpe);
dP dMPb(dMpb);
dP dMPe(dMpe);

typedef doubleValueWrapper_pointer DVP;
DVP DVPb(DVpb);
DVP DVPe(DVpe);
DVP DVMPb(DVMpb);
DVP DVMPe(DVMpe);

typedef doubleValueWrapper10_pointer DV10P;
DV10P DV10Pb(DV10pb);
DV10P DV10Pe(DV10pe);
DV10P DV10MPb(DV10Mpb);
DV10P DV10MPe(DV10Mpe);

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

int main(int argc, char** argv) {

	double dZero = 0.0;
	DoubleValueWrapper DVZero = 0.0;
	DoubleValueWrapper10 DV10Zero = DoubleValueWrapper10(0.0);

	// output command for documentation:
	int i;
	for (i = 0; i < argc; ++i)
		printf("%s ", argv[i] );
	printf("\n");

	if (argc > 1) iterations = atoi(argv[1]);
	if (argc > 2) init_value = (double) atof(argv[2]);

	// seed the random number generator so we get repeatable results
	srand( (int)init_value + 123 );


	fill(dpb, dpe, double(init_value));
	fill(DVpb, DVpe, DoubleValueWrapper(init_value));
	fill(DV10pb, DV10pe, DoubleValueWrapper10(init_value));

	test_accumulate(dpb, dpe, dZero, "double pointer");
	test_accumulate(dPb, dPe, dZero, "double pointer_class");
	test_accumulate(DVpb, DVpe, DVZero, "DoubleValueWrapper pointer");
	test_accumulate(DVPb, DVPe, DVZero, "DoubleValueWrapper pointer_class");
	test_accumulate(DV10pb, DV10pe, DV10Zero, "DoubleValueWrapper10 pointer");
	test_accumulate(DV10Pb, DV10Pe, DV10Zero, "DoubleValueWrapper10 pointer_class");

	summarize("Abstraction Accumulate", SIZE, iterations, kShowGMeans, kShowPenalty );


	// the sorting tests are much slower than the accumulation tests - O(N^2)
	iterations = iterations / 2000;
	
	// fill one set of random numbers
	fill_random<double *, double>( dMpb, dMpe );
	// copy to the other sets, so we have the same numbers
	::copy( dMpb, dMpe, DVMpb );
	::copy( dMpb, dMpe, DV10Mpb );

	test_insertion_sort(dMpb, dMpe, dpb, dpe, dZero, "insertion_sort double pointer");
	test_insertion_sort(dMPb, dMPe, dPb, dPe, dZero, "insertion_sort double pointer_class");
	test_insertion_sort(DVMpb, DVMpe, DVpb, DVpe, DVZero, "insertion_sort DoubleValueWrapper pointer");
	test_insertion_sort(DVMPb, DVMPe, DVPb, DVPe, DVZero, "insertion_sort DoubleValueWrapper pointer_class");
	test_insertion_sort(DV10Mpb, DV10Mpe, DV10pb, DV10pe, DV10Zero, "insertion_sort DoubleValueWrapper10 pointer");
	test_insertion_sort(DV10MPb, DV10MPe, DV10Pb, DV10Pe, DV10Zero, "insertion_sort DoubleValueWrapper10 pointer_class");
	
	summarize("Abstraction Insertion Sort", SIZE, iterations, kShowGMeans, kShowPenalty );


	// these are slightly faster - O(NLog2(N))
	iterations = iterations * 8;

	test_quicksort(dMpb, dMpe, dpb, dpe, dZero, "quicksort double pointer");
	test_quicksort(dMPb, dMPe, dPb, dPe, dZero, "quicksort double pointer_class");
	test_quicksort(DVMpb, DVMpe, DVpb, DVpe, DVZero, "quicksort DoubleValueWrapper pointer");
	test_quicksort(DVMPb, DVMPe, DVPb, DVPe, DVZero, "quicksort DoubleValueWrapper pointer_class");
	test_quicksort(DV10Mpb, DV10Mpe, DV10pb, DV10pe, DV10Zero, "quicksort DoubleValueWrapper10 pointer");
	test_quicksort(DV10MPb, DV10MPe, DV10Pb, DV10Pe, DV10Zero, "quicksort DoubleValueWrapper10 pointer_class");

	summarize("Abstraction Quicksort", SIZE, iterations, kShowGMeans, kShowPenalty );


	test_heap_sort(dMpb, dMpe, dpb, dpe, dZero, "heap_sort double pointer");
	test_heap_sort(dMPb, dMPe, dPb, dPe, dZero, "heap_sort double pointer_class");
	test_heap_sort(DVMpb, DVMpe, DVpb, DVpe, DVZero, "heap_sort DoubleValueWrapper pointer");
	test_heap_sort(DVMPb, DVMPe, DVPb, DVPe, DVZero, "heap_sort DoubleValueWrapper pointer_class");
	test_heap_sort(DV10Mpb, DV10Mpe, DV10pb, DV10pe, DV10Zero, "heap_sort DoubleValueWrapper10 pointer");
	test_heap_sort(DV10MPb, DV10MPe, DV10Pb, DV10Pe, DV10Zero, "heap_sort DoubleValueWrapper10 pointer_class");
	
	summarize("Abstraction Heap Sort", SIZE, iterations, kShowGMeans, kShowPenalty );


	return 0;
}

// the end
/******************************************************************************/
/******************************************************************************/