`Vec::from_iter` specialization is slower on `TrustedLen` iterators from `thin-vec`

[panstromek]

In #159974, #159975, we found out that updating and enabling "unstable" feature flag in thin-vec makes some new-solver benchmarks slower.

I tried to measure this in isolation on the old version in #160010, where the old "unstable" flag only adds TrustedLen impl to thin_vec::IntoIter and thin_vec::Drain. The results for only adding the flag are here and they reproduce the regression: #160010 (comment)

Based on the cachegrind diffs, the culprit is mostly in this iterator chain:

rust/compiler/rustc_trait_selection/src/solve/fulfill.rs

Lines 185 to 198 in d3ea035

	fn collect_remaining_errors(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<E> {
	self.obligations
	.pending
	.drain(..)
	.map(|(obligation, _)| NextSolverError::Ambiguity(obligation))
	.chain(
	self.obligations
	.overflowed
	.drain(..)
	.map(|obligation| NextSolverError::Overflow(obligation)),
	)
	.map(|e| E::from_solver_error(infcx, e))
	.collect()
	}

pending.drain() creates thin_vec::Drain iterator. The rest of it are iterators from std.

Adding no-op skip(0) before the collect() call disables the specialization (because Skip doesn't implement TrustedLen) and fixes most of the regression: #160010 (comment), but not all of it, so it looks like the problem is not specific to this chain.

If I understand the specialization resolution correctly, the problematic from_iter impl is this one:

rust/library/alloc/src/vec/spec_from_iter_nested.rs

Lines 50 to 62 in d3ea035

	fn from_iter(iterator: I) -> Self {
	let mut vector = match iterator.size_hint() {
	(_, Some(upper)) => Vec::with_capacity(upper),
	// TrustedLen contract guarantees that `size_hint() == (_, None)` means that there
	// are more than `usize::MAX` elements.
	// Since the previous branch would eagerly panic if the capacity is too large
	// (via `with_capacity`) we do the same here.
	_ => panic!("capacity overflow"),
	};
	// reuse extend specialization for TrustedLen
	vector.spec_extend(iterator);
	vector
	}

Note that #160005 optimizes some of the next-solver data structures, so it's possible the issue will no longer reproduce on this code on main as visibly, but the issue might still exist.

I currently don't have time to research this further and create smaller reproducer, but maybe somebody who has more experience with these specializations has a better idea for what's going on.

[panstromek]

@rustbot label +I-slow +A-specialization +A-iterators

[the8472]

It's not necessarily the FromIterator specialization, since that only takes care of the initial capacity reservation. It then delegates to Extend which also has a TrustedLen specialization. The difference between those is that one uses external iteration, the other internal iteration. So if there's a significant difference between ThinVec's fold() and next() that could explain it.

[panstromek]

So if there's a significant difference between ThinVec's fold() and next() that could explain it.

ThinVec doesn't contain fold() at all, it uses the default from the trait. Not sure if that counts as yes, but it shouldn't be that bad, because that's how most iterators behave by default, right?

[panstromek]

To add more context here, in #160073 we found out that the iterator from the reproducer is almost always empty, which might explain the difference. See the discussion following this comment for more info: #160073 (comment)