OCaml defunctorization and other optimizations

OCaml defunctorization and other optimizations

[Török Edwin]

Hi,

I've seen in several places recommendations to use 'ocamldefun' to speed
up OCaml programs that use functors heavily [*].

I was able to find the sources via the wayback machine.
Unsurprisingly it doesn't build with OCaml 3.11.2 (it wants OCaml 3.06).
Is there a more up to date variant of ocamldefun? Would it be possible
to port it to 3.11.2?

Is it possible to implement ocamldefun-like functionality via Camlp4's
AST filters?

Also is it possible to implement function specialization
(monomorphization?) using an AST filter?
The example from the OCaml tutorial is not optimized by
http://www.ocaml-tutorial.org/performance_and_profiling.

Or is it possible to get access to the OCaml compiler's IL
representation and make optimizations on that?

[*] For example when extracting ML programs from Coq using OCaml's
native 'int' type I get code like this (which is not inlined/optimized
at all by OCaml):
module Z_as_Int =
 struct
....
  let _2 = 2
  let mult = ( * )
...
end
module F =
 functor (I:Int) ->
 struct
  (** val mul2 : I.int -> I.int **)

  let mul2 n =
    I.mult I._2 n
 end
module F2 = F(Z_as_Int)

Best regards,
--Edwin

Re: [Caml-list] OCaml defunctorization and other optimizations

[Julien Signoles]

[-- Attachment #1: Type: text/plain, Size: 2038 bytes --]

Hello,

2010/5/19 Török Edwin <edwintorok@gmail.com>

> I was able to find the sources via the wayback machine.
> Unsurprisingly it doesn't build with OCaml 3.11.2 (it wants OCaml 3.06).
> Is there a more up to date variant of ocamldefun? Would it be possible
> to port it to 3.11.2?
>

As far as I know, there is no up to date variant of ocamldefun.
For porting to 3.11.2, you have at least to:
- update the caml AST
- migrate all the camlp4 stuff to new camlp4 or camlp5
- update the different analyses to take into account AST changes (in
particular the new caml constructs like recursive modules).

Besides ocamldefun could be hugely improved in order to generate more
efficient caml code. I know (I knew?) what to do for this purpose, but I
have no time from a while ago in order to implement myself a new version of
ocamldefun. I could provide some helps to someone motivated...

Is it possible to implement ocamldefun-like functionality via Camlp4's
> AST filters?
>

Defunctorisation is a fully syntactic task (that's not so true in presence
of recursive modules). But, among other thinks, defunctorisation requires to
perform the very same scope analysis than ocaml for binding each use of
variable to its declaration. I am not an expert of Camlp4 possibilities, but
defunctorisation requires to manipulate the full caml AST.


> Also is it possible to implement function specialization
> (monomorphization?) using an AST filter?
> The example from the OCaml tutorial is not optimized by
> http://www.ocaml-tutorial.org/performance_and_profiling.
>

I'm not an expert (again) but typing information should be required, isn't
it?


> Or is it possible to get access to the OCaml compiler's IL
> representation and make optimizations on that?
>

At this day, there is no public interface to the internal modules of the
caml compiler. But, depending on the context (possible license issues), you
could embed some parts of the caml compiler in your tool.

Hope this helps,
Julien

[-- Attachment #2: Type: text/html, Size: 2949 bytes --]

Re: [Caml-list] OCaml defunctorization and other optimizations

[Török Edwin]

On 05/20/2010 11:41 AM, Julien Signoles wrote:
> Hello,
> 
> 2010/5/19 Török Edwin <edwintorok@gmail.com <mailto:edwintorok@gmail.com>>
> 
>     I was able to find the sources via the wayback machine.
>     Unsurprisingly it doesn't build with OCaml 3.11.2 (it wants OCaml 3.06).
>     Is there a more up to date variant of ocamldefun? Would it be possible
>     to port it to 3.11.2?
> 
> 
> As far as I know, there is no up to date variant of ocamldefun.
> For porting to 3.11.2, you have at least to:
> - update the caml AST
> - migrate all the camlp4 stuff to new camlp4 or camlp5
> - update the different analyses to take into account AST changes (in
> particular the new caml constructs like recursive modules).
> 
> Besides ocamldefun could be hugely improved in order to generate more
> efficient caml code. I know (I knew?) what to do for this purpose

Thanks, this sounds good so far.

>, but I
> have no time from a while ago in order to implement myself a new version
> of ocamldefun.

Yes time is an issue for me too.

> I could provide some helps to someone motivated...

I think that'll have to be someone else than me, as I consider myself
just a beginner in OCaml.
However if you think that implementing AST transforms would be possible
for a beginner (in OCaml, I do have experience with compilers), I'm
willing to give it a try.

> 
>     Is it possible to implement ocamldefun-like functionality via Camlp4's
>     AST filters?
> 
> 
> Defunctorisation is a fully syntactic task (that's not so true in
> presence of recursive modules). But, among other thinks,
> defunctorisation requires to perform the very same scope analysis than
> ocaml for binding each use of variable to its declaration. I am not an
> expert of Camlp4 possibilities, but defunctorisation requires to
> manipulate the full caml AST.

It looks like there is access to AST, I don't know if it is the full AST
or just a simplified view:
http://brion.inria.fr/gallium/index.php/Abstract_Syntax_Tree
http://brion.inria.fr/gallium/index.php/Camlp4MapGenerator

>  
> 
>     Also is it possible to implement function specialization
>     (monomorphization?) using an AST filter?
>     The example from the OCaml tutorial is not optimized by
>     http://www.ocaml-tutorial.org/performance_and_profiling.
> 
> 
> I'm not an expert (again) but typing information should be required,
> isn't it? 

Right, so I would need an AST that has all the infered type information.
I don't know if Camlp4 can offer that.

>  
> 
>     Or is it possible to get access to the OCaml compiler's IL
>     representation and make optimizations on that?
> 
> 
> At this day, there is no public interface to the internal modules of the
> caml compiler. But, depending on the context (possible license issues),
> you could embed some parts of the caml compiler in your tool.

I think that if there is a defunctorizer written it should live in the
OCaml distribution itself (maybe in contrib/).
I certainly don't intend to write an external tool that uses OCaml
internal modules.

Best regards,
--Edwin

Re: [Caml-list] OCaml defunctorization and other optimizations

[Julien Signoles]

[-- Attachment #1: Type: text/plain, Size: 1254 bytes --]

Hello,

2010/5/20 Török Edwin <edwintorok@gmail.com>

>
> On 05/20/2010 11:41 AM, Julien Signoles wrote:
> I think that'll have to be someone else than me, as I consider myself
> just a beginner in OCaml.
> However if you think that implementing AST transforms would be possible
> for a beginner (in OCaml, I do have experience with compilers), I'm
> willing to give it a try.
>

I wrote ocamldefun during my master project where I done both the theory and
the implementation of this tool: I was a beginner both in ocaml and in
functional programming since I only wrote a mini-compiler in ocaml during my
studies without any lecture on functional programming. But ok: there were
ocaml experts in my research team which provide me some wonderful helps :-).

>
> I think that if there is a defunctorizer written it should live in the
> OCaml distribution itself (maybe in contrib/).
>

Ocaml is not Coq: there is no such "contrib/" directory ;-). As far as I
know, the Ocaml development team does not accept so much external
contributions (for many good reasons).


> I certainly don't intend to write an external tool that uses OCaml
> internal modules.
>

That is what ocamldefun actually does.

Best regards,
Julien

[-- Attachment #2: Type: text/html, Size: 1915 bytes --]

Re: [Caml-list] OCaml defunctorization and other optimizations

[Török Edwin]

On 05/20/2010 02:40 PM, Julien Signoles wrote:
> Hello,
> 
> 2010/5/20 Török Edwin <edwintorok@gmail.com <mailto:edwintorok@gmail.com>>
> 
> 
>     On 05/20/2010 11:41 AM, Julien Signoles wrote:
>     I think that'll have to be someone else than me, as I consider myself
>     just a beginner in OCaml.
>     However if you think that implementing AST transforms would be possible
>     for a beginner (in OCaml, I do have experience with compilers), I'm
>     willing to give it a try.
> 
> 
> I wrote ocamldefun during my master project where I done both the theory
> and the implementation of this tool: I was a beginner both in ocaml and
> in functional programming since I only wrote a mini-compiler in ocaml
> during my studies without any lecture on functional programming.

That sounds encouraging.

> But ok:
> there were ocaml experts in my research team which provide me some
> wonderful helps :-).
> 
> 
>     I think that if there is a defunctorizer written it should live in the
>     OCaml distribution itself (maybe in contrib/).
> 
> 
> Ocaml is not Coq: there is no such "contrib/" directory ;-).

