[CakeML-dev] Compilation times

Magnus Myreen magnus.myreen at gmail.com
Tue Feb 28 10:32:35 UTC 2017

On 28 February 2017 at 11:29, Scott Owens <S.A.Owens at kent.ac.uk> wrote:
> We now we have a preliminary version of the bootstrapped compiler that can actually run, and the compile times are pretty bad. It takes almost 2 minutes to compile fib. However, I don’t think that the problem is that the bootstrap is generating bad code for the compiler, or that we haven’t done enough optimisations yet. All of the other benchmark programs give us decent results, within a factor 3 or so of OCaml in the worst case (and sometimes faster than OCaml).
> I think this tells us that we have an algorithmic complexity problem in the compiler somewhere. If this is the case, then fixing it should speed up the bootstrap too, so I would like to put a high priority on fixing this. The bootstrap seems to spend most of its time in the assembler-level and later phases of compilation, so I guess this is the place to start looking. Are there any places where we already know it is using a quadratic (or worse) algorithm?

Ramana and Yong Kiam are working on this. It's know that computing the
string (that is the content of the .S file) at the end of the
bootstrapped compiler has terrible complexity. The simple solution is
to avoid returning a string and instead using an app_list string, and
have the print function walk the app_list without actually doing the

> Scott
> _______________________________________________
> Developers mailing list
> Developers at cakeml.org
> https://lists.cakeml.org/listinfo/developers

More information about the Developers mailing list