[CakeML-dev] Compilation times

Scott Owens S.A.Owens at kent.ac.uk
Tue Feb 28 10:54:23 UTC 2017

I accept that the register allocator can have a high complexity, and trading off code quality vs. compile time there is something that all compilers have to think about. However, I am skeptical that there are parts of the compiler that require imperative trickery to run fast enough. ghc is implemented in Haskell after all. Also, it would be nice if compile-time improvements affected evaluation time in the logic as well.

Is there any way to coarsely profile the bootstrapped compiler (even if just with some printfs) to see which phases are taking the time? 


> On 2017/02/28, at 10:42, Magnus Myreen <magnus.myreen at gmail.com> wrote:
> 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

More information about the Developers mailing list