rust doesn't optimize closure in scan iterator

[erickt]

Good evening. I ran across a missed optimization I was trying to convert std::result::collect into using FromIteratator. My initial version used iter::Scan, but it proved to be 2 times slower than at --opt-level=3 than the original implementation. I also created a custom iterator that doesn't have the closure, and it compiles down to the same speed as the original std::result::collect. I'm guessing llvm isn't able to inline the closure for some reason.

I've gathered up this test in a gist. Note that in this example, the Scan1::size_hint() is different than the std::iter::Scan::size_hint() method.

cc @thestinger

[SimonSapin]

Do unboxed closures fix this?

[shepmaster]

Do unboxed closures fix this?

Not completely, it seems. I rewrote the original tests provided.

The implementation in the standard library uses the adapter iterator, so I only compared it to a version using scan. I also added one with filter_map, just to see how that would play out. I didn't expect those to be different, but:

running 3 tests
test bench_from_iter                 ... bench:       6,991 ns/iter (+/- 941)
test bench_from_iter_with_filter_map ... bench:       8,324 ns/iter (+/- 1,320)
test bench_from_iter_with_scan       ... bench:       7,299 ns/iter (+/- 1,172)

So it seems like the adapter iterator is still the most performant.

[dotdash]

@shepmaster Thanks for updating the benchmarks! Unfortunately they primarily measure the time it takes to create the v source vectors. The results are highly unstable and re-running the benchmark a few times had a different winner everytime, because the results vary enough to make up for the differences.

Improved benchmark at https://gist.github.com/dotdash/5ce3f0bfa2e652ca58b5 -- I simply moved the vector creation out of the loop and user iter().cloned() instead of into_iter(). As the vectors are made up of i32 values, that shouldn't affect the result compared for the actual loop that we want to measure.

Results:

test bench_from_iter                 ... bench:       2,304 ns/iter (+/- 23)
test bench_from_iter_with_filter_map ... bench:       4,996 ns/iter (+/- 122)
test bench_from_iter_with_scan       ... bench:       3,071 ns/iter (+/- 33)

[shepmaster]

they primarily measure the time it takes to create the v source vectors

Yeah, I should have noted that. I left if that way just to be consistent with the original version, but I also figured that since each was doing the same over-work they would come out consistent. A small number (~5) runs had the same winners for me, so I shipped it! :-)

Thanks for improving it even more!

[pmarcelll]

Results with the improved benchmark on nightly:

running 3 tests
test bench_from_iter                 ... bench:       2,158 ns/iter (+/- 24)
test bench_from_iter_with_filter_map ... bench:       2,474 ns/iter (+/- 89)
test bench_from_iter_with_scan       ... bench:       2,145 ns/iter (+/- 35)