/*
 * Perlen der Informatik 4
 *
 * Branch misprediction and branch avoidance/reduction with SIMD instructions
 *
 * Capture branch misses:
 * perf stat -p $PROCESSID
 *
 * Record program execution:
 * perf record -e cycles:pp
 *
 * Show program execution report:
 * perf report --sort comm,dso,symbol
 *
 * Annotate source code of program:
 * perf annotate
 */
//---------------------------------------------------------------------------
#include <iostream>
#include <nmmintrin.h>
#include <chrono>
#include <stdlib.h>
#include <unistd.h>
//---------------------------------------------------------------------------
using namespace std;
typedef chrono::time_point<chrono::high_resolution_clock> tp;
typedef chrono::duration<double,micro> mus;
//---------------------------------------------------------------------------
int main(void)
{
	char* buffer=static_cast<char*>(malloc(1024*1024*1024));
	for (size_t i = 0;i<1024*1024*1024;++i)
		buffer[i]=rand()%255;

	cout << "Attach now ..." << endl;
	sleep(5);

	// A) avoid branching

	// Without SSE
	{
		tp start=chrono::high_resolution_clock::now();
		long as=0;
		for (size_t i = 0;i<1024*1024*1024;++i) {
			if (buffer[i]=='a')
				++as;
		}
		tp stop=chrono::high_resolution_clock::now();
		mus duration=stop-start;
		cout << "'a's: " << as << endl;
		cout << "took: " << duration.count() << "mus" << endl;
	}
	// Result:	1.106.237.301 branches	1339,294 M/sec

	// With SSE
	{
		tp start=chrono::high_resolution_clock::now();
		long as=0;
		__m128i a=_mm_set1_epi8('a');
		for (size_t i = 0;i<(1024*1024*1024)/16;++i) {
			__m128i vector=_mm_loadu_si128(reinterpret_cast<__m128i*>(buffer+i*16));
			__m128i mask=_mm_cmpeq_epi8(a,vector);
			as+=_mm_popcnt_u64(_mm_movemask_epi8(mask));
		}
		tp stop=chrono::high_resolution_clock::now();
		mus duration=stop-start;
		cout << "'a's: " << as << endl;
		cout << "took: " << duration.count() << "mus" << endl;
	}
	// Result:	103.287.337 branches	383,504 M/sec

	free(buffer);
	return EXIT_SUCCESS;
}
//---------------------------------------------------------------------------
