Function inlining and functor

Function inlining and functor

[Quôc Peyrot]

Hello,

I have a program with a generic function which takes a function as
a parameter and calls it heavily. Something along the lines of:

let toto f =
   (* call f a couple of million times *)

I was trying to see wether or not I could force the inlining of "f"
when f is small function.

For the sake of simplicity, let's imagine we have:

let toto f =
   let a = ref 0 in
   for i = 0 to 10 do
     a := !a + f i
   done;
   !a

let f a = a * a

let _ =
   print_endline (string_of_int (toto f))

of course we can see that f is not inlined in the inner loop:
(PPC)
L106:
    lwz   r4, 0(r1)
    lwz   r17, 0(r4)
    mtctr r17 -> prepare the call
L108: bctrl -> call it


I tried to use a functor, hoping that it would help the compiler to
inline the function:

module type A =
sig
val f: int -> int
end

module Make (F:A) = struct

let toto () =
   let a = ref 0 in
   for i = 0 to 10 do
     a := !a + F.f i
   done;
   !a

end

let f x = x * x

module Mod = Make (struct let f = f end)

let _ =
   print_endline (string_of_int (Mod.toto ()))

but it doesn't seem to help at all, I can still see the call in my
inner loop:
L109:
    lwz   r5, 0(r1)
    lwz   r19, 8(r5)
    lwz   r4, 0(r19)
    lwz   r17, 0(r4)
    mtctr r17
L114: bctrl

I was in fact hoping to get the same results than in C++ using
meta-programming/template:
#include <iostream>

using namespace std;

template<class F>
class Mod
{
   public:
   int toto()
   {
     int res = 0;
     for (int i = 0; i <= 10; ++i)
       res += F::f(i);
     return res;
   }
};

class Foo
{
   public:
   static int f(int i) { return i * i; }
};

int main(int argc, char**argv)
{
   Mod<Foo> mod;
   cout << mod.toto() << endl;
   return 0;
}

which gives this nice inlining:
L15:
    mullw r0,r2,r2
    addi r2,r2,1
    add r4,r4,r0
    bdnz L15
    addis r2,r31,ha16(L__ZSt4cout$non_lazy_ptr-"L00000000002$pb")
    lwz r3,lo16(L__ZSt4cout$non_lazy_ptr-"L00000000002$pb")(r2)


Am I out of luck to get similar performance than C++?

Thanks,

-- 
Best Regards,
Quôc

Re: [Caml-list] Function inlining and functor

[Jon Harrop]

On Monday 25 June 2007 15:39:02 Quôc Peyrot wrote:
> Am I out of luck to get similar performance than C++?

Short of generating OCaml code or using MetaOCaml, yes.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?e

Re: [Caml-list] Function inlining and functor

[Joel Reymont]

How would MetaOCaml help here?

On Jun 25, 2007, at 4:22 PM, Jon Harrop wrote:

> Short of generating OCaml code or using MetaOCaml, yes.
>
--
http://topdog.cc      - EasyLanguage to C# compiler
http://wagerlabs.com  - Blog

Re: [Caml-list] Function inlining and functor

[Basile STARYNKEVITCH]

Joel Reymont wrote:
> How would MetaOCaml help here?

You can generate code with MetaOcaml; in ordinary Ocaml (even fonctors) only function abstraction & application happens 
(without any code generation at "runtime").

-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faïencerie, 92340 Bourg La Reine, France
*** opinions {are only mines, sont seulement les miennes} ***

Re: [Caml-list] Function inlining and functor

[Quôc Peyrot]

On Jun 25, 2007, at 5:41 PM, Basile STARYNKEVITCH wrote:

> Joel Reymont wrote:
>> How would MetaOCaml help here?
>
> You can generate code with MetaOcaml; in ordinary Ocaml (even  
> fonctors) only function abstraction & application happens (without  
> any code generation at "runtime").

But in the functor example, what is missing during the compilation to  
be able to inline it?

-- 
Best Regards,
Quôc

Re: [Caml-list] Function inlining and functor

[Jon Harrop]

On Monday 25 June 2007 16:50:03 Quôc Peyrot wrote:
> But in the functor example, what is missing during the compilation to
> be able to inline it?

The thing that is missing is the code in the OCaml compiler than inlines these 
function calls. :-)

