ScanBenchmark // g++ -O2 Scanbenchmark.cc Timer.h

Makefile

all:
	g++ -O3 -c -o scans.o scans.cpp
	g++ -O3 scans.o ScanBenchmark.cpp

ScanBenchmark.cpp

#include <iostream>
#include <stdlib.h>

#include "scans.h"
#include "Timer.h"

using namespace std;
const long long size = 1024*1024*128; // 1GB

int main()
{

	Timer myTimer;
	int result = 0;
	long long* myArray = new long long[size];
	
	srand (0);
	for (long long i = 0;i<size;i++)
	{
		myArray[i] = rand() % 327681;
	}
	
	myTimer.start();
	result = simpleScan(myArray, EQUAL, 13, size);
	myTimer.stop();
	cout << fixed << "SimpleScan Result " << result << " Time " << myTimer.elapsed_time() << endl;

	myTimer.start();
	result = scnbranchfree(myArray, EQUAL, 13, size);
	myTimer.stop();
	cout << fixed << "SimpleScan Result " << result << " Time " << myTimer.elapsed_time() << endl;

	
	// myTimer.start();
	// result = simpleScan(myArray, LESS_THAN, 13, size);
	// myTimer.stop();
	// cout << fixed << "SimpleScan Result " << result << " Time " << myTimer.elapsed_time() << endl;
	
	// myTimer.start();
	// result = simpleScan(myArray, GREATER_THAN, 13, size);
	// myTimer.stop();
	// cout << fixed << "SimpleScan Result " << result << " Time " << myTimer.elapsed_time() << endl;
	

	// myTimer.start();
	// result = functionPointerScan(myArray, EQUAL, 13, size);
	// myTimer.stop();
	// cout << fixed << "FunctionPointerScan Result " << result << " Time " << myTimer.elapsed_time() << endl;

	// myTimer.start();
	// result = scntpl(myArray, EQUAL, 13, size);
	// myTimer.stop();
	// cout << fixed << "Scantemplate Result " << result << " Time " << myTimer.elapsed_time() << endl;


	// myTimer.start();
	// result = scntpl(myArray, LESS_THAN, 13, size);
	// myTimer.stop();
	// cout << fixed << "Scantemplate Result " << result << " Time " << myTimer.elapsed_time() << endl;


	delete myArray;


	return 0;
}

scans.cpp

#include "scans.h"
#include <functional>
#include <stdlib.h>

bool cmp_eq(int a, int b){return (a==b);}
bool cmp_le(int a, int b){return (a<=b);}
bool cmp_lt(int a, int b){return (a<b);}
bool cmp_ge(int a, int b){return (a>=b);}
bool cmp_gt(int a, int b){return (a>b);}

int simpleScan(long long data[], SCAN_COMPARATOR comparator, long long operand, size_t size)
{
	int result = 0;

	for (long long i = 0;i<size;i++)
	{

		if((comparator == 0 && data[i] == operand) ||
		   (comparator == -1 && data[i] <= operand) ||
		   (comparator == -2 && data[i] < operand) ||
		   (comparator == 1 && data[i] >= operand) ||
		   (comparator == 2 && data[i] > operand))
		        {
		            result++;
		        }
	}

	return result;
}

inline int branch_free_equal(long long data[], long long operand, size_t size)
{
	int result = 0;
	for (size_t i=0; i < size; ++i)
	{
		result += (unsigned long long)((~((data[i]-operand)|(operand-data[i])))) >> 63;		
	}
	return result;
}

int scnbranchfree(long long data[], SCAN_COMPARATOR comparator, long long operand, size_t size)
{
	if (comparator == EQUAL)
		return branch_free_equal(data, operand, size);
	else
		return 0;
}

int scntpl(long long data[], SCAN_COMPARATOR comparator, long long operand, size_t size)
{
	if (comparator == EQUAL)
		return scan<my_equal_to>(data, operand, size);
	if (comparator == LESS_THAN)
		return scan<less>(data, operand, size);
	
}

int functionPointerScan(long long data[], SCAN_COMPARATOR comparator, long long operand, size_t size)
{
	int result = 0;

	boolfp firstComparison = NULL;

	if (comparator==EQUAL)
		firstComparison = &cmp_eq;
	else if (comparator==LESS_EQUAL)
		firstComparison = &cmp_le;
	else if (comparator==LESS_THAN)
		firstComparison = &cmp_lt;
	else if (comparator==GREATER_EQUAL)
		firstComparison = &cmp_ge;
	else if (comparator==GREATER_THAN)
		firstComparison = &cmp_gt;

	for (long long i = 0;i<size;i++)
	{
		if (firstComparison(data[i],operand))
		{
			result++;
		}
	}

	return result;
}

