The Trusted Iterator Length Problem

1

Currently we have an ExactSize trait for an Iterator to claim that its size_hint is precise. Unfortunately, all code is forced to assume that ExactSize is exactly that: an unsubstantiated claim. The most we use it for is to allow certain iterator adaptors to implement DoubleEndedIterator iff they wrap an ExactSize iterator. Nice, but meh.

There is however a very real need for a way to unsafely assert that your iterator has a truly exact size. When we deprecated several Vec constructors in favour of iterators + collect, we introduced what I measured to be a 33% perf regression (3 vs 4 units of time when constructing a Vec of 100, 000 elements), because the Vec::from_iter code has to count and constantly branch on the number of elements inserted in case more than the iterator claimed to have is inserted (this is implemented by just calling push over and over). If we trusted the iterator, we could instead just unconditionally offset the write-head and set the length at the end.

Here are some candidate solutions to the problem:

Make ExactSize an unsafe trait

I honestly don’t think there’s any iterator that seriously “isn’t sure” about its precision, and you’ll get busted DoubleEnded impls if you’re wrong anyway. This seems relatively harmless to just do. This design has the benefit of having no redundant notion of exactness. Unfortunately we have basically no facilities for specialization, so implementing ExactSize would still be useless today. No reasonable code would only accept ExactSize iterators just for a performance optimization.

However assuming that we do get some specialization facilities, this would basically be flipping the bird to trait objects, because e.g. a Box<Iterator> would have its ExactSize-ness erased.

This would also be a breaking change for the current ExactSize trait, which I believe has been stabilized.

Add TrustedExactSize on top of ExactSize

All the same strengths and weakness of the previous design, but with two changes:

  • it’s back-compat to add whenever (yay!)
  • it further complicates the iterator trait story, while adding basically duplicate notions of ExactSize (boo!)

Add a default-impl’d fn to Iterator

e.g. unsafe exact_size(&self) -> bool { false }

For 99.9% of iterators, this will produce a statically known value, and therefore incur no runtime cost to branch on assuming sufficient optimization (Rust’s favourite kind of optimization).

Over trait-based designs, this design has the following advantages:

  • This design is compatible with Trait objects, it just requires an actual runtime branch to occur at the start of the procedure; a fairly trivial cost for collect, especially when performing dynamic dispatch on the iterator already.
  • This design can be used right now, and would be highly ergonomic to use: if iter.exact_size() { fast } else { slow }

However it has the following drawbacks:

  • This leaves us with a duplicate ExactSize trait, as it is still useful for DoubleEnded impls
  • The unsafe is “wrong” because it should be considered safe to use but not to override. We lack the tooling to express “unsafe overrides”.

That previous thing but with proper unsafe semantics

That’d be p. cool

3 Likes
2

Why not this? I think this is fantastic.*(I’ll revise this in a new post)

unsafe exact_size(&self) -> Option<usize> { None }

I’d favor removing ExactSizeIterator from libstd too, not sure it’s carrying its weight.

3

Can you clarify what you mean by "proper" unsafe semantics? My feeling is that we could add a wide variety of keywords conveying various nuances regarding just who is trusting whom, or we could just say that unsafe means "warning: read the docs carefully". I'm not sure that having a lot of keywords adds anything above that; everytime I've dived into it I've found quite a wide variety of shades of meaning that all wind up meaning "read the docs" in the end. (Put another way, I think if you're doing an audit, you always to examine both sides of a "unchecked-trust-relationship" -- one to check that the callee is doing the right thing, and another to check that the caller is relying only on what it said it would rely upon.) To that end, I think an unsafe method in the trait is a pretty good option.

However, there is one minor change that would be required to use an unsafe fn, which is that I think today it is legal to implement an unsafe fn with a safe fn. If so, we'd want to change that (which I think is fine). This is because unsafe the meaning of unsafe is being expanded from "unsafe to call" to "read the docs" :smile:

4

Here is a way to use unsafe by its usual meaning:

trait Iterator {
...

     fn size_hint(&self) -> SizeHint { SizeHint::from_bounds(0, None) }
}

pub enum Size {
    Exact(usize),
    Hint(usize, Option<usize>),
}

pub struct SizeHint(/* private */ Size);

impl SizeHint {
    pub fn from_bounds(low: usize, high: Option<usize>) -> Self { 
        SizeHint(Size::Hint(low, high))
    }
    /* **unsafe** */
    pub unsafe fn exact(size: usize) -> Self { SizeHint(Size::Exact(size)) }
    /* and then accessor methods etc */
    pub fn exact_size(&self) -> Option<usize> { .. }
    pub fn lower_bound(&self) -> usize { .. }
}

While size hints are revisited, we might want to simplify & remove the upper bound, it is never used.

I love spewing ideas, so why not this model instead?

 pub enum Size {
        Exact(usize),
        LowerBound(usize),
        Endless,
 }
1 Like
6

There was a discussion on reddit about this a few days ago.

I think that suffers the same "unsafe is wrong" problem: unsafe { ... } can be regarded as "I've taken on the compiler's job to prove this correct"... which is something the callers of exact_size literally cannot do since they get called with arbitrary user-defined code. It's up to the implementers to ensure they're not feeding bad data back up into the use-sites.

Unfortunately that model doesn't quite work: presumably the slice iter sets an exact size hint, in which case one can implement size_hint for any type as:

