#define MAGNITUDE 20
#define ITERATIONS 1024
#define VERIFICATION 1
#define VERBOSE 0
#define LIMITED_RANGE 0 // hide difference in output due to absense of overflows
/////////////////////////////
#if VERIFICATION
# include <boost/functional/hash.hpp>
#endif
#include <cassert>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <cstdint>
#include <random>
#include <iostream>
#include <chrono>
#if VERBOSE
# include <boost/spirit/include/karma.hpp>
namespace
{
template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v)
{
using namespace boost::spirit::karma;
return os << format("v(" << auto_ % ",\t" << ")", v);
}
}
#endif
namespace stackoverflow // the code from the Original Post
{
void theloop(const int64_t in[], int64_t out[], size_t N)
{
int64_t max = in[0];
out[0] = max;
for(uint32_t i = 1; i < N; i++) {
int64_t v = in[i];
max += v;
if (v > max) max = v;
out[i] = max;
}
}
void paper_plane(const int64_t in[], int64_t out[], size_t N)
{
int64_t max = 0;
int64_t i;
for(i=N-1; i > 0; --i) /* Comparing with 0 is faster */
{
max = in[i] > 0 ? max+in[i] : in[i]; /* Reduce operations v=in[i], max+=v by N times */
out[i] = max;
--i; /* Will reduce checking of i>=0 by N/2 times */
max = in[i] > 0 ? max+in[i] : in[i]; /* Reduce operations v=in[i], max+=v by N times */
out[i] = max;
}
if(0 == i) /* When N is odd */
{
max = in[i] > 0 ? max+in[i] : in[i];
out[i] = max;
}
}
}
template <typename C> void paper_plane(const C& data, C& output)
{
stackoverflow::paper_plane(&data[0], &output[0], data.size());
}
template <typename C> void run_original_code(const C& data, C& output)
{
stackoverflow::theloop(&data[0], &output[0], data.size());
}
namespace measuring
{
auto ts = std::chrono::system_clock::now();
auto stopwatch_split() -> decltype(ts)
{
auto split = ts;
ts = std::chrono::system_clock::now();
return split;
}
size_t report(const std::string& msg, bool newline=true)
{
auto split = stopwatch_split();
auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(ts - split);
std::cout << msg << elapsed.count() << " msecs.";
if (newline)
std::cout << std::endl;
return elapsed.count();
}
template <typename C>
size_t run_benchmark(const C& data, C& output,
const std::string& label,
void(implementation)(const C&,C&),
size_t& reference_hash)
{
for (int i=0; i<ITERATIONS; ++i)
{
implementation(data, output);
}
#if VERIFICATION
size_t hash = boost::hash_range(output.begin(), output.end());
if (!reference_hash)
{
reference_hash = hash;
}
else
{
# if VERBOSE
if (reference_hash!=hash)
{
std::cerr << label << " hash mismatch! " << std::hex << hash << " (reference implementation: " << reference_hash << ")" << std::dec << std::endl;
std::cerr << "data: " << data << std::endl;
std::cerr << "output: " << output << std::endl;
run_original_code(data, output);
std::cerr << "ref output: " << output << std::endl;
}
else
{
std::cerr << "data: " << data << std::endl;
std::cerr << "output: " << output << std::endl;
run_original_code(data, output);
std::cerr << "ref output: " << output << std::endl;
}
# endif
#endif
}
size_t elapsed = report(label + " elapsed: ", false);
std::cout << " Hash " << std::hex << hash << std::dec << (hash==reference_hash? " ok" : " FAILED!") << std::endl;
return elapsed;
}
}
int main()
{
typedef std::vector<int64_t> data_t;
data_t data(1ul << MAGNITUDE);
data_t output(data.size());
size_t total_op = 0ul,
total_pp = 0ul;
std::cout << "Benchmarking 20 x " << ITERATIONS << " iterations for data length " << data.size() << " (i.e. 20 different random seeds)" << std::endl;
for (size_t seed = 0; seed < 20; seed++)
{
std::mt19937 rng(seed);
#if LIMITED_RANGE
std::uniform_int_distribution<int64_t> gen(-3,3);
#else
std::uniform_int_distribution<int64_t> gen;
#endif
std::generate(data.begin(), data.end(), std::bind(gen, rng));
measuring::report(" --- randomized from new seed --- ");
size_t reference_hash = 0ul;
total_op += measuring::run_benchmark(data, output, "OP's code ", run_original_code <data_t> , reference_hash);
total_pp += measuring::run_benchmark(data, output, "paper.plane ", paper_plane <data_t> , reference_hash);
}
std::cout << "total time in OP algorithm: " << total_op << " msecs" << std::endl;
std::cout << "total time in Heuristic algorithm: " << total_pp << " msecs" << std::endl;
std::cout << "speedup factor: " << (1.0*total_op)/(1.0*total_pp) << " x" << std::endl;
}