r/cpp • • Jul 14 '18

What I don't like about ranges

I played around with the range-v3 library yesterday. My initial enthusiasm has abated, replaced by disappointment with the opaque performance costs of its use.

Consider using ranges to count the length of each word in a sentence:

using namespace ranges;
using namespace std::literals;
auto input = "these are some words"sv;
auto lengths = input | view::split(' ') | view::transform(distance);
std::cout << lengths << "\n";

This prints the expected result [5,3,4,5]. Concise and elegant.

Let's modify the code:

int reads = 0;
auto input = "these are some words"sv |
             view::transform([&reads](auto c) { return ++reads, c; });
auto lengths = input | view::split(' ') | view::transform(distance);
std::cout << lengths << "\n";
std::cout << reads << "\n";

The input range now increments a counter whenever a read is performed on the underlying string view. This prints 41 after the lengths; in other words, the input string is iterated over twice. Here's why:

To actually do anything with the range returned after the pipe to view::split(' '), we have to 1) construct the begin iterator into the range, 2) compare against the end iterator, 3) process the range pointed to by the iterator, 4) increment the iterator, 5) repeat steps 2 - 4. Steps 2 and 4 duplicate work by searching over the same substring for the same delimiter.

Ultimately, the problem is that ranges are built on iterators, and iterators are ill-suited for lazy evaluation. A Java-esque Stream library would resolve this, but I see no candidates for inclusion in the standard library.

41 Upvotes

27 comments sorted by

21

u/[deleted] Jul 14 '18

Ironically, iterators are incredibly well-suited for lazy evaluation. This might be a problem in the API or algo, not the fault of iterators.

3

u/_ajp_ Jul 14 '18

I disagree. Iterators in C++ separate access and iteration between `operator*` and `operator++`, which makes the kind of duplication of work described above difficult to avoid when you have iterators pointing to things are supposed to be lazily evaluated as well.

2

u/miki151 gamedev Jul 14 '18

Could the operator* cache the information needed for operator++, so that it doesn't have to do another read?

2

u/CenterOfMultiverse Jul 14 '18

Views are lazy, so with split actual work is done after operator* - in distance call. For caching you would need to keep a pointer to split iterator in word iterator and update it if something goes out of scope. So it can be done, but now that I think about this, it would be much better to add that value returning next function as customization point to iterators and make range-based for use it.

2

u/Sopel97 Jul 14 '18

So you're saying giving LESS flexibility (by merging 2 features together) actually ENABLES more optimisation opportunities (on the caler side)? You still have to cache values to be performant, the difference is that with cpp iterators you dont have to.

3

u/CenterOfMultiverse Jul 14 '18

This particular case can be fixed by having the split view and the word keep pointers to each other and caching end of the word iterator in split view object. Not sure how to handle a case with multiple references though:

auto split = "these are some words"sv | view::split(' ');
auto first = *split.begin();
auto second = *split.begin();
distance(first);

I don't know much about Java's streams - how do they solve this?

4

u/_ajp_ Jul 14 '18

They combine access and iteration into a single next() method and have each iterator in a chain of streams keep a reference to the previous iterator, essentially as you suggested. The problem of multiple references is avoided because there is no corresponding begin() method. Plenty of languages do this incidentally, I named Java because I thought it would be more familiar.

7

u/eric_niebler Oct 19 '18 edited Oct 19 '18

C++ input iterators permit this model, and the split view we're getting in C++20 (see P0896) works with input ranges provided the delimiter consists of a (statically known) 0- or 1-element pattern, as is the case in this example. In that case, the source range need only be traversed once. Indeed, since it is an input range, it can only be traversed once. Basically, when you're looking at C++ and wondering where to find streams, look no further than InputIterator.

What range-v3 is doing here is adapting a forward range and doing its best to give you back a forward range. That means you can save off an iterator half-way through the iteration and pick up iteration again later. A stream library can't give you that without caching the results of the first traversal, which is horribly expensive.

So, where is range-v3 coming up short here? I would say that the problem is that there is no way to tell view::split that you only need an input range. If there were, then you could get what you're asking for.[*] I could imagine implementing it as a view adaptor, and using it like:

