From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id MAA29354 for caml-redistribution; Tue, 3 Jun 1997 12:25:42 +0200 (MET DST)
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 MAA29343 for <caml-list@pauillac.inria.fr>; Tue, 3 Jun 1997 12:24:47 +0200 (MET DST)
Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.8.5/8.7.3) with ESMTP id MAA08435; Tue, 3 Jun 1997 12:24:39 +0200 (MET DST)
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id MAA29332; Tue, 3 Jun 1997 12:24:38 +0200 (MET DST)
From: Pierre Weis <Pierre.Weis@inria.fr>
Message-Id: <199706031024.MAA29332@pauillac.inria.fr>
Subject: Re: Instruction return
In-Reply-To: <3393D7D4.2F33@univ-valenciennes.fr> from Vincent Poirriez at "Jun 3, 97 09:37:40 am"
To: Vincent.Poirriez@univ-valenciennes.fr (Vincent Poirriez)
Date: Tue, 3 Jun 1997 12:24:38 +0200 (MET DST)
Cc: Pierre.Weis@inria.fr, zimmer@easynet.fr, caml-list@inria.fr
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
Sender: weis

> Cependant, j'ai rencontré la situation suivante dans un contexte
> où l'efficacité (à l'exécution) est essentielle.
> 
> Trouver l'indice du premier élément d'un tableau qui vérifie
> un prédicat p, s'il y en a un. 
> 
> Ce code étant compile avec l'option -unsafe, je ne peux pas
> compter sur les test de débordement des primitives Array.get ...
> 
> Le choix d'utiliser Array.unsafe_get serait inutile si j'inclus
> ce test de débordement dans la condition 
> du while ou de la fonction récursive ainsi:
> 
> let find p a =
>   let l = Array.length a in
>   let i = ref 0 in
>   while !i<l & not( p (Array.unsafe_get a !i) do
>   incr i
>   done;
>   !i
> 
> J'ai donc prefere le coût d'un try ... with:
> 
> exception Exit_for of int
>  let find p a =
>  let l = Array.length a in
>   try
>    for i = 0 to l-1 do
>     if p (Array.unsafe_get a i) then raise Exit_for i
>    done;
>    l
>   with Exit_for i -> i
[...]

As-tu fait des tests qui prouvent la supe'riorite' d'une version sur
l'autre ?

Comment crois-tu que la boucle for fait le bon nombre de tours puis
s'arre^te ? (En faisant un test a` chaque tour, et pratiquement le
me^me que celui de ta boucle while!).

English short version:

> But, due to runtime efficiency considerations I had to make
> the following choice.
> 
>  I want to find the index of the first item of an array which
> verifies a predicat p, if one exists. 
> 
> It is useless to prefer Array.unsafe_get if I add the test
> in the while (or recursive) condition as below:
> 
> let find p a =
>   let l = Array.length a in
>   let i = ref 0 in
>   while !i<l & not( p (Array.unsafe_get a !i) do
>   incr i
>   done;
>   !i
> 
> 
> I prefer to pay the cost of one try ... with ...
> 
> 
> exception Exit_for of int
>  let find p a =
>  let l = Array.length a in
>   try
>    for i = 0 to l-1 do
>     if p (Array.unsafe_get a i) then raise Exit_for i
>    done;
>    l
>   with Exit_for i -> i

Have you got some runtime figures that prove that this last version is more
efficient than the others ?

By the way, the for loop implies also a test each time its body is
executed (exactly the same as in your while loop) to decide to
continue or stop the loop...

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/