OK, I haven't payed much attention to the structure of the OCaml
package, I just assumed there was such a directory.

> As far as I
> know, the Ocaml development team does not accept so much external
> contributions (for many good reasons).

OK, then it'll have to be an external tool (if I decide to write it
after all).

>  
> 
>     I certainly don't intend to write an external tool that uses OCaml
>     internal modules.
> 
> 
> That is what ocamldefun actually does.

Yes, but I was thinking of something that is using an exported and
documented interface (like camlp4).
I think it would be easier to keep up with new OCaml versions that way.

Best regards,
--Edwin

Re: [Caml-list] OCaml defunctorization and other optimizations

[Maxence Guesdon]

On Thu, 20 May 2010 15:04:44 +0300
Török Edwin <edwintorok@gmail.com> wrote:

> 
> > As far as I
> > know, the Ocaml development team does not accept so much external
> > contributions (for many good reasons).
> 
> OK, then it'll have to be an external tool (if I decide to write it
> after all).

If you decide to do so, you can have a look at oug[1] distrib, which uses
internal modules of OCaml. You could copy the configuration machinery
(configure.in, configure, checkocaml.ml) used to detect/indicate ocaml
programs and ocaml compiled sources.

Hope this helps,

Maxence

[1] http://home.gna.org/oug/index.en.html

-- 
Maxence Guesdon                             http://yquem.inria.fr/~guesdon/
Service Expérimentation et Développements         https://sed-roc.inria.fr/
INRIA Paris-Rocquencourt                  http://www.inria.fr/rocquencourt/