[CakeML-dev] Compilation times

[Yong Kiam]

We're missing dead call-table entry removal as well. Ramana has started
some notes on this in the meetings page.

The register allocator is definitely above quadratic.

Also, the encoder evaluation is cached in the logic by Anthony's stuff but
it isn't cached outside, so that is another place with potential slowdown.

Both of those seem like they could fit well with a CF replacement for bits
of it.


On Tue, Feb 28, 2017 at 5:36 AM, Scott Owens <S.A.Owens at kent.ac.uk> wrote:

> Ok. I’d be happy to help look for other places (since the bootstrap was
> slow, even before we were making the string). Or I could just keep working
> on quicksort.
>
> Scott
>
> > On 2017/02/28, at 10:32, Magnus Myreen <magnus.myreen at gmail.com> wrote:
> >
> > 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
> > appends.
> >
> >> Scott
> >>
> >>
> >> _______________________________________________
> >> Developers mailing list
> >> Developers at cakeml.org
> >> https://lists.cakeml.org/listinfo/developers
>
> _______________________________________________
> Developers mailing list
> Developers at cakeml.org
> https://lists.cakeml.org/listinfo/developers
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.cakeml.org/pipermail/developers/attachments/20170228/0f976968/attachment.html>