[CakeML-dev] Compilation times

[Ramana Kumar]

The timings for the bootstrap evaluation
(https://cakeml.org/bootstrap-timing.txt) would give some indication
as to where to look for super-linear complexity phases.

On 28 February 2017 at 21:54, Scott Owens <S.A.Owens at kent.ac.uk> wrote:
> 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?
>
> Scott
>
>
>> 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
>>>
>>>
>
> _______________________________________________
> Developers mailing list
> Developers at cakeml.org
> https://lists.cakeml.org/listinfo/developers