[Caml-list] Can this be inlined?

[Caml-list] Can this be inlined?

[Jacques Carette]

I am experimenting with some fairly generic traversal code (over a 
complex AST), but am a little scared that the result will be horribly 
inefficient.  I have been trying (with -dlambda and -dcmm, but not 
reading the .s output from using -S) to experiment with this myself, 
unsuccessfully.  Here is a very simplified setup

type ('a,'b) t = A | B of 'a * ('a,'b) t | C of 'b * ('a, 'b) t

type ('a, 'b) ff = { a: ('a -> 'a) option; b : ('b -> 'b) option }

let oapply optf x = match optf with Some f -> f x | None -> x

let id x = x

let rec trav f = function
   | A -> A
   | B (x,e) -> B (oapply f.a x, trav f e)
   | C (x,e) -> C (oapply f.b x, trav f e)

let t1 = {a=Some id; b=None}

let tt x = trav t1 x

I would like for 'tt' to contain a version of trav with no traces of 
either oapply or t1 left.  How can I achieve that?  Is it possible?  I 
don't mind changing idioms (modules instead of record, etc), as long as 
I can get my inlining to go through.  [I also tried making oapply and 
trav "local" to tt's definition, but that did not seem to make much of a 
difference].

In any case, the real goal here is to see if I can safely adopt a coding 
style like this, or do I need to manually do all the inlining myself?

Jacques

Re: [Caml-list] Can this be inlined?

[Michael Ekstrand]

On 01/10/2011 03:22 PM, Jacques Carette wrote:
> let rec trav f = function
>   | A -> A
>   | B (x,e) -> B (oapply f.a x, trav f e)
>   | C (x,e) -> C (oapply f.b x, trav f e)
>
> let t1 = {a=Some id; b=None}
>
> let tt x = trav t1 x
>
> I would like for 'tt' to contain a version of trav with no traces of
> either oapply or t1 left.  How can I achieve that?  Is it possible?  I
> don't mind changing idioms (modules instead of record, etc), as long
> as I can get my inlining to go through.  [I also tried making oapply
> and trav "local" to tt's definition, but that did not seem to make
> much of a difference].
>
> In any case, the real goal here is to see if I can safely adopt a
> coding style like this, or do I need to manually do all the inlining
> myself?

I think that the problem is in the definition of 'trav' - it is both
recursive and allocates memory.  AFAIK, the OCaml compiler (at least the
native code one) does not inline functions that are either recursive or
allocate memory.  So I think your only option - unless trav can be
drastically rewritten - is to inline them yourself.

- Michael

Re: [Caml-list] Can this be inlined?

[Damien Doligez]

On 2011-01-10, at 22:22, Jacques Carette wrote:

> I am experimenting with some fairly generic traversal code (over a complex AST), but am a little scared that the result will be horribly inefficient.

Note that in your code the function oapply only adds constant overhead to some
function calls (and these are probably non-trivial functions).  So in any case
the result cannot be "horribly inefficient", since it's within a small constant
factor of the fully-inlined version.

> In any case, the real goal here is to see if I can safely adopt a coding style like this, or do I need to manually do all the inlining myself?

The question is, will you butcher your code just because you are scared of
a _potential_ performance problem, or will you write the short, readable,
bug-free code first and then see if it really becomes a bottleneck?

Even if the inlining is definitely needed, I would start by writing and
debugging the generic version, and only then optimize it (by inlining
or otherwise).

-- Damien