C++ "No raw loops" without losing perfomance

Question

So the 'new (old) big thing' is "No Raw Loops" in C++. I'm trying to write code that way, but it seems very inefficient. Yes, there are STL algoritms which can do about anything, but they don't seem very efficient.

I for instance have a situation where I want a pointer to a node in an array of nodes that has the highest score. Determining that score is a costly floating-point operation. So I implemented the STL algorithm version and compared it with the raw loop:

#include <cfloat>
#include <iostream>
#include <array>
#include <algorithm>
#include <numeric>

static int counter;

class Node {
public:
    auto Score() const -> double {
        std::cout << "complex calculation\n";
        counter++;
        return 1;
    }
};

int main()
{

    std::array<Node, 10> nodes;

    counter = 0;
    Node const* nodePtr = std::max_element(std::cbegin(nodes), std::cend(nodes),
        [](Node const& node1, Node const& node2) {
            return node1.Score() < node2.Score();
        });
    std::cout << "algorithm count " << counter << std::endl;

    counter = 0;
    double maxScore = -FLT_MAX;
    for (const auto& node : nodes) {
        auto score = node.Score();
        if (score > maxScore) {
            maxScore = score;
            nodePtr = &node;
        }
    }
    std::cout << "raw loop count " << counter << std::endl;
}

Evaluating this, for the STL version, the costly Score function is evaluated 18 times, while the raw loop only uses 10 evaluations...

Am I doing it wrong, or are raw loops just not that bad?

edit: After the suggestion by user58697 that cout and the static counter would prevent compiler optimization, I changed the code:

#include <cfloat>
#include <cmath>
#include <iostream>
#include <array>
#include <algorithm>
#include <numeric>
#include <random>
#include <chrono>

template <typename T>
class Random {
private:
    std::default_random_engine generator;
    std::uniform_real_distribution<T> distribution;
public:
    Random()
        : generator()
        , distribution(0.0, 1.0)
    {}

    auto operator()() {
        return distribution(generator);
    };
};

static Random<double> myRandom;

class Timer {
private:
    std::chrono::high_resolution_clock::time_point startTime{};
public:
    void Start() noexcept {
        startTime = std::chrono::high_resolution_clock::now();
    }
    [[nodiscard]] auto ElapsedMs() const noexcept {
        return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - startTime).count();
    }
};

static Timer timer;

class Node {
private:
    double val;
public:
    Node() noexcept : val(myRandom()) {}

    [[nodiscard]] auto Score() const noexcept {
        auto score = std::sqrt(std::log(10.0 / val));
        score = std::sin(score) / std::cos(score);
        score = std::sqrt(std::sqrt(std::sqrt(std::sqrt(std::sqrt(score)))));
        score = std::pow(score, 1000);
        return score;
    }
};

int main()
{
    std::array<Node, 100000> nodes; // yeah, yeah... overloading the stack, I know

    for (auto i = 0; i < 2; i++) {
        timer.Start();
        Node const* nodePtr = &*std::max_element(std::cbegin(nodes), std::cend(nodes),
            [](Node const& node1, Node const& node2) {
                return node1.Score() < node2.Score();
            });
        std::cout << "algorithm elapsed time " << timer.ElapsedMs() << std::endl;

        timer.Start();
        double maxScore = -FLT_MAX;
        for (const auto& node : nodes) {
            auto score = node.Score();
            if (score > maxScore) {
                maxScore = score;
                nodePtr = &node;
            }
        }
        std::cout << "raw loop count " << timer.ElapsedMs() << std::endl;
    }
}

I run the loop twice to eliminate startup behavior... results of second loop (compiled with g++ 9.1 -O3):

algorithm elapsed time 16
raw loop count 8 (<== I see I forgot to change "count" to "time" :P)

So that's not it.

Answer 1

Replacing raw loops with abstracted algorithms is good style because then you can reuse the algorithm many times but test it only once. Wrapping the loop this way may seem like syntactic sugar, but it greatly reduces the potential for bugs in your code because you can now do extensive unit tests on the abstracted algorithm and you never need to worry about mistakenly implementing it incorrectly when you need it.

