Re: [Caml-list] Three way comparaisons

[Luc Maranget <luc.maranget@inria.fr>]

> 
>     Bonjour,
> 
Bonjour,

Un conseil : essayer les deux codes, plus une info perdue plus bas sur les
optimisations de ocamlopt.

> Dans une note d'Arno Andersson [signal=E9e par Okasaki dans Oka98] est
> pr=E9sent=E9 un algorithme de recherche dans un arbre en (log n + 1)
> comparaisons :
> 
> au lieu de
  code classique.

> Arno propose un algorithme qui ne fait qu'une comparaison par noeud.
> Il explique que "since most high-level languages do not supply three
> way comparaisons the number of comparaisons used _de facto_ are
> reduced by a factor of two"
> 

J'ai lu vite mais dans les deux cas le nombre d'appels a` compare me
semble identique. Si les clefs sont compliquées (des chaînes par ex)
c'est là l'essentiel.


Enuite ça va être plus serré. Il faut essayer...



> Il ajoute en plus "However, so far the autor has never observed a
> compiler which actually translate these two comparaisons into one
> three-way comparaison"
Mais y a-til des machines qui les réalisent ces fameuses comparaisons
trois voies ? C'est bien la question au final.

Avec un processeur muni de drapeaux d'états on peut imaginer
une comparaison suivie de deux sauts conditionnels.

Avec un Risc genre Mips, je vois pas trop.


> 
> - Qu'est exactement une comparaison =E0 trois voies ? (est-ce une fa=E7on
> d'exploiter que les processeurs en g=E9n=E9ral l=E8vent des drapeaux de
> signe ou de nullit=E9 pour leurs op=E9rations ?)
C'est un truc mysterieux pour moi. qui par magie envoie sur trois
choix possibles de façon « atomique » vu du processeur ça a peut être existé un
jour...
En gros ça correspond à un modèle du coût de la machine où ce choix
entre trois possibilités compte pour un..

En pratique et pour avoir essayé longtemps il est dur de relier les
modèles de coût basés sur le nombre de comparaisons élémentaires au
temps machine.  La raison est assez simple, les deux (trois ?) cas
possibles n'ont pas le même coût, car on a un dileme saut/pas saut et
le temps d'un saut est disons variable.


En pratique, les sauts pris sont souvent dominants dans le coût du
code natif, dès lors, le coût effectif dépend  des entrés et aie.

En bytecode c'est moins net.



> 
> - Le compilateur Caml effectue-t-il cette optimisation ?

Il en fait une de ce style.

Sur le pentium et pour un

match du style (type t = A | B | C)

match x with
| A -> ...
| B -> ...
| C -> ...

Alors le code produit aura une instruction de compraison 
et deux sauts conditionnels.
Savoir si l'on gagne beaucoup à ce jeu-là, on gagne sans doute un peu
et dans certains cas (une instruction compare en moins..).


De façon générale, il est assez dur de se faire une idée précise de
possibles différences d'efficacité entre ces deux codes, au seul vu du
source (comme souvent).

L'argument supplémentaire peut être un facteur de ralentissement, mais
pas forcément exagéré (passage en registres).

Comme déjà dit c'est pas facile de relier un match ou même un if à un
quelconque coût final. Ça va dépendre de l'allignement de l'addresse
du code cible, de l'état des caches de la prédiction des sauts, voire
de la phase de la lune...


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

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