Développeur : Erlang/OTP R11B supporte les architectures multiprocesseur
Posté par Mickaël Rémond (page perso, ). Modéré le 22 mai 2006.
Une nouvelle version de la machine virtuelle Erlang et du canevas de développement a été publiée. Cette version R11B est une avancée majeure, car elle supporte désormais les architectures multiprocesseur. Une même application Erlang peut ainsi bénéficier directement d'amélioration de ses performances sans retoucher son code.
![[en]](../images/en.png)
Erlang (677 hits)-
Nouveautés de la version R11B (270 hits)
-
IBM DeveloperWorks: Concurrent programming with Erlang (298 hits)
-
Planet Erlang (236 hits)
![[fr]](../images/fr.png)
Livre: Erlang programmation (535 hits)-
Définition Wikipédia (1013 hits)
> Lire la dépêche (114 commentaires, moyenne: 3,4).
Vous avez demandé le commentaire #714280.
[+] ...
Et on peut avoir un vrai bench C/Erlang ?
C'est pas pour dire, mais ça fait des années que pleins de gens pensent avoir découvert le langage idéal, et on en revient toujours au C...
Surtout pour de la programmation serveur...
[^]Re: ...
Oh, ça fait aussi des années que plein de gens savent choisir le bon outil pour la bonne tâche, tout en écoutant d'une oreille amusée les discours caricaturaux façon "on en revient toujours au C" .
[^]Re: ...
à propos de Alan Kay (le père de Smalltak) :
dernier paragraphe de : http://gracewanderer.livejournal.com/89519.html
There was a handfull of Comp Sci students there that I hung out with for a bit, and they told me about a lunch that they were all at earlier in the day with Alan Kay.
Apparently, one of the students said to Kay, "I don't see why you need anything more than C to write an operating system with."
This is like saying to Einstein, "I don't see why we need anything better than Newtonian physics to describe the universe."
A good 15 minutes of humiliation followed.
Windows has no users. It has hostages.
[^]Re: ...
Faudra arreter de comparer un jour des pommes et des bananes ...
De manière générale, chaque langage existe car il a le mérite de poroposer quelque chose que les autres ne proposent pas. J'adore le language C, mais ce n'est pas approprié pour faire certaines choses, même si on peut tout faire en C.
J'ai un pote qui developpe en smalltalk en ce moment, il se fait bien plaisir car c'est un bon language, mais en contre partie les performances sont pitoyables. Alors bon ... il faudra finir par admettre un jour que la nature est bourrée de compromis, et qu'il n'y a pas de language miracle qui permette de tout bien faire facilement et de façon performante, simple d'accès mais ultra-sécurisé, exploitant bien les ressources, et avec une description mixte impérative/fonctionnelle.
Soutenez le logiciel libre, en adhérant dès maintenant à l'April
[^]Re: ...
Si, si !
Lisaac. Et c'est le but (bon évidemment pour le fonctionnel par exemple, on fera jamais mieux que Caml, Lisp, etc...).
Et s'il manque des choses a ton goût, c'est ici : http://wiki.loria.fr/wiki/Sp%C3%A9cifications_compilateur
Bon j'ai fait ma prosel de la semaine, c'est bon...
Ok, je --> []
[^]Re: ...
Je surveille Lisaac de près (enfin, surtout isaac), depuis que ca traine sur DLFP. Je prendrais le temps de l'essayer cet été (et oui, ya des gens qui n'aiment pas trop aller a la plage).
So, wait and see.
Soutenez le logiciel libre, en adhérant dès maintenant à l'April
[^]Re: ...
T'as de la chance, si tout se passe bien on publie IsaacOS cette été (juste le temps de bien commenter le code, de faire une distrib propre, s'assurer que l'OS se compile bien avec la dernière version du compilo en cours d'écriture).
Mais on réfléchi depuis quelques temps, surtout à l'instigation de nicO à des fonctionnalités massivement parralèles un peu comme Erlang. Mais faut spécifier tout cela et ensuite réfléchir si c'est intégrable et comment l'intégrer...
[^]Re: ...
C'est pas pour dire, mais ça fait des années que pleins de gens pensent avoir découvert le langage idéal, et on en revient toujours au C...
Euh, au contraire, mis à part les systèmes embarqués, ou nécessitant une patate pas possible (et encore), le C a tendance à être marginalisé dans ce que j'ai vu autour de moi.
Surtout pour de la programmation serveur...
Là pareil, tout dépend. Tu peux avoir une infrastructure à partir de C (genre Apache, etc.), avec une base de code relativement petite, mais quand tu vois Apache+Tomcat, ou JBoss, les applications serveur en Java sont très utilisées (et on pourrait sans doute dire la même chose des applications C#, Perl, Ruby &co.).
Erlang a ça de génial qu'il embarque tout un tas de mécanismes qui sont fastidieux à utiliser (voire à programmer) dans un langage comme le C. Franchement, celui qui me dit que la gestion des threads en C, c'est super simple, que la gestion des accès concurrents, ça ne pose pas de problème, etc..., j'aurai du mal à le croire. Ou alors, les threads sont indépendants, et alors, pourquoi en utiliser en premier lieu ? :-)
[^]Re: ...
euh ... " Franchement, celui qui me dit que la gestion des threads en C, c'est super simple" --> ben l'api des thread posiw est pas vraiment complexe .... bon c'est sur tu geres tous les access toi même mais je dirai chiant ou long mais pas compliqué .
"Ou alors, les threads sont indépendants, et alors, pourquoi en utiliser en premier lieu ?" ben pour parallèliser le traitement ( archi multi-proc tous ca ... ) et pourquoi pas des fork a la place? ben histoire de changement de contexte plus court ...
[^]Re: ...
> ben l'api des thread posiw est pas vraiment complexe .... bon c'est
> sur tu geres tous les access toi même mais je dirai chiant ou long
> mais pas compliqué .
La gestion des threads en C/C++ est compliqué par le fait que ces deux langages ne possede aucune primitives de concurence et de gestion des threads en interne.
Si effectivement au premier abord tu peux avoir l'impression que ce n'est pas si compliqué de faire du multithread en C/C++, le fait est que dans le cas d'applications réelles (autre que toy-app) le programmeur se trouve confronté à de nombreux bugs, non reproductibles, très difficille à trouver et encore plus à éliminer.
Le gestion des threads à travers une bibliotheque est d'ailleur très critiquée. voir :
"Threads Cannot be Implemented as a Library"
http://www.hpl.hp.com/techreports/2004/HPL-2004-209.html
qui en detaille les raisons
> "Ou alors, les threads sont indépendants, et alors, pourquoi en
> utiliser en premier lieu ?" ben pour parallèliser le traitement
> ( archi multi-proc tous ca ... )
Les threads peuvent en effet etre utilisé pour accelerer certain traitement. Mais ceci n'est qu'un cas particulier de leur utilisation.
De mon point de vu, les threads permettent surtout d'offrir aux programmeurs un acces au paradigme de la programmation concurente.
L'intérêt n'est pas d'aller plus vite, c'est surtout de coder plus simplement certain type de probleme très complexe qui se pretent mieux à mode de pensée.
> et pourquoi pas des fork a la place? ben histoire de changement
> de contexte plus court ...
Sache que sous Linux processus et thread sont pour ainsi dire la meme chose (Ce n'est pas le cas sur tout les OS, et Solaris possede une gestion des threads réellement intéressante).
Ce sont dans les fait des processus kernel-land avec comme seul difference que pour les threads ces processus partage le même espace mémoire. le scheduling se fait ensuite par le kernel comme n'importe quel process et "quasiment" à la même vitesse.
Voir ainsi l'appel system clone
$ man clone =>
NAME
clone - create a child process
DESCRIPTION
clone creates a new process, just like fork(2).
...
The main use of clone is to implement threads: multiple threads
of control in a program that run concurrently in a shared
memory space.
Il me semble que fork (...) fait appel à clone dans les fait
[^]Re: ...
Sache que sous Linux processus et thread sont pour ainsi dire la meme chose
Ca n'est (et heureusement) plus le cas. Linux est passé en mode NPTL depuis un petit moment, donc on a des vrais threads sous Linux et non juste des processus à moitié forkés.
Personellement ca fait pratiquement deux ans que ma Glibc est en NPTL only (elle ne supporte plus du tout les linux threads) et ca marche très bien (sauf pour MySQL, mais c'est un autre débat).
Maintenant les threads sont des entités dépendantes du processus (ie tous les threads d'un process sont ratachés à l'ID de ce process et le kernel ne voit qu'un seul process) et en plus on a une API standard pour créer toutes sortes de threads, les mutex et les sémaphores qui vont avec.
Kha
root est un privilège, pas un droit !
[^]Re: ...
pour commencer, je peux me tromper dans ce que je dis, et je suis heureux de pouvoir discuter de ceci.
Je parlais bien cependant de la NPTL quand je disais que chaque thread etaient en fait encapsulé dans un process.
La NPTL semble surtout ensuite apporter certaine primitive de synchronisation entre les threads(process) crées.
j'ai tenu a verifier et dans WikiPedia
http://en.wikipedia.org/wiki/NPTL
(qui bien sur n'est pas parole d'evengile, mais bon) je lis :
NPTL uses a similar approach to LinuxThreads, in that the primary abstraction known by the kernel is still a process, and new threads are created with the clone() system call (called from the NPTL library). However, NPTL requires specialized kernel support to implement (for example) the contended case of synchronisation primitives which might require threads to sleep and be re-awoken. The primitive used for this is known as a futex.
NPTL is a so-called 1×1 threads library, in that threads created by the user (via the pthread_create() library function) are in 1-1 correspondence with schedulable entities in the kernel (processes, in the Linux case). This is the simplest possible threading implementation.
Maintenant je peux me meprendre sur certain point et je suis ouvert a toutes discussions.
[^]Re: ...
pour commencer, je peux me tromper dans ce que je dis, et je suis heureux de pouvoir discuter de ceci.
Apparament cependant tu en te trompais pas et c'est moi qui affabulait. Actuellement il semblerait que la NPTL soit toujours basé sur un modèle 1-on-1 (ie chaque thread utilisateur correspond un thread système, c'est à dire un processus) et non pas M-on-N comme ca avait été promis à une époque lointaine et reculée.
C'est un peu dommage pour les ordinateurs vraiment multiprocesseurs (comprendre 8 et plus) mais c'est vrai que pour le reste du monde ca ne change pas grand chose au niveau des perfs et ca allège considérablement la complexité du code.
Je pars me flageller avec des orties fraiches en penitence....
Kha
root est un privilège, pas un droit !
[^]Re: ...
Heu, c'est moi ou un modèle 1:1 est justement plus adapté à des machines massivement multi processeurs qu'un modèle M:N puisqu'il permet plus de parallélisme. Chaque thread pouvant tourner sur un processeur alors que dans le cas M:N, même s'il y a des processeurs libres, il peut y avoir des threads dans l'état exécutable en attendant qu'un de leurs frères rende la main (ou se fasse préempter).
Sinon en pratique il semblerait que les seuls OS un peu populaires qui ne font pas du 1:1 sont FreeBSD et NetBSD (sans doute aussi DragonFlyBSD ?).
http://web.mit.edu/nathanw/www/usenix/freenix-sa/freenix-sa.(...)
Au passage, j'ai écrit ça il y a quelques mois qui devrait faire une bonne introduction aux threads et processus en français pour ceux qui « débutent » : http://www.krunch.be/vrac/txt/sco-resume.pdf (oui, typographiquement c'est dégeulasse, désolé)
Free Softwares Users Group Arlon (Sud Luxembourg, Belgique)
pertinent, e adj. Approprié ; qui se rapporte exactement à ce dont il est question.
[^]Re: ...
Je croyais que c'était aussi le cas de Windows ...
[^]Re: ...
D'après « Modern Operating Systems » de Tanenbaum, les threads Windows 2000 (ça m'étonnerait que ça ait changé pour XP) c'est bien du 1:1. Ca change peut-être avec Vista.
Free Softwares Users Group Arlon (Sud Luxembourg, Belgique)
pertinent, e adj. Approprié ; qui se rapporte exactement à ce dont il est question.
[^]Re: ...
Windows c'est du 1:1, de la premiere version de NT jusqu'a Vista.
[^]Re: ...
Oui, cependant, y'a quand même la notion de Fiber (http://msdn.microsoft.com/library/default.asp?url=/library/e(...) ), si tu veux vraiment t'amuser à scheduler en userland. (et qui permettrait d'implémenter des scheduler plus exotique)
Et les priorités des threads dépendent de leur process (y'a un lien fort entre process et thread) et de leur propre priorité. Cependant, ce sont en effet bien des threads qui sont scheduler, et pas des process.
Bref, c'est pas simple ;)
[^]Re: ...
Les fibres c'est du 1:N AFAIK donc aucun parallélisme.
Free Softwares Users Group Arlon (Sud Luxembourg, Belgique)
pertinent, e adj. Approprié ; qui se rapporte exactement à ce dont il est question.
[^]Re: ...
Pas exactement, un fiber n'a pas d'affinité avec un thread donné, tu peux exécuter ton fiber (poursuivre son exécution) sur n'importe quelle thread disponible (et actif).
Les fiber, sont (était) un outil pour diminuer le nombre de context switching en permettant à un thread de profiter de son quanta complètement. (sachant qu'un context switching arrive sur un sleep, sur l'attente d'un objet de synchro ou à la fin du quota, tu peux éviter ces deux premiers cas à l'aide d'un fiber).
Cependant faut relativiser leur utilité maintenant: le context switching est relativement de moins en moins cher (les cpu deviennent de plus en plus rapide, alors que les quantas CPU alloués par thread n'ont pas diminué de la même façon), et ce qu'on veut éviter quand on cherche des perfs, c'est de perdre sa cache (ce qui coute relativement de plus en plus cher, vu que la mémoire n'évolue pas aussi vite que la fréquence du cache...)
Enfin, je parle pas de parallélisation, mais de montée en charge, il est amha, naif de croire que rendre tout parallèle permet toujours de gagner en temps d'exécution, en fait, c'est même le contraire, une fois arrivé à un CPU par thread, la question est de ne pas bloquer les thread, pas d'en rajouter plus (et comme ce n'est pas toujours possible, ne fut-ce que parce que la plupart des applications requérant de la scalability sont IO bound, faciliter la gestion des threads, ça aide...).
[^]Re: ...
Pour l'instant, DragonFly est encore en 1:N mais le passage en 1:1 est prévu (avec l'utilisation de libthread_xu pour gérer les threads utilisateurs) . Par contre il n'y a pas vraiment de date arrêtée. Je ne sais pas exactement ce qui empêche le passage en 1:1 mais c'est probablement du côté du noyau.
[^]threading 1:1 DragonFlyBSD
Je viens de vérifier. C'est bien le noyau qui n'est pas encore prêt pour le passage en 1:1.
Pour info, la roadmap écrite en octobre 2005 (en anglais) :
http://leaf.dragonflybsd.org/mailarchive/kernel/2005-10/msg0(...)
Pour l'instant les développements nécessaires à ce sujet semblent ralentis, voire arrêtés.
[^]Re: ...
Heu, c'est moi ou un modèle 1:1 est justement plus adapté à des machines massivement multi processeurs qu'un modèle M:N puisqu'il permet plus de parallélisme.
Le pire de tout c'est le 1:N , dans ce cas là grosso-modo c'est quasiment comme si les threads n'existait pas. Tout se dérouel en userland et totu est rattaché au même processus (donc au même thread kernel, donc au même CPU)
Le 1:1 permet pas mal de parallelisation, mais il a ses limites. L'immense avantage de la gestion 1-on-1 est qu'elle ne nécessite pas du tout de planificateur en userland, il suffit généralement de rajouter quelques signaux au planificateur de processus pour s'en sortir.
Le M:N est très complexe à mettre en oeuvre, il nécessite deux scheduler (un en kernelland et un en userland) et il faut en plus que ces deux planificateur soient très bien coordonés. Cependant, il est celui qui offre le plus de flexibilité : dans un modèle avec un SA (Scheduler Activation) le kernel distribue des processeurs virtuels à tous les processus qui font appels aux threads et peut mettre à jour le nombre de processeurs virtuels attribués dynamiquement. Ca permet de constament adapter les threads à la charge effective des processus. Sous certaines conditions on peut même déplacer un thread d'un processeur à l'autre. Mais bon c'ets clair que vu l'overhead impliqué au niveau système, il vaut mieux avoir du processeur disponible, sinon ca sert pas à grand chose.
Pour plus de détails : http://people.redhat.com/drepper/Scheduler.pdf
Kha
root est un privilège, pas un droit !
[^]Re: ...
> Le pire de tout c'est le 1:N , dans ce cas là grosso-modo c'est quasiment
> comme si les threads n'existait pas. Tout se dérouel en userland et totu est
> rattaché au même processus (donc au même thread kernel, donc au même CPU)
tout depend du point de vu et surtout de l'usage que l'on fait des threads.
Ainsi que je le disait precedement, les threads permettent d'offrir aux programmeurs un acces au paradigme de la programmation concurente qui peut s'averer plus adapté pour ecrire certains types de programmes.
Dans ce cas la, la gestion des threads en 1:N est bien souvent celle qui permet la gestion la plus fine pour le scheduler. Ainsi si tu considere la simulation d'un tres grand nombre d'entités et que tu a un imperatif de reactivité, ce mode est le plus adapté.
Je me pose d'ailleur une question : est il si simple de savoir si l'on gere plusieurs threads legers (géré par le langage ou user-land si on veut) en mode 1:N.
Apres tout lorsqu'on programme, le runtime du langage sur lequel on repose
peut tout a fait switcher plusieurs threads legers (si le langage integre bien sur les threads leger en interne, ce qui est loin d'être le cas de tout les langages) sur plusieurs threads kernell (process) si cela lui lui semble plus adapté à l'archi sur laquelle il repose, par exemple si le code s'execute sur du multi-core.
Il n'est en effet pas a la charge du programmeur d'un langage haut niveau de s'adresser directement à l'un ou l'autre des coeurs.
Donc au final pour arriver à la fin de cette digression alambiquée (c'est confu dans ma tete aussi) la gestion des threads par le kernel en 1:1 ne pose aucun probleme particulier, et n'empeche pas necessairement les langages qui permettent de faire de manière interne du 1:N d'un coté et de faire usage des threads kernel de l'autre, d'optenir du M:N.
Un langage generaliste moderne doit donc pouvoir offrir les moyens de programmer aisement de manière concurrente et ceci en permettant de gerer des threads user-land ET kernel-land.
Je pense au langage Haskell et plus particulierement à l'implementation GHC de celui-ci, pour laquelle une active discussion est mené pour gérer la concurrence.
[^]Re: ...
En fait, sous Linux, c'est pas que les threads sont implémentés comme de la merde (== sont lents comme des forks), c'est plutôt que les forks sont super bien foutus (== sont aussi rapides qu'une création de thread).
vala vala..
[^]Re: ...
Pendant longtemps les threads ont ete implemente comme de la m..., pas Posix, PID differents pour des threads dans le meme processus, ... faire un soft multithread qui tourne sur Linux et d'autres Unix etait un petit cauchemard a l'epoque.
J'ai pas regarde ce qui a change de ce cote depuis un petit moment, mais j'esperes que ca a ete corrige, parce que c'etait vraiment ch....
[^]Re: ...
"The problem with Threads"
http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-1.(...)
où le monsieur explique que la sémantique des threads introduit du non-déterminisme (et tout ce qui va avec dont la difficulté à débugger) dans un contexte déterministe. D'où une difficulté à résoudre des problèmes simple comme faire un design pattern observateur en Java qui soit correct dans un environnement multithreadé (code à l'appui). Il se place dans le contexte de l'embarqué mais je pense que ses remarques sur les threads sont tout à fait pertinentes.
[^]Re: ...
Oui mais est-ce qu'erlang (le sujet de la dépêche) résoud cette problématique de façon élégante contrairement à java ou est-elle par nature insoluble ?
[^]Re: ...
Oui, Erlang résout le problème de manière élégante.
Regarde le troisième lien proposé:
http://www-128.ibm.com/developerworks/java/library/j-cb04186(...)
--
Mickaël Rémond
http://www.process-one.net/
Mickaël Rémond
Process-one
[^]Re: ...
Tiens, moi aussi j'ai lu ce document il n'y pas longtemps. C'était sur LtU , accompagné de qq commentaires qui parlent aussi d'Erlang :
http://lambda-the-ultimate.org/node/1481
[^]Re: ...
Et on peut avoir un vrai bench C/Erlang ?
Ca dépend ? Qui veux-t-on comme gagnant ? Si on veut juste se rassurer sur l'inutilité à apprendre un autre langage que le C je suggère le calcul de décimales de Pi ou des suites de Fibonacci en mono processus - mono utilisateur. Le C devrait plier à peu près tout ce qui passe. Erlang va apparaitre comme lent et gourmand en mémoire.
Par contre si on s'amuse à faire un bête programe qui créé 200 serveurs intersynchronisés (comme par exemple pour un MMORPG) et que l'on connecte dessus quelques dizaines de milliers de clients on risque d'avoir 99% des programmeurs C qui vont avoir vraiment du mal. Alors que les programmeurs Erlang ayant un peu d'expérience devraient s'en sortir tous a peu près convenablement. Alors après reste la question de savoir qui entre le meilleur programmeur C et le meilleur programmeur Erlang du monde remporterait la palme. En toute honnêteté ce serait probablement le meilleur programmeur C du monde, mais le meilleur programmeur Erlang du monde aurait à coup sur un code maintenable par d'autres que le meilleur programmeur Erlang du monde.
Erlang à un très fort overhead (charge initiale), donc lui faire éxecuter des petits programmes en boucle le met forcément en position de faiblesse. Ceci dit il scale (monte en charge) très bien (très très même).
De toutes les façons, le langage Erlang est certes turing complet, mais il est destiné très prioritairement aux applications communicantes (archi point à point, client/serveur, n tiers etc.) de fait le comparer avec un langage aussi généraliste que le C n'a pas grand intéret. On pourrait éventuellement imaginer un bench d'une bibliothèque réseau ou IPC face à Erlang, mais comparer brut de décoffrage C et Erlang revent à la bonne vieille comparaison entre le couteau et la fourchette.
Kha
root est un privilège, pas un droit !
[+] [^]Re: ...
salut,
quelle drôle d'idée de comparer des choux et des poires :).
Vitesse : C gagne car proche du langage machine.
Portabilité : C gagne grâce aux différents compilateurs.
Lisibilité : Erlang gagne car il a des fonctions déjà toutes prêtes.
Si on comparait C++ et Java ? Oups, on m'appelle :).
blog
[^]Re: ...
>Vitesse : C gagne car proche du langage machine.
Sans doute.
>Portabilité : C gagne grâce aux différents compilateurs.
Oui, le C est portable, si on utilise des bibliothèques portables et qu'on ne se repose pas sur les idiosyncraties du compilateur.
Mais l'infrastructure Erlang a été portée vers de très nombreuses architectures matérielles (et des plus exotiques), plus même que la JVM si je m'en souviens correctement. Le bytecode Erlang est donc plus que raisonnablement portable lui aussi.
>Lisibilité : Erlang gagne car il a des fonctions déjà toutes prêtes.
Ouhla, ça me paraît un peu réducteur. Erlang "gagne" parce qu'il dispose certes d'un framework important (mais pas bloated), mais aussi qu'il est fonctionnel et a une syntaxe claire et concise. Troll : tu considères Java plus lisible que C++ parce qu'il a "des fonctions déjà toutes prêtes" ?
Et surtout, comme expliqué plus haut, Erlang "gagne" (j'aime pas vraiment le terme) largement pour les serveurs, parce qu'il est très facile d'écrire des programmes concurrents, distribués, clusterisables, et qui peuvent être mis à chaud.
Wr ar fbhunvgr cnf ha qrfgva sharfgr à yn cncnhgé. Nzra.
[+] [^]Re: ...
Mais c'est carrément l'équipe Erlang qui attaque ;).
Ok, Erlang c'est génial, mangez-en ;). (troll : pour les serveurs hein, sinon c'est le C ).
blog
[^]Re: ...
> Vitesse : C gagne car proche du langage machine.
Mouai. Faudrait commencer a evoluer.
Par exemple, sur le "language shootout", OCaml est extremement proche du C pur en terme de vitesse:
http://shootout.alioth.debian.org/old/benchmark.php?test=all(...)
Et pourtant, je ne crois pas que OCaml soit "proche de la machine".
De meme, IronPython, une version de python ecrite pour le CLR de C# est plus rapide que la version de python en C.
Le C se prete bien a certaine manipulations mais pour des gros programme, je suis persuade qu'un langage qui expose correctement les intentions du programmeur dans sa grammaire pourra a terme etre mieux optimise par un bon compilateur. Le C et le C++ ont ce probleme que leur grammaire est complexe, avec des manipulations qui cachent ce que veut faire le developpeur. Au final, une information est perdue, celle de l'intention du programmeur et les optimisations sont donc limitees dans la mesure de l'expressivite du langage.
Si on regarde Java ou C#, on trouve plein d'outils de refactoring, d'analyseurs de code, de programmation oriente aspect, etc etc. La richesse de ces outils vient du fait que ces langages exposent une grammaire plus facile et que les outils annexes peuvent mieux comprendre et aider le programmeur.
phil.freehackers.org
[+] [^]Re: ...
Evoluer ? Comment ça ? Depuis l'age des cavernes, c'est un fait immuable : C est los plus rapidos ;).
OCaml le joujou de recherche plus rapide ? Ca vient surtout du compilo et le langage n'est pas complexe ;).
Pourquoi Ironpython est plus lent en C qu'en C# ? Mal optimisé ?
Le C peut aussi bien faire de gros programmes, faut créer les bibliothèques et bien modulariser et bien savoir coder aussi ;).
La grammaire du C est complexe ? :o Pourquoi ?
Des manipulations qui cachent ce que veut faire le developpeur ? C'est quoi ?
La suite n'est pas claire non plus... Tu peux donner des exemples ?
Les outils n'ont rien à voir avec la simplicité du langage...
Et les outils ne font pas obligatoirement faire de meilleur code ;).
blog
[^]Re: ...
OCaml le joujou de recherche plus rapide ? Ca vient surtout du compilo et le langage n'est pas complexe ;).
ouatte ?? c'est vrai que l'inférence de types, les types paramétriques, le garbage collector hybride, l'héritage multiple, le pattern matching, tout ça c'est nettement plus simple qu'un bête compilateur C (qui je le rappelle ne fait rien de compliqué à part l'optimisation puisque c'est un traducteur quasi litéral vers le code assembleur).
[^]Re: ...
<<
Pourquoi Ironpython est plus lent en C qu'en C# ? Mal optimisé ?
>>
Une partie du gain vient du fait que le CLR peut detecter des organisations de code qu'il peut optimiser a la volee au moment de l'execution, ce que ne peut pas du tout faire le C.
Guido Van Rossum et tous les gens qui bossent sur python dpeuis 10 ans ne sont pas des machots donc je doute que le code C de python soit "mal optimise".
<<
Le C peut aussi bien faire de gros programmes, faut créer les bibliothèques et bien modulariser et bien savoir coder aussi
>>
Donc en fait, ta defense du C est une attaque des programmeurs. "Vous ne savez pas coder, sinon, ca marcherait mieux". C'est plutot minable comme argumentaire.
Sur des tres gros programmes en C, tu es souvent conduit a utiliser par exemple des pointeurs en (void *) car tu dois stocker plusieurs types de donnees dans un pointeur. L'absence de notion de dictionnaire, d'heritage, les notions de tableaux tres limitees, l'absence de notion d'interface font que beaucoup de paradigmes indispensables de programmation sont fait completement a l'insu du compilateur, qui du coup a un champ tres limite pour comprendre les intentions du programmeur et optimiser le code en fonction.
L'utilisation d'un (void *) est le plus flagrant mais tous les parametres jouent ensemble. Un dictionnaire a 3 elements est plus facile a optimiser avec une recherche lineaire, un dictionnaire avec 500 elements est plus facile a optimser avec une table de hashage. C'est une decision que le compilateur pourait prendre plutot que le programmeur.
L'absence de ramasse-miette fait aussi que les programmes en C demandent plus de travail au programmeur. Le ramassage des miettes (== desalllocation des ressources inutilisees) est aussi quelque chose que le compilateur peut faire mieux que le programmeur si on lui passe les bonnes information.
<<
La grammaire du C est complexe ? :o Pourquoi ?
>>
Au hasard et en survol :
- pas de distinction entre un tableau et un pointeur
- un melange entre la declaration de type et le nom de la variable :
<type de la variable> <nom de la variable> <info supplementaire facultative sur le type de la varible>
int a[30];
- le pre-processeur qui peut rendre la grammaire du texte decrivant le code completement irreguliere.
- l'absence de taille predefinies pour les types de bases.
<<
Des manipulations qui cachent ce que veut faire le developpeur ? C'est quoi ?
>>
Pour les plus simples :
- passage d'arguments par void *
- passage de tableaux par pointeur, on perd toute l'information sur la notion de tableau (de toute facon, le C n'est stocke aucune, mais c'est bien la une de ses limitations)
- bidouilles a coup de struct et de pointeurs de fonctions pour faire des interfaces
- pas de liste, pas de dictionnaire donc plein d'optimisations a la portee du compilateur qui sont perdues
<<
Et les outils ne font pas obligatoirement faire de meilleur code ;).
>>
T'as vraiment des arguments a 3 francs. T'as deja reflechi au sujet avant d'ecrire un truc pareil ?
Bien sur que la qualite des outils permettent d'ecrire du code de meilleur qualite et de le faire evoluer de meilleure facon.
Un outil de refactoring en java te permet de faire facilement evoluer ton code par exemple. La meme operation en C oblige a faire un gros grep dans les sources et a faire de modifs a la main, super penible donc rarement fait dans la pratique, donc code qui devient vite immaintenable.
Des que tu fais du C++, tu t'apercois que gdb n'as acces qu'a une partie limitee des objets, et que donc le debuggage est super penible, tu en reviens au printf, ce qui est long et penible.
Des outils comme la programmation oriente aspect permettent d'explorer des nouveaux concepts de programmation, plus en rapport avec les besoins de certains projets.
En java, il est possible de debugger a distance un programme java qui s'execute. Par exemple, je peux debugger une javacard depuis mon PC, poser des points d'arrets, inspecter les variables, etc. C'est difficile et lourd a faire avec du code embarque en C, tu es souvent oblige de developper un simulateur complet de ta plate-forme cible.
Des outils d'analyses de code peuvent te permettre de mieux comprendre un code existant. Ces outils sont limites dans leur comprehension du code C a cause des limitations de la grammaire du C (je commence a me repeter la).
<<
Les outils n'ont rien à voir avec la simplicité du langage...
>>
Je n'ai pas parle de simplicite mais d'expressivite. Si ton langage transcrit bien ce que tu veux faire, les outils peuvent t'aider beaucoup. Si ce n'est pas le cas, les outils ne peuvent rien pour toi.
Le cas d'erlang est frappant. Je ne connais pas le langage, mais je suis persuade que si tu informes le compilateur des morceaux de code qui doivent s'executer en parallele ou non, tu obtiens un truc bien plus propre que avec des mutex dans tous les sens, des sections critiques et des forks a tout va. Dans un cas, le compilateur peut t'aider et distributer pour toi l'execution du code sur plusieurs threads/processeurs/machines, dans l'autre, c'est toi pauvre programmeur, qui va essayer de le faire. Tu vas passer ton temps a re-inventer la roue.
phil.freehackers.org
[^]IronPython
De meme, IronPython, une version de python ecrite pour le CLR de C# est plus rapide que la version de python en C.
C'est une comparaison fallacieuse, car tu compares deux machines virtuelles différentes, et non pas deux implémentations différentes de la même machine virtuelle.
Les machines virtuelles écrites pour .Net (que ce soit celle de Microsoft ou de Mono) ont été beaucoup plus optimisées que celle de CPython. D'ailleurs, cette dernière ne fait pas de JIT (il y a Psyco qui est un projet séparé développé par une seule personne...).
[^]Re: IronPython
Le langage Python fourni à travers sa grammaire une sémantique au programmeur : c'est l'ensemble des spécifications de "fonctionnement" qui constitue la machine virtuelle. La notion de machine virtuelle est une notion abstraite qui représente uniquement le comportement et les services fournit à l'exécution. En ce sens IronPython fournit une implémentation de la même machine virtuelle que celle de Python original : l'interface fournit au programmeur et le comportement à l'exécution sont les mêmes (en tout cas c'est l'objectif), on compare donc bien 2 machines virtuelles, et il n'y a rien de fallacieux là dedans.
Tu dis que .NET et Mono sont beaucoup plus optimisés que celles de CPython... C'est un petit peu le but de la comparaison :) De plus les 2 premiers n'ont pas du tout était conçu pour des langages dynamiques contrairement à CPython... IronPython sert d'ailleur de "cobaye" à MS pour améliorer sa VM en matière de langages dynamiques.
En fait sa comparaison est foireuse mais à pour une toute autre raison : il veut démontrer que le C n'est pas plus "rapide" que le C# en prenant pour exemple IronPython... Ce qu'il oublie c'est que .NET/Mono ne sont PAS écrits en C# mais en C :)
Bref, les seuls conclusions que l'on peut tirer ne sont pas sur le langage en soit mais sur les détails d'implémentation de la même VM : JIT ou non, VM dédiée langages dynamique ou pas, etc.
MonoFrance
[^]Re: ...
Vitesse : C gagne car proche du langage machine.
Houlà, de moisn en moins vrai çà. Les processeurs commencent à être suffisament costaud poru que l'on puisse s'éloigner assez fortement du langage machine sans que celà pose de problèmes de perfs. Encore plus fort : sur une machine raisonnablement chargé (ie 50% de load CPU moyen) une machine virtuelle peu battre un programme natif. Par exemple toujours sur les codes clients/serveurs une fois la connexio établie il y a pleins de tests, de branchements et de boucles qui deviennent innutiles. Lors d'une éxecution dans une machine virtuelle on peut faire sauter tous ces ralentissements inutiles (Technique d'optimisation post bytecode par linéarisation) et le gain de performance est loin d'être négligeable. A titre d'éxemple le programme Dynamo qui est une machine virtuelle proche des processeurs alpha (i.e : un alpha virtuel) permet un gain jusqu'à 15% de performance sur des programmes nativement compilés pour alpha quand on l'execute sur un alpha.
Pour faire plus court, certains programmes alpha tournent 15% plus lentement quand ils sont executés directement sur un processeur alpha que quand ils sont executés sur une Dynamo sur un processeur alpha.
Portabilité : C gagne grâce aux différents compilateurs.
Pas tout à fait vrai non plus, tout d'abord parceque même si il y a pas mal de compilatuers, très peu sont C Ansi strict. Ensuite en C l'OS influence souvent beaucoup la programmation (Il suffit de comparer du code win32 avec du code GlibC pour comprendre). De toute les façons si le framework est bien fichu, il est quasiment impossible de battre en portabilité une machine virtuelle qui possède la triple compatibilité API/ABI/Source .
Lisibilité : Erlang gagne car il a des fonctions déjà toutes prêtes.
On peut cependant écrire des choses relativement illisibles en Erlang et utiliser des bibliothèques qui rendent le code très lisible en C. Après c'ets plus une question de méthode et de propreté du codeur.
Kha
root est un privilège, pas un droit !
[+] [^]Re: ...
Vitesse : comment je fais pour compiler et exécuter du code en langages de oufs sur de vieilles machines ? Non ça battra pas le C.
Portabilité :Si t'utilises gcc, ben il est C ANSI strict et il marche sur tous les Unix, et plein de processeurs non ?
L'OS peut influer ? Ca dépend si tu veux des fenêtres par ex. ;).
La machine virtuelle est une émulation, donc c'est moins rapide, et portabilité, ça dépend si elle existe ou non.
Lisibilité : ça dépend du codeur aussi mais avoir des bibli, ça aide.
blog
[^]Re: ...
comment je fais pour compiler et exécuter du code en langages de oufs sur de vieilles machines
Tu attends dix ans. Les vieilles machines auront fait de gros progrès d'ici là.
Si t'utilises gcc, ben il est C ANSI strict et il marche sur tous les Unix, et plein de processeurs non ?
Non. a) Il n'est pas C ANSI strict, il peut se comporter comme C ANSI strict si on lui demande. Sinon il fait aussi du C ISO et si on ignore les warnings dans un cas comme dans l'autre on peut glisser assez loin de la norme.
b) Ce qui marche (plus ou moins bien) sur un paquet d'Unix c'est le trio GCC+Autotools et make+GLibc/Libc . Il existe entre les différents composants un degré de compatibilité assez élevé qui fait que les applications sont raisonnablement portables d'un systeme à l'autre, cependant on est loin de pouvoir prendre un programme Linux x86 pour le compiler sur uen station HP-UX.
La machine virtuelle est une émulation, donc c'est moins rapide
CF mon exemple de la Dynamo, parfois c'est plus rapide car plus flexible et donc optimisable pendant l'éxecution du code.
Kha
root est un privilège, pas un droit !
[^]Re: ...
Tu confonds 2 choses: le fait de pouvoir compiler/executer du code dans un langage sur différentes plateformes et le fait de pouvoir réaliser des application portables (compatibilité API).
Si le C était si portable que ça pour ecrire des application ne searit-ce que de bas niveau, tu peux m'expliquer pourquoi la fondation apache a eu besoin de créer une librairies dédiée et réutilsée par Subversion. On est loin des fenêtres Hein ;) ; ) ;) ;) .....
http://apr.apache.org/
Par experience j'ai participé il y a quelques années au portage d'une appli depuis OS/2 vers Windows NT, et bien bizarrement ce qui nous a couté le plus cher etait le portage des apis de plus bas niveau par exemple quand tu découvres que NT ne supporte pas la mémoire partagée et que tu dois la simuler, que les mutex ont une conception complètement différentes, ....
[^]Re: ...
Il s'agit d'un cas particulier... Ces optimisations ne sont pas applicables par les compilateurs C ?
Enfin, plus généralement, plus il y a de couches présentes à l'exécution , plus le temps d'exécution tend à s'allonger, non ? Si on ne tient pas compte de facteurs comme l'optimisation meilleure d'une machine/d'un compilateur (puisque les techniques d'optimisation pourrait être réutilisée par d'autres compilateurs) mais uniquement de la structure du code exécutable et de la méthode d'exécution (machine virtuelle ou réelle)...
Evidemment, plus les processeurs augmentent en puissance, plus la différence s'amenuise. A strictement parler, cependant, il ne s'agit pas de la question.
Ce n'est pas sur linux...
[^]Re: ...
Enfin, plus généralement, plus il y a de couches présentes à l'exécution , plus le temps d'exécution tend à s'allonger, non ?
Il tend à s'allonger si on ne fait rien oui. Mais par contre plus on a de couches disponibles plus on va pouvoir faire d'optimisations post-compilation.
En C on ne peut pas faire d'optimisation à posteriori, une fois que le porgramme est lancé, sa partie executable (ie par la partie données) ne bouge pas sauf cas super particuliers et très casse gueule tel que l'assembleur automodifiant ou le self linking dynamique.
A l'inverse les programmes tournant sur une machine virtuelle peuvent s'optimiser tout seul en permanence. Par exemple lorsqu'il passent dans une fonction ils peuvent créer une table de hashage des paramêtres passés et de leur résultats et ainsi répondre instantanément si la fonction est appelé deux fois avec les mêmes paramêtres. De même ils peuvent faire sauter un paquet de tests et donc linéariser le code. Pareillement la machine virtuelle peut conserver une empreinte de la config système et ainsi court-circuiter un paquet d'appels systèmes en n'executant pas le bytecode et en plaçant la réponse directement au bon endroit etc.
En d'autres termes on passe d'un mode de calcul de branchement, éventuellement de prédiction de branchement à un mode de branchement direct.
A l'heure actuelle ces optimisations post-execution ne sont pas encore très rentables par rapport à la complexité qu'elles induisent dans la machine virtuelle, mais elles le deviennent. Sur des protocoles de communications complexes il est certain que les machines virtuelles finiront par battre à plate couture les programmes compilés traditionnels gràce a des meccanisme de prise d'empreinte mémoire et système qui leur permettront d'éviter la grosse majorité des tests.
Kha
root est un privilège, pas un droit !
[^]Re: ...
Ah désolé, je n'avais pas lu (ou compris) l'expression "post-bytecode". Il s'agit d'une optimisation par mémoire cache. Merci pour l'éclaircissement.
La différence tient donc du fait que la machine virtuelle, de nature logique, est de conception plus dynamique - donc plus facile et plus rapide - à gérer (nouvelle version d'une machine virtuelle -> nouveau paquet, nouvelle version d'une machine réelle -> nouveau modèle).
Sinon, ces optimisations post-génération de code exécutables sont quand même applicables aux machines physiques ?
Ce n'est pas sur linux...
[^]Re: ...
Sinon, ces optimisations post-génération de code exécutables sont quand même applicables aux machines physiques ?
Soit tu met des primitives dans le processeur et j'ose pas imaginer les conséquences...
Soit tu te débrouilles pour que le compilateur intègre les techniques que Kha citait plus haut. Et là ça devient assez chaud. Ca n'est possible à mon avis qu'avec :
- Un compilateur utilisant massivement une analyse de flot
- Un compilateur qui dispose de bonnes informations, à priori sur les statistiques d'utilisation du code (ie. distribution des valeurs les plus courantes en entrée des fonctions).
De là, soit tu t'amuses à compiler ton programme, à lui balancer une batterie de tests - en espérant qu'ils soient représentatifs - et à recompiler celui-ci en connaissance de cause, ou soit tu lui colle une sémantique du type contrat, définition d'intervals/ensemble afin d'avoir de bonnes infos sur le comportement de ton code.
Dans tous les cas c'est problématique, et faut bien analyser
- Quels appels extérieurs cela implique pour optimiser leur appel (table de hashage, etc...) et le cas échant, il faut que l'OS soit optimisé pour ça
- Les problèmes de mise à jour des données (table de hashage sur appels de fonction).
Dans le compilateur, il faudrait que l'analyse de flot analyse les sous graphes potentiellement très consommateurs en calculant leur complexité ainsi que les possibilités de "distributions" des paramètres dans l'intervalle possible (typiquement , on peut déduire, dans certains cas, par un moteur logique, que le param appliqué à la fonction f, dans le contexte se trouvera dans l'interval [20;100]).
Avec ça, le compilateur peut poser un système de table de hashage dessus, voire découper le code de la méthode en petit bout et la spécialiser aux seuls paramètres qui change.
Merci pour l'idée Kha, ça serait sympa à intégrer au compilo...
[^]Re: ...
<< Sinon, ces optimisations post-génération de code exécutables sont quand même applicables aux machines physiques ? >>
C'est plus ou moins ce qu'a fait transmeta avec son code morphing. Au final, c'etait beaucoup plus lent qu'un processeur pur.
<<
- Un compilateur utilisant massivement une analyse de flot
- Un compilateur qui dispose de bonnes informations, à priori sur les statistiques d'utilisation du code (ie. distribution des valeurs les plus courantes en entrée des fonctions).
>>
Et on en revient a la necessite d'avoir une grammaire du langage de programmation qui soit suffisamment expressive. Sinon, ces optimisations sont tres difficiles a mettre en oeuvre.
C'est bien pour cela que le JIT a attendu des langages comme Java ou C# pour devenir populaire.
<<
Dans le compilateur, il faudrait que l'analyse de flot analyse les sous graphes potentiellement très consommateurs en calculant leur complexité ainsi que les possibilités de "distributions" des paramètres dans l'intervalle possible (typiquement , on peut déduire, dans certains cas, par un moteur logique, que le param appliqué à la fonction f, dans le contexte se trouvera dans l'interval [20;100]).
>>
C'est tres proche de ce que fait le compilateur OCaml. C'est d'ailleurs ce qui explique malgre un langage "loin de la machine", il arrive a de tres bonne perfs : il y a une analyse de code tres poussee derriere qui va bien chercher les optimisations.
Cependant, l'analyse statique restera toujours limitee. Le comportement d'un programme depend de son code et de ses parametres en entree. Une optimisation statique a la compilation ne peut optimiser que le code d'un point de vue general. Elle ne peut pas connaitre quelle fonction est appelee plus souvent dans la pratique. C'est la que les optimisations JIT interviennent. Elles regardent le code s'executer et peuvent trouver les fonctions qui sont reellement utilisees en permanence.
Le C etant compile en assembleur avant d'etre execute, toute l'information sur la notion de fonction et de variable est perdue. Meme si cette information perdurait, a terme, la grammaire du C est trop peu expressive a mon sens pour permettre des optimisations de longue haleine (pas de notion d'interface, pas de notion de dictionnaire, utilisation de pointeurs pour gerer des tableaux, utilisation de pointeurs sans types, etc).
Donc plus ca va, plus le C va etre a la rue parce qu'il ne peut guere evoluer. D'un autre cote, cette stabilite est aussi ce qui a fait son succes.
phil.freehackers.org
[^]Re: ...
Et on en revient a la necessite d'avoir une grammaire du langage de programmation qui soit suffisamment expressive. Sinon, ces optimisations sont tres difficiles a mettre en oeuvre.
C'est bien pour cela que le JIT a attendu des langages comme Java ou C# pour devenir populaire.
On a surtout besoin de grammaires expressives.
Dans le langage auquel je pensais (toujours le même), Lisaac, la conditionnel, les briques de bases pour les boucles n'existent pas. Le compilateur ne connait que 7 primitives (-,*,/,and, or, =, >). Toute la lib est faîte avec ça.
Le if est une résolution dynamique sur les objets true et false héritant de booléan. Le compilateur l'optimise pour retomber sur un if comme en C. Ce qui fait que toutes les structures de ce type n'importe où dans le code sont optimisées. De même pour les récursives etc...
Plus ta grammaire est minimaliste, plus le compilateur se concentre sur la sémantique du code, pare que tu retombes toujours dessus quand tu fait l'analyse sémantique dans le compilateur (le micro langage interne).
Et c'est là que les optimisations sont possibles.
Le nombre de primitives dans Java et C# sont énormes, (http://isaacos.loria.fr/li_simplicity.html ), par contre le langage de la machine virtuelle est sufisament minimaliste et expressif pour que les optims soient faites dessus.
Cependant, l'analyse statique restera toujours limitee. Le comportement d'un programme depend de son code et de ses parametres en entree. Une optimisation statique a la compilation ne peut optimiser que le code d'un point de vue general. Elle ne peut pas connaitre quelle fonction est appelee plus souvent dans la pratique. C'est la que les optimisations JIT interviennent. Elles regardent le code s'executer et peuvent trouver les fonctions qui sont reellement utilisees en permanence.
Le C etant compile en assembleur avant d'etre execute, toute l'information sur la notion de fonction et de variable est perdue. Meme si cette information perdurait, a terme, la grammaire du C est trop peu expressive a mon sens pour permettre des optimisations de longue haleine (pas de notion d'interface, pas de notion de dictionnaire, utilisation de pointeurs pour gerer des tableaux, utilisation de pointeurs sans types, etc).
Donc plus ca va, plus le C va etre a la rue parce qu'il ne peut guere evoluer. D'un autre cote, cette stabilite est aussi ce qui a fait son succes.
Il y a C et C : il y a C écrit par un humain et C généré par un compilateur.
Le C écrit par un être humain exprime de la sémantique humaine : c'est à dire que le code est proche d'une représentation humaine du programme et moins un représentation adaptée à la machine.
Il est par exemple quasiment impensable qu'on s'amuse à faire un gros malloc au début et gérer les pointeurs pour faire en sorte que la mémoire cache soit utilisée au mieux. Ca devient vite ingérable. Par contre un compilateur peut le faire.
De même, souvent, tu vas utiliser des chaînes pour représenter une structure sémantique préfixée, alors que des nombres peuvent le faire, car c'est bijectif. C'est un peu ce qu'on fait dans les bases de données relationnelles.
Il est vrai qu'en l'état actuel des choses, on devrait réfléchir non à la machine virtuelle, mais à une espèce de programme possédant des informations sur son code et capable dans certains cas de générer son propre code. Mais il faut faire très attention : là où la machine virtuelle virtualise tout, il faudrait un système qui permette d'utiliser des optimisations faites par les VM seulement là et quand c'est utile.
C'est en tout cas une piste intéressante, mais le problème est qu'elle impose de connaître ton assembleur cible ou d'embarquer une part du compilateur (le back end de GCC par exemple)...
[^]Re: ...
C'est comme le code C généré par Lex et Yacc (Flex et bison). Je ne suis jamais parvenu très loin dans la lecture du code. Pourtant il fonctionne sacrément bien !
[^]Transmeta
C'est plus ou moins ce qu'a fait transmeta avec son code morphing. Au final, c'etait beaucoup plus lent qu'un processeur pur.
Non, ça n'a rien à voir avec la question posée.
Pour savoir si le "code morphing" de Transmeta était responsable d'une perte de performance, il aurait fallu comparer pour le même code C :
1) la version compilée pour x86 et exécutée via le code morphing
2) la version compilée en natif pour le processeur transmeta (donc exécutée directement)
Comme Transmeta ne dévoilait pas le jeu d'instructions de son processeur et ne fournissait pas de compilateur permettant de l'attaquer directement, personne n'a la réponse (à part peut-être Transmeta eux-mêmes).
[^]Re: ...
Cet exemple précis me semble assez mal choisi. La plupart des langages de programmation n'imposent pas que la valeur de retour d'une fonction ne dépende que de ses arguments (même parmi les langages dits fonctionnels). Et quand c'est le cas, GCC permet ce genre d'optimisation aussi (attributs pure et const).Par ailleurs, qu'est-ce que tu entends par "self linking dynamique" ? Google m'aide pas beaucoup.
Free Softwares Users Group Arlon (Sud Luxembourg, Belgique)
pertinent, e adj. Approprié ; qui se rapporte exactement à ce dont il est question.
[^]Re: ...
Cet exemple précis me semble assez mal choisi. La plupart des langages de programmation n'imposent pas que la valeur de retour d'une fonction ne dépende que de ses arguments (même parmi les langages dits fonctionnels). Et quand c'est le cas, GCC permet ce genre d'optimisation aussi (attributs pure et const).
je faisais allusion aux techniques comem le fragment cache de la Dynamo. Mais c'est vrai que j'aurais du dire "Si le contexte d'exécution de focntion se représente alors ..." mais c'est vraiment très pédant, et pas forcément compréhensible en plus vu le double sens du mot contexte d'éxecution dans une discussion sur les threads (contexte au sens emplacement d'éxecution du thread et contexe au sens empreinte données+pile d'execution)
Par ailleurs, qu'est-ce que tu entends par "self linking dynamique" ? Google m'aide pas beaucoup.
C'est une des techniques les plus gore qui soit avec les bibliothèques dynamique. Il s'agit en fait de réussir à forcer une bibliothèque à se charger elle même puis à utiliser tout un tas d'effet de bord pour modifier le comportement de certaines fonctions de façon à ce que lorsque la même bibliothèque sera appelé par un autre programme, celui ci aura le comportement modifié et non le comportement initial.
Ce genre de techniques étaient utilisées de façon très light pour faire passer des message entre les processus via la biliothèque (oui ca a été possible, sous windows notamment) mais maintenant c'est fini. Ceci étant il resterait encore de très "jolies" choses à faire avec des virtual, des callback et en s'appuyant un peu sur les méccanismes du kernel.
Je n'ai pas d'exemple de ce que l'on peut faire sur un OS moderne...
Kha
root est un privilège, pas un droit !
[^]Re: ...
>Dynamo qui est une machine virtuelle proche des processeurs alpha
Non, des PA-RISC si je me souviens bien.
Et pour ce qui est du gain de performances, je me suis toujours demandé s'il serait si bon si on comparait avec du code optimisé "par profil" (on execute une fois le code qui génère un profil d'execution puis on recompile le code de nouveau en exploitant le profil pour amméliorer les perf).
[^]Re: ...
Et pour ce qui est du gain de performances, je me suis toujours demandé s'il serait si bon si on comparait avec du code optimisé "par profil" (on execute une fois le code qui génère un profil d'execution puis on recompile le code de nouveau en exploitant le profil pour amméliorer les perf).
En théorie si le profil d'execution est bien ciblé alors le code compilé repasse devant la dynamo. Cependant la Dynamo restera toujours plus performante sur les appels de fonctions déjà dans son "cache fragment". En francais : même si un a un profil d'execution très bien ciblé, le programme sera quand même obligé de faire et refaire certains tests dont le résultat peut changer, alors que la dynamo peut determiner que le résultat sera identique sans faire les calculs simpelment en comparant les contextes d'éxecution (ce qui est impossible à faire en dehors de l'exécution).
Un fouillant un poil j'ai retrouvé le doc d'origine : http://www.cs.utexas.edu/users/lin/cs380c/dynamo.pdf effectivement c'est bien sur du matériel HP que la dynamo a été implémentée en premier.
Kha
root est un privilège, pas un droit !
[^]Re: ...
>Erlang scale (monte en charge) très bien (très très même).
Oui, euh c'est quand meme la *premiere version* qui supporte le multi-CPU..
J'ai peut-être trop pris l'habitude de Sun et de leurs octoprocesseurs, mais quand on me dit 'tiens la montée en charge' et restreint au mono-CPU (si je comprends bien c'était le cas avant en mode 'natif'), je trouve ça un peu curieux.
Oui, je sais Erlang supporte plein de thread légés, mais bon si tes threads font quelque-chose, tu te retrouve facilement avec une machine a genoux..
[^]Re: ...
AMHA ici "montée en charge" c'est aussi (et surtout) l'exécution du code sur un cluster de machines. Y a un exemple assez parlant de l'utilisation des forces d'Erlang dans le jeu vidéo ici http://www.devmaster.net/articles/mmo-scalable-server/
Wr ar fbhunvgr cnf ha qrfgva sharfgr à yn cncnhgé. Nzra.
[^]Re: ...
Oui, euh c'est quand meme la *premiere version* qui supporte le multi-CPU..
Oui et non, C'est la première version ou chaque machine Erlang peut s'appuyer nativement sur plusieurs CPU sans efforts de la part du programmeur. Il a toujorus été extrèmement facile de faire tourner un programme Erlang sur plusieurs CPU voir sur plusieurs machines distinctes en mettant les différents process communicants sur différentes machines. Au final il était tout à fait possible de tirer parti de l'architecture complète (mais il est vrai que celà demandait une certainne finesse programmatique).
Kha
root est un privilège, pas un droit !
[^]Re: ...
Tu as tronqué mon commentaire, je disais supporte le multi-CPU en 'mode natif', c'est à dire sans différence entre mono et multi-CPU.
Je comprends bien qu'avant en utilisant des interfaces differentes on pouvait utiliser aussi plusieurs CPU.
[^]Comment casser le mythe de rapidité de Fibonacci :-)
Les micro-benchmark, c'est le design pattern TrollFactory
Langage C, gcc -O3
Java
Interprétation naïve génératrice de Troll : Java est plus rapide que C
En fait, en faisant un programme en C plus sioux qui stocke les résultats intermédiaires dans une pile on arrive a des perfs équivalentes ou meilleures (j'ai la flemme de faire le prog, mais j'ai déjà essayé), de même le programme est écrit sous forme récursive, mais
Langage C linéaire, gcc -O3
Java Linéaire
Finallement, on retient :
- Il faut toujours choisir l'algorithme le moins naïf, si ce n'est pas couteux pour la conception du programme (shell sort contre bubble sort par ex pour 2 tri sans appels de piles)
- Il faut choisir le langage qui offre le meilleur compromis paresse du programmeur/rapidité d'éxecution.
Franchement, je ne connais pas Erlang, mais pour faire des agents distribués concurrents, je pense que j'aurais un résultat concret et plus fiable plus rapidement en apprenant Erlang et sa méthode de pensée, que de le coder en pur C.
Et puis ces discours étaient les mêmes dans les années 90 entre l'asm et le C sur 68k/80x86 :-))) et le C a gagné, cas son niveau d'abstraction ;-) permet d'être plus productif que de l'asm pur.
<µTroll>
Vive l'ASM et les démo framerate 60fps sur amiga et les démos ST sont pourries :-)))) (je dis ça par nostalgie, tout le monde est mort maintenant !)
</µTroll>
[^]Re: Comment casser le mythe de rapidité de Fibonacci :-)
Tiens, pour s'amuser, en Lisp :
(defun fib (n) (if (<= n 1) 1 (+ (fib (- n 1)) (fib (- n 2))))) (defun memo (fn) (let ((table (make-hash-table))) #'(lambda (x) (multiple-value-bind (val found-p) (gethash x table) (if found-p val (setf (gethash x table) (funcall fn x))))))) (defun memoize (fn-name) (setf (symbol-function fn-name) (memo (symbol-function fn-name))))CL-USER> (memoize 'fib) #<CLOSURE (LAMBDA (X)) {A748FC5}> CL-USER> (time (fib 1000)) Evaluation took: 0.002 seconds of real time 0.001999 seconds of user run time 0.0 seconds of system run time 0 page faults and 135,064 bytes consed. 7033036771142281582183525487718... CL-USER> (time (fib 1000)) ; 2eme appel -> instantané Evaluation took: 0.0 seconds of real time 0.0 seconds of user run time 0.0 seconds of system run time 0 page faults and 0 bytes consed. 7033036771142281582183525487718...Comme quoi le choix de l'algorithme est parfois (beaucoup) plus important que le langage. /me range sont PAIP, enfonce des portes ouvertes et --> [ ][^]Re: Comment casser le mythe de rapidité de Fibonacci :-)
C'est exactement la méthode de "sioux" que j'ai eu la flemme de poster ici, tu stocke les résultats des appels intermédiaires dans une hash table, ce qui réduit le nombre d'appel récusifs de ~2^n à quasiment ~2*n
Le problème, c'est que ce genre d'optimisation est envisageable dans une librairie système, ou un programme de calcul lourd, mais dans la vie de tous les jours au boulot, tu programmes de manière naïve (il faut maintenir le code après, et les optimisations rende le déroulement du programme moins lisible).
D'autant plus que la meilleure optimisation dans ce cas là est de transformer l'appel récursif en boucle -> gain de vitesse ET de mémoire.
Alors que ton exemple permet de gagner en vitesse, mais au détriment de la mémoire (et encore ça se discute, moins de pile à gérer)
Le principe de la table de hash pour stocker les résultats intermédiaires d'appels récursifs est quand même une trés bonne solution en général.
[^]Re: Comment casser le mythe de rapidité de Fibonacci :-)
Oui, tout à fait : c'est joli mais ça ne sert pas tout les jours :)
Par contre, je pense que ça peut servir de savoir qu'on a ce genre d'outil à portée de main sans rien changer au code de base (enfin, en Lisp en tout cas et à condition qu'il soit purement fonctionnel).
Sinon, du point de vue mémoire, entre stocker 1000 entiers dans une hash table et refaire un très grand nombre de fois le même calcul, le choix est vite fait à mon avis.
[^]Re: Comment casser le mythe de rapidité de Fibonacci :-)
Ce qui est fou, c'est qu'apparement l'interpreteur LISP a déjà compris lors du premier appel que c'est un appel "tail recursive" au vu de tes temps d'execution. Si c'est le cas et sans directives, je suis vraiment épaté.
Je ne pense pas a priori dans ce cas précis que ta fonction memoize apporte un énorme gain, je pense même que normalement, en faisant 2 appels naïf, le deuxième devrait être "immédiat" sans le memoize.
Je serais interessé d'avoir les temps sans passer par la hash table pour confirmer cette hypothése.
Dommage que je ne digére vraiment pas la syntaxe lisp (et ce ne sont pas les parenthéses qui me dérange le plus) et l'ordre prefixe.
En fait ça me fait penser à une démo de math, sauf qu'il n'y a pas de symboles graphiques (Sigma, PI, QuelqueSoit, barre d'intégrale, etc...) pour faire des points d'ACCROCHE à l'oeil et l'ordre infixe.
< troll>
Et ceux qui me dise que la polonaise inversé, c'est le top, pourquoi l'écriture mathématique est infixe et n'est pas en polonaise inversée, hein, si conceptuellement c'était mieux pour réflechir.
C'est uniquement une facilité pour la conception des programmes de parsing, le cerveau humain ne pense pas polonaise inversée, bien qu'avec l'habitude, on se dit que c'est aussi simple (c'est juste que le cerveau fait la transformation infixe->postfixe de manière plus mécanique avec l'usage et que sur les vielles calculatrices SANS mémoire, c'est plus pratique pour évaluer une expression, au passage ça évite l'usage des parenthèse, mais LISP a raté le coche de ce côté là :-)))))
< /troll>
C'est ce que je disais, ça se discute :-)
Si au lieu d'un entier, c'est tout une structure à stocker, la taille de la pile qu'il faudra peut être augmenter avant l'execution du programme, etc...
A chaque cas sa solution, et je crois que c'est un peu l'esprit qui se dégage sur cette news.
[^]Re: Comment casser le mythe de rapidité de Fibonacci :-)
En fait, tu commences par calculer fib(999), puis pour calculer fib(999) tu calcules fib(998), etc, etc -> tu ne descends qu'un fois pour calculer chaque valeur de fib jusqu'à 1 et ensuite tout ce que tu calcules est déjà stocké dans la table de hachage => gain de temps là où normalement tu devrais calculer chaque valeur à chaque fois en remontant.
Sinon, niveau optimisation, je n'ai rien rajouté (juste compilé chaque fonction).
Par contre, sans la mémoization, fib(44) met environ 80 secondes sur ma machine avec la version recursive de base (je n'ai pas encore eu le temps de tester la version avec une boucle) et j'ai arrété fib(1000) ;-)
Pour la notation infix, j'en ai déjà parlé ici, mais tu as des macros qui te permettent de faire tes calculs dans cette notation, et c'est le compilateur qui se charge de les transformer en notation prefix avec de les évaluer.
http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/l(...)
Oui, je crois que ça resume bien la situation.
[^]Re: Comment casser le mythe de rapidité de Fibonacci :-)
Et justement, je n'ai pas vraiment compris l'intérêt. N'est-ce pas beaucoup de bruit pour pas grand chose ?
(vous pourriez m'expliquer comment on met du code indenté ? Avec ou sans blockquotes ça foire à la prévisualsation)
[^]Re: Comment casser le mythe de rapidité de Fibonacci :-)
On utilise la balise < pre > en supprimant les retours à la ligne automatique ...
Mais adieu les paragraphes ... Et commes les balises < p > ou < br / > sont interdites ...La Roue du Temps
[^]Re: Comment casser le mythe de rapidité de Fibonacci :-)
Bien la première chose que je vois c'est qu'avec la version memoïzée pour calculer fib(1001), il suffit d'ajouter fib(1000) et fib(999) qui ne sont pas des appels recursifs et qui sont déjà stockés dans la table de hachage si on a calculer fib(1000) auparavant.
(Pour le code indenté: texte avec du html sans retour chariot + balise <pre>code</pre>).
Sinon, effectivement, désolé pour le bruit : on s'éloigne du sujet.
[^]Re: Comment casser le mythe de rapidité de Fibonacci :-)
Q ce sujet chercher programmation dynamiwue dans google.
par exemple, http://www.google.fr/search?hs=z6b&hl=fr&c2coff=1&am(...)
Le principe de base est de supprimer la recursivite en stockant les resultats intermediaire, le tout en s calulant ces resultat de sorte qu on ait besoin a chaque fois que de resultats deja en memoire. En version la plus optimiae on utilise que des tableaux.
Desole pour les accents, leger probleme de config ...
[^]Re: Comment casser le mythe de rapidité de Fibonacci :-)
ARG !!!!!
pourquoi tant de haine^Wtable de hashage.
fibo, la bonne façon de le coder, c'est de ne pas calculer
fib(n) mais de calculer fibAux n= ( fib (n-1), fib n )
parce qu'à l'étape d'après, on a directement
fibAux (n+1) = (fib n, fib (n-1)+fib n).
En chameau, ça donne un truc du genre:
let rec fibAux n =
if n=1 then (1,1)
else
let (a,b)=fibAux (n-1) in (b,a+b);;
let fib n=
if n=0 then 1
else
let (a,b)=fibAux n in b;;
[^]Re: Comment casser le mythe de rapidité de Fibonacci :-)
Évidemment mais ce genre d'optimisation c'est autrement plus compliquée à faire faire automatiquement par le compilateur. Et l'utilisation d'une table de hachage permet quand même de faire du O(1) contre O(n) pour ton truc.
(j'ai failli faire le même commentaire cette nuit (mais avec du Scheme) avant de comprendre que c'était hors sujet :)
Free Softwares Users Group Arlon (Sud Luxembourg, Belgique)
pertinent, e adj. Approprié ; qui se rapporte exactement à ce dont il est question.
[^]Re: Comment casser le mythe de rapidité de Fibonacci :-)
ouais enfin bon le meilleur moyen ça reste d'utiliser le bon algorithme, à savoir celui en log(n) appels récursifs.
en chameau, en utilisant la bibliothèque de calculs avec les grands nombres, ça donne ceci:
open Num
let pmul (a, b) (c, d) =
let ac = a */ c in
(ac +/ a */ d +/ b */ c,
ac +/ b */ d)
let rec pow x a n =
if n = 0
then a
else
pow
(pmul x x)
(if n mod 2 = 0 then a else pmul a x)
(n / 2)
let fib n =
if n < 0 then invalid_arg "fib" ;
fst (pow (Int 1, Int 0) (Int 0, Int 1) n)
let _ =
print_endline (string_of_num (fib 100000))
Pour cacluler fib(100000) chez moi ça va 10× plus vite qu'avec l'algo linéaire.
[^]Re: Comment casser le mythe de rapidité de Fibonacci :-)
Chouette, c'est parti !
Et ben moi, j'ai un algo encore plus mieux bien.
Comme la suite de Fibonacci est linéaire, on sait la résoudre
analytiquement.
a=(1+sqrt(5))/2.;
b=(1-sqrt(5))/2.;
l=(1+.sqrt(5))/(2*sqrt(5));
fib(n)=l*a^n+(1-l)*b^n;
Paf.
Alors, après, tu fais tes multiplications et ton exponentiation comme tu veux.
Comment ça, ça n'a plus rien a voir avec la problématique initiale ?
P.S. Je suis nul en calcul donc en plus le truc que j'ai écrit doit être faux.
[^]Re: Comment casser le mythe de rapidité de Fibonacci :-)
Ca me confirme une idée que j'ai depuis longtemps : faudrai que le compilateur intègre un résolveur mathématique (qui reconstitue la formule à partire du graphe, bon courage), le résolveur aurait pour tâche de simplifier les calculs.
Petite difficulté informatique : ne pas mettre les calculs par terre à cause des arrondis.
[^]Re: Comment casser le mythe de rapidité de Fibonacci :-)
Comme quoi le choix de l'algorithme est parfois (beaucoup) plus important que le langage. :)
[^]Re: Comment casser le mythe de rapidité de Fibonacci :-)
Le choix de l'algo est quasi toujours plus important que celui du langage/compilateur. Mais on remarquera que le choix de l'algorithme est bien souvent influencé par le langage. On ne code pas de la même manière en C qu'en Lisp.
Free Softwares Users Group Arlon (Sud Luxembourg, Belgique)
pertinent, e adj. Approprié ; qui se rapporte exactement à ce dont il est question.
[^]Re: Comment casser le mythe de rapidité de Fibonacci :-)
Je crois plutôt que le problème vient du compilateur C. Je ne sais pas si la norme le permet, mais le compilateur devrait être capable, si c'est possible, de transformer les algorithme récursifs les plus simples en algorithmes itératifs. Je pense notamment à la récursivité terminale.De toute façon, ici, la meilleure solution au solution problème reste encore d'exprimer la suite en fonction de n plutôt qu'en fonction des termes précédents -> algo en O(1) (quoique ça dépende de l'implémentation de l'exponentielle...).
La comparaison est mauvaise : la principale raison pour laquelle le C a gagné est que l'assembleur n'est pas portable et qu'un langage assembleur est censé avoir une durée de vie limitée.
Cela dit, il y a quand même un point qui me gêne. Comment justifier cette surenchère de couches alors qu'il y a de nombreuses tâches qui ne sont pas parallélisables (ou difficilement parallélisables) et que la puissance des coeurs CPU augmente de plus en plus lentement.
Par exemple : réactivité des IHM, compression de données, etc.
[^]Re: Comment casser le mythe de rapidité de Fibonacci :-)
C'est plutôt le problème des langages fonctionnels qui ne "connaissent pas la boucle", vu que la récursivité terminale, c'est comment transformer une boucle en appel récursif et vice-versa.
Ce n'est vraiment pas le but du compilateur C de chercher à optimiser la structure du programme.
Le but c'est quand même d'avoir un "macro assembleur" qui te garantisse que les séquences d'intructions écrites seront executées dans le même ordre (