Julia function composition with many functions

Question

I have a vector of 100 functions which I want to compose together. I need to run these 100 functions in sequence many times, so I figured composing them would be faster than making a nested loop, however, I was sadly mistaken. I tried reduce(∘, reverse(instructions))(input) and it was taking quite some time. I started timing it and was shocked to discover that composing any significant number of functions together is quite a bit slower than simply looping through the list of functions and applying them in sequence. All 100 functions I have are constant time operations, yet here's what I get when I time running the composition of any of these.

julia> @time reduce(∘, reverse(instructions[1:2]))(2019)
  0.000015 seconds (9 allocations: 448 bytes)
2041

julia> @time reduce(∘, reverse(instructions[1:5]))(2019)
  0.006597 seconds (4.43 k allocations: 212.517 KiB)
6951

julia> @time reduce(∘, reverse(instructions[1:10]))(2019)
  0.022688 seconds (31.01 k allocations: 1.405 MiB)
4935

julia> @time reduce(∘, reverse(instructions[1:20]))(2019)
  0.951510 seconds (47.97 k allocations: 2.167 MiB)
3894

julia> @time reduce(∘, reverse(instructions[1:21]))(2019)
  1.894370 seconds (60.45 k allocations: 2.715 MiB)
6242

julia> @time reduce(∘, reverse(instructions[1:22]))(2019)
  3.748505 seconds (50.59 k allocations: 2.289 MiB)
1669

julia> @time reduce(∘, reverse(instructions[1:23]))(2019)
  6.638699 seconds (65.98 k allocations: 2.982 MiB, 0.12% gc time)
8337

julia> @time reduce(∘, reverse(instructions[1:24]))(2019)
 12.456682 seconds (68.45 k allocations: 3.096 MiB)
6563

julia> @time reduce(∘, reverse(instructions[1:25]))(2019)
 31.712616 seconds (73.44 k allocations: 3.296 MiB)
8178

Just adding one more composed function seems to double the time it takes to run. Rerunning all this code results in it being much faster:

julia> @time reduce(∘, reverse(instructions[1:2]))(2019)
  0.000019 seconds (9 allocations: 448 bytes)
2041

julia> @time reduce(∘, reverse(instructions[1:5]))(2019)
  0.000021 seconds (12 allocations: 752 bytes)
6951

julia> @time reduce(∘, reverse(instructions[1:10]))(2019)
  0.000020 seconds (17 allocations: 1.359 KiB)
4935

julia> @time reduce(∘, reverse(instructions[1:20]))(2019)
  0.000027 seconds (27 allocations: 4.141 KiB)
3894

julia> @time reduce(∘, reverse(instructions[1:25]))(2019)
  0.000028 seconds (32 allocations: 6.109 KiB)
8178

But then if I add one more again then it takes double whatever the last one took

julia> @time reduce(∘, reverse(instructions[1:26]))(2019)
 60.287693 seconds (68.03 k allocations: 3.079 MiB)
3553

So it seems like all the time it's taking is in compiling the functions together, and for 100 functions it'd take way more time than I have. This is confirmed by the following results:

julia> @time reduce(∘, reverse(instructions[1:27]))
  0.000041 seconds (99 allocations: 10.859 KiB)
#52 (generic function with 1 method)

julia> @time precompile(ans, (Int,))
117.783710 seconds (79.01 k allocations: 3.650 MiB)
true

What's the deal here? I'll just run the functions in sequence I suppose, but why does this reduction take so long to compile? It seems like a failing of the ∘ function itself that deeply nested compositions take so long to compile. That was quite surprising to me, and it seems like a pretty basic use case of ∘. Basically, it appears that compile time is O(2^n), where n is the number of functions you're composing together. That seems like a big problem

Answer 1

I realized I was using an old version of Julia. On the latest version (1.3) it goes much quicker. It still starts getting slow if you get up into the high thousands (compiling 3000 functions composed together takes a few seconds) but it seems it's no longer O(2^n)