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 RAA09540; Wed, 7 Aug 2002 17:22:47 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f 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 RAA09430 for ; Wed, 7 Aug 2002 17:22:46 +0200 (MET DST) Received: from beaune.inria.fr (beaune.inria.fr [128.93.8.3]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g77FMk529897 for ; Wed, 7 Aug 2002 17:22:46 +0200 (MET DST) Received: by beaune.inria.fr (8.8.8/1.1.22.3/14Sep99-0328PM) id RAA0000006153; Wed, 7 Aug 2002 17:22:45 +0200 (MET DST) From: Luc Maranget Message-Id: <200208071522.RAA0000006153@beaune.inria.fr> Subject: Re: [Caml-list] Three way comparaisons To: Diego-Olivier.FERNANDEZ-PONS@cicrp.jussieu.fr (Diego Olivier Fernandez Pons) Date: Wed, 7 Aug 2002 17:22:45 +0200 (MET DST) Cc: caml-list@inria.fr In-Reply-To: from "Diego Olivier Fernandez Pons" at aoû 07, 2002 04:41:35 MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > > 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