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 RAA02457 for caml-redistribution; Tue, 3 Jun 1997 17:16:22 +0200 (MET DST) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA01437 for ; Tue, 3 Jun 1997 15:21:26 +0200 (MET DST) Received: from pulsar.univ-valenciennes.fr (pulsar.univ-valenciennes.fr [193.50.192.1]) by nez-perce.inria.fr (8.8.5/8.7.3) with ESMTP id PAA22866; Tue, 3 Jun 1997 15:21:24 +0200 (MET DST) Received: from titan.univ-valenciennes.fr (titan.univ-valenciennes.fr [193.50.192.38]) by pulsar.univ-valenciennes.fr (8.7.3/jtpda-5.1) with SMTP id PAA28628 ; Tue, 3 Jun 1997 15:29:01 +0200 (MET DST) Received: from titan (localhost) by titan.univ-valenciennes.fr (5.x/SMI-SVR4) id AA07504; Tue, 3 Jun 1997 15:17:51 +0100 Message-Id: <3394278E.137E@univ-valenciennes.fr> Date: Tue, 03 Jun 1997 15:17:50 +0100 From: Vincent Poirriez Organization: limav X-Mailer: Mozilla 3.01Gold (X11; I; SunOS 5.4 sun4m) Mime-Version: 1.0 To: Pierre Weis Cc: Vincent Poirriez , zimmer@easynet.fr, caml-list@inria.fr Subject: Re: Instruction return References: <199706031024.MAA29332@pauillac.inria.fr> Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Sender: weis Pierre Weis wrote: > > > 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 > 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 ? Je n'avais pas, voila une série de test (cf fin du message) Est-ce que cela prouve? en tout cas la version for est toujours plus rapide que la version while (exactement le code ci-dessus aux erreurs de syntaxe pres) La difference est marginale, je le reconnait, je ne suis pas allé voir dans le code d'implantation du for et while pour expliquer la difference. test réalisé sur DEC alpha en ocaml 1.05 deux process executes en concurrence, l'un pour le for, l'autre pour le while. Les temps sont stables pour plusieurs executions > > 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!). > Je reconnais la naïveté, ce n'est pas parce que l'on connait la borne que l'on est dispensé de tester si on la atteinte!!! > 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 > 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 ? I had not, but it's done now Does it prove? These tests were executed on a Dec Alpha with ocaml-1.05 two distinct processes, one for the while version and the other for the for version (exactly the above code except for syntax mistakes) times are rather stable for several executions > > 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... > I agree with the naivety of the "for" code, the knowledge of the bound does not exempted to test if it is reached!!! I did not Vincent Poirriez CPU times (as report by the times function) an array of int randomly generated between 10 and 10000010 Size of the array : 10000000 first find the first item equal to the length second (all) find the first negative item ten instances of the pb for: 0.183 index: 912770 while : 0.2 index: 912770 for (all): 2.05 index: 10000000 while (all): 2.166 index: 10000000 for: 0.566 index: 2509612 while : 0.583 index: 2509612 for (all): 2.05 index: 10000000 while (all): 2.266 index: 10000000 for: 0.75 index: 3345779 while : 0.783 index: 3345779 for (all): 2.033 index: 10000000 while (all): 2.25 index: 10000000 for: 0.216 index: 1101347 while : 0.266 index: 1101347 for (all): 2.016 index: 10000000 while (all): 2.266 index: 10000000 for: 2.05 index: 9398524 while : 2.2 index: 9398524 for (all): 2.066 index: 10000000 while (all): 2.216 index: 10000000 for: 0.016 index: 36893 while : 0.016 index: 36893 for (all): 2 index: 10000000 while (all): 2.3 index: 10000000 for: 2.166 index: 10000000 while : 2.283 index: 10000000 for (all): 2.05 index: 10000000 while (all): 2.233 index: 10000000 for: 0.6 index: 2881739 while : 0.683 index: 2881739 for (all): 2.116 index: 10000000 while (all): 2.2 index: 10000000 for: 0.5 index: 2243375 while : 0.516 index: 2243375 for (all): 2.016 index: 10000000 while (all): 2.216 index: 10000000 for: 1.766 index: 8282931 while : 2 index: 8282931 for (all): 2.033 index: 10000000 while (all): 2.2 index: 10000000 -- Tel: (33) {0}3 27 14 13 33 Fax: (33) {0}3 27 14 12 94 mailto:Vincent.Poirriez@univ-valenciennes.fr http://www.univ-valenciennes.fr/limav/poirriez ISTV Université de Valenciennes Le Mont Houy BP 311 F59304 Valenciennes CEDEX