[Caml-list] Optimizing false polymorphic local functions

[Caml-list] Optimizing false polymorphic local functions

[Pascal Zimmer]

The other day, I ran into a significant speedup improvement.
Here is a simpler (and artificial) version:

let min_list l =
 let rec loop mini = function
    [] -> mini
  | (x::r) -> loop (if x <= mini then x else mini) r
 in loop max_int l;;

This function computes the minimal element of an int list. Note however
that the inner local function "loop" is polymorphic.

Now consider the slightly different version where "loop" is forced into
a monomorphic function:

let min_list l =
 let rec loop (mini:int) = function
    [] -> mini
  | (x::r) -> loop (if x <= mini then x else mini) r
 in loop max_int l;;

On my computer in native code, the speedup is really significant: more
than 6 times faster (OK this example was built on purpose...). The
reason is that in the first case, the operator <= is replaced by a call
to the internal polymorphic compare_val function, whereas is the second
case a direct comparison between integers is performed.
Note also that if you replace the "if" statement by "min x mini", you
don't get any speedup because the polymorphic function "min" is called
in any case.

I suspect there are other cases in which the compiler can produce a
better code when it knows more precisely the types involved. So my
question is: would it be possible to help him in this way by enforcing
the type checker to infer a monomorphic type in such situations ? By
"such situations", I mean: local polymorphic functions that are used in
exactly one monomorphic setting afterwards. Of course, this is not
desirable for global functions, since it may break the calculus; but for
local functions, it should be of no harm since we know all the places
where they are used, and it would not change the type of the wrapper,
thus being transparent for the user...

Any comment ?

Pascal Zimmer
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Optimizing false polymorphic local functions

[Xavier Leroy]

> The other day, I ran into a significant speedup improvement.
> [...]
> Now consider the slightly different version where "loop" is forced into
> a monomorphic function:
> [...]
> On my computer in native code, the speedup is really significant: more
> than 6 times faster (OK this example was built on purpose...). The
> reason is that in the first case, the operator <= is replaced by a call
> to the internal polymorphic compare_val function, whereas is the second
> case a direct comparison between integers is performed.
> 
> I suspect there are other cases in which the compiler can produce a
> better code when it knows more precisely the types involved. 

Yes: besides comparisons, array and bigarray accesses can be compiled
more efficiently if the exact types of the data are known statically.

> So my question is: would it be possible to help him in this way by
> enforcing the type checker to infer a monomorphic type in such
> situations ? By "such situations", I mean: local polymorphic
> functions that are used in exactly one monomorphic setting
> afterwards. Of course, this is not desirable for global functions,
> since it may break the calculus; but for local functions, it should
> be of no harm since we know all the places where they are used, and
> it would not change the type of the wrapper, thus being transparent
> for the user...
> Any comment ?

The following paper formalizes exactly this idea, and gives a type
inference algorithm that avoids unecessary polymorphism like you suggest:

  http://citeseer.nj.nec.com/bjorner94minimal.html

- Xavier Leroy
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Optimizing false polymorphic local functions

[Pascal Zimmer]

Many thanks for the reference.
Just a last question: are there any reasons why this algorithm is not 
currently used in OCaml ? It does not seem very costly: as I was 
expecting, it is only a back-end to the classical typing algorithm, 
performing modifications on the type-annotated tree...

Pascal Zimmer


Xavier Leroy wrote:
>>The other day, I ran into a significant speedup improvement.
>>[...]
>>Now consider the slightly different version where "loop" is forced into
>>a monomorphic function:
>>[...]
>>On my computer in native code, the speedup is really significant: more
>>than 6 times faster (OK this example was built on purpose...). The
>>reason is that in the first case, the operator <= is replaced by a call
>>to the internal polymorphic compare_val function, whereas is the second
>>case a direct comparison between integers is performed.
>>
>>I suspect there are other cases in which the compiler can produce a
>>better code when it knows more precisely the types involved. 
> 
> 
> Yes: besides comparisons, array and bigarray accesses can be compiled
> more efficiently if the exact types of the data are known statically.
> 
> 
>>So my question is: would it be possible to help him in this way by
>>enforcing the type checker to infer a monomorphic type in such
>>situations ? By "such situations", I mean: local polymorphic
>>functions that are used in exactly one monomorphic setting
>>afterwards. Of course, this is not desirable for global functions,
>>since it may break the calculus; but for local functions, it should
>>be of no harm since we know all the places where they are used, and
>>it would not change the type of the wrapper, thus being transparent
>>for the user...
>>Any comment ?
> 
> 
> The following paper formalizes exactly this idea, and gives a type
> inference algorithm that avoids unecessary polymorphism like you suggest:
> 
>   http://citeseer.nj.nec.com/bjorner94minimal.html
> 
> - Xavier Leroy
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
> Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> 

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners