JuliaLang/julia — pull request #3305 by carlobaldassi (2013-06-06 02:47:14+00:00)
Title: [RFC] Faster Enumerate and Zip iterators + inlining issues

I tried to improve the performance of `Enumerate` and `Zip`. The gains are not huge, but see below.

For the case of `Enumerate`, it basically just amounts at changing the state variable from a `Tuple` to an immutable `EnumState`, with type parameters. I'm actually a little surprised that this makes any difference at all. However, the most surprising fact is what happens when I manually inline the `start`, `next` and `done` calls:

```
Function Elapsed Relative Replications
[1,] "olden" 3.31237 276.495 10
[2,] "oldeninline" 1.03624 86.4982 10
[3,] "newen" 2.03722 170.053 10
[4,] "neweninline" 0.0120131 1.00278 10
[5,] "manualen" 0.0119799 1.0 10
```

As can be seen, inlining helps also in the case of the current version (`olden` vs `oldeninline`), but the performance improves dramatically when inlining the version of this pull request (`newen` vs `neweninline`) and get on par with manual enumeration (`manualen`). The code for the benchmark is [here](https://gist.github.com/carlobaldassi/5718864).

For the case of `Zip`, code changes are more substantial. Besides immutability, I tried to leverage dispatch as much as possible, in this case based on the size of the tuples used for states (custom states didn't provide any advantage here). I also used macros to avoid calls to anonymous functions: I hope I did them right (a review would be appreciated). Possibly, the increase in code complexity will be too much compared to the modest performance gains, which are less than 2x. Here are the benchmarks for zipping 2 or 3 iterables.

```
# PERF ZIP 2
#
Function Elapsed Relative Replications
[1,] "oldzip" 2.58043 754.516 100
[2,] "oldzipinline" 2.51329 734.884 100
[3,] "newzip" 1.56089 456.404 100
[4,] "newzipinline" 0.942679 275.638 100
[5,] "manualzip" 0.00341999 1.0 100

# PERF ZIP 3
#
Function Elapsed Relative Replications
[1,] "oldzip" 3.96949 870.477 100
[2,] "oldzipinline" 3.5982 789.055 100
[3,] "newzip" 2.21593 485.936 100
[4,] "newzipinline" 1.52698 334.855 100
[5,] "manualzip" 0.00456013 1.0 100
```

Again, inlining helps in all cases (much more in the `new` cases though), but manual zipping is unmatched by a very large margin, which is kind of disappointing. The code for these benchmarks is in the same gist linked above.