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 #925713.
Run by 
Cette page a été générée par Templeet en 0.0831s (dont 0.0074 de SQL).
Cette page est peut-être conforme xhtml 1.0.
Information sur le site.
Ton titre se démonte en 1 minute top chrono.
Lisaac créé du C, qui sera compilé par GCC ou autre ensuite.
Si tu suis un raisonnement scientifique (logique), Lisaac ne peut pas, par conception, être plus rapide que du C.
En effet, en suivant un simple raisonnement logique, un code C au minimum (le code généré par Lisaac), sera aussi rapide que du code Lisaac.
Il existera toujours un code C aussi rapide qu'un code Lisaac pour la même fonctionnalité.
CQFD.
Tu peux dire que tu peux coder plus rapidement du code rapide avec Lisaac, tu ne peux en aucun cas dire que Lisaac est plus rapide que le C.
[^]Re: Ton titre se démonte en 1 minute top chrono.
Comprendre, "Du C écrit par un humain".
[^]Re: Ton titre se démonte en 1 minute top chrono.
Un humain peut écrire aussi le C codé par Lisaac, rien ne l'en empêche techniquement. Si Lisaac sait faire, un humain sait aussi le faire.
Tu peux dire "par un humain dans le même laps de temps" peut-être, mais tu ne peux pas dire "Lisaac est plus rapide que du code C écrit par un humain" vu qu'un humain sait écrire du C, sait réfléchir (Lisaac implémente des algo écrit par des humains non? Donc les humains connaissent les algo C... Lisaac ne fait qu'automatiser une tache très fastidieuse)
[^]Re: Ton titre se démonte en 1 minute top chrono.
Lisaac ne fait qu'automatiser une tache très fastidieuse
que?
[^]Re: Ton titre se démonte en 1 minute top chrono.
Je suis d'accord qu'on puisse dire « un humain peut écrire du C aussi rapide que le C généré par Lisaac » mais il est plus difficile de soutenir qu' « un humain peut écrire un code en C aussi rapide que le C généré par Lisaac, et qui soit également aussi maintenable que le code Lisaac ».
Ça doit être un peu comme maintenir un code après passage au préprocesseur, ou pire un code décompilé.
† In te confirmátus sum ex útero : de ventre matris meæ tu es protéctor meus.
[^]Re: Ton titre se démonte en 1 minute top chrono.
Dans la distribution de lisaac, il y a un lisaac.c qui est le compilé Lisaac vers C du compilo, pour avoir une idée de la tronche du code généré.
"Si tu suis un raisonnement scientifique (logique), Lisaac ne peut pas, par conception, être plus rapide que du C."
Et donc par conception, du code C ne peut pas être plus rapide que de l'assembleur ? Et par extension, aucun langage ne peut être plus rapide que l'assembleur ?
Il est évident que je parle pour un temps de développement "borné". "Plus rapide" n'a de sens que dans ce cadre.
[^]Re: Ton titre se démonte en 1 minute top chrono.
Et donc par conception, du code C ne peut pas être plus rapide que de l'assembleur ? Et par extension, aucun langage ne peut être plus rapide que l'assembleur ?
Oui, et je ne vois pas ce qui te choque.
Un langage, pas sa façon de voir les choses, va imposer des limitations par rapport au code assembleur (langue maternelle du CPU)
Un code assembleur sera potentiellement toujours plus rapide que du C, et du C ne sera jamais plus rapide que de l'assembleur, tout bêtement parce que tu ne peux pas faire tout code assembleur avec du C. Tu as x milliards de façons de faire du code en Assembleur, tu en a moins que x milliards en C.
Lisaac produit du C, donc reprend obligatoirement la limitation du C, en plus d'ajouter les siennes.
Donc Lisaac <= C <= Assembleur.
C'est scientifique, je ne vois pas ce qui te pose problème...
Il est évident que je parle pour un temps de développement "borné".
As-tu fixé les bornes? Sont-elles acceptée par tous? Est-ce que tu as fait des tests sur les autres langages avec les mêmes bornes? Dire des "vérités" brutes, c'est pas si évident, tu généralises à partir d'un exemple, on peut te donner un autre exemple ou C est plus rapide que Lisaac (genre void main(){}) et dire "Lisaac ca rame.
Tu balances une truc super-général, avec quelques tests, désolé mais ça n'a rien de scientifique, ça fait la personne qui veut prouver quelque chose et qui va biaiser son étude pour arriver à la conclusion qui l'arrange...
[+] [^]Re: Ton titre se démonte en 1 minute top chrono.
, tu en a moins que x milliards en C.
Sachant que tu peux mettre de l'asm dans du code C, si!
/me sort en courant
Sinon plus sérieusement, tu nous dis que C est injectif dans l'ASM (tous le c est contenu dans l'asm) , mais pas surjectif (tous les élements de l'asm a au moins un antécédents dans c). Ansi donc C n'est pas bijectif dans l'asm.
Maintenant reste plus qu'a le prouver :P
As-tu fixé les bornes? Sont-elles acceptée par tous?
Je pense que si tu dis que n'importe que programme doit pouvoir etre terminé dans les 100 ans, les bornes sont accepté par tous.
Subete ga wakatta toki…watashi ga anta wo korosu.
[^]Re: Ton titre se démonte en 1 minute top chrono.
code assembleur (langue maternelle du CPU)
C'est faux ça. J'ai souvent vu des instructions qui sont en fait des macros ou des concatenations d'instruction (par exemple pour faire un saut absolue en ARM, le call est transformé en call indirect qui va chercher l'adresse de saut un peu plus loin en mémoire).
C'est encore un poil au dessus du binaire de base.
Tu balances une truc super-général, avec quelques tests, désolé mais ça n'a rien de scientifique, ça fait la personne qui veut prouver quelque chose et qui va biaiser son étude pour arriver à la conclusion qui l'arrange...
Espèce de rabat-joie.
Ne t'inquiète pas je sais très bien ce que veut dire ce bench et ce qu'il ne veut pas dire.
Mais si il y a 2 ans tu aurais dit qu'un langage à prototype qui est encore plus haut niveau que Eiffel aurait des performances proches du C, tu aurais été mis à l'asile.
As-tu fixé les bornes? Sont-elles acceptée par tous? Est-ce que tu as fait des tests sur les autres langages avec les mêmes bornes? Dire des "vérités" brutes, c'est pas si évident, tu généralises à partir d'un exemple, on peut te donner un autre exemple ou C est plus rapide que Lisaac (genre void main(){}) et dire "Lisaac ca rame.
Je fais pas mal d'optimisation pour m'amuser. Je suis sûr que je peux battre Lisaac, car c'est une partie de mes idées qui sont à la base de certaine optimisation. Mais entre prendre un code clean, pour le transformer en truc immonde 2 fois plus rapide, il y a des heures de boulot. Et encore, certaine optimisation nécessite d'avoir la connaissance adéquate, cela n'est pas à la porté de tout codeur.
[^]Re: Ton titre se démonte en 1 minute top chrono.
Mais si il y a 2 ans tu aurais dit qu'un langage à prototype qui est encore plus haut niveau que Eiffel aurait des performances proches du C, tu aurais été mis à l'asile.
Bah... tu sais, j'ai déjà tellement entendu que le C++ c'est plus lent que le C car plus haut niveau (alors que bon, à utilisation identique, c'est pareil... Un peu comme Lisaac, le C++ est olus facile à maintenir que le C :-D ), voir Java, qui n'a pas grand chose à voir avec le C mais qu'on dit super-lent (alors que non, correctement utilisé ça se bat bien), que je ne m'intéresse pas au "niveau" d'un langage.
Je ne suis pas d'accord avec toi donc pour dire que plus le langage est haut niveau, plus il est lent. (Ca va dans ton sens ;-) ).
Mais je reste stupéfait quand je lis "Le langage A crachant du langage B est plus rapide que le langage B"
Non, et non, ça ne peut pas marcher, rien qu'intellectuellement.
Et c'est dommage de se "battre" sur ce terrain, l'avantage d'un langage haut-niveau n'étant pas la mesure de sa rapidité (un langage qui pour faire la même chose rame 10x plus n'est pas forcement un mauvais langage, c'est surtout le compilo qui est merdique).
Car au final, tu as dis "Lisaac est plus rapide que le C sur tel test", en comparant quoi? Des compilos. Tu a comparé le compilo Lisaac au compilo C que tu veux, alors que suivant le compilo, suivant sa configuration, ça peut changer sa perf.
Dire que tel langage est plus rapide que tel autre est une grosse connerie : ce n'est pas le langage qui fait forcement la vitesse, mais le compilo.
Bref, c'est surtout le titre du journal qui m'a fait bondir, tu l'auras compris.
[^]Re: Ton titre se démonte en 1 minute top chrono.
"Mais je reste stupéfait quand je lis "Le langage A crachant du langage B est plus rapide que le langage B"
Non, et non, ça ne peut pas marcher, rien qu'intellectuellement."
Cela démontre juste qu'intellectulement, tu n'as rien compris à la compilation, voir même à l'intérêt d'un langage de programmation (qui doit aider à gérer les problèmes de maintenabilité et d'absence d'erreur).
Et on revient à la débilité où on compare C et l'assembleur.
Or le C n'est qu'un assembleur un poil plus évolué.
l'avantage d'un langage haut-niveau n'étant pas la mesure de sa rapidité (un langage qui pour faire la même chose rame 10x plus n'est pas forcement un mauvais langage, c'est surtout le compilo qui est merdique).
Et pourtant, tous les langages de haut niveau sont plus lent que C (jusqu'à présent). On connait tous les avantages du haut niveau si en plus on a la vitesse, c'est encore mieux...
"Dire que tel langage est plus rapide que tel autre est une grosse connerie : ce n'est pas le langage qui fait forcement la vitesse, mais le compilo."
Sauf que c'est simplement faux. Faire un compilo rapide pour perl ou python est super difficile, car le langage ne le permet pas au contraire de lisaac. C montre aussi ces limites (contrainte sur le structure de donné en mémoire par exemple).
Pour un effort identique, un compilo ne te donnera pas du tout le même résultat selon le langage. Dans le cas de génération du C, tu peux en plus utiliser toutes les optimisation bas niveau du compilo C.
[^]Re: Ton titre se démonte en 1 minute top chrono.
"Mais si il y a 2 ans tu aurais dit qu'un langage à prototype qui est encore plus haut niveau que Eiffel aurait des performances proches du C, tu aurais été mis à l'asile."
Moi je suis sûr que madame michu elle le pense toujours. :)
Le wiki de l'association culture libre : collection d'œuvres sous licence art libre.
[^]Re: Ton titre se démonte en 1 minute top chrono.
Mais si il y a 2 ans tu aurais dit..., tu aurais été mis à l'asile.
Par maître Capello sans doute.
[^]Re: Ton titre se démonte en 1 minute top chrono.
Attention au raisonnement tout de même : qu'est-ce qu'un programme assembleur fourni par du C ? c'est du C compilé. Qu'est-ce qu'un programme assembleur ? c'est de l'assembleur, écrit par quelqu'un. Donc on ne compare que des compilateurs et des programmeurs, pas des langages, vu que ce qui est exécuté ce n'est jamais que de l'assembleur.
Et encore on n'a pas parlé de la distribution des données d'entrées, qui joue fortement sur les performances des programmes quand on les compare.
En effet, définissons un programme comme suit : il prend des données dans une certaine zone de mémoire (comprenant éventuellement les données aléatoires qu'il aura à récupérer, sans perdre de généralité). Il fait ensuite un traitement déterministe et sort les résultats dans une certaine zone de la mémoire (bon c'est presque une machine de Turing notre programme, ami lecteur sauras-tu retrouver la différence ? ).
Si on prend le compilateur théorique suivant, on aura parfaite égalité de vitesse dans les programmes entre tous les langages :
1) il prend le code initial (du C, du Lisaac, etc.)
2) il génère tous les codes assembleurs qui réalisent la même opération (données en mémoire -> sortie en mémoire). C'est possible en temps fini (il suffit de tout énumérer) mais c'est long (bon j'ai précisé que c'était un compilateur théorique, hein ;-) )
3) le compilateur lance chaque programme sur toutes les entrées possibles (pareil, c'est encore plus long ;-) )
4) il choisit à chaque fois le programme le plus rapide pour effectuer les tâches.
Alors l'assembleur, écrit par un humain, sera forcément plus lent ou au mieux aussi rapide que le C/Lisaac/tout ce que vous voulez.
ensuite si on veut chipoter sur les données on se met d'accord sur une distribution de probabilité des données d'entrées et sur la façon de calculer la meilleure vitesse (vitesse moyenne sur les entrées ? vitesse dans le pire cas ? ... ? ) et on recommence le compilateur précédent, en choisissant le programme le plus rapide.
[^]Re: Ton titre se démonte en 1 minute top chrono.
Raisonnement correct sur des bases fausses: Tu sous entends que tu es capable d'exprimer avec chacun des langages exactement ce que tu veux faire et rien de plus.
Quelque soit le compilateur, il se doit de retranscrire ce que tu as exprime en utilisant un langage. Mais parfois le langage manque de nuance dans un cas precis et tu lui dit plus que ce que tu penses, volontairement ou pas.
[^]Re: Ton titre se démonte en 1 minute top chrono.
Euh erreur, le compilateur ne retranscrit pas nécessairement exactement ce qu'on lui a demandé de faire : il se permet de rajouter diverses optimisations (réordonnancement de code, suppression de variables inutiles s'il estime que ne pas la nommer et de la laisser dans un registre ne changera rien à la fonction, parallélisation de certaines instructions, suppression de boucles, suppression de récursivité dans certains cas etc.).
L'essentiel est bien qu'étant donné une entrée le calcul soit le même que celui spécifié par le langage, c'est en ce sens là seulement que le compilateur se doit de retranscrire ce qu'on a exprimé.
Le langage initial n'étant pas exécutable directement sur une machine, il n'est qu'une indication de ce qui doit être fait, pas une description exacte.
[^]Re: Ton titre se démonte en 1 minute top chrono.
Ca ne change pas ce que j'ai dit. Mais on peut preciser: Le compilateur peut faire tout ce qu'il veut tant que le resultat final correspond exactement a ce qui aurait ete obtenu si il n'avait pas fait de modifications. Tu le dis toi meme dans ta reponse: "
L'essentiel est bien qu'étant donné une entrée le calcul soit le même que celui spécifié par le langage".
Je parlais de l'expression du resultat final: Si je ne peux pas decrire ce que je veux exactement, par exemple je desire obtenir un resultat satisfaisant certaintes contraintes que le langage ne me permet pas d'exprimer. Je me trouve donc dans l'obligation d'ajouter certaines contraintes de tel sorte que le resultat soit satisfaisant, mais avec un cout supplementaire de calcul.
[^]Re: Ton titre se démonte en 1 minute top chrono.
je vois ce que tu veux dire, mais tu piques ma curiosité ;-) quel serait un exemple de contrainte sur le résultat final qui ne soit pas exprimable avec un langage (complet/etc. ; par exemple du C) que pourrait exprimer l'assembleur ?
(surtout qu'on peut écrire un simulateur de processeur, un interpréteur d'assembleur en fait, en n'importe quel langage)
[^]Re: Ton titre se démonte en 1 minute top chrono.
Ca reste theorique, tout comme ton compilo ;-)
En effet comme tu le dis, on peut simuler un processeur. Donc on a une equivalence dans la theorie, sous reserve de resource illimitee, que l'on reste dans le calculable, et que le compilo soit capable de non pas optimiser le simulateur, mais le couple (simulateur, code). Mais avec tout ce que ton compilo est capable de faire, pourquoi pas...
Apres y avoir repense, tu as raison. Si je devais re-repondre, je dirais: Le raisonnement est correct, mais la situation initiale reste a prouver.
[^]Re: Ton titre se démonte en 1 minute top chrono.
Ah ouai je viens de regarder le fameux lisaac.c c'est assez affreux à voir ^^.
En fait ce qu'on peut-dire aussi c'est que Lisaac dépend du compilateur C, et donc qu'un code en lisaac ne peut donner un programme plus rapide que ce que peut donner ce même compilateur C, quelque soit le langage à la base et les étapes de transcription.
Je pense donc que Lisaac est plus dépendant du compilateur C que du langage C lui même (qui est assez bas-niveau pour pouvoir être torturé dans tout les sens).
En fait c'est bien là où pèche la rhétorique : c'est qu'il doit être possible de faire à peu près tout en C (sans prendre en compte les critères de lisibilité, clarté, concision, maintenabilité...) donc forcément tout code, même s'il ne passait pas par l'étape C à la compilation comme Lisaac, pourrait avoir un équivalent en C aussi rapide que lui.
Conclusion : améliorons toujours gcc. :)
Je pense qu'il faut voir le code C produit par Lisaac comme une étape de précompilation : ce n'est déjà plus le source. Écrire un programme en C aussi rapide qu'un programme en C pourrait revenir à programmer un programme directement en binaire avec éditions de liens et tout et tout, et qui soit aussi rapide que celui en assembleur. c'est possible, certains l'ont fait peut-être, mais bon...
D'ailleurs, si j'ai bien, deux langages turing-complets doivent pouvoir être retranscrit dans l'un ou dans l'autres des langages avec un comportement final identique, à l'instruction près, où alors ils ne seraient pas turing-complets. Donc il est possible d'écrire un code Lisaac qui soit aussi lent qu'un code C. (qui veut écrire le compilateur ? XD).
† In te confirmátus sum ex útero : de ventre matris meæ tu es protéctor meus.
[^]Re: Ton titre se démonte en 1 minute top chrono.
Je pense qu'il faut voir le code C produit par Lisaac comme une étape de précompilation
Un compilateur ne produit pas forcément de l'assembleur. Le compilateur Lisaac est un compilateur de plein droit.
Et effectivement le code C produit n'est plus le source, et si quelqu'un s'amusait à rajouter des blobs en C issues d'une compilation Lisaac dans la distribution d'un programme GPL et qu'il distriburait le résultat sans fournir les sources Lisaac, il violerait clairement la GPL.
[^]Re: Ton titre se démonte en 1 minute top chrono.
Oui, enfin le code C généré est quand même de l'ANSI C (et si ce n'est pas le cas, tu peux envoyer le bug sur la mailing list our sur GNA)
La Roue du Temps
[^]Re: Ton titre se démonte en 1 minute top chrono.
Bon je crois que tout le monde à compris que c'était un abus de langage. Puisque on ne peut pas appliquer le concept de vitesse à un langage de programmation.
C'est : un programme généré par un compilateur (ou une suite de compilateur) à partir d'un code source redigé dans un langage, qui peut être rapide ou non à délivrer un résultat pour une certaine entrée.
sachant que chacun de ces élément influence la vitesse finale...
En plus lisaac est a la fois le nom du compilateur et du langage, ce qui rajoute encore à la confusion.
Pauvres mouches ...