Larger schedules cause compile times to balloon

[Anders429]

It seems that larger schedules cause large blow-ups in compile time. I just compiled a schedule with 3 components and 14 systems, and the whole thing took over 11 minutes to compile.

I need to investigate exactly what is going on, but I have a hunch that the problem is the compile-time Claims traits. I'm guessing that during type resolution the index types take some quadratic time complexity to resolve.

This also will address the slowly-increasing time of the continuous integration jobs.

[Anders429]

Took some time to do actual analysis of the compile times. I built a project using a registry of 5 components, with a single system that uses none of these components (meaning multiple would be scheduled as one stage). I created a schedule with 5 copies of these systems, and recorded how long it took to compile for each version from 0.4.0 and on:

Version	Time
0.4.0	0.53 s
0.5.0	0.66 s
0.6.1	2.51 s
0.7.0	4.35 s
0.8.2	6.00 s
0.9.0	9.55 s

There is an unfortunate pattern here: as more features are added to scheduling, the compile times are increasing.

I also checked for how the compile time grows as more systems are added. I ran this using 0.5.0, and I think it will be the same for 0.4.0 (using an early version shows that there was a problem from the beginning that wasn't caught):

System Count	Time
5	0.66 s
10	3.80 s
15	19.44 s
20	75.00 s

This shows that the growth was apparently quadratic from the start, but it wasn't caught due to the tests being small enough. As the complexity of the scheduling has increased, so has the time, which has made this more apparent. Like I said earlier, compiling a schedule with 14 systems took over 11 minutes on the most recent version, which makes the problem very obvious.

Therefore, we need to either figure out a way to redo the compile-time scheduling, or switch back to dynamic scheduling. I would prefer to keep this as zero-cost as possible by keeping the scheduling at compile-time, but if no one can reasonably compile it then we have to make the compromise.

[Anders429]

After researching this further, I'm not actual sure generating the schedule at compile-time is possible. I had thought I could solve this by reversing the list of tasks before scheduling it, but I think the solution is still quadratic: we have to touch each task once, and for each task we have to evaluate the current component claims against the previous component claims in the same stage. I'm no expert on the intricacies of trait resolution, but if I had to guess it seems I keep running into the compiler reevaluating the claims for the stages from scratch for each new task.

To save myself the headache, I will try to reimplement dynamic scheduling this weekend. This will at least get scheduling into a usable state again. Considering the age of this issue, it's about time I come to a solution here so that I can work on some other more pressing issues.