itertools: Audit for missing `fold` implementations.

I’m interested to contribute to this crate and I digged a bit into the source code. I think one potential candidate to override fold is Combinations.

https://github.com/rust-itertools/itertools/blob/master/src/combinations.rs#L100

What do you guys think ?

I can create a PR in coming few days to implement this.

I tried this out and, although it works, it is markedly slower than the unspecialized implementation

@kinto-b We won’t specialize it if it’s slower (but that alone is a valuable information). About combinations, the slowest thing is heap-allocate the generated items. fold by nature generates them all (to give them to f) so we can’t win anything on that side. The only thing Combinations::fold could do is simpler code after the initialization phase while the default fold repeatedly doing next have “init code” lying around without use after a few steps, basically what you did but even it was a perf win, I did not expect much out of it since the heap-allocation is the bottleneck here and nothing else really impact performance (or at least I think so). I kinda wonder if mutate a combination IN-PLACE and give clones would be faster but it’s a lot of work for a probable small win (if any): while !self.increment_indices_and_comb(&mut comb) { acc = f(acc, comb.clone()); } or something like that.

I will eventually work again on configure clippy::missing_trait_methods and (if accepted) we will be able to mark that some fold are allowed to not be specialized and ensures all other fold are.

@Philippe-Cholet Hi there, on Combinations::fold, once #914 is merged, I think something like this should work as the core of an implementation:

// increment_indices returns true once we run out of combinations
while !self.increment_indices() {
  combination = self.indices.iter().map(|i| self.pool[*i].clone()).collect();
  acc = f(acc, combination)
}

If you think that looks reasonable I’ll put through a PR.

Edit: I tried this out and, although it works, it is markedly slower than the unspecialized implementation

@phimuemue Oh… I find embarrassing I was aware about --message-format json for “check” (never used) but not for “clippy”.

After some tinkering on jq playground, I think I have a new git alias (it’s not git-related but useful anyway):

missing-trait-methods = "!f() { cargo clippy --quiet --message-format json -- --warn clippy::missing_trait_methods | jq -r '. | select(.message.code.code == \"clippy::missing_trait_methods\") | select(.message.message | endswith(\"`'$2'`\")) | .message.spans[0] | .file_name + \":\" + (.line_start | tostring) + \"    \" + .text[0].text' | grep $1 | uniq; }; f"

then

git missing-trait-methods Iterator fold
git missing-trait-methods DoubleEndedIterator rfold

src\adaptors\mod.rs:498    impl<B, F, I> Iterator for Batching<I, F>
src\groupbylazy.rs:387    impl<'a, K, I, F> Iterator for Groups<'a, K, I, F>
src\groupbylazy.rs:440    impl<'a, K, I, F> Iterator for Group<'a, K, I, F>
src\groupbylazy.rs:556    impl<'a, I> Iterator for Chunks<'a, I>
src\groupbylazy.rs:599    impl<'a, I> Iterator for Chunk<'a, I>
src\grouping_map.rs:25    impl<K, V, I, F> Iterator for MapForGrouping<I, F>
src\sources.rs:127    impl<A, St, F> Iterator for Unfold<St, F>

I’m looking to give this issue a try. Started with Combinations and I wonder how does folding on that one would look like? with LazyBuffer and such. I can also use some mentoring/walkthrough of the crate if someone is willing to show me around.

Yes, the idea is to add lints to clippy itself to warn us about missing fold specializations. For any adaptors where we explicitly didn’t want to specialize fold, we would need to write #[allow(clippy::missing_iterator_fold)]. This would allow us to audit for missing clippy lints as simple as running cargo clippy, and to provide an automated warning if we ever tried to add a new adaptor without a fold implementation.

I’m interested to contribute to this crate and I digged a bit into the source code. I think one potential candidate to override fold is Combinations.

https://github.com/rust-itertools/itertools/blob/master/src/combinations.rs#L100

What do you guys think ?

I can create a PR in coming few days to implement this.

@Philippe-Cholet I think you’re the most knowledgeable there. Could you mentor/review this?

Once we do this, we should test all of them via test_specializations.

Whoops, yes, of course. I’ll modify the issue accordingly.

Note that the vast majority of the time, you should be overriding fold, not for_each.

The default for_each just calls fold with a trivial () accumulator, which is easily optimized out (since in the default Rust calling convention, it’s not even passed).

Thus the only reason to override for_each in addition to fold is if you can optimize something by knowing that the accumulation is stateless, but I can’t off-hand recall any case where I’ve seen that to be the case.