Re: Instruction return

[Vincent Poirriez <Vincent.Poirriez@univ-valenciennes.fr>]

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<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 ?

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<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 ?

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