Trying to diagnose difference between C++ standard for-loop and accumulate with side effects

Viewed 70

I'm implementing the Max-Profit Algorithm in C++.

Find the Maximum Profit for a given stock trading day. Solution should be O(N) in Time and O(1) in Space requirements. You're allowed to purchase once in the day, and sell once in the day.

And I originally implemented like:

int maxprofit_int(vector<int> const& v) {
    int resProfit = 0;
    int minPrice  = v[0];
    for (auto i = 1; i < v.size(); i++) {
        auto price  = v[i];
        minPrice    = min(minPrice, price);
        auto profit = price - minPrice;
        resProfit   = max(resProfit, price);
    }
    return resProfit;
}

Nothing unusual.

I thought to myself - "The STL typically gives the same or better performance, what would that look like?" Also "can I make this generic too?"

template <class itr>
auto maxprofit_generic(itr begin, itr end) -> typename std::iterator_traits<itr>::value_type {
    using v_t = typename iterator_traits<itr>::value_type;
    return std::accumulate(next(begin, 1), end, v_t{0},
                      [minPrice = *begin](auto const& maximumProfit, auto const& price) mutable {
                          minPrice          = std::min(minPrice, price);
                          auto const profit = price - minPrice;
                          return std::max(maximumProfit, profit);
                      });
}

The accumulate acts as a fold operation, I use the first value of the container as the minPrice, which can be updated every pass. The starting value is always the same type as the return value. From everything I can gather, these two algorithms should be effectively identical.

However, bringing these two over to quick-bench, I found that was not the case. Both in GCC 10.1 and Clang 10.0, with -O3, I found that runtime doubled between the integer version, and the generic version. It's hard for me to believe that Clang and GCC have a bug, so I'm left wondering why my generic performance is abysmal.

What are some recommendations to improve the speed of the generic version?

Performance of Integer and Generic Versions of Max-Profit Algorithm

My Quick-Bench code:

#include <vector>
#include <algorithm>
#include <numeric>

// Functions definitions removed for brevity

std::vector<int> uut = {1,2,4,1,3,5,2,5,7,9,3,4,5,5,5,7,9,9,4,2};

static void Maxprofit_Normal(benchmark::State& state) {
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    auto res = maxprofit(uut);
    benchmark::DoNotOptimize(res);
  }
}
// Register the function as a benchmark
BENCHMARK(Maxprofit_Normal);

static void Maxprofit_Generic(benchmark::State& state) {
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    auto res = maxprofit(uut.cbegin(),uut.cend());
    benchmark::DoNotOptimize(res);
  }
}
BENCHMARK(Maxprofit_Generic);

1 Answers

Your code is benchmarked, but not tested...

resProfit   = max(resProfit, price);

should read

resProfit   = max(resProfit, profit);

After this change the two versions run at the same speed.

Related