Ranges (C++20)

At work-work, we try to stick to the forefront of C++ language development: C++20 all the time, C++23 as it shows up and is available in compilers. It’s a weird mix sometimes with a codebase that has a lengthy history. A while back I bumped into a for loop, tried to be clever and then hit limitations of Clang – and those limitations are sometimes relevant for KDE code that lands in FreeBSD, which is why I’m writing about it.

Some of this is inspired by Tina Ulbrich’s talk at Meeting C++2021, although I swear I wrote it before watching the whole thing through. It’s a decent talk, in particular because it also presents considerations: you can be too clever with ranges.

Code Sample

The code snippets in this blog post come from a complete program here which you can compile with a suitable GCC (11 or 12 will do) with g++ -std=c++20 ranges1.cc.

Data Structure

The code in question uses a struct-of-arrays data structure. In this data structure, there are multiple fields (data members) where each field is an array; the data held at corresponding array indexes is related.

struct MyData {
    int dataPoint[8] = {};
    bool dataPointIsValid[8] = {};
};

This is, a priori, an unfortunate choice of data structures. We know that dataPoint[3] is valid only if the corresponding dataPointIsValid[3] is true, but that isn’t clear from looking only at the data points. An often (but not always!) nicer data structure is the array-of-structs:

struct MyDataPoint {
    int value = 0;
    bool isValid = false;
};
struct MyNicerData {
    MyDataPoint data[8];
};

In this data structure, a data point’s validity is carried with the data itself, rather than being in some other array. Let’s look at some algorithms applied to the two different data layouts.

Taking Sums

Let’s suppose we need the sum of the data points.

int sumOfDataPoints(const MyData& data)
{
    int sum = 0;
    for (int i = 0; i < 8; ++i) {
        sum += data.dataPoint[i];
    }
    return sum;
}

With the “nicer” data structure it looks very similar, only the indexing happens somewhere slightly different in the expression.

int sumOfNicerDataPoints(const MyNicerData& data)
{
    int sum = 0;
    for (int i = 0; i < 8; ++i) {
        sum += data.data[i].value;
    }
    return sum;
}

Feel free to suggest constexpr size_t array_size = 8; or “why not std::array<>?”

Explicit for-loops like this are considered a bit “old-school”, at least in my work-work codebase. While they are easy to read from a “basics of the language” point of view, they do not express intent very well. You have to read the body of the for-loop to know what it’s doing. Here, naming can help, or maybe a comment, but wouldn’t it be nice if the code itself expressed intent.

On the topic of naming, I cannot reccomment Kate Gregory Naming is Hard: Let’s Do Better enough. She’s given the talk many times, here’s a CppCon 2019 YouTube video if you want a recap.

Algorithms

C++ algorithms are great, if you know them. Finding out which algorithms are there is a matter of practice. I can recommend Ivan Čukić as a mind-bending introduction. For a visual representation, the world map of C++ algorithms helps. It’s on the wall at work-work.

Standard algorithms provide a standard “vocabulary” of things you can do with a container. Having them around gives you a richer vocabulary. Much like the two “sum” functions defined above – except they are standard and so you can expect anyone who claims to speak C++20 to know about them. With good good descriptive function names you can skirt the issue, but at some point “std::accumulate on MyNicerData.data” becomes a natural way to say “iterate over the elements of MyNicerData.data and add them together”.

Taking Sums, Algorithmically

There is a standard algorithm (which unfortunately lives in the header <numeric>), called accumulate, which is a fancy word for “sum” that adds up values over a collection. It has some variations and gotchas but it turns the “sum” function into a one-liner.

int stdSumOfDataPoints(const MyData& data)
{
    return std::accumulate(std::begin(data.dataPoint), std::end(data.dataPoint), 0);
}

I’m prepared to argue over whether this is “better”, but we had better have a cup of tea and some biscuits to argue over, and it will be polite. Here there is already a good name available, so the interior of the function may as well be a black box. But if we use standard vocabulary terms, we might not need to introduce special names because the generic term encompasses all the specific implementations – in other words, we could write the one-liner at the call site.

Looking at that snippet, it’s a bit wordy, but you can read it as a fancy for loop:

• from the begin of the array,
• to the end of the array,
• counting from 0,
• accumulate (sum up) the values.

Let’s take a look at the same code with the “nicer” data structure. Here, we can’t just “add” the values stored in the array because they are not integers – they are MyDataPoint values, which have an integer value. There is an overload of std::accumulate for that which takes an operation to apply:

int stdSumOfNicerDataPoints(const MyNicerData& data)
{
    return std::accumulate(std::begin(data.data), std::end(data.data), 0,
        [](int v, const MyDataPoint& p) { return v + p.value; });
}

