The Trusted Iterator Length Problem

[bluss]

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,
 }

[huon]

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

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

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.

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

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.

[tbu]

The unsafe is “wrong” because it should be considered safe to use but not to override. We lack the tooling to express “unsafe overrides”.

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.

[tbu]

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?

[bluss]

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.

[Gankro]

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.

[Gankro]

we could just say that unsafe means “warning: read the docs carefully”.

I’d be okay with this design.

[tbu]

@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.

[Gankro]

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.

[tbu]

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”.

[Gankro]

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?

[Gankro]

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.

[frankmcsherry]

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, … ?

[aturon]

@Gankro, 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.

[ahmedcharles]

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.

[reem]

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.

[P1start]

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 }
}

[reem]

Oh, I would just have exact_size be an unsafe method and implementing it would therefore require typing unsafe.

[huon]

@reem, that’s the problem that @P1start (and the rest of the thread ) is describing: a method declared unsafe in the trait doesn’t require the implementer to write unsafe.

[reem]

That seems wrong then.