[CakeML-dev] Compilation times

[Magnus Myreen]

On 28 February 2017 at 11:39, Yong Kiam <tanyongkiam at gmail.com> wrote:
> 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.

One can ease the pressure on the register allocator by lowering the
cut_size in bvl_to_bvi (lower size makes register allocator see
smaller problems).

However, eventually we want a CF-verified imperative version of the
register allocator.

> 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.

Unfortunately, memoisation won't fit with CF as it currently stands.

Cheers,
Magnus

> 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
>
>