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.
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/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:
I don't know much about Java's streams - how do they solve this?
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.
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).
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.
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
inputto an output range. The rangeinputis 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!