fn size_hint(&self) -> SizeHint {
     [1, 2, 3].iter().size_hint()
}

with absolutely no connection between the return value and the real size, and no unsafe. A solution may be to make size_hint unsafe to call, essentially combining the two approaches.

7

It's even worse than I understood from that comment. The proposed method would be unsafe to call, but you can implement it without unsafe, with a simple fn exact_size(&self) -> bool { true }.

EDIT: unsafe.

8

How does this work with unwinding? Will it only work for iterators that don’t panic? Will it only work for iterators whose element types don’t need drop code to run?

9

Good catch. I wasn’t going to be worried, but that might even happen by mistake (wrap an exact length iterator, but change the .next() impl).

It’s like we have a man-in-the-middle attack and need a way to authenticate the implementor. What if we just parameterize SizeHint by the Self type? Example Then MITM is removed from the equation!

Edit: Apparently I missed the link to reddit (I swear I read “it was discussed on irc”), and SizeHint<Self> too was debunked there. Maybe it still is the way forward in combination with negative bounds.

10

I think it’s fine for an iterator to panic, even if it’s exact. In e.g. the Vec case it’s easy enough to see how far you’ve gone if something explodes. You need some kind of “cleanup” guard, though.

11

I'd be okay with this design.

12

@Gankro So where’s the difference between now and “trusted” iterators if the trusted iterators might panic any time?

If you have to keep the number of elements successfully returned from the Iterator anyway, why can’t you do this now and also just clean up as much as the iterator has produced in the None case? What I want to say is that panicking should result in the same action as an early None, so I don’t see what would be gained with such a trusted iterator.

13

I think for most uses of trusted ExactSize, the real concern is more elements being yielded. This would cause e.g. a buffer overflow in Vec.

14

As much as I hate saying it, have you tried to benchmark this? I have no idea what has a bigger performance penalty, the checking for “too few elements” or the one for “too many”.

15

tbu: too many has to be checked on every element, too few only has to be checked at the end. e.g.

// can be more than size_hint
let size = iter.size_hint().0
let mut vec = Vec::with_capacity(size);
let mut ptr = vec.ptr_mut();
for (i, elem) in iter.enumerate() {
  if i > size { 
    resize_or_something() 
  } else {
    ptr.write(elem);
    ptr = ptr.offset(1);
  }
  vec.set_len(i);
}
vec

vs

// can be less than size_hint
let size = iter.size_hint().0
let mut vec = Vec::with_capacity(size);
let mut ptr = vec.ptr_mut();
let mut guard = PanicGuard::new(&mut vec, &ptr as *const _);
for elem in iter {
    ptr.write(elem);
    ptr = ptr.offset(1);
}
drop(guard);
vec

impl Drop for PanicGuard {
    let len = (*self.ptr as usize) - (self.vec.ptr() as usize);
    self.vec.set_len(len);
}

Seems pretty obvious which is going to have better perf?

16

The PanicGuard thing is actually wrong since a “natural” exit has the ptr diff correct, but a “panic” exit has the ptr diff off-by-one, so you actually need an all_is_well method to manually drop, but that’s not actually the main point.

eh no wait it’s always right. ugh pointer arithmetic.

The key point is that one is constantly counting and branching on the possibility of a resize inside the loop regardless of the possibility of a panic, while the other only has some constant amount of setup and teardown before and after the loop, plus something someting landing pads only if a panic is actually possible.

17

I’m not sure this is moving in the right direction, but there should be plenty of scuzzy fixes if the 33% perf is what bothers you. Rather than test on every element, some loop unrolling (read 16 elements, test that remaining_space >= 16, repeat …), should speed things up. It’s not really addressing the exciting metaphysical question about “unsafe”, but if this was the only problem it introduced, … ?

18

@Gankra, thanks for this awesome writeup of the issues.

I originally wanted the final option you present – an analog of unsafe traits at the method level. But @nikomatsakis convinced me that the shades of nuance there aren’t really worth the complexity. So these days I favor adding something like the exact_size method, and patching the “hole” around being able to give a safe impl of it.

I’d probably call it trusted_size instead, at least assuming we keep ExactSizeIterator around as well.

Providing this functionality would help not just with these recent performance problems, but also give us opportunities to improve performance of iterator consumption in many places throughout std.

19

I just noticed this topic and I’m curious if there will be similar accommodations for comparison functions when used with sorting algorithms which rely on comparison functions actually returning reasonable results? Insertion sort’s optimal implementation requires inserting the minimum element at the beginning and using it as a sentinel, which saves the check that one is still inside the list. This obviously requires certain properties to hold true of the comparison function.

20

I think an unsafe exact_size method should be fine - the implementor does have to fulfill part of the contract, so I do not view the unsafe on the part of the implementer as exacting or unnecessary.

21

As I understand it, the problem is that the implementer doesn’t have to specify unsafe. Because of that, one could write something like this:

struct LieIter;

impl Iterator for LieIter {
    type Item = ();
    fn next(&mut self) -> Option<()> {
        None
    }
    fn size_hint(&self) -> (usize, Option<usize>) {
        (100, Some(100)) // this is a lie!
    }
    // Doesn’t specify `unsafe`, but this still works
    fn exact_size(&self) -> bool { true }
}