Heavy slowdown in ExpandTemplates due to subtypes function

[epatters]

The steps of the ExpanderPipeline are dispatched by iterating over the subtypes of this abstract type. The subtypes function is called for every Markdown element processed, meaning that it can easily be called hundreds or thousands of times during a run of Documenter.

However, under some circumstances (possibly involving generated functions or type metaprogramming, see #1261), the subtypes function is extremely slow:

julia> import Documenter

julia> @time subtypes(Documenter.Expanders.ExpanderPipeline);
  0.057625 seconds (92.08 k allocations: 5.367 MiB)

julia> @time subtypes(Documenter.Expanders.ExpanderPipeline);
  0.011200 seconds (2.44 k allocations: 724.125 KiB)

julia> import Catlab

julia> @time subtypes(Documenter.Expanders.ExpanderPipeline);
 40.238011 seconds (1.29 M allocations: 109.522 MiB, 0.18% gc time)

julia> @time subtypes(Documenter.Expanders.ExpanderPipeline);
  5.237196 seconds (29.11 k allocations: 4.189 MiB)

julia> @time subtypes(Documenter.Expanders.ExpanderPipeline);
  5.265813 seconds (29.11 k allocations: 4.189 MiB)

I figure this should be considered a bug in Julia itself and I'm going to file another issue upstream.

That being said, since the issue is currently severely impacting the build times for the docs of Catlab.jl and its dependers, I was hoping that a workaround could be implemented here. A simple workaround would move the call sort(subtypes(T); by = order) from inside dispatch to the body of the main function expand. That would ensure that subtypes is only called once during the ExpandTemplates step.

[MichaelHatherly]

Thanks for tracking it down @epatters, would you be able to prepare a PR with that workaround and we can try get it sorted asap.

[epatters]

Sure, I can prepare a PR. Thanks.