From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA21588; Tue, 11 Feb 2003 18:28:21 +0100 (MET)
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA21580 for <caml-list@pauillac.inria.fr>; Tue, 11 Feb 2003 18:28:20 +0100 (MET)
Received: from sophia.inria.fr (sophia.inria.fr [138.96.64.20])
	by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h1BHSKf28940
	for <caml-list@inria.fr>; Tue, 11 Feb 2003 18:28:20 +0100 (MET)
Received: from sophia.inria.fr (vishnu.inria.fr [138.96.82.1])
	by sophia.inria.fr (8.12.5/8.12.5) with ESMTP id h1BHSJEW007290
	for <caml-list@inria.fr>; Tue, 11 Feb 2003 18:28:20 +0100
X-Authentication-Warning: sophia.inria.fr: Host vishnu.inria.fr [138.96.82.1] claimed to be sophia.inria.fr
Message-ID: <3E4932B3.22A041D1@sophia.inria.fr>
Date: Tue, 11 Feb 2003 18:28:19 +0100
From: Pascal Zimmer <Pascal.Zimmer@sophia.inria.fr>
Organization: INRIA Sophia Antipolis
X-Mailer: Mozilla 4.76 [en] (X11; U; Linux 2.2.17pre19 i686)
X-Accept-Language: fr-FR, en
MIME-Version: 1.0
To: caml-list@inria.fr
Subject: [Caml-list] Optimizing false polymorphic local functions
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

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