Specialize `TupleCombinations::fold`

[Philippe-Cholet]

Related to #755.

[8.2569 ms 8.2733 ms 8.2907 ms]             // Benchmark `TupleCombinations::fold`
[3.2749 ms 3.2875 ms 3.3007 ms]             // `TupleCombinations::fold`
[3.3237 ms 3.3439 ms 3.3661 ms] (same perf) // `Tuple1Combinations::fold`
[237.52 µs 238.81 µs 240.59 µs]             // `Tuple*Combinations::fold` (macro)

This is so much faster that I'm wandering if I'm missing something here!

I previously added the specialization test: https://github.com/rust-itertools/itertools/commit/a9aaeb4cbacee3f4e83df56b3bb45d35d9167fa9

I'm unsure we can fold the while let loop as we need to clone iter at every step of it. Both attempts below successfully pass the tests but are not faster.

Maybe there is a solution involving std::cell::??? but I'm not familiar enough with this, are you? I tried with itertools::rciter but it was 60% slower (and Rc means the use_alloc feature). And with a basic RcIter::fold specialization, I even had an (expected) error at runtime.

let iter = $crate::rciter(iter);
iter.clone().fold(init, |acc, z| {
    let iter_ref = iter.rciter.borrow();
    <$P<I>>::from(iter_ref.clone())
        .map(|($($X),*,)| (z.clone(), $($X),*))
        .fold(acc, &mut f)
})

I eventually found a way to rely on iter.fold using unsafe only (to hold &mut I and &I at the same time) but it's the same performance as the current fold specialization. I'm not familiar with unsafe Rust so it might just be dumb in the first place.

let iter_mut = &mut iter;
let iter_ref: &I = unsafe {
    std::mem::transmute_copy(&iter_mut)
};
iter_mut.fold(init, |acc, z| {
    let c: $P<I> = iter_ref.clone().into();
    c.map(|($($X),*,)| (z.clone(), $($X),*))
        .fold(acc, &mut f)
})

[Philippe-Cholet]

Maybe I should merge .map(...).fold(init, &mut f) into a single .fold(init, |...| ...)?!

EDIT: It would be 6% slower.

[Philippe-Cholet]

As mentionned in the too big message, the specialization test was previously added (by me). I'm unsure I can merge this myself though. I wanted a feedback first anyway, thanks for it. EDIT: I guess now I can since you "approved those changes".