why do std collection iterators use raw pointer + PhantomData instead of normal ref?

Question

for example, slice Iter https://doc.rust-lang.org/src/core/slice/iter.rs.html#62 and LinkedList Iter https://doc.rust-lang.org/src/alloc/collections/linked_list.rs.html#74

both, rather than storing a normal ref to the struct they iterate over, store raw pointer variants (e.g. NonNull).

I imagine that slice::Iter could instead be built as

pub struct Iter<'a, T: 'a> {
  slice_ref: &'a [T],
  current_pos: usize,
}

so, why are raw pointers preferred/required here?

Answer 1

Slice iterators are very, very performance sensitive. They're used in pretty much all Rust code out there, and they might be the hottest code in all of std. So their design and implementation was carefully constructed and benchmarked to be the most performant possible, and every change requires a performance measurement.

In particular, the form you're suggesting is pretty bad (even very bad). It increases the fields count, which means more registers are occupied, and it requires an addition (to add the current offset to the beginning of the slice) for each element. Using pointers avoids that.

They could probably use a single slice and advance it, but there are complexities with handling ZSTs, and frankly, it seems just easier to have it all raw pointers.

Answer 2

Addressing the linked-list iterator implementation: You may notice a LinkedList does not use references internally.

The standard linked-list is doubly-linked - meaning a node in the list is connected to both the next element and previous element - which makes ownership less clear since its by-construction self-referencing. It also must provide mutation of the elements which would entirely prevent internal references altogether. A doubly-linked list simply doesn't mesh well with Rust's ownership model. You can read through Learn Rust With Entirely Too Many Linked Lists if you want to know more; the final chapter culminates with a design that is pretty much the same as the standard's.

So LinkedList uses pointers internally and thus the iterator implementation just follows suit.