Journal : Lisaac plus rapide que le C !
Posté par Nicolas Boulay () le 24 avril 2008
Tout le monde s'en fout, mais cela fait des années que je suis persuadé qu'un langage de très haut niveau à plus de potentiel d'optimisation qu'un langage aussi bas niveau que le C. Et pourtant dés que l'on veut de la performance, on pense C.
C'est fait, Lisaac, un langage impératif à prototype, a plus de point que le C dans le langage shoutout. Il s'agit de microbenchmarks, dont l'algorithme est imposé.
http://shootout.alioth.debian.org/gp4/benchmark.php?test=all(...)
Cela fait un test un peu plus complet que le code mpeg2 qui servait de test.
http://isaacproject.u-strasbg.fr/li/li_benchs.html
Chapeau à Ben !
C'est fait, Lisaac, un langage impératif à prototype, a plus de point que le C dans le langage shoutout. Il s'agit de microbenchmarks, dont l'algorithme est imposé.
http://shootout.alioth.debian.org/gp4/benchmark.php?test=all(...)
Cela fait un test un peu plus complet que le code mpeg2 qui servait de test.
http://isaacproject.u-strasbg.fr/li/li_benchs.html
Chapeau à Ben !
> Lire le journal (157 commentaires, moyenne: 3,4).
Vous avez demandé le commentaire #926723.
Run by 
Cette page a été générée par Templeet en 0.1663s (dont 0.0189 de SQL).
Cette page est peut-être conforme xhtml 1.0.
Information sur le site.
Hum
Dans l'article de wikipedia, on peut lire: "Le compilateur Lisaac génère du C ANSI optimisé".
Donc Lisaac n'est pas plus rapide que le C, puisque c'est du C.
[ Répondre ]
[^]Re: Hum
A bah, non, c'est de l'assembleur puisque le C génère de l'assembleur.
[ Répondre ]
[^]Re: Hum
C'est gcc qui fait de l'assembleur.
Enfin, je comprend très bien l'idée qu'un langage de plus haut niveau arrive à faire mieux en rajoutant ses propres optimisations en plus de celles de gcc. C'est juste que on en revient encore une fois à gcc, et donc la puissance du C.
[ Répondre ]
[^]Re: Hum
Dire que Lisaac c'est du C, c'est aussi débile que dire que du C, c'est de l'assembleur car c'est ce que génère gcc.
[ Répondre ]
[^]Re: Hum
Je suis d'accord, mais dans ce cas faut pas venir clamer avec des trompette que tel langage est plus rapide que tel autre. Ça veux dire quoi la vitesse d'un langage?
Ce sont les processus exécutants des tâches aux finalités équivalentes sur un même matériel qui sont plus où moins performants. Éventuellement les programmes qu'éxécutent ces processus sont écrit dans un langage différent.
Le wiki de l'association culture libre : collection d'œuvres sous licence art libre.
[ Répondre ]
[^]Re: Hum
Disons que si tu prends 2 codeurs moyen avec un temps fixe de développement, tu auras un binaire plus rapide sous Lisaac que sous C. Car c'est plus costaux d'optimiser à mort pour C.
Ce sont les processus exécutants des tâches aux finalités équivalentes sur un même matériel qui sont plus où moins performants. Éventuellement les programmes qu'éxécutent ces processus sont écrit dans un langage différent.
c'est ça un bench. Même algo, même machine, même donné, seul change le langage, donc toute différence de performance peut-être imputé au langage, ou au codeur. C'est l'intérêt du développement ouvert du shoutout tout le monde peut proposer mieux.
[ Répondre ]
[^]Re: Hum
donc toute différence de performance peut-être imputé au langage, ou au codeur.
Ou au compilateur, vu qu'il est possible de faire deux compilateurs pour un même langage dont les binaires résultants n'auront pas la même vitesse d'exécution.
[ Répondre ]
[^]Re: Hum
Il n'y a rien de débile à dire que Lisaac c'est du C et de l'assembleur ; ce qui serait débile, c'est de dire que l'assembleur c'est du C ou du Lisaac.
Dit de manière (un peu) plus formelle, pour tout code en Lisaac, il existe un code équivalent en C ou en assembleur (ça reste encore un peu boiteux car le terme équivalent dépend du compilateur utilisé).
Et de fait, Lissac ne sera jamais plus rapide ou économe en mémoire que le C (désolé pour ton journal). Évidemment, ça ne prouve pas qu'il s'agisse d'un mauvais langage, car il est peut être plus facile à écrire et à débugger que le C, ce que le benchmark en question n'essaye pas de juger.
[ Répondre ]
[^]Re: Hum
ça reste encore un peu boiteux car le terme équivalent dépend du compilateur utilisé
C'est pas boiteux du tout. Tout langage est équivalent à tout autre sur le plan théorique. Ce qui définit le terme de langage c'est un formalisme pour décrire un calcul au sens Turing du terme.
Donc c'est pas boiteux... Seulement on a l'habitude de convertir dans un sens (compiler le C en assembleur par exemple) et pas dans l'autre.
be a sheep isn't cheap
[ Répondre ]
[^]Re: Hum
Ouhla ! Il y a équivalence et équivalence !
Tout langage de programmation digne de ce nom est Turing-complet, c'est à dire équivalent fonctionnellement à une machine de Turing.
Cela ne veut pas dire que l'on peut programmer des programmes également efficaces dans tous les langages Turing-complets.
D'ailleurs, y a qu'à voir comment est décrite la machine de Turing pour s'en rendre compte (combien de temps pour faire tourner un algo disons de tri sur une machine à ruban unique ?).
[ Répondre ]
[^]Re: Hum
Si je ne me trompe pas, un systeme turing-complet est un systeme qui est capable de calculer tout ce que la machine de Turing peut calculer.
C'est different de Turing-equivalent, qui inclue en plus le fait qu'une machine de Turing soit capable de calculer ce que ton system peut calculer [L'autre sens, en gros].
Si Turing-complet n'implique pas Turing-equivalent au sens strict, il s'observe dans la pratique que les systemes Turing complet sont aussi Turing-equivalent.
[ Répondre ]
[^]Re: Hum
Hein ?
les machine de turing peuvent tout calculer. En particulier en peut prendre la machine de turing universelle qui simule une machine de turing codé dans sa bande.
Et tous les langage des prog peuvent simuler une machines de turing (ca doit prendre 10minutes a programmer).
bref je ne vois pas la différence entre ta turing-équivalence et complétude.
[ Répondre ]
[^]Re: Hum
Non une machine de Turing ne peut pas tout calculer, juste ce qui est calculable. Pas le problème de l'arrêt, par exemple. Pas la question dont la réponse est 42 non plus.
[ Répondre ]
[^]Re: Hum
Arf c'était sous entendu.
Concernant 42, si on suppose que la question a laquelle on répond 42 est calculable. Ce qui semble logique puisque dans l'histoire pensée profonde arrive trouver la réponse en un temps fini de 7 500 000 année. Alors on pourrait imaginer énumérer toutes les machines de turing en ordre canonique (toutes les machines de taille 1, puis toutes les machines de taille 2). Et en même temps simuler simultanément (en parallèle) toutes les machines déjà générée à l'instant t sur toutes les entrée possible dans l'ordre canonique également. Quand je dis simuler en parallèle c'est important, puisque une machine de turing ne se termine pas forcement (sur une entrée) on ne peut pas se contenter de lancer chaque calcul à la suite.
Donc à partir de là on pourrait avoir une liste de machines de turing qui termine en écrivant 42. Bon le problème c'est pour savoir quelle est la bonne question parmi toutes celles qui sont dans la liste. Là effectivement faudrait ptet ouvrir la tête d'Arthur pour la choisir, mais bon je doute de la trouver là :-)
[ Répondre ]
[^]Re: Hum
Moui, ce que tu dis est juste dans l'absolu (normalement la X-complétude n'est pas l'équivalence à X).
Enfin tout ça aurait un sens si on avait d'autres modèles de calcul plus puissants (fonctionnellement) que la machine de Turing, ce qui n'est pas possible avec ce qu'on appelle calculable, et encore moins avec ce qui est effectivement calculable dans un ordinateur (à mémoire finie).
Enfin bref quoiqu'il en soit, tout en gardant la puissance d'une machine de Turing universelle, on peut imaginer des paquets de modèles de calcul plus ou moins efficaces, dont un paquet qui sont basés sur les comportements possibles d'un processeur classique sur un sous-langage de l'assembleur. Ces sous-langages étant la cible des différents compilateurs.
[ Répondre ]
[^]Re: Hum
On est d'accord. J'apportais juste une precision (qui ne remettait pas en cause l'idee). Un restant de mon traumatisme issue de ma prof de Math.
[ Répondre ]
[^]Re: Hum
Mais, on en a des modèles de calcul plus puissants que la machine de Turing : hypercalcul ! Ce qui sauve la thèse se Church, c'est que ce ne sont que des modèles et que personne n'a jamais vu de machines qui sont effectivement super-Turing... Mais qui a vu des machines de Turing de toute façon ?
[ Répondre ]
[^]Re: Hum
Bon, c'est pas exactement des machines de Turing, mais perso j'ai vu une Bombe et un Colossus reconstruits. Habitant a coté de Bletchley Park fallait bien que je visite quand meme :)
"While a monkey can be a manager, it takes a human to be an engineer" Erik Zapletal
[ Répondre ]
[^]Re: Hum
M'enfin certes. Mais c'est hors-sujet. Aucune machine physique ne peut ni ne pourra jamais implanter un hypercalculateur.
D'où les précautions que je mettais autour du terme "calculable" pour qu'on se limite aux cas pratiques réels (temps fini et mémoire finie pour une instance), alors même que j'ignorais l'existence de l'hypercalcul (mais me doutais bien qu'un truc dans ce genre devait exister ! ;-) ).
[ Répondre ]
[^]Re: Hum
Comment ça c'est débile ?
C'est pas de l'assembleur d'ailleurs, ce sont des octets.
[ Répondre ]
[^]Re: Hum
Il faut lire « du C écrit par un humain ».
[ Répondre ]
[^]Re: Hum
Bah il suffit d'être un humain capable de faire toutes les optimisations imaginables dans ce cas.
Bon ok, on risque de perdre en lisibilité toussa mais c'est un autre problème.
[ Répondre ]
[^]Re: Hum
et passer un temps hyper long...
[ Répondre ]
[^]Re: Hum
c'est pour ça que l'homme a inventé l'informatique : pour faire les taches longues pénibles et très souvent répétitive à une armée de singe en silicone.
Comme ça, le serpent se mord bien la queue :P
Subete ga wakatta toki…watashi ga anta wo korosu.
[ Répondre ]
[^]Re: Hum
Pour revenir à ce que disait yellowiscool, je ne comprend pas vraiment son moinsage... Il n'a pas tord :
Si Lisaac génère du C, j'ai du mal à voir comment on peut dire que c'est plus rapide que le C comme tu le prétends dans ton titre.
Par contre en effet, le Lisaac permet visiblement de générer un code plus optimisé et donc plus rapide que si on avait codé directement en C sans être un génie de l'optimisation.
[ Répondre ]
[^]Re: Hum
Pour revenir à ce que disait yellowiscool, je ne comprend pas vraiment son moinsage... Il n'a pas tord :
Si Lisaac génère du C, j'ai du mal à voir comment on peut dire que c'est plus rapide que le C comme tu le prétends dans ton titre.
gcc génère de l'assembleur à partir de C, est-ce qu'on peut dire que le C c'est de l'assembleur ?
Faut arrêter de faire souffrir les drosophiles tout le monde a bien compris de quoi il s'agissait au delà de l'abus de langage.
[ Répondre ]
[^]Re: Hum
gcc génère de l'assembleur à partir de C, est-ce qu'on peut dire que le C c'est de l'assembleur ?
Ce n'est pas du tout ce qui est dit : personne n'a dit que Lisaac c'était du C.
Quelqu'un a-t-il aussi proclamé que le C était plus rapide que l'assemble ? Je ne pense pas.
[ Répondre ]
[^]Re: Hum
Bon, on dirait que mon clavier s'est blo (sur l'assembleur) ;-)
En tous cas, dans le cas de Lisaac, il existera toujours au moins un programme C aussi performant que celui en Lisaac : celui généré par Lisaac, ou un autre. C'est tout.
[ Répondre ]
[^]Re: Hum
Sauf qu'un humain mettra infiniment plus de temps à le générer que le compilo Lisaac.
[ Répondre ]
[^]Re: Hum
Parle pour toi ! :-)
[ Répondre ]
[^]Re: Hum
Je n'ai pas dit que Lisaac c'était du C mais il a été dit que ça générait du C.
Par exemple, pour ceux comme moi qui ne connaissent pas Lisaac, on peut imaginer un langage qui a des fonctions de très haut niveau et qui te génère du C méga optimisé et tu pourras en arriver à la même conclusion qu'ici.
Après, on peut prendre le même raisonnement avec le C et l'assembleur. On pourra tjs dire que le C peut-être plus facilement optimisable mais au final, vu qu'on se retrouve avec du code assembleur, on ne peut pas dire qu'il est plus rapide mais seulement qu'il peut être plus rapide que du code assembleur qui sort d'un codeur.
Un exemple simple :
Tu fais un programme de tri qui fait appel à la fonction qsort en C. Derrière ça te génère du code ultra optimisé mélangeant du quicksort à d'autres tris etc.
Maintenant, tu me demandes de te le faire en assembleur, je vais te faire un truc moins optimisé car je serais déjà bien content que ça marche :).
Est-ce qu'on peut dire que le C est plus rapide que l'assembleur ? non.
[ Répondre ]
[^]Re: Hum
>Par contre en effet, le Lisaac permet visiblement de générer un code
>plus optimisé et donc plus rapide que si on avait codé directement en
>C sans être un génie de l'optimisation.
Il n'y pas besoin d'être un génie du C pour faire repasser le C devant... Il suffit de faire de la pré-allocation pour les arbres binaires (cfr. mon code dans un post plus haut).
[ Répondre ]
[^]Re: Hum
La différence est minime de toute façon, c'est symbolique...
Propose ta modification. Mais fait attention aussi que tu respectes bien les règles de codages, si tu change l'algo cela n'a pas de sens, et que si tu fais exploser la consommation mémoire tu y perds sur ce paramètre.
[ Répondre ]
[^]Re: Hum
>Propose ta modification.
Pour ça, il faudrait que l'allocation soit un peu plus propre et plus dynamique ;-) J'ai pas trop envie d'en faire plus. C'était juste pour avoir une estimation de l'ordre de grandeur du remplacement de l'allocation de mémoire.
>si tu change l'algo cela n'a pas de sens
Rien changé, juste remplacé les malloc/free par les miens.
[ Répondre ]
[^]Re: Hum
Voila, j'ai soumit un autre programme :
http://alioth.debian.org/tracker/index.php?func=detail&a(...)
Les perfs sont encore meilleures que lors de mes modifications précédentes. Nous en sommes à un facteur de plus ou moins 15.
Bientôt (si c'est accepté), un journal avec le titre :
"Lisaac plus rapide que le C ? Pas du tout, efface !"
[ Répondre ]
[^]Re: Hum
Si tu as respecté l'algo de base, c'est le jeu !
[ Répondre ]
[^]Re: Hum
>Si tu as respecté l'algo de base, c'est le jeu !
Oui mais non :
How should I implement programs for the Benchmarks Game?
We prefer plain vanilla programs - after all we're trying to compare language implementations not programmer effort and skill.
De plus, je viens de remarquer qu'il existe une implémentation qui est beaucoup plus performante que celle utilisée sur le site http://alioth.debian.org/plugins/scmcvs/cvsweb.php/shootout/(...)
La mienne est plus rapide mais peu être considérée moins "vanilla". (Par ailleurs, je ne sais pas pourquoi cette version n'est pas utilisée).
[ Répondre ]
[^]Re: Hum
Les algos proposés sont parfois loin d'être optimal pour le problème posé. Une solution plus performante mais ne respectant pas l'algo original ne sera pas retenu.
[ Répondre ]
[^]Re: Hum
http://alioth.debian.org/plugins/scmcvs/cvsweb.php/shootout/(...)
Cela fait 18 mois qu'il est dans le cvs mais pas dans la comparaison, je ne sais pas pourquoi (Rien trouvé à ce sujet) :
- L'algo est le même (c'est juste une minimisation des appels à malloc via une réutilisation des noeuds libérés).
http://shootout.alioth.debian.org/gp4/faq.php#alternative
What does Interesting Alternative Program mean?
Interesting Alternative Program means that the program doesn't implement the benchmark according to the arbitrary and idiosyncratic rules of The Computer Language Benchmarks Game - but we simply couldn't resist showing the program.
= En résumé, les règles sont arbitraire...
[ Répondre ]
[^]Re: Hum
C'est clair. Et c'est dommage. On a du se battre pour insérer le langage, et ya fallu que Dominique Colnet, l'auteur d'Eiffel pousse une gueulante pour que ça passe.
C'est vraiment dommage, car on pourrait inclure d'autres langages intéressants. Personnellement, je me fiche que le langage soit connu ou pas.
Le shootout est un des rares cas où l'on peut voir différents langages en action pour autre choses que des hello world ou 1001 bottle of beer, et ça serait passionant de voir les spécificités de chacun, en vitesse, en concision, en syntaxe, etc...
ça me ferait franchement marrer de voir un bench avec du brainfuck ou du whitespace !
Franchement, je me suis carrément dit qu'il faudrait leur piquer le code source (c'est libre) et remonter le projet ailleurs, en étant moins arbitraire..
[ Répondre ]
[^]Re: Hum
>en étant moins arbitraire..
La première chose à faire pour ça, c'est d'autoriser tous les algo pour résoudre un problème précis car il est évident que certains paradigmes(OO, fonctionnel, impératif, ...)/algo s'implémentent mieux (sont plus efficaces) dans certains langages.
[ Répondre ]
[^]Re: Hum
Oui mais là, on compare des algorithmes, et plus des compilateurs.
Comparer des algos, c'est ce que fait le meteor-contest par exemple...
Ce serait intéressant de mettre les deux, mais de bien pouvoir séparer les résultats.
[ Répondre ]
[^]Re: Hum
>Oui mais là, on compare des algorithmes, et plus des compilateurs.
Oui mais non, si un algo est meilleurs pour un langage, il suffit d'implémenter le même dans les autres... On se retrouvera rapidement aux meilleurs algo dans tous les langages.
[ Répondre ]
[^]Re: Hum
Tu ne sais plus trop ce que tu tests dans ce cas là.
Il vaut mieux un truc imparfait avec une imperfection borné, qu'un truc ou tu ne sais quoi dire des chiffres. Est-ce que les chiffres est faibles car l'algo n'est pas le meilleur ?, etc...
[ Répondre ]
[^]Re: Hum
Cfr. (un post plus haut) :
https://linuxfr.org/comments/926979.html#926979
>Tu ne sais plus trop ce que tu tests dans ce cas là.
Si on sait exactement ce qu'on teste, le meilleur algo dans chaque langage. Car , par exemple, dans un langage fonctionnel, on ne développe pas comme dans de l'oo ou de l'impératif et les algos efficaces sont par voie de conséquence différents.
>Il vaut mieux un truc imparfait avec une imperfection borné, qu'un truc
>ou tu ne sais quoi dire des chiffres.
Non, figer l'algo biaise car certains algo sont plus adaptés aux paradigmes de certains langages.
[ Répondre ]
[^]Re: Hum
"Non, figer l'algo biaise car certains algo sont plus adaptés aux paradigmes de certains langages."
J'y crois moyen... Que certain algo soit plus facile à écrire avec certain langage, c'est une évidence. Mais les performances sont lié à l'algorithme et le traitement capable d'être fait par le compilateur.
Tu as des exemples ?
[ Répondre ]
[^]Re: Hum
Oui, par exemple :
http://www.haskell.org/haskellwiki/Introduction#When_C_is_be(...)
Les langages fonctionnels ont tendance à faire exploser la complexité en espace. Mais l'espace c'est du temps aussi ;-) Donc, les versions fonctionnelles du quicksort sont moins efficaces que dans un langage impératif. Un quicksort en place est plus efficace qu'un quicksort non en place. Le quicksort en place n'est pas exprimable en fonctionnel (a moins que le compilo soit vraiment vraiment vraiment intelligent, mais ça c'est de la science fiction actuellement).
Un quicksort en place et un non en place ne sont pas les mêmes algos. Si on choisit d'implémenter le non en place ce n'est pas équitable car C peut faire mieux (et pas Haskell). Si on prend le en place ce n'est pas équitable car Haskell aura des problèmes pour l'exprimer.
[ Répondre ]
[^]Re: Hum
Je trouve que c'est très équitable : Haskel ne permet pas de faire l'algo quicksort le plus rapide. C'est bien l'intéret d'un (micro) bench !
Pour être juste, je pense qu'il faudrait pouvoir mettre l'algo de trie que l'on veut. Mais si le quicksort est le plus rapide, alors Haskel produit dans tous les cas de trie, un code plus lent que C.
Si on prend le en place ce n'est pas équitable car Haskell aura des problèmes pour l'exprimer.
Je ne vois pas pourquoi cela serait injuste, c'est le but du test de montrer ce genre de limitation.
[ Répondre ]
[^]Re: Hum
[...] Dominique Colnet, l'auteur d'Eiffel [...]
Du compilateur (dialecte ?) SmartEiffel plutôt, non ? Pour Eiffel c'est Bertrand Meyer si je ne m'abuse.
[ Répondre ]
[^]Re: Hum
On peut pas faire un langage C qui s'auto-optimise ? Genre du C transformé en C optimisé transformé en ASM transformé en binaire transformé en signaux électriques transformé en déplacement de molécules transformé en ...
(et si on pouvait re-optimiser le C déjà optimisé, quelle classe)
[ Répondre ]
[^]Re: Hum
Vu que gcc optimise ton code C, tu voudrais qu'en plus il te donne l'équivalent en C que tu aurais dû taper pour que ce soit optimal ?
Quel est l'intérêt ? Pouvoir te la péter avec du code illisible mais plus rapide si gcc n'optimisait pas ? C'est tordu quand même :P.
[ Répondre ]
[^]Re: Hum
Genre un compilateur qui est capable d'effectuer des optimisations poussees en terme d'analyse inter-procedurales mais qui n'a pas de backend pour ta plateforme?
Ou que le resultat reinjecte dans GCC, avec moins d'ambiguite permet a GCC de rajouter un couche d'optimisation?
Hum.... llvm avec le backend cbe.
[ Répondre ]
[^]Re: Hum
Bin c'est couillons parce que l'optimisation dépend aussi fortement de la plateforme. Une façon de faire quelque chose peut-être plus rapide sur une plate-forme que sur une autre.
Du coup, en optimisant ton code pour une plate-forme, et en balancant le résultat sur une autre plate-forme, tu pourrais même y perdre.
De plus, je pense que ça n'a pas toujours de sens de parler d'équivalent en C du programme optimiser. Parfois, tu décris une action en C, et le compilateur aura un choix a faire pour le retranscrire en assembleur. Il n'y a pas forcément une équivalence strict entre l'assembleur et le C.
[ Répondre ]
[^]Re: Hum
Un compilo travaille sur plusieurs niveaux. L'optimisation de code pour une plateforme donnee en est un mais pas le seul. Celles de haut-niveau sont generiques et ne dependent pas de la plateforme.
En terme d'optimisation de code, tu as deux approches compatibles:
- Faire moins
- Faire plus vite
Si une approche de haut niveau est capable d'eliminer du code, peux importe l'optmisation de la plateforme: ne rien faire est plus rapide que quelque chose d'optimise. Un exemple pratique: Une classe A avec appel de methode virtuelle. A chaque appel de la methode, le code genere doit d'abord determiner quelle methode doit etre effectivement appele. Si une analyse pousse prouve que seule une sous-classe B est utilisee, et que la methode correspondante est statique, alors tu peux supprimer la recherche: tu connais la methode au moment de la compilation.
Pour info, les compilos avec une sortie en C n'effectue pas une traduction code machine vers C. La traduction s'effectue depuis la representation intermediaire, avant l'optmisation pour la plateforme.
[ Répondre ]