This is a talk from the 2021 c++now conference: https://www.youtube.com/watch?v=d3qY4dZ2r4w
June 14, 2021 Iterators and Ranges: Comparing C++ to D to Rust | ||||
---|---|---|---|---|
| ||||
June 14, 2021 Re: Iterators and Ranges: Comparing C++ to D to Rust | ||||
---|---|---|---|---|
| ||||
Posted in reply to Friendly Neighborhood Weirdo | On Monday, 14 June 2021 at 01:48:18 UTC, Friendly Neighborhood Weirdo wrote: >This is a talk from the 2021 c++now conference: https://www.youtube.com/watch?v=d3qY4dZ2r4w Interesting video. There is something that I'm kind of confused about. The narrator in the video claims that in D popFront doesn't consume the element. Is this true? When I do a popFront, doesn't it consume the first element in an array for example. Can someone clarify this? Also in Rust, next does consume the element. However, in Rust you can iterate over references (which also automatically borrows). So iterating over borrowed references does not consume the underlying data structure. |
June 14, 2021 Re: Iterators and Ranges: Comparing C++ to D to Rust | ||||
---|---|---|---|---|
| ||||
Posted in reply to IGotD- | On 6/14/21 5:33 AM, IGotD- wrote: > The narrator in the video claims that in D popFront doesn't consume the > element. Is this true? When I do a popFront, doesn't it consume the > first element in an array for example. Can someone clarify this? popFront() consumes the range, not the container: import std.range; void main() { auto arr = [ 1, 2, 3, 4 ]; auto half = arr[0..$/2]; half.popFront(); assert(arr[0] == 1); // Nothing happened to the array (which 'arr' // is just another slice of it) } Ali |
June 14, 2021 Re: Iterators and Ranges: Comparing C++ to D to Rust | ||||
---|---|---|---|---|
| ||||
Posted in reply to IGotD- | On Monday, 14 June 2021 at 12:33:37 UTC, IGotD- wrote: >On Monday, 14 June 2021 at 01:48:18 UTC, Friendly Neighborhood Weirdo wrote: >This is a talk from the 2021 c++now conference: https://www.youtube.com/watch?v=d3qY4dZ2r4w Interesting video. There is something that I'm kind of confused about. The narrator in the video claims that in D popFront doesn't consume the element. Is this true? When I do a popFront, doesn't it consume the first element in an array for example. Can someone clarify this? In D, So it's not an insight w.r.t D's design, but rather a clarification for the C++ audience which presumably expects That said, the whether
Also in Rust, next does consume the element. However, in Rust you can iterate over references (which also automatically borrows). So iterating over borrowed references does not consume the underlying data structure. I don't have much Rust experience, but my understanding is that Rust's |
June 14, 2021 Re: Iterators and Ranges: Comparing C++ to D to Rust | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ali Çehreli | On Monday, 14 June 2021 at 13:30:52 UTC, Ali Çehreli wrote: > popFront() consumes the range, not the container: I glossed over the presentation, and I don't think he really covered things as well as he should. For instance there is a difference between generators, nonconsuming-iterators/table–pointers, consuming-iterators, but sometimes the distinction is blurry. What if you create a range that consumes a queue. What if you create a range that interpolates and doubles the length of the source. What if you want to modify the underlying container while iterating over it. It would be nice with an ontology for table-pointers, iterators and generators, along the lines of the original Gang of Four book on design patterns, but I didn't really feel this presentation brought anything to the table. His take on this was very "syntactical". Also, his assumptions about performance were not really well founded. You have to look at how iterators are used in actual alogrithms and how that could block optimizations to say anything sensible about that. E.g. his take on StopIteration in Python is not really correct either, you can write a generator (coroutine) with no explicit StopIteration (although the semantics implies a raised exception, but that does not mean the implementation has to). |
June 14, 2021 Re: Iterators and Ranges: Comparing C++ to D to Rust | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ola Fosheim Grøstad | On Monday, 14 June 2021 at 13:45:14 UTC, Ola Fosheim Grøstad wrote:
> Also, his assumptions about performance were not really well founded. You have to look at how iterators are used in actual alogrithms and how that could block optimizations to say anything sensible about that.
Think of it this way:
If it is possible write an O(1) wrapper around an iterator/range implementation and emulate any of the other interfaces, then they have the same performance (in terms of the ability to optimize).
I suspect that (except for table pointers) they are equivalent in O(1). So basically all the same...
|
June 14, 2021 Re: Iterators and Ranges: Comparing C++ to D to Rust | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ola Fosheim Grøstad | On Monday, 14 June 2021 at 13:45:14 UTC, Ola Fosheim Grøstad wrote: > On Monday, 14 June 2021 at 13:30:52 UTC, Ali Çehreli wrote: >> popFront() consumes the range, not the container: > > I glossed over the presentation, and I don't think he really > covered things as well as he should. Rust iterators have been discussed here before, e.g. in https://forum.dlang.org/thread/arufovtvoewhyfuesvco@forum.dlang.org?page=1 and there are tones like "Rust has a better design and D does things differently only for historical reasons.", and maybe "it'd be too hard for D to emulate Rust without a borrow checker". Similarly, I think people could agree that D's ranges are simpler than than C++'s iterators, and that C++ just has iterators because they hadn't though of ranges first. What this presentation does well is to add nuance to these "X is just better than Y" relationships. Some tasks are trivial for C++ but a hassle for D, and surprisingly many tasks are excluded by Rust's iterators. The only clear loser is Java, where there really are historical reasons that hampered its design. I'd also never noticed std.algorithm.cache until I went searching for a library solution that I was sure must exist for the "filter calls map's function twice" problem that D has, but Rust doesn't have. |
June 14, 2021 Re: Iterators and Ranges: Comparing C++ to D to Rust | ||||
---|---|---|---|---|
| ||||
Posted in reply to jfondren | On Monday, 14 June 2021 at 14:10:48 UTC, jfondren wrote: > What this presentation does well is to add nuance to these "X is just > better than Y" relationships. Some tasks are trivial for C++ but a > hassle for D, and surprisingly many tasks are excluded by Rust's > iterators. But then he should have focused on concrete complex algorithms and how one approach makes the algorithm much harder to read or some other usability measure. But C++ didn't have iterators until C++20, they had table pointers/cursors (which they wrongly call "iterators"). > I'd also never noticed std.algorithm.cache until I went searching for > a library solution that I was sure must exist for the "filter calls > map's function twice" problem that D has, but Rust doesn't have. I think C++ may gain an edge with concepts. D will eventually need something similar and make it easier to write composable template libraries. By composable I mean that you compose new types applying templates to templates to templates. Right now, this is not really possible in D because of the type unification issue. If C++ library authors succeed in making good use of such features, they might gain an edge. BUT the D community is much smaller, so it should in theory be much easier for the D community to develop "standards" for creating composable template libraries. So even though C++ may have an edge right now, they also have a bigger hurdle to overcome for establishing eco system "standards". D needs to capitalize on being small and improve template composability between libraries, IMO. |
June 14, 2021 Re: Iterators and Ranges: Comparing C++ to D to Rust | ||||
---|---|---|---|---|
| ||||
Posted in reply to Friendly Neighborhood Weirdo | On 6/13/21 9:48 PM, Friendly Neighborhood Weirdo wrote:
> This is a talk from the 2021 c++now conference: https://www.youtube.com/watch?v=d3qY4dZ2r4w
The talk was really interesting and engaging. Thanks for sharing!
One thing I'll note, he said for C++ `ranges::search`, there are 6 pairs of iterators that can be used:
first .. last
first .. mid.begin()
first .. mid.end()
mid.begin() .. mid.end()
mid.begin() .. last
mid.end() .. last
But in reality, there are 6 more:
last .. first
last .. mid.begin()
... // etc
Of course those are invalid, but the C++ compiler will happily use them, and graciously allow memory corruption. And of course, that is the point of D using ranges instead of iterators (maybe he glossed over it because C++ developers take unsafety as a given).
It got me thinking again about iterators in D and how that might look like. A lifetime ago I had a collection library (dcollections) that had both ranges and "iterators" that I called cursors. The benefit of a cursor is it could refer to exactly one element, and you could use them to compose ranges from the original. In dcollections, when you did `container.find` you got a cursor, and you can use the collection to construct a range using 2 cursors, or remove a specific element using the cursor. I find this functionality extremely useful, and it sucks that D doesn't have something formal for this situation. He is right that composing ranges from the result of algorithms is needlessly complex in D.
I wonder if there is room for hobbled iterators (cursors) to be in D in some capacity.
-Steve
|
June 14, 2021 Re: Iterators and Ranges: Comparing C++ to D to Rust | ||||
---|---|---|---|---|
| ||||
Posted in reply to Steven Schveighoffer | On Monday, 14 June 2021 at 14:29:57 UTC, Steven Schveighoffer wrote: >Of course those are invalid, but the C++ compiler will happily use them, and graciously allow memory corruption. And of course, that is the point of D using ranges instead of iterators (maybe he glossed over it because C++ developers take unsafety as a given). Apples and oranges. Gang of Four defined iterator to be what D and C++ call "ranges", basically a "heavy" object that has builtin knowledge of how to traverse a data-structure. Of course, the term "range" is a misnomer since you can traverse a graph in numerous ways, so you can have a depth-first-iterator, breadth-first-iterator, and indeed have iterators that to randomized walks... so iterator is a better name. C++ STL "iterators" are light-weight pointer-abstractions. You can create heavy C++ "iterators" that keeps track of where "the end" is and have it throw an exception. C++ does support safe iterators. STL does not. |