The lambda at the end is the bit of code that tells how to “add” an int and a MyDataPoint. It adds the point’s value to the integer. Alternatively, we could define an operator+() on MyDataPoint, but + is a very generic name and it is difficult to say if any particular implementation is “the right one” generically. Better to have bespoke functions at the call site.

Iterators

The standard algorithms work on iterators. An interator is, generically, an object that helps iterate over / enumerate / travers / point at the elements of a collection, in some order.

Iterators can take on many forms, and if you squint, you can see one in the code code for sumOfValidDataPoints, the first code snippet in this blog entry. The iterator there is i, which is the object (an int) that helps iterate over the elements of the collection (two collections, really: the arrays dataPoint and dataPointIsValid).

More standard, iterators are made by the std::begin() and std::end() functions, or by methods on a collection (e.g. std::vector::begin()). They’re all over the place, sometimes implicitly.

Taking Sums, Algorithmic Take Two

So far, we have ignored the “valid data point” boolean entirely. Let’s change the functions to only sum the valid ones. With for-loops, this can be done in many ways.

int sumOfValidDataPoints(const MyData& data)
{
    int sum = 0;
    for (int i = 0; i < 8; ++i) {
        if (data.dataPointIsValid[i]) {
            sum += data.dataPoint[i];
        }
    }
    return sum;
}

With the “nicer” data structure it looks very similar, again only differing in the indexing.

int sumOfNicerValidDataPoints(const MyNicerData& data)
{
    int sum = 0;
    for (int i = 0; i < 8; ++i) {
        if (data.data[i].isValid) {
            sum += data.data[i].value;
        }
    }
    return sum;
}

But for-loops are old-school. Algorithms are the hotness. It’s relatively easy to adapt the algorithm with the nicer data structure: all we need to do is change the definition of how to add an integer and a MyDataPoint. If the data point isn’t valid, leave the integer unchanged.

int stdSumOfValidNicerDataPoints(const MyNicerData& data)
{
    return std::accumulate(std::begin(data.data), std::end(data.data), 0,
        [](int v, const MyDataPoint& p) { return p.isValid ? v + p.value : v; });
}

But with the other, less-nice, data structure, there’s a problem: there is no way to get to the “other” array that we need. The iterator in the algorithm is an iterator over the dataPoint array, which doesn’t have the isValid information we need.

int stdSumOfValidDataPoints(const MyData& data)
{
    return std::accumulate(std::begin(data.dataPoint), std::end(data.dataPoint), 0,
        /* How to get data.dataPointIsValid here? */);
}

An iota of cleverness

There’s a Dutch saying “ik snap er geen iota van” which means “this is totally incomprehensible”.

At this point, I’m really reaching: I insist on applying an algorithms-based approach to the struct-of-arrays, and I don’t want to define a custom iterator myself (one which would, for instance, produce indexes suitable for use on the arrays inside MyData). Fortunately the standard ranges library (since C++20) already has something for me.

An iota_view provides a way to treat a sequence integers as something that can be iterated over.

Consider this “range”:

auto r = std::ranges::iota_view(std::size_t(0), std::size(data.dataPoint));

This says “when iterating over r, the dereferenced iterator will produce values size_t(0) up to, but not including, std::size(data.dataPoint)”. In other words, values 0 through 7. We can then create a suitable lambda to give to the accumulate algorithm: it can use the dereferenced iterarator value as an index into the data structure:

int iotaSumOfValidDataPoints(const MyData& data)
{
    auto r = std::ranges::iota_view(std::size_t(0), std::size(data.dataPoint));
    return std::accumulate(r.begin(), r.end(), 0,
        [&data](int v, std::size_t index)
        { return data.dataPointIsValid[index] ? v + data.dataPoint[index] : v; });
}

I’d like to claim that this is terrible code. Obscure, overly-clever. It’s based on piling poor choice (insisting on algorithms) on top of poor choices (struct-of-arrays) and then hitting things with a hammer until it fits.

Don’t do this.

Fortunately, Clang 15 does not have a std::ranges::iota_view at all, so this code does not compile on FreeBSD (or in other contexts where Clang would be used).

Standard Library Quality-of-Implementation

This somewhat rambling post has gone from “here are two data structures” via “algorithms are cool” to “data structure influences what algorithms can be applied” to “here’s a convoluted and contrived example of how to Make It Fit”. And then Clang torpedoed the contrived example.

But iota_view is, in general, a useful thing. I can imagine it ending up in KDE code at any moment, in some algorithms-based code that needs indexes. And if it does, then things blow up in the Clang world. KDE CI would catch it, but I would be hard-pressed to explain why good code, readable code, standard-compliant code, fails with a particular compiler. “Fix your compiler” seems like a reasonable instruction at that point.

This is visible already with NeoChat, which uses a libQuotient function that fails in template specialization – NeoChat hasn’t built successfully for production FreeBSD releases in quite some time.