Simplify Permutations

[Philippe-Cholet]

Fixes #747

This is quite a rewrite, very little is untouched.
count and size_hint are really simplified with the new PermutationState::size_hint_for.

cargo bench permutation
// Before this PR
permutations iter       [62.130 µs 62.355 µs 62.620 µs]
permutations range      [61.637 µs 61.850 µs 62.104 µs]
permutations slice      [64.177 µs 64.314 µs 64.459 µs]
// Now
permutations iter       [57.280 µs 57.478 µs 57.702 µs]    -8.4%
permutations range      [59.714 µs 59.914 µs 60.138 µs]    -4.7%
permutations slice      [59.584 µs 59.720 µs 59.868 µs]    -7.1%

I did not expect any performance improvement, but nice to have a little one.

[phimuemue]

Hi @Philippe-Cholet, looks good to me. The flattened structure seems much nicer.

This took me a while to review, and I could only do it by "replaying" what you possibly did yourself (see d188e8e...phimuemue:rust-itertools:permutations-states-2, the end result being exactly what you proposed). Unfortunately, I am not aware of a process that would allow quicker reviews apart from more fine-grained commits.

Maybe it's worth preserving the history of fine-grained transformations. Please use your judgment, and either merge this or take my commits and merge them.

[phimuemue]

So, we go via SizeHint (i.e. (usize, Option<usize>)) to compute count. Fine given the simplification we gain by this.

[Philippe-Cholet]

Indeed, size_hint_for mostly ends with (x.unwrap_or(usize::MAX), x) on which we either do .0 or .1.
At worst, it needlessly unwrapped an option one time.

[phimuemue]

Could you shortly explain why this debug_assert holds?

[Philippe-Cholet]

I wrote that in my previous branch some weeks ago so I was not much familiar with it, and take a glance at it is definitely not enough as it requires a bit of thinking.

This debug_assert! only occurs with Start and Buffered variants.
At definition, we prefill the lazy buffer with k values. It has enough values (or we would have the End variant) so vals.len() >= k (vals.len()==k at definition, more later).
size_hint_for is then called with:

• in the case of count: n = vals.count() >= vals.len() (see lazy buffer for >=) ;
• in the case of size_hint: n = vals.size_hint().0 >= vals.len() (see lazy buffer).
  Similar for n = vals.size_hint().1.

So in each case: n >= vals.len() >= k. Basically, it holds because we prefilled with k values.

[Philippe-Cholet]

However, I'm considering to soon work on making all our iterators lazy (such as #602) and I'll surely turn that assertion into if n < k { return (0, Some(0)); } (and move the "prefill the lazy buffer" part).

[phimuemue]

This pattern seems familiar to me... Do you know if it occurs somewhere else? If so, should we introduce size_hint::map? (We can do this separately, it just occured to me.)

[Philippe-Cholet]

This pattern occurs most of the time I think. I thought of a similar method in a messy PR but I had headaches about the conditions on f for the resulting size hint to be correct, so as I wrote several size hints I went with applying the pattern manually.

[Philippe-Cholet]

@phimuemue
I'm sorry you had some hard time reviewing it. I definitely tried and struggled to make more fine-grained commits here. But I should have thought of your very helpful intermediary Loaded(CompleteState) -> LoadedStart, LoadedOngoing.
I'm a work in progress (especially git), and to improve myself I splitted it again myself, trying to leave the last commit intact (FusedIterator, but I git-failed so I had to write it again).

You can check that there is no difference between our branches:
https://github.com/Philippe-Cholet/itertools/compare/permutations-states-2..phimuemue:rust-itertools:permutations-states-2 (I've just learnt that .. and ... have different meaning in this url).

[phimuemue]

@phimuemue I'm sorry you had some hard time reviewing it. I definitely tried and struggled to make more fine-grained commits here. But I should have thought of your very helpful intermediary Loaded(CompleteState) -> LoadedStart, LoadedOngoing. I'm a work in progress (especially git), and to improve myself I splitted it again myself, trying to leave the last commit intact (FusedIterator, but I git-failed so I had to write it again).

You can check that there is no difference between our branches: https://github.com/Philippe-Cholet/itertools/compare/permutations-states-2..phimuemue:rust-itertools:permutations-states-2 (I've just learnt that .. and ... have different meaning in this url).

No worries. I hope it didn't come across an offense. Thanks again for taking the time to simplify this.

[Philippe-Cholet]

@phimuemue I did not see any offense, only the opportunity to improve the way I write commits.