Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] Optimizing false polymorphic local functions
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Pascal Zimmer <Pascal.Zimmer@s...>
Subject: [Caml-list] Optimizing false polymorphic local functions
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