Best practices regarding iterator "specialization"?

Long story short, I can implement some functionality in my library through forward iteration or backwards iteration. The backwards iteration is an order of magnitude faster in real-world use cases.

Ideally, I'd like my library to work with all iterators, but allow users to enjoy the optimized implementation for DoubleEndedIterators. I could do this in C++ with template specialization, but I haven't researched if it's possible with Rust's specialization features, and I don't want to use nightly features anyways. The simplest solution would be to write two functions (one for Iterator, one for DoubleEndedIterator). That seems a bit cluttered, though, and I wonder if there's a more elegant solution. Is there a "best practice" that I should follow in these sorts of situations? Thanks.

With an order of magnitude difference, I would make them explicitly separate and make it clear in documentation which one is preferable. Otherwise you risk performance footguns for your users, like if they added a simple take_while and suddenly fall on the slow path.

4 Likes

I can't make your first paragraph and second paragraph line up with each other in my mind well enough to figure out what you're doing. The first paragraph sounds like you're implementing iteration for a struct in your library, while the second paragraph makes me think you're talking about a function (or two) in your library that takes an iterator.

Assuming the latter: DoubleEndedIterator has Iterator as a supertrait, so if your method takes an I: Iterator, it will also work with any DoubleEndedIterator.

I'm not exactly sure what this could mean in that context though. The speed of iteration itself is outside of your control when accepting an iterator; for "forward vs backward iteration" to make any sense in this context implies some prior agreement on the order of elements that any given iterator returns.

E.g. I could give you an double_ended_iter and you could call next_back on it, or I could give you a double_ended_iter.rev() and you could call next on it to get the elements in the same order.


If you're implementing an iterator, I agree with @cuviper. If there's a way to transform a fast-forward-but-slow-backwards iterator struct into a (separate) fast-backwards-but-slow-forwards iterator, you may have some additional options.

Note that while C++ generally tries to make things work with all iterators (even if doing so ends up really slow because std::advance is O(n)), Rust is generally far more willing to say "no, I want a DoubleEndedIterator -- or even a slice -- for that".

So if the difference is that substantial, I'd say you should just offer the fast one. People can collect their forward thing if they want.

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.