Oui, mais l'auteur dit qu'elles semblent au premier abord équivalentes, alors qu'une des valeurs est incluse dans l'un ou l'autre groupe en fonction de la comparaison effectuée. C'est en ça que je trouve bizarre sa façon de présenter les choses.
« Quand est-ce que les gens comprendront que la complexité est une notion mathématique faisant appel à des concepts d'infinis qui n'existent pas en informatique ? »
On t'a déjà répondu en partie, mais juste pour préciser : j'ai fait exprès de parler de complexités spatiale et temporelle ; il y a bien une notion « physique » dans ces deux types de complexité.
Ensuite, une fois qu'on a un algorithme qui dans le cas général est correct, il faut encore se pencher sur une implémentation efficace.
Oui, il existe des cas où la complexité théorique n'est pas si importante. J'ai en tête un exemple assez frappant :
1°) Pour pouvoir mettre sous forme SSA un programme ( http://en.wikipedia.org/wiki/Static_single_assignment_form ) il faut construire des frontières de domination (dominance frontiers en Anglais). Il existe un algorithme, avec une complexité théorique qui pour le moment n'a pas été améliorée (ou alors juste ses constantes).
2°) Les auteurs d'un papier ont mis au point un algorithme ayant une complexité théorique moins bonne, mais
3°) La différence de complexité n'entre réellement en compte que lorsque le graphe de flot de contrôle (CFG, Control Flow Graph) totalise plus de 30 000 noeuds.
4°) Ça n'arrive presque jamais (en fait, je n'ai jamais vu un cas pareil, mais mon expérience de l'informatique est très petite).
5°) L'algorithme des auteurs est beaucoup plus simple à mettre en oeuvre
6°) Les auteurs de l'article ont tripatouillé à mort leurs structures de données
Résultat : en pratique, tant que les CFG sont en dessous de 30 000 noeuds, ils ont un algorithme qui va plus vite que les implémentations connues de l'algo classique, et qui, étant plus simple dans son énoncé, risque moins d'être sujet à bugs pour sa mise en oeuvre.
Dans cet exemple, on touche directement à la limite séparant la recherche de l'ingénierie. L'ingénierie concerne l'optimisation des structures de données ; la recherche la mise au point de l'algo ; le flou concerne le fait qu'on prend en compte la complexité, tout en faisant attention aux cas réels.
D'autre part, la complexité n'est pas qu'un outil mathématique. Elle donne des bornes, ce qui est très important pour l'implémentation. À quoi bon implémenter un algorithme de complexité O(m^n), par exemple ? Ou mieux : lorsqu'on demande à quelqu'un d'effectuer une tâche, et que ce quelqu'un parvient à démontrer que le problème donné à résoudre est NP-complet [1], il est temps de reformuler le problème, pour le circonscrire un peu plus. Je réagis assez vivement parce que tu donnes l'impression de croire que l'informatique théorique n'est que de la masturbation intellectuelle ; or ce n'est clairement pas le cas [2].
Quand on parle d'algorithmes répartis, par exemple, tu as intérêt à être sûr que ton algorithme converge, sinon tu vas au devant de grosses surprises. Là encore, les « maths » aident beaucoup (même si maintenant il existe tout un tas d'outils sympa pour aider l'infoteux à se dépatouiller de tout ça).
[1] Oui bon, OK, non seulement ça n'arrive pas tous les jours, mais en plus, ça prend du temps de le démontrer correctement.
[2] Y'a des exceptions, comme toujours. ;-)
Ah oui tiens, soit dit en passant, tiré du blog du monsieur en question (qui effectivement est intéressant) :
1. x < y ? x : y
2. x <= y ? x : y
3. x > y ? y : x
4. x >= y ? y : x
Chez moi, l'expression 1. et l'expression 2. n'ont absolument rien d'équivalent, idem pour 3. Vs 4. Ça n'empêche pas le reste de son article d'être intéressant, mais c'est quand même un peu bizarre ...
Ben c'est pas dur, y'a que deux règles pour l'optimisation :
1°/ On n'optimise pas.
2°/ (pour experts seulement) On n'optimise pas encore.
Blague à part, effectivement, les compilateurs optimisants sont plutôt assez bien fichus de nos jours, et un bon algo restera en général bien plus efficace qu'une micro-optimisation locale. Il y a des exceptions, bien entendu.
Pour répondre à un commentaire vu plus haut concernant les histoires d'optimisation pour les caches, etc.. Si on prend la bibliothèque MKL (Math Kernel Library) d'Intel qui a été optimisée aux petits oignons et tout, on s'aperçoit que les défauts de cache, on s'en fout. Elle en fait plein, plus que des bibliothèques justement étudiées pour les minimiser. En contrepartie, elle fait plein de préchargements intelligents.
C'est ça le gros problème de l'optimisation : on cherche à améliorer la localité ? Très bien, on améliore. Mais on oublie que les défauts de cache sont parfois peu important vis à vis d'autres facteurs (un défaut de TLB par exemple est souvent bien plus déterminant qu'un défaut de cache L2). Ou bien on se rend compte que tout bêtement, un compilateur donné ne sait pas correctement dérouler des boucles un peu irrégulières, et qu'il suffit de le faire à la main pour gagner 20 à 30% de performances (déjà expérimenté sur icc version Itanium). Mais là, on se rend dépendant d'un compilateur donné.
Donc toute la difficulté est dans le compromis portabilité du code/portabilité des performances/optimisations spécifiques, et franchement, avant d'en arriver à ce genre de choses, je pense que bien définir ses structures de données et ses algorithmes est sacrément plus important.
C'est vrai, mais comme nous disait mon prof d'architecture des ordis : les processeurs haute performance, mis à part le calcul scientifique et les jeux vidéos, personne n'en a besoin. C'est pour ça que je n'ai pas abordé ces deux domaines qui sont très particuliers.
Le truc, c'est que jusqu'à il y a peu, c'était plutôt les boites qui disaient « entre payer une équipe de programmeurs pour optimiser un logiciel [qui en plus pouvait être proprio] et acheter des machines plus puissantes, la deuxième solution est plus économique ».
J'ai aussi des exemples dans le domaine du calcul scientifique, mais ça commence à devenir un peu trop ciblé.
Je suis d'accord dans l'ensemble concernant l'optimisation du code, mais ...
... Mais les gens oublient qu'à partir du moment où on optimise, on perd le plus souvent en lisibilité du code ; que tout le monde n'a pas le même niveau en programmation ; que beaucoup de code produit (et jeté) provient de stagiaires qui par définition ne sont pas encore rôdés [1]; etc.
Si on a pu démultiplier ainsi le nombre d'applications complexes, c'est grâce en grande partie à la réutilisation de composants, de bibliothèques, etc., car c'était plus simple pour des programmeurs moins expérimentés de construire au-dessus des briques de base pas toujours évidentes à faire. Mais ce faisant, et l'abstraction aidant, beaucoup de programmeurs (surtout débutants, je souligne) ignorent de quoi sont faites les briques sur lesquelles ils s'appuient (nombre de programmeurs Java - mais c'est valable pour tout autre langage avec une bibliothèque aussi importante - ne mesurent pas toujours les conséquences d'utiliser un ArrayList plutôt qu'un TreeMap plutôt que ... en termes de complexité spatiale et temporelle).
Moralité : oui, il faut essayer de faire attention à ne pas faire n'importe quoi, pour que ça tourne au mieux, mais il faut faire aussi attention aux excès de zèle.
Lorsque j'étais minuscule (vu que je suis toujours petit, il faut changer d'échelle), j'avais un ordinateur-jouet, qui me servait à faire du calcul mental, de la grammaire et de l'orthographe, principalement (y'avait aussi un module sonore pour « composer » d'atr^Wd'amusants morceaux grâce au doux son du buzzer, et quelques autres trucs).
C'était déjà assez lourd pour moi à 5 ou 6 ans, je me vois mal trimballer un ordinateur de pièce en pièce (car n'oublions pas qu'il s'agit d'un jouet avant tout) avec une caisse en bois...
« Et puis bon "linux le plus connu et le plus __stable__" (merci pour les projets bsd) »
D'accord, mais on est dans la vulgarisation, hein.
« et le passage sur la fiabilité(je connais du code proprio qui tourne dans des applis embarquées critiques qui est bien plus fiable de le code php libre dévellopé par jeune boutoneux qui veut impressionner ses potes) sont pas tres objectif ... »
Là par contre, pas d'accord avec cet argument : ils parlent de façon générale, alors que tu abordes un/des cas particulier(s), dans des contextes non comparables. Il faudrait comparer la fiabilité de logiciels appartenant au même domaine pour savoir à quel point ils exagèrent.
C'est toujours le même problème avec Windows, ça marche jamais comme il faut ...
Ah ben c'est vrai que le DLL hell de windows n'a pas son équivalent (SO hell) sous linux... Rah lala.
C'est vrai qu'à une époque, y'avait jamais de problème de dépendances avec les RPM. Maintenant c'est sûr, on a yum, urpmi, apt, ... Mais ça n'a pas toujours été le cas.
« Outlook : Des bugs oui, mais ca n'a rien a voir avec un OS ou je me trompes ? »
C'est une remarque extrêmement pertinente. Imaginons un instant que Linux se répande réellement dans les foyers (je l'espère hein, mais y'a encore du chemin avant que cela ne soit vrai). De deux choses l'une : soit il y a une répartition homogène des utilisateurs sur les clients de courriel ; chaque client (il n'y en a pas des milliers) a donc potentiellement des milliers d'utilisateurs, voire des centaines de milliers. Un virus qui trouverait une faille pour l'un de ceux-là réussirait donc à contaminer un nombre important de machines, mais les autres utilisateurs ne seraient pas inquiétés ; soit un client se démarque des autres (et à mon sens, il y a bien plus de chances que le grand public se concentre sur deux ou trois solutions plutôt que des dizaines), et le mal sera encore plus flagrant en cas de contamination.
Prenons le cas de Firefox : si je me souviens bien, tout un tas de machins sont installés dans le compte de l'utilisateur local, sans qu'il y ait réelle vérification. Rien n'empêcherait un programme malicieux de tirer partie d'une faille (par exemple, en allant sur un site web/en lisant un mail en html qui demanderait un plugin tout à fait valide, que firefox proposerait de télécharger, et en exploitant une faille mise en évidence sans le vouloir par ledit plugin). On peut trouver tout un tas de cas comme ça.
Alors oui, ça réduit le problème à des logiciels et plus l'OS en lui-même, mais Windows aussi commence à se sécuriser bien plus sérieusement (je parle de l'OS, pas d'outlook/ie/etc).
« SI c'est un problème de Freebox, Free propose un échange standard sans frais d'expédition pour le client. »
Oui enfin, le dispositif d'échange, c'est d'aller dans un point de distribution de colis (« Kiala » je crois), et c'est à toi de te déplacer pour récupérer la freebox (et apporter la tienne au passage pour faire l'échange). Donc tu vas chez un déménageur/un cordonnier/un fleuriste/etc pour récupérer ton colis. Du coup j'ai deux remarques à faire :
1/ Au téléphone, c'est à toi de savoir quel est le point kiala le plus proche de chez toi (j'ai un couple de collègues qui viennent de déménager au fin fond de l'Ile de France, heureusement qu'ils bossent dans une ville relativement grande et qu'ils ont pu aller se faire livrer chez un commerçant sur le chemin du boulot, sinon ils étaient bons pour prendre la voiture pour aller chercher leur colis « sans frais » dans un bouis-bouis que la personne de chez Free n'a même pas su trouver). Donc Free n'a pas d'outil pour savoir quel est le point kiala le plus proche de chez toi, ce qui est gênant tout de même (la coopération a des limites [1]). J'habite Paris, donc je suis clairement avantagé car au pire je perds 20 à 40 minutes de mon temps pour aller chercher mon colis (aller-retour) ; ce n'est pas le cas de tout le monde [2].
2/ Ce système a un inconvénient : tu perds du temps (et parfois de l'argent - l'essence, ça coûte) pour aller chercher ton colis ; il a aussi un avantage : tu n'es pas obligé de rester chez toi entre 14h et 18h un jeudi après-midi (et donc griller un jour de congés/RTT) pour recevoir le colis. En ce qui me concerne c'est un compromis acceptable, mais de toute façon je suis piéton dans une ville où les transports en commun sont somme toute bien foutus.
[1] Parce qu'ils sont gentils chez Free, mais dès que tu as le malheur de répondre « oui » à la question « avez-vous un ami qui possède une freebox », ils refusent d'aller plus loin dans la procédure (ça leur permet de gagner du temps). Et si la coopération entre le client et le fournisseur de service, je suis tout à fait pour, là c'est dépasser les bornes des limites ! :-) Parce que faire coopérer TOUS les clients de free à la fois, c'est franchement gonflé.
[2] Et encore, mon point kiala était en vacances quand j'y suis allé, donc le paquet a été rerouté vers un autre point, et je ne l'ai su qu'en appelant free, car le machin automatique qui envoie les SMS avait considéré que le premier point d'arrivée, même en vacances, avait été un succès pour la livraison.
« Je veux juste dire que la recherche ca serait bien qu'il y pense un peu autrement que juste 'comment avoir l'arme la plus efficace' »
C'est un peu pour ça que j'avais tenté de nuancer ton propos plus haut, en citant tout un tas d'applications de recherches qui se servent de supercalculateurs dans des buts autres que pour faire plaisir à la défense.
De plus, ton problème au CEA n'est pas dû ... au CEA, comme tu viens de le dire (franchement, t'as pas été très honnête sur ce coup-là). Par contre oui, je confirme : dans la recherche publique, c'est souvent au chercheur d'avancer les fonds/le boulot, pour ensuite seulement se faire rembourser (vivent les confs à 2000 ¤ pour le billet d'avion \o/). On peut éventuellement demander une avance, mais c'est fastidieux à faire, et pas toujours possible.
« Le CEA/DAM de bruyere le chatel ...
Ah c'est le truc ou quand tu descend du bus, tu as un maitre chien et un gars avec un fusil à pompe pour rentrer, non ? »
Étonnant, dans un endroit où des secrets militaires et technologiques sont entreposés, où des informations qui tomberaient entre de mauvaises mains pourraient vraiment faire du mal non-seulement à ce pays, mais à beaucoup d'autres aussi, on est paranoïaque ? Vraiment, je ne peux qu'acquiéser et me ranger à ton avis, ça en fait automatiquement un endroit de pourris par excellence (tu permets, vue la virulence de tes propos, je me permets de légèrement déformer les tiens).
Tu peux m'expliquer en quoi ça a rapport avec le CEA DAM ? Tu cites les chiffres pour le budget de l'état français là, pas ceux du CEA. Alors oui, pour pouvoir se servir de Tera 10, il faut montrer patte blanche ; il faut se présenter physiquement au CEA (avec le bus/la voiture, etc) ; ce n'est même pas toi qui va lancer le programme, l'horreur ! D'un autre côté, je vois mal l'un des plus gros supercalculateurs du monde être accessible depuis internet, pour risquer de se faire pirater, et servir à commettre des infractions.
J'ai surtout réagi au côté « les possesseurs de super calculateurs, tous pourris ! » que tu as sorti deux messages plus haut. Tu trouves que j'exagère ? Loin de moi l'idée de dire que le CEA DAM n'utilise pas son super calculateur pour effectuer des modélisation dans les cas que tu décris, par exemple - après tout, DAM = Direction des Applications Militaires, quand même. Mais applications militaires ne signifie absolument pas « armement militaire seulement ».
Et je réitère : certes, on ne pourra pas se servir de boinc pour faire du calcul sur Tera 10, mais les supercalculateurs ne servent pas qu'à tuer, et même très souvent servent à comprendre les phénomènes naturels, ou servent en pharmacologie, etc. J'ai cité la DAM pour une raison très simple : malgré leur engagement militaire, ils ont une politique vis à vis de la recherche qui est à la fois pragmatique (ils font quand même dans les applications industrielles, aussi) mais - ne t'en déplaise - ouverte : du moment que l'objet de la recherche ne dépend pas d'un quelconque label « top secret »/« secret défense » ou que sais-je, ils lâchent leurs logiciels en CeCILL par exemple.
Et oui, le CEA fait sans doute aussi payer assez cher l'utilisation de son cluster à ceux qui ne sont pas des partenaires. Heureusement, l'état français est un partenaire du CEA (étonnant, non ?). Et un certain nombre de labos universitaires travaillent avec aussi.
Concernant l'acceptation des contributions de n'importe qui : lorsqu'ils lâchent un logiciel en CeCILL, ils assurent le support, et évidemment, ils acceptent tous les patches, par exemple. :-)
Si un logiciel libre de calcul haute performance (maillage, éléments finis, que sais-je) est vraiment puissant, je doute que le CEA - ou toute autre organisation possédant un supercalculateur - refuse de s'en servir, de l'améliorer, et de relâcher les modifications - en fait, je suis même plutôt persuadé du contraire.
« Ensuite vas m'expliquer pourquoi apres avoir fait un stage en été au cea/dam de bruyere le chatel justement, ben en décembre je suis toujours pas payé. Mais je croyais qu'il y avait tant de sous pour la recherche! »
Je ne vois pas le rapport avec ce qui a été dit juste avant. Et que tu n'aies pas été payé, c'est très dommage pour toi, mais je vais te dire : tu es le premier que je connais qui y as fait un stage qui me dise ça (si si). Tous les autres que je connais y ont été payés en temps et en heure.
Sinon, j'ai pas trop eu l'impression que le CNRS et l'INRIA avaient des problèmes de collaboration avec le CEA (DAM en l'occurrence) lors de leurs réunions...
... On les utilise aussi dans le cadre d'études sismologiques, pour comprendre comment les tremblements de terres (dont on a les relevés) se sont déroulés, et comment exploiter ces données pour pouvoir éviter certaines catastrophes à l'avenir.
On s'en sert pour calculer la houle dans les ports pour savoir où entreposer certains produits dangereux qui n'aiment pas être trop remués.
On modélise un nombre pas possible de variables pour pouvoir examiner ce qui est relié à l'activité météo.
On modélise aussi tout un tas de trucs pour les centrales (nucléaires ou pas).
Blue Gene sert pour la bio-informatique, etc.
Bref, la simulation pour les armes nucléaire n'est qu'un aspect de l'usage fait par les super calculateurs. Même Tera 10, qui se trouve au CEA DAM (donc armement militaire, tout ça), sert aussi en grande partie à effectuer des calculs qui n'ont rien à voir avec l'armement, mais avec la simulation de phénomènes naturels, etc.
Bon, je vais supposer que tu as lu le document déjà donné deux ou trois fois précédemment. L'API interne ne concerne que ... la tambouille interne du noyau. Mais ledit document précise bien un truc : si jamais quelqu'un modifie une api, c'est à sa charge de répercuter le changement d'API sur le code noyau, i.e. l'intérêt de tout ça c'est la factorisation de code, et d'avoir à effectuer le moins de changement dans les pilotes eux-mêmes. Si ces derniers sont inclus dans le noyau officiel, alors oui, ils seront aussi modifiés en conséquence ; sinon, c'est à charge de celui qui fournit le pilote de le modifier. Ça me semble assez logique, finalement.
Le côté « oui mais bon, les API stables, ça permet de pouvoir garder une compatibilité plus longtemps, etc » ne tient pas selon moi dans une optique de logiciel libre, car si tu fais du code hors-noyau (le plus souvent propriétaire), alors de toute façon il ne te reste plus qu'à maintenir un seul et unique driver - ce qui suppose que tu suis les changements opérés dans le noyau, certes, mais d'un autre côté, ça fait partie du jeu : de ce que j'ai compris, seuls les pilotes codés avec les pieds [1] et ceux qui sont proprio sont concernés, au final. Dans le premier cas, je comprends qu'une équipe de développement n'ait pas envie de servir de debugger pour un pilote qui gagnerait à être proprifié. Dans le deuxième, si tu fais du propriétaire, et tu assumes un chouilla. Ça ne me semble pas démesuré, comme principe.
Pour faire un rapide résumé/traduction de stable_api_nonsense.txt :
- Croire qu'avec une API stable, on obtient une ABI stable est faux, car suivant le compilateur utilisé, par exemple, les alignements, lef ait d'inliner certaines fonctions, etc. changent ; stabilité = nil.
- suivant les options noyau choisies, on se retrouve avec des champs qui apparaissent ou disparaissent dans les structures, l'alignement va changer, etc. ;
- Il y a tout plein d'architectures différentes supportées par linux ; aucune compatibilité binaire entre elles donc.
Donc on se retrouve avec l'obligation de devoir utiliser un compilateur pour une distribution et une architecture spécifiques, si on veut pouvoir garder cette propriété de stabilité. Sans parler du côté SMP/SMT/CMP/MonoProc qu'on doit choisir...
Je m'arrête là. Comme il a été dit plus tôt ( https://linuxfr.org/comments/785368.html#785368 ) tout cela tient plus au modèle choisi qu'à quelqu'un ayant tort ou raison. Par contre, si pour un OS comme celui de MS (ou d'Apple, d'ailleurs), utiliser une seule architecture ainsi qu'un seul noyau permet de réduire fortement les inconvénients cités précédemment, je ne vois pas comment Linux pourrait faire de même.
[1] D'après les critères de qualité de l'équipe de dév. du noyau, certes.
« 1°) trouver un graphe hamiltonien
2°) parcourir ce graphe hamiltonien et attribuer un poid en fonction de la position géographique du lien
Tu vois 2 lignes ... Et ben essaie de me trouve un algo dans P. »
Je crois que la preuve a été démontrée dans « Numb3rs ».
Mouais, perfectionniste, perfectionniste ... Un vrai perfectionniste va être obsédé par son code pour que celui-ci non-seulement marche, mais en plus soit le meilleur qui soit. Il est compulsif obsessionnel, quoi. Ce que tu décris est le syndrôme du poil dans la main. Je connais bien, j'ai un baobab dans la mienne.
Tout est question de concentration, et/ou de motivation.
J'ai croisé quelques perfectionnistes : ils ont fait des trucs déments (pas tous, cela dit). Ben c'est simple, ils n'avaient aucun autre projet entre temps (sauf éventuellement ceux du boulot). N'empêche, au bout d'un certain temps, si tu ne donne pas un côté pragmatique à tes projets (« ouais bon ok, c'est crade, mais le code est bien isolé, je pourrai le changer plus tard »), tu n'iras pas très loin, et tout restera au même point : au stade de projet.
J'ai pertinenté, mais quand même, quand certains stagiaires reprennent le boulot crade du/des chercheur(s)/thésard(s) [1], remettent tout à plat, se font chier à réimplémenter certains algos (parce qu'ils existent sur papier, mais bon, le chercheur il a pas que ça à faire de les implémenter), etc. et même parfois que tu te retrouves avec des initiatives à prendre, certes ce n'est sans doute pas de la recherche pure et dure, mais ça commence à y ressembler fortement.
Un cas s'est présenté dans notre labo, ben c'est simple, les élèves-stagiaires ont eu leur nom sur la publication. Parce que la recherche, au moins en info, si on peut prouver par des expériences que les dires sont vrais, c'est quand même mieux (là il s'agissait d'un outil d'aide à l'optimisation, qui fait des trucs assez complexes). Je trouve franchement normal que ce soit fait comme ça. Alors oui ensuite, on se retrouve comme certaines équipes US avec 300 contributeurs à l'article. Bon, ça dilue d'autant sa « valeur ». Mais je trouve normal qu'on crédite les gens qui permettent de faire avancer un sujet.
[1] Oui parce que bon, les chercheurs qui clament que « on se fout du code, on fait de la recherche, pas du génie logiciel », c'est vaguement gonflant, notamment lorsque des collègues veulent ensuite réexploiter les résultats pour aller plus loin. Oui, c'est du vécu.
[^] # Re: configurations
Posté par lasher . En réponse au journal Kde !. Évalué à 3.
continu -> continue
Attention...
[^] # Re: Bonne année
Posté par lasher . En réponse au journal ça y est. Évalué à 6.
[^] # Re: Le libraire qui me fait rêver...
Posté par lasher . En réponse au journal Un auteur contre Amazon. Évalué à 2.
[^] # Re: Plop !
Posté par lasher . En réponse au journal "L'informatique Paradoxale". Évalué à 3.
[^] # Re: Plop !
Posté par lasher . En réponse au journal "L'informatique Paradoxale". Évalué à 5.
On t'a déjà répondu en partie, mais juste pour préciser : j'ai fait exprès de parler de complexités spatiale et temporelle ; il y a bien une notion « physique » dans ces deux types de complexité.
Ensuite, une fois qu'on a un algorithme qui dans le cas général est correct, il faut encore se pencher sur une implémentation efficace.
Oui, il existe des cas où la complexité théorique n'est pas si importante. J'ai en tête un exemple assez frappant :
1°) Pour pouvoir mettre sous forme SSA un programme ( http://en.wikipedia.org/wiki/Static_single_assignment_form ) il faut construire des frontières de domination (dominance frontiers en Anglais). Il existe un algorithme, avec une complexité théorique qui pour le moment n'a pas été améliorée (ou alors juste ses constantes).
2°) Les auteurs d'un papier ont mis au point un algorithme ayant une complexité théorique moins bonne, mais
3°) La différence de complexité n'entre réellement en compte que lorsque le graphe de flot de contrôle (CFG, Control Flow Graph) totalise plus de 30 000 noeuds.
4°) Ça n'arrive presque jamais (en fait, je n'ai jamais vu un cas pareil, mais mon expérience de l'informatique est très petite).
5°) L'algorithme des auteurs est beaucoup plus simple à mettre en oeuvre
6°) Les auteurs de l'article ont tripatouillé à mort leurs structures de données
Résultat : en pratique, tant que les CFG sont en dessous de 30 000 noeuds, ils ont un algorithme qui va plus vite que les implémentations connues de l'algo classique, et qui, étant plus simple dans son énoncé, risque moins d'être sujet à bugs pour sa mise en oeuvre.
Dans cet exemple, on touche directement à la limite séparant la recherche de l'ingénierie. L'ingénierie concerne l'optimisation des structures de données ; la recherche la mise au point de l'algo ; le flou concerne le fait qu'on prend en compte la complexité, tout en faisant attention aux cas réels.
D'autre part, la complexité n'est pas qu'un outil mathématique. Elle donne des bornes, ce qui est très important pour l'implémentation. À quoi bon implémenter un algorithme de complexité O(m^n), par exemple ? Ou mieux : lorsqu'on demande à quelqu'un d'effectuer une tâche, et que ce quelqu'un parvient à démontrer que le problème donné à résoudre est NP-complet [1], il est temps de reformuler le problème, pour le circonscrire un peu plus. Je réagis assez vivement parce que tu donnes l'impression de croire que l'informatique théorique n'est que de la masturbation intellectuelle ; or ce n'est clairement pas le cas [2].
Quand on parle d'algorithmes répartis, par exemple, tu as intérêt à être sûr que ton algorithme converge, sinon tu vas au devant de grosses surprises. Là encore, les « maths » aident beaucoup (même si maintenant il existe tout un tas d'outils sympa pour aider l'infoteux à se dépatouiller de tout ça).
[1] Oui bon, OK, non seulement ça n'arrive pas tous les jours, mais en plus, ça prend du temps de le démontrer correctement.
[2] Y'a des exceptions, comme toujours. ;-)
[^] # Re: Esprit
Posté par lasher . En réponse au journal L'utopie infantile du kantisme de la pureté totale. Évalué à 2.
[^] # Re: Plop !
Posté par lasher . En réponse au journal "L'informatique Paradoxale". Évalué à 2.
Chez moi, l'expression 1. et l'expression 2. n'ont absolument rien d'équivalent, idem pour 3. Vs 4. Ça n'empêche pas le reste de son article d'être intéressant, mais c'est quand même un peu bizarre ...
[^] # Re: Plop !
Posté par lasher . En réponse au journal "L'informatique Paradoxale". Évalué à 2.
Parce que icc -Wall est bien plus (trop ?) verbeux que gcc, au point que c'en est gênant.
[^] # Re: Plop !
Posté par lasher . En réponse au journal "L'informatique Paradoxale". Évalué à 7.
1°/ On n'optimise pas.
2°/ (pour experts seulement) On n'optimise pas encore.
Blague à part, effectivement, les compilateurs optimisants sont plutôt assez bien fichus de nos jours, et un bon algo restera en général bien plus efficace qu'une micro-optimisation locale. Il y a des exceptions, bien entendu.
Pour répondre à un commentaire vu plus haut concernant les histoires d'optimisation pour les caches, etc.. Si on prend la bibliothèque MKL (Math Kernel Library) d'Intel qui a été optimisée aux petits oignons et tout, on s'aperçoit que les défauts de cache, on s'en fout. Elle en fait plein, plus que des bibliothèques justement étudiées pour les minimiser. En contrepartie, elle fait plein de préchargements intelligents.
C'est ça le gros problème de l'optimisation : on cherche à améliorer la localité ? Très bien, on améliore. Mais on oublie que les défauts de cache sont parfois peu important vis à vis d'autres facteurs (un défaut de TLB par exemple est souvent bien plus déterminant qu'un défaut de cache L2). Ou bien on se rend compte que tout bêtement, un compilateur donné ne sait pas correctement dérouler des boucles un peu irrégulières, et qu'il suffit de le faire à la main pour gagner 20 à 30% de performances (déjà expérimenté sur icc version Itanium). Mais là, on se rend dépendant d'un compilateur donné.
Donc toute la difficulté est dans le compromis portabilité du code/portabilité des performances/optimisations spécifiques, et franchement, avant d'en arriver à ce genre de choses, je pense que bien définir ses structures de données et ses algorithmes est sacrément plus important.
[^] # Re: Plop !
Posté par lasher . En réponse au journal "L'informatique Paradoxale". Évalué à 3.
[^] # Re: Plop !
Posté par lasher . En réponse au journal "L'informatique Paradoxale". Évalué à 7.
J'ai aussi des exemples dans le domaine du calcul scientifique, mais ça commence à devenir un peu trop ciblé.
Je suis d'accord dans l'ensemble concernant l'optimisation du code, mais ...
... Mais les gens oublient qu'à partir du moment où on optimise, on perd le plus souvent en lisibilité du code ; que tout le monde n'a pas le même niveau en programmation ; que beaucoup de code produit (et jeté) provient de stagiaires qui par définition ne sont pas encore rôdés [1]; etc.
Si on a pu démultiplier ainsi le nombre d'applications complexes, c'est grâce en grande partie à la réutilisation de composants, de bibliothèques, etc., car c'était plus simple pour des programmeurs moins expérimentés de construire au-dessus des briques de base pas toujours évidentes à faire. Mais ce faisant, et l'abstraction aidant, beaucoup de programmeurs (surtout débutants, je souligne) ignorent de quoi sont faites les briques sur lesquelles ils s'appuient (nombre de programmeurs Java - mais c'est valable pour tout autre langage avec une bibliothèque aussi importante - ne mesurent pas toujours les conséquences d'utiliser un ArrayList plutôt qu'un TreeMap plutôt que ... en termes de complexité spatiale et temporelle).
Moralité : oui, il faut essayer de faire attention à ne pas faire n'importe quoi, pour que ça tourne au mieux, mais il faut faire aussi attention aux excès de zèle.
[1] Il y a toujours des exceptions, bien sûr.
[^] # Re: Parce que...
Posté par lasher . En réponse au journal PC ordinaire + écran tactile + OPIE = PC pour les mômes. Évalué à 2.
C'était déjà assez lourd pour moi à 5 ou 6 ans, je me vois mal trimballer un ordinateur de pièce en pièce (car n'oublions pas qu'il s'agit d'un jouet avant tout) avec une caisse en bois...
[^] # Re: Et toi tu exiges rien peut-être ?
Posté par lasher . En réponse au journal L'utopie infantile du kantisme de la pureté totale. Évalué à 3.
[^] # Re: un peu simpliste
Posté par lasher . En réponse à la dépêche Pages sur le logiciel libre dans un guide diffusé avec Science et Vie Junior. Évalué à 4.
D'accord, mais on est dans la vulgarisation, hein.
« et le passage sur la fiabilité(je connais du code proprio qui tourne dans des applis embarquées critiques qui est bien plus fiable de le code php libre dévellopé par jeune boutoneux qui veut impressionner ses potes) sont pas tres objectif ... »
Là par contre, pas d'accord avec cet argument : ils parlent de façon générale, alors que tu abordes un/des cas particulier(s), dans des contextes non comparables. Il faudrait comparer la fiabilité de logiciels appartenant au même domaine pour savoir à quel point ils exagèrent.
[^] # Re: Teste supertux version windows et linux
Posté par lasher . En réponse à la dépêche Supertux 0.3.0, l'aventure continue. Évalué à 4.
Ah ben c'est vrai que le DLL hell de windows n'a pas son équivalent (SO hell) sous linux... Rah lala.
C'est vrai qu'à une époque, y'avait jamais de problème de dépendances avec les RPM. Maintenant c'est sûr, on a yum, urpmi, apt, ... Mais ça n'a pas toujours été le cas.
[^] # Re: Partisant ?
Posté par lasher . En réponse à la dépêche La guerre contre l'ODF et le RGI fait rage.... Évalué à 4.
C'est une remarque extrêmement pertinente. Imaginons un instant que Linux se répande réellement dans les foyers (je l'espère hein, mais y'a encore du chemin avant que cela ne soit vrai). De deux choses l'une : soit il y a une répartition homogène des utilisateurs sur les clients de courriel ; chaque client (il n'y en a pas des milliers) a donc potentiellement des milliers d'utilisateurs, voire des centaines de milliers. Un virus qui trouverait une faille pour l'un de ceux-là réussirait donc à contaminer un nombre important de machines, mais les autres utilisateurs ne seraient pas inquiétés ; soit un client se démarque des autres (et à mon sens, il y a bien plus de chances que le grand public se concentre sur deux ou trois solutions plutôt que des dizaines), et le mal sera encore plus flagrant en cas de contamination.
Prenons le cas de Firefox : si je me souviens bien, tout un tas de machins sont installés dans le compte de l'utilisateur local, sans qu'il y ait réelle vérification. Rien n'empêcherait un programme malicieux de tirer partie d'une faille (par exemple, en allant sur un site web/en lisant un mail en html qui demanderait un plugin tout à fait valide, que firefox proposerait de télécharger, et en exploitant une faille mise en évidence sans le vouloir par ledit plugin). On peut trouver tout un tas de cas comme ça.
Alors oui, ça réduit le problème à des logiciels et plus l'OS en lui-même, mais Windows aussi commence à se sécuriser bien plus sérieusement (je parle de l'OS, pas d'outlook/ie/etc).
[^] # Re: echange de freebox ?
Posté par lasher . En réponse au journal Free n'est pas prêt pour assumer le téléphone. Évalué à 7.
Oui enfin, le dispositif d'échange, c'est d'aller dans un point de distribution de colis (« Kiala » je crois), et c'est à toi de te déplacer pour récupérer la freebox (et apporter la tienne au passage pour faire l'échange). Donc tu vas chez un déménageur/un cordonnier/un fleuriste/etc pour récupérer ton colis. Du coup j'ai deux remarques à faire :
1/ Au téléphone, c'est à toi de savoir quel est le point kiala le plus proche de chez toi (j'ai un couple de collègues qui viennent de déménager au fin fond de l'Ile de France, heureusement qu'ils bossent dans une ville relativement grande et qu'ils ont pu aller se faire livrer chez un commerçant sur le chemin du boulot, sinon ils étaient bons pour prendre la voiture pour aller chercher leur colis « sans frais » dans un bouis-bouis que la personne de chez Free n'a même pas su trouver). Donc Free n'a pas d'outil pour savoir quel est le point kiala le plus proche de chez toi, ce qui est gênant tout de même (la coopération a des limites [1]). J'habite Paris, donc je suis clairement avantagé car au pire je perds 20 à 40 minutes de mon temps pour aller chercher mon colis (aller-retour) ; ce n'est pas le cas de tout le monde [2].
2/ Ce système a un inconvénient : tu perds du temps (et parfois de l'argent - l'essence, ça coûte) pour aller chercher ton colis ; il a aussi un avantage : tu n'es pas obligé de rester chez toi entre 14h et 18h un jeudi après-midi (et donc griller un jour de congés/RTT) pour recevoir le colis. En ce qui me concerne c'est un compromis acceptable, mais de toute façon je suis piéton dans une ville où les transports en commun sont somme toute bien foutus.
[1] Parce qu'ils sont gentils chez Free, mais dès que tu as le malheur de répondre « oui » à la question « avez-vous un ami qui possède une freebox », ils refusent d'aller plus loin dans la procédure (ça leur permet de gagner du temps). Et si la coopération entre le client et le fournisseur de service, je suis tout à fait pour, là c'est dépasser les bornes des limites ! :-) Parce que faire coopérer TOUS les clients de free à la fois, c'est franchement gonflé.
[2] Et encore, mon point kiala était en vacances quand j'y suis allé, donc le paquet a été rerouté vers un autre point, et je ne l'ai su qu'en appelant free, car le machin automatique qui envoie les SMS avait considéré que le premier point d'arrivée, même en vacances, avait été un succès pour la livraison.
[^] # Re: Et les licences de découvertes ?
Posté par lasher . En réponse au journal Partagez votre CPU pour le bien de l'humanité. Évalué à 4.
C'est un peu pour ça que j'avais tenté de nuancer ton propos plus haut, en citant tout un tas d'applications de recherches qui se servent de supercalculateurs dans des buts autres que pour faire plaisir à la défense.
De plus, ton problème au CEA n'est pas dû ... au CEA, comme tu viens de le dire (franchement, t'as pas été très honnête sur ce coup-là). Par contre oui, je confirme : dans la recherche publique, c'est souvent au chercheur d'avancer les fonds/le boulot, pour ensuite seulement se faire rembourser (vivent les confs à 2000 ¤ pour le billet d'avion \o/). On peut éventuellement demander une avance, mais c'est fastidieux à faire, et pas toujours possible.
[^] # Re: Et les licences de découvertes ?
Posté par lasher . En réponse au journal Partagez votre CPU pour le bien de l'humanité. Évalué à 3.
Ah c'est le truc ou quand tu descend du bus, tu as un maitre chien et un gars avec un fusil à pompe pour rentrer, non ? »
Étonnant, dans un endroit où des secrets militaires et technologiques sont entreposés, où des informations qui tomberaient entre de mauvaises mains pourraient vraiment faire du mal non-seulement à ce pays, mais à beaucoup d'autres aussi, on est paranoïaque ? Vraiment, je ne peux qu'acquiéser et me ranger à ton avis, ça en fait automatiquement un endroit de pourris par excellence (tu permets, vue la virulence de tes propos, je me permets de légèrement déformer les tiens).
« budget 2005 :
5. Recherche/Ens. sup. (20,5)
4. Défense (36,2) »
Tu peux m'expliquer en quoi ça a rapport avec le CEA DAM ? Tu cites les chiffres pour le budget de l'état français là, pas ceux du CEA. Alors oui, pour pouvoir se servir de Tera 10, il faut montrer patte blanche ; il faut se présenter physiquement au CEA (avec le bus/la voiture, etc) ; ce n'est même pas toi qui va lancer le programme, l'horreur ! D'un autre côté, je vois mal l'un des plus gros supercalculateurs du monde être accessible depuis internet, pour risquer de se faire pirater, et servir à commettre des infractions.
J'ai surtout réagi au côté « les possesseurs de super calculateurs, tous pourris ! » que tu as sorti deux messages plus haut. Tu trouves que j'exagère ? Loin de moi l'idée de dire que le CEA DAM n'utilise pas son super calculateur pour effectuer des modélisation dans les cas que tu décris, par exemple - après tout, DAM = Direction des Applications Militaires, quand même. Mais applications militaires ne signifie absolument pas « armement militaire seulement ».
Et je réitère : certes, on ne pourra pas se servir de boinc pour faire du calcul sur Tera 10, mais les supercalculateurs ne servent pas qu'à tuer, et même très souvent servent à comprendre les phénomènes naturels, ou servent en pharmacologie, etc. J'ai cité la DAM pour une raison très simple : malgré leur engagement militaire, ils ont une politique vis à vis de la recherche qui est à la fois pragmatique (ils font quand même dans les applications industrielles, aussi) mais - ne t'en déplaise - ouverte : du moment que l'objet de la recherche ne dépend pas d'un quelconque label « top secret »/« secret défense » ou que sais-je, ils lâchent leurs logiciels en CeCILL par exemple.
Et oui, le CEA fait sans doute aussi payer assez cher l'utilisation de son cluster à ceux qui ne sont pas des partenaires. Heureusement, l'état français est un partenaire du CEA (étonnant, non ?). Et un certain nombre de labos universitaires travaillent avec aussi.
Concernant l'acceptation des contributions de n'importe qui : lorsqu'ils lâchent un logiciel en CeCILL, ils assurent le support, et évidemment, ils acceptent tous les patches, par exemple. :-)
Si un logiciel libre de calcul haute performance (maillage, éléments finis, que sais-je) est vraiment puissant, je doute que le CEA - ou toute autre organisation possédant un supercalculateur - refuse de s'en servir, de l'améliorer, et de relâcher les modifications - en fait, je suis même plutôt persuadé du contraire.
« Ensuite vas m'expliquer pourquoi apres avoir fait un stage en été au cea/dam de bruyere le chatel justement, ben en décembre je suis toujours pas payé. Mais je croyais qu'il y avait tant de sous pour la recherche! »
Je ne vois pas le rapport avec ce qui a été dit juste avant. Et que tu n'aies pas été payé, c'est très dommage pour toi, mais je vais te dire : tu es le premier que je connais qui y as fait un stage qui me dise ça (si si). Tous les autres que je connais y ont été payés en temps et en heure.
Sinon, j'ai pas trop eu l'impression que le CNRS et l'INRIA avaient des problèmes de collaboration avec le CEA (DAM en l'occurrence) lors de leurs réunions...
[^] # Re: Et les licences de découvertes ?
Posté par lasher . En réponse au journal Partagez votre CPU pour le bien de l'humanité. Évalué à 3.
On s'en sert pour calculer la houle dans les ports pour savoir où entreposer certains produits dangereux qui n'aiment pas être trop remués.
On modélise un nombre pas possible de variables pour pouvoir examiner ce qui est relié à l'activité météo.
On modélise aussi tout un tas de trucs pour les centrales (nucléaires ou pas).
Blue Gene sert pour la bio-informatique, etc.
Bref, la simulation pour les armes nucléaire n'est qu'un aspect de l'usage fait par les super calculateurs. Même Tera 10, qui se trouve au CEA DAM (donc armement militaire, tout ça), sert aussi en grande partie à effectuer des calculs qui n'ont rien à voir avec l'armement, mais avec la simulation de phénomènes naturels, etc.
[^] # Re: Faut pas exagerer...
Posté par lasher . En réponse à la dépêche Une plongée dans le développement de Linux. Évalué à 8.
Le côté « oui mais bon, les API stables, ça permet de pouvoir garder une compatibilité plus longtemps, etc » ne tient pas selon moi dans une optique de logiciel libre, car si tu fais du code hors-noyau (le plus souvent propriétaire), alors de toute façon il ne te reste plus qu'à maintenir un seul et unique driver - ce qui suppose que tu suis les changements opérés dans le noyau, certes, mais d'un autre côté, ça fait partie du jeu : de ce que j'ai compris, seuls les pilotes codés avec les pieds [1] et ceux qui sont proprio sont concernés, au final. Dans le premier cas, je comprends qu'une équipe de développement n'ait pas envie de servir de debugger pour un pilote qui gagnerait à être proprifié. Dans le deuxième, si tu fais du propriétaire, et tu assumes un chouilla. Ça ne me semble pas démesuré, comme principe.
Pour faire un rapide résumé/traduction de stable_api_nonsense.txt :
- Croire qu'avec une API stable, on obtient une ABI stable est faux, car suivant le compilateur utilisé, par exemple, les alignements, lef ait d'inliner certaines fonctions, etc. changent ; stabilité = nil.
- suivant les options noyau choisies, on se retrouve avec des champs qui apparaissent ou disparaissent dans les structures, l'alignement va changer, etc. ;
- Il y a tout plein d'architectures différentes supportées par linux ; aucune compatibilité binaire entre elles donc.
Donc on se retrouve avec l'obligation de devoir utiliser un compilateur pour une distribution et une architecture spécifiques, si on veut pouvoir garder cette propriété de stabilité. Sans parler du côté SMP/SMT/CMP/MonoProc qu'on doit choisir...
Je m'arrête là. Comme il a été dit plus tôt ( https://linuxfr.org/comments/785368.html#785368 ) tout cela tient plus au modèle choisi qu'à quelqu'un ayant tort ou raison. Par contre, si pour un OS comme celui de MS (ou d'Apple, d'ailleurs), utiliser une seule architecture ainsi qu'un seul noyau permet de réduire fortement les inconvénients cités précédemment, je ne vois pas comment Linux pourrait faire de même.
[1] D'après les critères de qualité de l'équipe de dév. du noyau, certes.
[^] # Re: HP
Posté par lasher . En réponse à la dépêche L'UFC Que Choisir contre la vente liée. Évalué à 3.
2°) parcourir ce graphe hamiltonien et attribuer un poid en fonction de la position géographique du lien
Tu vois 2 lignes ... Et ben essaie de me trouve un algo dans P. »
Je crois que la preuve a été démontrée dans « Numb3rs ».
------------------>[*]
[^] # Re: Tout pareil...
Posté par lasher . En réponse au journal Pourquoi la Wii saimal(tm)(r). Évalué à 10.
[^] # Re: ...
Posté par lasher . En réponse au journal Terminer ses projets, pas si facile ?. Évalué à 2.
Tout est question de concentration, et/ou de motivation.
J'ai croisé quelques perfectionnistes : ils ont fait des trucs déments (pas tous, cela dit). Ben c'est simple, ils n'avaient aucun autre projet entre temps (sauf éventuellement ceux du boulot). N'empêche, au bout d'un certain temps, si tu ne donne pas un côté pragmatique à tes projets (« ouais bon ok, c'est crade, mais le code est bien isolé, je pourrai le changer plus tard »), tu n'iras pas très loin, et tout restera au même point : au stade de projet.
[^] # Re: CDD ?
Posté par lasher . En réponse au journal L'INRIA recherche un(e) stagiaire pour ObjectWeb. Évalué à 4.
Un cas s'est présenté dans notre labo, ben c'est simple, les élèves-stagiaires ont eu leur nom sur la publication. Parce que la recherche, au moins en info, si on peut prouver par des expériences que les dires sont vrais, c'est quand même mieux (là il s'agissait d'un outil d'aide à l'optimisation, qui fait des trucs assez complexes). Je trouve franchement normal que ce soit fait comme ça. Alors oui ensuite, on se retrouve comme certaines équipes US avec 300 contributeurs à l'article. Bon, ça dilue d'autant sa « valeur ». Mais je trouve normal qu'on crédite les gens qui permettent de faire avancer un sujet.
[1] Oui parce que bon, les chercheurs qui clament que « on se fout du code, on fait de la recherche, pas du génie logiciel », c'est vaguement gonflant, notamment lorsque des collègues veulent ensuite réexploiter les résultats pour aller plus loin. Oui, c'est du vécu.