This was one of the demands on the "what optimizations would we like" list 
that was discussed here recently.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?e

Re: [Caml-list] Function inlining and functor

[Quôc Peyrot]

On Jun 25, 2007, at 5:58 PM, Jon Harrop wrote:

> On Monday 25 June 2007 16:50:03 Quôc Peyrot wrote:
>> But in the functor example, what is missing during the compilation to
>> be able to inline it?
>
> The thing that is missing is the code in the OCaml compiler than  
> inlines these
> function calls. :-)
>
> This was one of the demands on the "what optimizations would we  
> like" list
> that was discussed here recently.

I see, thanks,

of course I have to concur with this conclusion as well ;)

PS: I just tried to read the code for inlining in the compiler, to  
have some
idea how complicated it is, but of course, without much exposure I
couldn't make sense of what I was reading.
Is there any "Hacking" doc for the compiler somewhere?

-- 
Best Regards,
Quôc

Re: [Caml-list] Function inlining and functor

[Jon Harrop]

On Monday 25 June 2007 18:04:46 Quôc Peyrot wrote:
> PS: I just tried to read the code for inlining in the compiler, to
> have some
> idea how complicated it is, but of course, without much exposure I
> couldn't make sense of what I was reading.
> Is there any "Hacking" doc for the compiler somewhere?

Not AFAIK but I'd love one. Any chance we could impose on one of the Wikis 
people were discussing here recently?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?e

Re: [Caml-list] Function inlining and functor

[Jon Harrop]

On Monday 25 June 2007 16:36:53 you wrote:
> How would MetaOCaml help here?

You rewrite higher-order functions that accept closures (e.g. Array.fold_left) 
as higher-order functions that accept code. Then the inlining is up to you.

In the case of Array.fold_left, you make partial application generate and 
compile specialized implementations, giving you a type-specialized closure:

let fold_left f =
  .<
    fun accu a ->
      let accu = ref accu in
      for i=0 to Array.length a - 1 do
        accu := .~f !accu a.(i)
      done;
      !accu
  >.;;

Partial application of "f" now gives you a specialized function:

# fold_left .<( +. )>.;;
- : ('a, float -> float array -> float) code =
.<fun accu_1 ->
   fun a_2 ->
    let accu_3 = (ref accu_1) in
    for i_4 = 0 to ((Array.length a_2) - 1) do
     (accu_3 := ((! accu_3) +. a_2.(i_4)))
    done;
    (! accu_3)>.

Run-time compilation of this gives you the efficiency of inlining and, 
therefore, type specialization:

# .!(fold_left .<( +. )>.);;
- : float -> float array -> float = <fun>

Instead of:

  Array.fold_left ( +. ) 0.

You write:

  .!(fold_left .<( +. )>.) 0. a

which is twice as fast on my machine. MetaOCaml rocks. I do hope it becomes 
mainstream... :-)

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?e

Re: [Caml-list] Function inlining and functor

[Joel Reymont]

On Jun 25, 2007, at 5:07 PM, Jon Harrop wrote:

> MetaOCaml rocks. I do hope it becomes mainstream... :-)

I wonder what kind of process is used to decide what becomes  
mainstream (part of the OCaml distribution?) and what doesn't.

I suppose that keeping up CVS tree containing, say, MetaOCaml and  
JoCaml would quickly get tedious. I may be mistaken, though.


--
http://topdog.cc      - EasyLanguage to C# compiler
http://wagerlabs.com  - Blog

Re: [Caml-list] Function inlining and functor

[Jon Harrop]

On Monday 25 June 2007 21:11:34 Joel Reymont wrote:
> On Jun 25, 2007, at 5:07 PM, Jon Harrop wrote:
> > MetaOCaml rocks. I do hope it becomes mainstream... :-)
>
> I wonder what kind of process is used to decide what becomes
> mainstream (part of the OCaml distribution?) and what doesn't.

I believe standard procedure is to get Xavier drunk before persuading him that 
chicks dig MetaOCaml maintainers (a testimonial from Walid would help).

> I suppose that keeping up CVS tree containing, say, MetaOCaml and
> JoCaml would quickly get tedious. I may be mistaken, though.

I would certainly appreciate it if someone brought MetaOCaml up to date (3.10) 
and added Alain's AMD64 support.

MetaOCaml seems to have stabilized, so this might not be completely out of the 
question...

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?e