Iterators and Ranges: Comparing C++ to D to Rust - Barry Revzin - [CppNow 2021]
Vložit
- čas přidán 28. 05. 2024
- #Boost #Cpp #CppNow
Slides: cppnow.org/history/2021/talks/
CppNow Website: cppnow.org
CppNow Twitter: @CppNow
Streamed & Edited By Digital Medium Ltd: events.digital-medium.co.uk
------
The STL introduced an iterator abstraction into C++ that generalized the notion of pointer and allowed for the ability to have arbitrary sequences that could be generically traversed and have algorithms performed on them. But the C++ iterator-pair model isn't the only possible approach to solving this problem. The D Ranges model, while isomorphic to the C++ one, is still quite distinct and has some interesting characteristics. Many languages (including Rust and Python) have an entirely different iteration model from the C++/D one.
Are D Ranges better or worse than C++ Ranges? Is Rust's better than C++'s? Does it depend on what your definition of is is? The goal of this talk is to examine the problem space and find out.
------
Barry Revzin
Jump Trading
Barry is a senior C++ developer at Jump Trading in Chicago, a research and technology driven trading firm. After programming for many years, he got really into the nuances and intricacies of C++ by being unreasonably active on StackOverflow (where is he is the top contributor in C++14, C++17, and C++20). A lot of his C++ knowledge comes from just answering questions that he doesn’t know the answers to, especially when he answers them incorrectly at first.
His C++ involvement escalated when he started attending standards committee meetings in 2016, having written dozens of papers for C++20 and now C++23. You might know him from such features as , pack expansion in lambda init-capture, explicit(bool), conditionally trivial special member functions and, hopefully coming soon to a C++ near you, deducing this.
Outside of the C++ world, Barry is an obsessive swimming fan. He writes fun data articles for SwimSwam and also does analysis for the DC Trident, a professional swim team with multiple Olympic Gold Medalists (including Katie Ledecky and Natalie Coughlin).
------
May 1, 2022 - May 6, 2022 - Aspen, Colorado
-------------------------
---
*--*
--- - Věda a technologie
![Don't constexpr All the Things - David Sankel [CppNow 2021]](http://i.ytimg.com/vi/NNU6cbG96M4/mqdefault.jpg)
![Don't constexpr All the Things - David Sankel [CppNow 2021]](/img/tr.png)
![The Complete Guide to `return x;` - Arthur O'Dwyer - [CppNow 2021]](http://i.ytimg.com/vi/OGKAJD7bmr8/mqdefault.jpg)
really good presentation
you managed to stay everyone's friend, while stating all disadvantages
loved it
Everyone but Java, that is ;-)
I'm not sure... i'm not an expert but i see Rust misrepresented or presented from outdated or partial information
@@AK-vx4dywhat's outdated? Seems to me he presented the fundamentals of Rust's library design, which certainly don't change every year.
It would be interesting to see how the c++ design would look like in D or Rust
Thanks, Barry. This is a very enlightening presentation.
An excellent overview. One starts to appreciate the decoupled design of the STL iterator only while going outside of the trivial.
It would have been nice to have the simple read-once model as a compatible-to the extent it could be-option in the standard library, but it's not hard to maintain such a thing outside of it.
I'm new to Rust but i saw rotate and sort also some examples can be implemented differently for example instead of separte find_if and erase this can be one function.
Also when was example with drop, compiler can optimize whole like is done in C# Linq
Couldn't you implement the group_by in rust using peek?
The find_if example where he reuse it to remove an array can simply be implemented by filter isn't it? groupBy can also be implemented by pairing zip . mapG where mapG will max X => Same(X) if its the same and X => Div(X) if its a divider, i.e. that its different than the previous element. This is in fact a lazy iterator and therefore doesn't require its consumer to perform memory allocation if unneeded.
i love languages comparisons like this
Is that some C++ code under the comment "// D" in 28:04 ?
it's all c++
Maybe this is whats wrong with C++. Trying to have all these edges cases in the std.
I'm wondering where Java's Streams fall into. I dislike Java's implementation of Iterators and usually avoid them, but using Java Streams has always been a great way to get complex logic down into a single line of code. It also allows for sorting e.g.
aren't java streams are just functional wrappers around the actual iterator model of java ?
This exact topic is discussed in a newer version of this talk: czcams.com/video/95uT0RhMGwA/video.html. Actually non trivial and interesting
1:01:50 if there are any Rust people watching, I'd be curious if there is a different pattern around this limitation. I use iterators/ranges/algos heavily in C++ and it is one of the reasons why I have stayed away from Rust, but maybe I'm missing something.
As ordered lists of elements are usually stored in contiguous memory (array, `Vec`), you can most of the time get a mut slice (equivalent of dynamic-extent `std::span`), which has (or could have) these algorithms. Not sure what the proper solution would be for non-contiguous memory.
The itertools crate (see the docs) has a huge number of iterator adaptors extending the ones in the standard library, and I didn't see anything that is actually impossible to implement in a library here.
* binary group_by: it doesn't seem to be available, but it is possible to implement. A library implementation would probably hold on to a copy of the previous element, but you would use it on an iterator which yields references anyway, so the copy is cheap.
* adjacent_find: tuple_windows() returns adjacent pairs, which you can then find() for equality.
* adjacent_difference: tuple_windows() and then map()
* sort: sorted(). There isn't much special about this iterator, it just collects into a vector and sorts that. The example with sorting one iterator using a key from a different iterator is indeed not possible without allocating some space for the result, but it's less painful to have a vector of pairs in rust so this doesn't come up much.
* slide: tuple_windows(). Note that this does copy the elements in order to return them multiple times, but you can add an adapter to turn the values into references so that the copy is cheap.
* search: you should really be doing this over vector or string, where the algorithms are way better, but for arbitrary iterators you can still do it by using searching windows() on the iterator
* mismatch: zip() and then find(|x, y| x != y)
* find_end: same as search, but on windows().rev()
* lower_bound, upper_bound, equal_range, binary_search: these are inherently random access, so you can only do them on vectors in the standard library, but there are crates that offer these functions given a random access trait
* prev_permutation, next_permutation: permutations() and permutations().rev()
* stable_partition: this is inherently a collection operation, not an iterator operation, but partition() does this
* rotate: I don't understand how this can be considered an iterator operation at all. You can of course rotate a vector but doing this on a generator function is nonsense. Still, you can do it via it.skip(n).chain(it.take(n)) if you can copy the iterator
@@digama0Yes but I think most of those iterators don't meet the zero overhead principle, in other words they are posible to implement, but you have to save states or do extra operations
When he says "we have to keep a copy of this item to compare, unlike in C++ where we can just keep another iterator on the range" - what is the actual overhead here? You can keep the _reference_ returned by Iterator until the next iteration, it's just a pointer. C++ iterators are usually also an abstraction of pointers.
Lots of the methods requiring random access (permutations, binary search, rotate) I would consider container methods rather than iterator adaptors. In particular you mostly use them on contiguous memory (spans/slices), where these things _are_ implemented.
If this isn't the case then you may have to implement them yourself, but could you provide an example in C++ of where this would actually be used? You can implement the range interfaces for more unusual types, but usually without random access, and often with different performance considerations than the std algorithms.
Is it just me, or did other people want to actually SEE the darn iterators in practice? just something simple, like a pipeline of operations -- taking 10 ints -> sorting them -> finding prime numbers -> mulltipllying those by 100. I would have loved to have seen how each of the languages achieved this, and how it looked syntacticallly. But this talk, while interesting, got too much into the weeds and i feell like a simple 1 slilde overview showing the alternative APIs in practice woulld have been a much better way to go.
It seem to me, that in dranges filter you just could call 'prime' in constructor. Thus, neither other 'prime' calls are needed, nor do 'isPrimed'.
Or did I misunderstand something?
views tend to be lazy and trivial to initialize, so you tend to avoid doing anything until they're called
This is clearly NOT and explanation of the Iterator Pattern!
This is incorrect.
Rust chose the "iterator" model as presented for a very good reason - you can't return a pointer-like object to the value without explicitly reasoning about the value's ownership. A value cannot be owned by a container and an unrestricted iterator at the same time so in Rust the iterator either takes ownership over the value or it borrows it. In the former case the container no longer has the value and we cannot read it from there again, in the latter case, we're bound by Rust's mutation XOR aliasing guaranty.
C++ simply doesn't protect you here and that's why iterator invalidation exists.
Having said that, this isn't impossible as the OP claims since you can always "uplift" this model into the reader model like so:
wrap your source(s) with an iterator that yields a pointer-like object to the values instead of the values themselves. These extended iterators would then be able to provide these additional functions in a composable way, **when needed**. Of course in Rust this is more involved since we need to account for the ownership semantics described above which I imagine would be a case-by-case endeavour.
In C++ terms: the next method would return "Optional" (maybe a Weak in rust? depends on the use-case)
Nothing you said establishes that the presenter is incorrect. You merely added context for the motivations in the initial paragraph, and provided a non-generic workaround in the second. The fundamental tradeoffs are still there.
At 39:31, the slide is just false. Iterator in rust only have the associated type `Item` which is the equivalent of `value_type`, but neither `reference`, nor `difference_type`. And the `next()` function returns `Optional`, and not `Optional`. EDIT: since rust references are basically the equivalent of `not_null`, you can create an iterator over a reference, since `not_null` is just a value.
...none of this syntax is D
It's c++
18:17 "if we were to implement it in c++"