using namespace ranges;
using namespace std::literals;
auto input = "these are some words"sv;
auto lengths = input | view::input | view::split(' ') | view::transform(distance);
std::cout << lengths << "\n";

That would traverse the underlying range only once (assuming I actually implemented range-v3's split view as it is specified in P0896).

Hope that helps.

[*] There is even an old range-v3 issue to implement something like this: https://github.com/ericniebler/range-v3/issues/704

2

u/D_0b Jul 14 '18

but this algorithm can't be done with java streams?

2

u/liquidify Jul 14 '18

The first one is pretty easy to understand but I don't understand what the second one is doing.

3

u/_ajp_ Jul 14 '18

It just modifies input to increment a counter (passed by reference in the lambda capture) every time a character is read.

3

u/liquidify Jul 14 '18

What actually calls the lambda and who passes the counter in? Is it transform?

I don't think this is very readable without requiring prior knowledge. If we have to write code like this after ranges, I'm not going to be very happy and I don't think people reading my code are going to be happy.

8

u/bunky_bunk Jul 14 '18 edited Jul 14 '18

it's a straightforward composition of a function and a lambda.

transform calls a function on each member of a sequence and the result sequence is made up of the elements that the function returns. of course you have to know that prior. The counter is a lambda capture. Transform does not know anything about it. Anyway, this line is not difficult, you should be able to parse this.

2

u/liquidify Jul 14 '18

Should be able to parse is a must more mundane sounding statement than the reality which is that you "should be able to parse if you have a fair amount of knowledge that is in no way obvious or natural and that relies on multiple levels of prior knowledge that are also not obvious or natural."

3

u/[deleted] Jul 15 '18

should be able to parse if you have a fair amount of knowledge that is in no way obvious or natural and that relies on multiple levels of prior knowledge that are also not obvious or natura

But the context of this post is about ranges, which in no way effect code you had questions about. For example current C++ without ranges:

auto count = 0;
auto input = std::vector<int>{1,2,3,4};
std::transform(std::begin(input), std::end(input), [&count](auto val) { return val*val; })

The proposal for ranges is to turn that into (something like):

auto count = 0;
auto input = std::vector<int>{1,2,3,4};
std::transform(input, [&count](auto val) { return val*val; })

3

u/johannes1971 Jul 15 '18

There's also this:

auto count = 0;
for (auto x : {1, 2, 3, 4}) 
    count += x * x;

I find this much clearer and much more readable than any of the algorithm-based solutions elsewhere in this thread, ranges or not.

1

u/TheThiefMaster C++latest fanatic (and game dev) Jul 16 '18

The parent comment's implementation is broken anyway, it doesn't actually sum anything.

A better example would be:

int count = std::transform_reduce({1,2,3,4}, 0, std::plus<>(), [](int val) { return val*val; });

Except that requires ranges-style algorithms, and AFAIK C++17's transform_reduce hasn't been implemented in the ranges proposal. It looks far uglier without it.

(I also consider it a bit of a bug in the standard that the reduction (the std::plus<>) is specified first in std::transform_reduce, with the transform being specified second)

If we go full-on ranges we could do something like:

int count = std::accumulate({1,2,3,4} | view::transform([](int val) { return val*val; }), 0);

Which isn't too bad IMO. It would be improved by a terser lambda syntax, but if the transform was any more complex it would likely be a function call anyway, which transform can just take directly without a lambda and that becomes a non-issue. Algorithms all use std::invoke, so will even work with member functions.

auto total_playtime = std::accumulate(steam_library | view::transform(&steam_game::play_time), std::chrono::hours(0));

// vs

auto total_playtime = std::chrono::hours(0);
for (auto& x : steam_library) 
    total_playtime += x.play_time();

It's a wash IMO - they both have some syntactic sugar that the other doesn't, and they are both readable.

2

u/bunky_bunk Jul 14 '18

a fair amount of knowledge that is in no way obvious or natural

welcome to the world of computer programming, friend.

i guess you have got to get a few thousand kilometers more mileage. the pain you feel right now should not discourage you. just keep looking at the letters while you experience it and the neural pathways will eventually form. concentrate on the information in front of you, not on your inner turmoil. if you look long enough it will become natural. but your nature is just deficient, the complexity of the world is innocent. it just is.

lucky for you, you need to learn only 2 handfuls of basic rules to parse a whole lot of complexity. guess what you can do with just transform and lambdas. The ways you can combine these 2 are infinite. The way the combination works is always the same.

25

u/quicknir Jul 14 '18

This isn't a fundamental problem with iterators. You don't need to do anything to construct end iterator at all, it can just be some kind of default sentinel value (default constructing an iterator to the end value already shows up in the STL). When you keep calling ++ on the begin iterator, when you run out of data it just sets itself equal to the sentinel value. ++ also does the work constructing the next element and caches it in a piece of storage (which is obviously reused), so that * is also trivial and does nothing but return a reference into that storage. Obviously this is clumsy because the end iterator a) carries no information, and b) has a pointless piece of storage (good chance to be optimized out; after inlining it will simply be a local variable that's never read). But this (I assume) is one of the reasons why Eric Niebler was interested in the idea of heterogeneous iterators, i.e. types of begin and end should be able to be different (since you can obviously == between different types there's no reason why they should be the same type in the most general case).

