C++ algorithm loop fusion optimization

Question

I find that occasionally in my code, I'll have a data structure and I want to get two or more values out of it, each of which can be extracted using a standard algorithm. The problem is, to use the standard algorithms means doing multiple loops through the data. Take the following example, where I have a vector and want to get the sum, value of the first element above some threshold, and the total number of elements above that threshold:

constexpr auto GetValuesSTL(const std::vector& testdata)
{
    constexpr auto value_above_threshold = [](const auto value) constexpr { return value > THRESHOLD; };
    constexpr auto optional_from_iterator = [](const auto it, const auto end) constexpr { return it != end ? std::make_optional(*it) : std::nullopt; };

    return std::make_tuple(
        std::accumulate(testdata.begin(), testdata.end(), 0L),
        optional_from_iterator(std::find_if(testdata.begin(), testdata.end(), value_above_threshold), testdata.end()),
        std::count_if(testdata.begin(), testdata.end(), value_above_threshold) );
}

but I can write this more efficiently as a raw loop:

constexpr auto GetValuesRawLoop(const std::vector& testdata)
{
    auto sum = 0L;
    std::optional first_above_threshold = std::nullopt;
    auto num_above_threshold = 0;

    auto it = testdata.begin();
    for (; it != testdata.end(); ++it)
    {
        const auto value = *it;

        if (value > THRESHOLD)
        {
            first_above_threshold = value;
            break;
        }

        sum += value;
    }
    for (; it != testdata.end(); ++it)
    {
        const auto value = *it;

        sum += value;

        if (value > THRESHOLD)
        {
            ++num_above_threshold;
        }
    }

    return std::make_tuple( sum, first_above_threshold, num_above_threshold );
}

I was hoping that the compiler would be able to fuse the algorithm calls into a single loop, since it has enough info to know that the vector isn't being modified, but profiling these two functions on various length vectors of randomly generated ints (compiled with g++-9 -O3) shows that the STL version of the function consistently takes about 2-2.5x times as long as the raw loop, exactly as you'd expect without loop fusion.

Is there a good reason the compiler can't/doesn't apply this optimisation? Is there some sort of assumption required to be able to fuse the loops that the compiler isn't allowed to make? Or is it a fundamentally difficult thing to detect and apply? Is there an alternative way to write it that could be as efficient as the raw loop and as expressive as the algorithm version?

user_41704 · Answer

I am just going to answer the last part of your question:

Is there an alternative way to write it that could be as efficient as the raw loop and as expressive as the algorithm version?

Depending on what you consider to be "expressive", using a single std::accumulate may work like this:

constexpr auto GetValuesACC(const std::vector& testdata)
    auto accumulator = [](std::tuple, int> init, int val) {
        return std::make_tuple(
            std::get<0>(init) + val, 
            std::get<1>(init).has_value() ? std::get<1>(init) : 
                (val > THRESHOLD ? std::make_optional(val) : std::nullopt),
            std::get<2>(init) + int(val > THRESHOLD));
};

    return std::accumulate(testdata.begin(), testdata.end(),
        std::make_tuple(0, std::nullopt, 0), accumulator);
}

This code implements an accumulator that maintains a tuple containing:

sum of elements so far
first above thresdhold seen so far -or- nullopt
above threshold count so far

Note: I have not benchmarked the performance of this algorithm vs. your original version, or the raw loop, because the outcome will vary based on your hardware and exact compiler. However, this should be equivalent to a single hand-written loop.

Edit: I did some benchmarks locally...

Hardware: MacOS, 1.8GHz Intel Core i5
Compiler: LLVM 10, x86_64, --std=c++17, -O3
Test used 3 runs with 10 iterations each, on input of 5x10^7 element vectors, containing sequential integers (std::iota), with THRESHOLD=5.
Subtracted time to initialize the vectors (~1s).
Data recorded using the 'user' output of the 'time' command, and all values are in seconds and sorted in ascending order.

GetValuesRawLoop: 3.7, 4.0, 4.2 GetValuesSTL: 4.4, 4.5, 4.6 GetValuesACC: 78s (only did one run)

Summary so far:

No significant difference between GetValuesRawLoop and GetValuesSTL in my environment.
GetValuesACC is an order-of-magnitude slower.

Following hint from @John Ilacqua about std::optional being slow, I re-wrote all 3 algorithms using plain int and using THRESHOLD as the guard value to mean "there is no value above threshold".

Example of GetValuesACC without optional:

auto GetValuesACC2(const std::vector& testdata)
{
    auto accumulator = [](const std::tuple& init, int val) {
        return std::make_tuple(
            std::get<0>(init) + val, 
            std::get<1>(init) > THRESHOLD ? std::get<1>(init) : 
                (val > THRESHOLD ? val : THRESHOLD),
            std::get<2>(init) + int(val > THRESHOLD));
    };

    return std::accumulate(testdata.begin(), testdata.end(),
        std::make_tuple(0, THRESHOLD, 0), accumulator);
}

New results:

GetValuesRawLoop2: 0.3, 0.3, 0.6
GetValuesSTL2:     4.4, 4.4, 4.5
GetValuesACC2:     1.7, 1.8, 1.9

New summary:

the implementation of optional in my version of LLVM is slow in this context
- but doesn't really affect GetValuesSTL
single accumulator is faster than 3 loops, but slower than raw loops

As always, "your mileage may vary!" These results underscore why it is important to profile in real-world usage before trying to optimize.

C++ algorithm loop fusion optimization

1 Answers