The Trusted Iterator Length Problem

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

[tbu]

Currently the unsafe declaration in the trait just means that the function is unsafe to call, so it might have to fulfill a contract. This doesn’t necessarily mean that every implementation of this function has to rely on that contract, and when they don’t they can just omit the unsafe.

[bluss]

We need real specialization based on optionally available traits. An impl of an unsafe trait TrustedIteratorLength could be present, and functions should be able to specialize for that case.

[theme]

Filed an issue for making ExactSizeIterator unsafe

Issue: ExactSizeIterator should be an unsafe trait

[quantheory]

I’m not sure if this is sensible, but if not it might inspire someone to have a better idea:

unsafe trait ExactSizeIterator {}
trait MaybeExactSizeIterator {
    // Edit: The `&self` isn't actually used in the blanket impls, but it
    // seems necessary for object safety?
    fn size_hint_is_exact(&self) -> bool;
}
impl<T> MaybeExactSizeIterator for T where T: ExactSizeIterator {
    fn size_hint_is_exact(&self) -> bool { true }
}
impl<T> MaybeExactSizeIterator for T where T: !ExactSizeIterator {
    fn size_hint_is_exact(&self) -> bool { false }
}
trait Iterator : MaybeExactSizeIterator {
    // ...
}

Pros:

• Addresses this issue.
• Everyone who accepts an Iterator can get this information without loss of generality.
• unsafe is in the right place.

Cons:

• It makes no sense to implement ExactSizeIterator without also implementing Iterator, so the dependence is a bit weird.
• We have to have specialization that can get something like the above past the coherence rules. If you don’t have negative bounds of some sort, you unfortunately can’t express anything about the absence of an unsafe trait.

[nikomatsakis]

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

I just wanted to note that this is no longer true now that PR https://github.com/rust-lang/rust/pull/23452 has landed. If you have an unsafe fn in a trait, the impl must now implement it with an unsafe fn as well.

[huon]

Great! I think I’m pretty happy with the unsafe method solution now.

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.