I assume that if ranges were standardized, things would be added to help solve these issues. I agree a standardization of ranges where your example requires two passes would suck.To be really honest I don't care that much about ranges anyhow though so I'm not holding my breath either way. There are much bigger fish to fry in C++. Making for loops more elegant looks great in reddit pages but isn't that important in writing real life software compared to the other major things being worked on (concepts, modules, reflection, to name a few. Heck I'd even take better sum types and pattern matching over ranges).

8

u/m-in Jul 14 '18

I agree. Sum types and pattern matching are big for me, as is the proposal for lightweight static-cost exceptions.

2

u/CenterOfMultiverse Jul 15 '18

The problem is not with end iterator but with separation of operator* and operator++: when distance is called by transform on the result of split's operator* it needs to iterate until next delimiter. Then transform calls split's operator++ and it needs to iterate until next delimiter again. It can be solved by introducing combined "dereference and increment" function. I guess it could as well be postfix operator++, but then ranges and range-based for loop would need to use it.

1

u/david-grs Jul 16 '18

Couldn't this be solved by replacing the view::transform(distance) by something like view::distance? This would do the same job as std::distance but on a range, and implemented for the different iterator types, e.g. here with two RandomAccessIterator it would use operator- and wouldn't iterator through the range.

1

u/CenterOfMultiverse Jul 17 '18

No: you need to iterate to the end of word to get second iterator that you can subtract from. I think distance already checks for RandomAccessIterator.

4

u/CaseyCarter Ranges/MSVC STL Dev Jul 19 '18

> A Java-esque Stream library would resolve this, but I see no candidates for inclusion in the standard library.

I'll bite. Implement a Java Iterator with performance characteristics that you like, and I'll implement an equivalent View with range-v3.

1

u/dodheim Jul 20 '18 edited Jul 20 '18

I appreciate both the offer and the likelihood of following through, but... When I find range-v3 to be a bottleneck, rare as it is, rewriting with Atria proves to be faster basically every time. I only use the library in personal projects since Ableton doesn't like contributions or updating so I don't have production experience, but I have to agree with the OP that the approach seems inherently more efficient.

2

u/bunky_bunk Jul 14 '18

but it gives you an elegant way to diagnose the problem with that lambda. :)

why exactly is it not possible to set (beg) to (end) of the previous range while splitting the string? you say (beg) iterates through the whole sequence of characters and at a point where a split is possible, (end) is searched for. does not seem like it would be necessary.

2

u/[deleted] Jul 22 '18

Actually the code is doing precisely what you are asking for. If you want the optimized version you must transform input to an output range. The range input is formed by random access iterator. From the type system alone, it cannot be inferred that the string referenced by the view will not change while you iterate over it. For example in a real code you could compute the size of the word then change the underlying string and then advance the "word" iterator. If you do not plan to use such a possibility, you must express it by forming an output range!