Efficiency of `.contains` on `Range::into_iter()`

help
1

I'm writing a program that needs to handle numbers within a specific range. The program itself isn't that important (FWIW, it's calculating "Square loops"), but I want to make it as general as I can, in order to be able to use it for variations on the original problem.

I'm struggling to find the best way to express the type of one of my arguments. Logically, it's a collection of values (i32, typically), and all I ever do with it is extract the "first" value, and test a value for membership.

At the moment, I'm using a RangeBounds<T> as my parameter type, because the typical usage is to pass a range like 1..10. The .contains method is efficient (it's just 2 comparisons), and I can get the first value via .start_bound() (with some juggling to catch ranges with no lower bound). But this limits me to only passing ranges. An alternative would be to declare the type as Iterator<T>, and use .first() and .contains(). If I do that, I'd pass (1..10).into_iter(), which is fine, but my concern is whether that would still use the efficient .contains() implementation that a Range object can support.

To some extent, this doesn't matter - for my current use, it's fast enough either way. But I'm interested in learning how to write good Rust code, not just solve my current problem. And I don't know how I can find out the answer to this question. Any pointers would be very helpful :slightly_smiling_face:

2

std::range::RangeIter doesn't appear to provide its own implementation of .contains(), nor does std::ops::Range, so it will probably go over all numbers in the range.

You could accept an iterator of ranges, perhaps?

3

Iterator doesn't have contains or first methods though, so that makes it unclear what you're asking.
If you mean Iterator::find, then that one takes a closure, so we can't optimize it at the library level to do the O(1) thing for integers because we don't know what user-provided closures do.

LLVM still might be able to, let's see what godbolt says:

Nope, still a loop

example[98f869ed581a9870]::contains:
.LBB0_1:
        mov     rax, rsi
        cmp     rdi, rsi
        je      .LBB0_3
        lea     rsi, [rax + 1]
        cmp     rax, rdx
        jb      .LBB0_1
.LBB0_3:
        cmp     rax, rdx
        setb    al
        ret
4

In these kind of situations I usually feel better if I apply YAGNI rather than DRY.

If, however, you want to explore how to make your API "just right".

  1. Make sure you have a test that covers your current use case
  2. Add another that covers a different case, which you expect to be currently unsupported
  3. Change the signature and code to support this
  4. Tweak them code until it feels "as good as it needs to be right now"
  5. Repeat from step 2

This will probably lead you in the direction of a trait bound on Iterator, Index, OR killing them idea and sticking to the specific case as contains is a direct impl method and but a trait in stdlib.

In other words. The question sounds a little to wide scoped right now. Can you squeeze it down to a specific case that works and a specific one that doesn't?

5

std::ops::Range does - see here. Or am I misunderstanding the docs?

Huh, that's confusing. I must have mis-transcribed something when I simplified my example. For first it's not so much of an issue, as I can always use next instead[1]. But contains is a bigger problem - I am using contains, maybe I'd left the Range constraint around so the compiler used Range::contains without me realising.

But it's a good point. Any notion of containment on an iterator will exhaust the iterator, so that's not what I intended. I'm translating concepts from Python (my main language) into Rust, and I was probably thinking of iterables, rather than iterators, and then confusing the translation. But really, the equivalent in Python of what I want is Container (which supports containment and iteration). Is there such a trait in Rust? One of the big difficulties I have when writing Rust is finding traits - it's easy to see what traits a particular type supports, but much harder to find what traits exist.

Should I be writing my own trait? That seems a bit over-engineered, but maybe it's my expectations that are too grand. Coming from Python and its duck-typing, I'm used to the feeling that I can use a bunch of methods that I want, and then it's just a matter of making sure that what I pass "conforms" to my expectations. But that may be too much to ask of Rust, where compile-time type checking is so much stricter.

The problem is, it's not really a matter of "working". If we ignore the confusion I describe above, and assume I have the right declarations so that I can call something like contains on my argument, a linear search through the valid values will always work. But for Range, that's unnecessary - you can just check if the supplied value is between the lower and upper bounds. And that's what I'm trying to ensure - that I get the efficient implementation rather than the inefficient one.

Yes, I know premature optimisation is the root of all evil, and all that. But I'm not optimising prematurely here. I have a working program, and if that was all I wanted I'd stop there. But I want to learn how to write efficient and extensible Rust code, and I don't want to wait until I have a huge project with significant efficiency requirements before I learn the basics. So it's not really YAGNI - I don't need it to solve my initial problem, but I do need it to address my learning goals (if that makes sense...)

  1. Although it does advance the iterator, affecting other operations ↩︎

6

Simplifying things a bit further, but at the cost of making the example more abstract, suppose I have a function that can take either a Vec<i32> or a Range<i32>, and in both cases I want to be able to do two things in the function:

  1. Get the "first" element of the argument (treat ranges like ..2 as having no "first" element, just like an empty vector). Basically, arg.into_iter().next()
  2. Check if a value is contained in the argument, i.e., arg.contains(val).

How do I specify the type of the argument?

7

There isn't such a trait[1], and as far as I know one of the relevant reasons against having a very general “Container” trait/interface is the vastly different performance characteristics of certain methods between different container types.

Another problem with functionality like a contains method in particular is that efficient implementations of such functionality can depend on traits like Ord (or Hash) whereas linear scans only require [Partial]Eq. The analogous problem exists for example in Haskell, where they have a Foldable trait[2] that offers a function called elem to check for element membership in - basically - any type you can iterate over. But the Set datatype needs to offer its own member function, and using elem on it is actually an anti-pattern / bug, since it's much less efficient.

  1. unless you count IntoIterator, I guess? ↩︎

  2. in Haskell lingo a "typeclass" ↩︎

8

I fully understand. I was in that situation (from python to rust) 2 years ago and Combining rust & python - FizzBuzz was the result (I challenge anyone not to scream YAGNI at me!). But the whole point was the learning journey.

I still find that "DRY before YAGNI then iterate in little bits" as a mindset helps me, particularly in these situations where I know I'm going to go well past YAGNI.

As for how to work through and find this stuff in rust:

  1. Look for a trait in stdlib - I intutitively searched for "contains" in stdlib docs and ran down the list looking for a Trait - no luck
  2. Decide whether it's worth looking for a 3rd party trait (crates.io & docs.rs are even better for this than pypi). In your case - certainly not the road I'd go down.
  3. Roll your own trait - to get a feel for how this would work. Maybe something like trait Bounded with a default implementation of fn contains(&self, &val) -> bool that calls self.contains(val) then impl that for anything you feel like that is in stdlib and has a contains method. (Others could impl your trait for their types, but stdlib can't.)
  4. Spend some time working around the ideas of overlapping impls when you think about adding a generic impl<T> Bounded for T where T: IntoIterator that uses find.[1] (That's a good part of rust to learn)

I hope this helps, even if it (sometimes deliberately) opens more avenues for questions than it provides answers

  1. The "more correct" solution involves using find in the default solution and the more performant contains in the specific cases. But seriously - don't start there, it won't help with gaining the right understanding. ↩︎

9

You can of course define a trait for your specific usecase. It could look something like this: