# The Trusted Iterator Length Problem **URL:** \ **Category:** Uncategorized\ **Created:** [January 13, 2015, 3:17am UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302 "2015-01-13T03:17:00Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![Gankra](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gankra/32/6002_2.png) [@Gankra](https://internals.rust-lang.org/u/Gankra)\ **Post date:** [January 13, 2015, 3:17am UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/1 "2015-01-13T03:17:00Z")
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` 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 ---
**Author:** ![bluss](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bluss/32/2264_2.png) [@bluss](https://internals.rust-lang.org/u/bluss)\ **Post date:** [January 13, 2015, 9:46am UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/2 "2015-01-13T09:46:05Z")
Why not this? I think this is fantastic.\*(I’ll revise this in a new post) ``` unsafe exact_size(&self) -> Option { None } ``` I’d favor removing ExactSizeIterator from libstd too, not sure it’s carrying its weight. ---
**Author:** ![nikomatsakis](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nikomatsakis/32/5410_2.png) [@nikomatsakis](https://internals.rust-lang.org/u/nikomatsakis)\ **Post date:** [January 13, 2015, 11:06am UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/3 "2015-01-13T11:06:28Z")
> [@Gankra](#): > > That previous thing but with proper unsafe semantics > > That'd be p. cool 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" 😄 ---
**Author:** ![bluss](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bluss/32/2264_2.png) [@bluss](https://internals.rust-lang.org/u/bluss)\ **Post date:** [January 13, 2015, 11:37am UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/4 "2015-01-13T11:37:37Z")
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), } pub struct SizeHint(/* private */ Size); impl SizeHint { pub fn from_bounds(low: usize, high: Option) -> 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 { .. } 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, } ``` ---
**Author:** ![huon](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/huon/32/3698_2.png) [@huon](https://internals.rust-lang.org/u/huon)\ **Post date:** [January 13, 2015, 1:09pm UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/6 "2015-01-13T13:09:04Z")
There was [a discussion on reddit](http://www.reddit.com/r/rust/comments/2rf6pi/this_week_in_rust_26/cnfrtxt) about this a few days ago. > [@blake](#): > > unsafe exact\_size(&self) -\> Option\ { 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. > [@blake](#): > > 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: ```rust 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. ---
**Author:** ![tbu](https://avatars.discourse-cdn.com/v4/letter/t/839c29/32.png) [@tbu](https://internals.rust-lang.org/u/tbu)\ **Post date:** [January 13, 2015, 1:20pm UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/7 "2015-01-13T13:20:19Z")
> [@Gankra](#): > > 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 **un** safe to call, but you can implement it without unsafe, with a simple `fn exact_size(&self) -> bool { true }`. EDIT: **un** safe. ---
**Author:** ![tbu](https://avatars.discourse-cdn.com/v4/letter/t/839c29/32.png) [@tbu](https://internals.rust-lang.org/u/tbu)\ **Post date:** [January 13, 2015, 1:21pm UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/8 "2015-01-13T13:21:31Z")
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? ---
**Author:** ![bluss](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bluss/32/2264_2.png) [@bluss](https://internals.rust-lang.org/u/bluss)\ **Post date:** [January 13, 2015, 1:34pm UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/9 "2015-01-13T13:34:49Z")
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](http://is.gd/rq26Be) 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` too was debunked there. Maybe it still is the way forward in combination with negative bounds. ---
**Author:** ![Gankra](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gankra/32/6002_2.png) [@Gankra](https://internals.rust-lang.org/u/Gankra)\ **Post date:** [January 13, 2015, 6:39pm UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/10 "2015-01-13T18:39:40Z")
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. ---
**Author:** ![Gankra](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gankra/32/6002_2.png) [@Gankra](https://internals.rust-lang.org/u/Gankra)\ **Post date:** [January 13, 2015, 6:41pm UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/11 "2015-01-13T18:41:10Z")
> [@nikomatsakis](#): > > we could just say that unsafe means "warning: read the docs carefully". I'd be okay with this design. ---
**Author:** ![tbu](https://avatars.discourse-cdn.com/v4/letter/t/839c29/32.png) [@tbu](https://internals.rust-lang.org/u/tbu)\ **Post date:** [January 13, 2015, 7:07pm UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/12 "2015-01-13T19:07:56Z")
@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. ---
**Author:** ![Gankra](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gankra/32/6002_2.png) [@Gankra](https://internals.rust-lang.org/u/Gankra)\ **Post date:** [January 13, 2015, 7:16pm UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/13 "2015-01-13T19:16:11Z")
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. ---
**Author:** ![tbu](https://avatars.discourse-cdn.com/v4/letter/t/839c29/32.png) [@tbu](https://internals.rust-lang.org/u/tbu)\ **Post date:** [January 13, 2015, 7:19pm UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/14 "2015-01-13T19:19:05Z")
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”. ---
**Author:** ![Gankra](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gankra/32/6002_2.png) [@Gankra](https://internals.rust-lang.org/u/Gankra)\ **Post date:** [January 13, 2015, 8:45pm UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/15 "2015-01-13T20:45:13Z")
tbu: too many has to be checked on every element, too few only has to be checked at the end. e.g. ```rust // 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 ```rust // 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? ---
**Author:** ![Gankra](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gankra/32/6002_2.png) [@Gankra](https://internals.rust-lang.org/u/Gankra)\ **Post date:** [January 13, 2015, 8:49pm UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/16 "2015-01-13T20:49:57Z")
~~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. ---
**Author:** ![frankmcsherry](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/frankmcsherry/32/3115_2.png) [@frankmcsherry](https://internals.rust-lang.org/u/frankmcsherry)\ **Post date:** [January 14, 2015, 6:50am UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/17 "2015-01-14T06:50:53Z")
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, … ? ---
**Author:** ![aturon](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/aturon/32/3272_2.png) [@aturon](https://internals.rust-lang.org/u/aturon)\ **Post date:** [January 14, 2015, 7:55am UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/18 "2015-01-14T07:55:50Z")
@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`. ---
**Author:** ![ahmedcharles](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ahmedcharles/32/4041_2.png) [@ahmedcharles](https://internals.rust-lang.org/u/ahmedcharles)\ **Post date:** [January 22, 2015, 8:16am UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/19 "2015-01-22T08:16:18Z")
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. ---
**Author:** ![reem](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/reem/32/167_2.png) [@reem](https://internals.rust-lang.org/u/reem)\ **Post date:** [February 24, 2015, 2:08am UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/20 "2015-02-24T02:08:52Z")
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. ---
**Author:** ![P1start](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/p1start/32/23_2.png) [@P1start](https://internals.rust-lang.org/u/P1start)\ **Post date:** [February 24, 2015, 2:37am UTC](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302/21 "2015-02-24T02:37:26Z")
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: ```rust struct LieIter; impl Iterator for LieIter { type Item = (); fn next(&mut self) -> Option<()> { None } fn size_hint(&self) -> (usize, Option) { (100, Some(100)) // this is a lie! } // Doesn’t specify `unsafe`, but this still works fn exact_size(&self) -> bool { true } } ``` [Next page](https://internals.rust-lang.org/t/the-trusted-iterator-length-problem/1302.md?page=2)