bench paperplane code

#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;
}