However, you're comparing apples and oranges here. Your max_element implementation always calculates Score() for its comparison whereas your for loop caches the result of the Score() function.

A better implementation of Node might be:

class Node {
mutable:
    double cached_score = std::numeric_limits<double>::quiet_Nan();
public:
    auto Score() const -> double {
        if(std::isnan(cached_score)){
           std::cout << "complex calculation\n";
           counter++;
           cached_score = 1;
        }
        return cached_score;
    }
    void invalidate_cache() {
      cached_score = std::numeric_limits<double>::quiet_Nan();
    }
};

This way the complex calculation is only performed once.

Alternatively, write your own abstraction:

#include <cfloat>
#include <iostream>
#include <array>
#include <algorithm>
#include <numeric>

static int counter;

class Node {
public:
    auto Score() const -> double {
        std::cout << "complex calculation\n";
        counter++;
        return 1;
    }
};

template<class ForwardIt, class Evaluate, class Compare>
ForwardIt max_eval_element(
    ForwardIt first,
    ForwardIt last,
    Evaluate eval,
    Compare comp
){
    if (first == last) return last;

    ForwardIt largest = first;
    auto largest_val = eval(*first);
    ++first;
    for (; first != last; ++first) {
        const auto this_val = eval(*first);
        if (comp(largest_val, this_val)) {
            largest = first;
            largest_val = this_val;
        }
    }
    return largest;
}

int main()
{

    std::array<Node, 10> nodes;

    counter = 0;
    Node const* nodePtr = max_eval_element(std::cbegin(nodes), std::cend(nodes),
                                       [](Node const& node){ return node.Score(); },
                                       [](double const &a, double const &b) {
                                           return a<b;
                                       });
    std::cout << "algorithm count " << counter << std::endl;

    counter = 0;
    double maxScore = -FLT_MAX;
    for (const auto& node : nodes) {
        auto score = node.Score();
        if (score > maxScore) {
            maxScore = score;
            nodePtr = &node;
        }
    }
    std::cout << "raw loop count " << counter << std::endl;
}

In this instance, both loops perform the same number of evaluations.

Many internal codebases I've worked with have extensive libraries which extend the STL. It gives the teams I've worked on much greater confidence that their code has been written correctly and allows you to interpret complex operations at a glance. In this way, these abstractions also reduce the effort of understanding code and the effort of communication.

Answer 2

I just wanted to post the algo I used based on Richard's answer:

template <typename FwdIt, typename Eval, typename Pred = std::less<>>
constexpr FwdIt max_eval_element(FwdIt first, FwdIt last, Eval eval, Pred pred = Pred()) {
    FwdIt found = first;
    if (first != last) {
        auto best = eval(*found);
        while (++first != last) {
            if (auto const thisVal = eval(*first);
                pred(best, thisVal)) {
                found = first;
                best = thisVal;
            }
        }
    }
    return found;
}

which allows me to call the algo as

Node const* nodePtr = &*std::max_eval_element(std::cbegin(nodes), std::cend(nodes), std::mem_fn(&Node::Score));

Answer 3

I think your case is somewhat pathological to std::max_element, since your comparator calls Score() on both elements every time, and you declare it to be expensive. So where you do:

for (const auto& node : nodes) {
    auto score = node.Score();
    if (score > maxScore) {
        maxScore = score;
        nodePtr = &node;
    }
}

... std::max_element effectively has to do:

for (const auto& node : nodes) {
    if (node.Score() > nodePtr->Score()) {
        nodePtr = &node;
    }
}

I think std::max_element would be just fine in a more normal case, where the value to compare by is cheap to access.

Answer 4

It seems that the problem is in how the test is written. The statements

    std::cout << "complex calculation\n";
    count++;

make a visible side effect, and the compiler is obliged to call Score every time it appears. If it was pure (that is, having no side effects), the compiler would optimize the redundant calls away by cacheing.

Try to use a real Score (I hope the real one is pure), and compare the execution times.