scans.h

#ifndef scans
#define scans

#include <string.h>
#include <functional>

using namespace std;

typedef bool(*boolfp)(int,int);

enum SCAN_COMPARATOR
{
	NOTSET = 99,
	EQUAL = 0,
	LESS_EQUAL = -1,
	LESS_THAN = -2,
	GREATER_EQUAL = 1,
	GREATER_THAN = 2
};

int simpleScan(long long data[], 
				SCAN_COMPARATOR comparator, 
					long long operand, size_t size);

template <class T> struct my_equal_to : binary_function <T,T,bool> {
inline bool operator() (const T& x, const T& y) const
    {return x==y;}
};

template<template<typename T> class Operator>
int scan(long long data[], long long operand, size_t size)
{
	int result = 0;
	static Operator<long long> o;
	for (size_t i=0; i<size;++i)
	{
		if (o(data[i], operand)) result++;
	}
	return result;
};

int scntpl(long long data[], SCAN_COMPARATOR comparator, long long operand, size_t size);
int scnbranchfree(long long data[], SCAN_COMPARATOR comparator, long long operand, size_t size);

int functionPointerScan(long long data[], SCAN_COMPARATOR comparator, long long operand, size_t size);

#endif

Timer.h

/* Copyright (c) 2011 Hasso Plattner Institute
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR(S) DISCLAIM ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL AUTHORS BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#ifndef TIMER_H
#define TIMER_H

#include <ctime>
#include <iostream>
#include <iomanip>
#include <sys/time.h>

using namespace std;

class Timer
{
	friend std::ostream& operator<<(std::ostream& os, Timer& t);

private:
	bool running;
	timeval startTime, endTime;

public:
	// 'running' is initially false.  A timer needs to be explicitly started
	// using 'start' or 'restart'
	Timer() : running(false) { }

	void start(const char* msg = 0);
	void stop(const char* msg = 0);
	double elapsed_time();
	double start_time();
	double end_time();
}; // class timer

//===========================================================================
// Return the total time that the timer has been in the "running"
// state since it was first "started" or last "restarted".  For
// "short" time periods (less than an hour), the actual cpu time
// used is reported instead of the elapsed time.

inline double Timer::elapsed_time()
{
	long seconds, useconds;

	seconds  = endTime.tv_sec  - startTime.tv_sec;
	useconds = endTime.tv_usec - startTime.tv_usec;

	return seconds + useconds / 1000.0 / 1000.0;
} // timer::elapsed_time

inline double Timer::start_time()
{
	long seconds, useconds;

	seconds  = startTime.tv_sec;
	useconds = startTime.tv_usec;

	return seconds + useconds / 1000.0 / 1000.0;
} // timer::elapsed_time

inline double Timer::end_time()
{
	long seconds, useconds;

	seconds  = endTime.tv_sec;
	useconds = endTime.tv_usec;

	return seconds + useconds / 1000.0 / 1000.0;
} // timer::elapsed_time

//===========================================================================
// Start a timer.  If it is already running, let it continue running.
// Print an optional message.

inline void Timer::start(const char* msg)
{
	// Print an optional message, something like "Starting timer t";
	if (msg) std::cout << msg << std::endl;

	// Return immediately if the timer is already running
	if (running) return;

	// Set timer status to running and set the start time
	running = true;
	gettimeofday(&startTime, NULL);

} // timer::start

//===========================================================================
// Stop the timer and print an optional message.

inline void Timer::stop(const char* msg)
{
	// Print an optional message, something like "Stopping timer t";
	if (msg) std::cout << msg << std::endl;

	// Compute accumulated running time and set timer status to not running
	if (running) gettimeofday(&endTime, NULL);
	running = false;

} // timer::stop

//===========================================================================
// Print out an optional message followed by the current timer timing.


//===========================================================================
// Allow timers to be printed to ostreams using the syntax 'os << t'
// for an ostream 'os' and a timer 't'.  For example, "cout << t" will
// print out the total amount of time 't' has been "running".

/*inline std::ostream& operator<<(std::ostream& os, timer& t)
{
	os //<< std::setprecision(8) << std::setiosflags(std::ios::fixed)
	<< t.acc_time + (t.running ? t.elapsed_time() : 0) ;
	os = os / 1000
			return os;
}
*/
//===========================================================================

#endif // TIMER_H