rust-itertools / itertools

Extra iterator adaptors, iterator methods, free functions, and macros.
https://docs.rs/itertools/
Apache License 2.0
2.72k stars 309 forks source link

Specialize `WithPosition::fold` #772

Closed Philippe-Cholet closed 1 year ago

Philippe-Cholet commented 1 year ago

Each call to f is done with a Position variant known at compile time so I think it might be optimized away in some cases?

Without specialization: [5.3231 µs 5.3487 µs 5.3806 µs]
With specialization:    [2.6974 µs 2.7042 µs 2.7132 µs]

We should mention #755 in PRs that specialize fold (such as this one) to help keep track of the advancement of the TODO list I'm gonna make there.

Philippe-Cholet commented 1 year ago

@phimuemue I do not update handled_first field anymore, as it's consumed. I avoid to peek entirely, the bench become even faster. Control flow is quite updated but remains nice, might be even nicer. And rebased on master.

[5.4031 µs 5.4195 µs 5.4353 µs] // without specialization
[2.6974 µs 2.7042 µs 2.7132 µs] // previous specialization with peek+next
[563.64 ns 565.92 ns 568.61 ns] // with new specialization

It bothered me a bit too to peek before calling next but I didn't think it would matter that much, thanks!

Philippe-Cholet commented 1 year ago

Just adding that I initially tried to avoid std::mem::swap with (init, head) = self.peekable.fold((init, head), ...); which worked for me but not for the msrv CI test. It did not like assigning to a tuple. The performance was not affected.

phimuemue commented 1 year ago

Nicely done, thanks.

As an aside: Does the mail address from your commits work?

Philippe-Cholet commented 1 year ago

@phimuemue I did not check the mail address for quite some time, but I definitely did this time.