c++c++20std-ranges

Why chained range views sometimes increase in size?


I have been playing around with std::ranges::views and have noticed that every chained view gets bigger. For view iterators this pattern is simple, each is always 8 byte bigger than the one before. But for views themselves, the transform does not increase size at all, while filter increases it by an amount I cannot make sense of. On MSVC this pattern is slightly different, but still unpredictable to me.

Test code:

#include <iostream>
#include <ranges>
#include <string>

int main() {
    static constexpr auto printed = [](auto&& v) {
        std::cout << "sizeof(v): " << sizeof(v) << ", ";
        std::cout << "sizeof(it): " << sizeof(v.begin()) << ", ";
        std::cout << "values: { ";
        for (auto&& x : v) {
            std::cout << x << ", ";
        }
        std::cout << "}\n";
        return v;
    };

    using namespace std::ranges::views;
    auto hundred = printed(iota(0ull, 100ull));
    auto small = printed(hundred | filter([](auto i) { return i < 50; }));
    auto times_seven = printed(small | transform([](auto i) { return i * 7; }));
    auto even = printed(times_seven | filter([](auto i) { return i % 2 == 0; }));
    auto as_string = printed(even | transform([](auto i) { return std::to_string(i); }));
    auto no_twos = printed(as_string | filter([](auto s) { return s.find('2') == s.npos; }));
}

Run it on GodBolt

Results:

view sizeof(it) delta sizeof(view), GCC/Clang delta sizeof(view), MSVC delta
iota 8 16 16
filter 16 8 32 16 48 32
transform 24 8 32 0 64 16
filter 32 8 64 32 112 48
transform 40 8 64 0 128 16
filter 48 8 112 48 192 64

My code does not really care about the size of the views since they are never stored anywhere, I am just wondering why they cannot be constant, only dependent on size of the lambda (here always empty). I tried looking into source code, but I find it very hard to read with all the layers of base classes, template specialization and concept constraints.


Solution

  • But for views themselves, the transform does not increase size at all, while filter increases it by an amount I cannot make sense of.

    In order to maintain the amortized constant time of ranges::begin guaranteed by the range concept, filter_view needs to cache the first iterator of the underlying view that matches the predicate, so that each call to its begin() can return the cached iterator without repeated seeks.

    This is why filter_view's begin() is not const-qualified, because the first iterator needs to be cached and stored in the filter_view itself when begin() is called for the first time.

    This means that, unlike transform_view, when filter_view acting on other views, in addition to saving copies of the underlying view and predicates, it also needs to save its iterator.

    The increased amount is the size of the internal cache that saves the iterator of the underlying view.


    For view iterators this pattern is simple, each is always 8 byte bigger than the one before.

    The function object is stored in filter_view and transform_view itself, so their iterators need to save not only the underlying iterator, but also an extra pointer (8 bytes) to the view class to facilitate access to the function object.

    This is why these two are never borrowed_range, because when they are destroyed, their iterators will access dangling pointers.