Re: [Caml-list] <SPAM> Re: Compile-time performance problem

[Pierre Chambart <pierre.chambart@ocamlpro.com>]

Le 08/11/2016 à 11:10, Goswin von Brederlow a écrit :
> On Tue, Nov 08, 2016 at 09:56:33AM +0100, Christoph H??ger wrote:
>> let (<+) a v = Array.append a [|v|] 
>> let foo k s =
>>   ((fun k  -> fun s  -> (k#_continue_ (object (self)  end)) 1)
>>      (object (self)
>>         val _continue_ =
>>           fun x  ->
>>             (fun k  ->
>>                fun s  ->
>>                  ((fun k  -> fun s  -> (k#_continue_ (object (self)  end)) 2)
> ...
>
> Do you have to use objects there? Does the problem go away if you use
> a simple type for the continuation?
>
> The thing with CPS is that your code can be converted into simple
> jumps instead of function calls. Everything is a tail call. And all
> your objects are dummies that can be optimized away if you try hard
> enough. Really complex dummies. I can imagine the bytecode simply
> creates the objects and calls the methods while the native code
> optimizes it all away. Hard to say if that is linear (and really
> slow), quadratic or exponential with just one example though.
>
> MfG
> 	Goswin
>
It is linear with a very large constant factor.

It is linked to a known exponential case in closure conversion that was
limited: In case of deeply nested functions when the initial closeness
estimation is systematically wrong, this can fall into that case. To prevent
problems the search depth is limited to 5. See
https://github.com/ocaml/ocaml/blob/trunk/asmcomp/closure.ml#L765
and
https://github.com/ocaml/ocaml/blob/trunk/asmcomp/closure.ml#L1195

Please fill a bug on mantis for this.

Side not: Flambda does not have this kind of problem, this estimation
is done by a linear time fixpoint. (this might be the only known example
where flambda compilation is faster...)
-- 
Pierre