En effet, avec la récente intégration de ordonnanceur O(1) de Ingo Molnar, associée à la toute nouvelle bibliothèque sponsorisée par Red Hat de support natif des threads POSIX (Native POSIX Thread Library), le noyau se montre capable de créer et détruire sur un « vieux » IA-32 dual 450MHz PII Xeon 100 000 threads en 2,3 secs (avec jusqu'à 50 threads à tourner en même temps).
Même si concrètement aucune application n'utilise pour le moment autant de threads en parallèle, ce test montre surtout que ce nouveau design supporte bien mieux des changements d'échelle et est bien plus efficace (le même test prend 15 minutes sur un noyau non modifié).
La NPTL est appelée à être incluse à la bibliothèque GNU C quand elle sera jugée suffisamment stable.
NdM: Merci à MadCoder qui nous a proposé aussi cette nouvelle en indiquant également que des architectures powerPC récentes, il a même été réussi de lancer près d'un million de threads avec 200 qui tournaient en parallèle.
Aller plus loin
- Linux: Native POSIX Threading Library (NPTL): (4 clics)
- Le White Paper de la NPTL: (3 clics)
- Une interview de Ingo Molnar (2 clics)
# Bravo les gars
Posté par let antibarbie = xp <- xp - 1 . Évalué à 10.
[^] # Re: Bravo les gars
Posté par Gaël Le Mignot . Évalué à 10.
[^] # Re: Bravo les gars
Posté par matiasf . Évalué à 10.
[^] # Re: Bravo les gars
Posté par lucio . Évalué à -10.
Ca devrait donc être disponible sur debian en 2012...
</humour>
# Ordonnanceur?
Posté par Anonyme . Évalué à 10.
[^] # Re: Ordonnanceur?
Posté par pasBill pasGates . Évalué à 10.
[^] # Re: Ordonnanceur?
Posté par let antibarbie = xp <- xp - 1 . Évalué à 10.
[^] # Re: Ordonnanceur?
Posté par Anonyme . Évalué à 6.
[^] # Re: Ordonnanceur?
Posté par pasBill pasGates . Évalué à 10.
[^] # Re: Ordonnanceur?
Posté par Gaël Le Mignot . Évalué à 10.
[^] # Re: Ordonnanceur?
Posté par Alan_T . Évalué à 10.
[^] # Re: Ordonnanceur?
Posté par PLuG . Évalué à 10.
[^] # Re: Ordonnanceur?
Posté par dinomasque . Évalué à 0.
BeOS le faisait il y a 20 ans !
[^] # Re: Ordonnanceur?
Posté par Matafan . Évalué à 0.
[^] # Re: Ordonnanceur?
Posté par LupusMic (site web personnel, Mastodon) . Évalué à -1.
[^] # Re: Ordonnanceur?
Posté par Gaël Le Mignot . Évalué à 10.
[^] # Re: Ordonnanceur?
Posté par Alan_T . Évalué à 8.
[^] # Re: Ordonnanceur? -1
Posté par Gloo . Évalué à -5.
[^] # Re: Ordonnanceur?
Posté par pasBill pasGates . Évalué à 10.
[^] # Re: Ordonnanceur?
Posté par tene . Évalué à 10.
Je me posais quelques questions, il semble évident que pousser à l'extrème le O(1) d'Ingo écrase ce qui existe, mais qu'en est-il avec un nombre de thread restreint (car dans ce cas la complexité théorique n'est plus la seule à compter, mais également le temps d'exécution de l'algo, si un passe de cet algo prend 10ms tandis que l'autre en O(n) prends 1ms... il faut plus de 10 threads pour que cela deviennent interessant)? Est-ce meilleurs que ce qu'il y'a actuellement? nettement meilleurs? En bref, verra-t-on la différence quand on fera autre chose qu'un bench?
[^] # Re: Ordonnanceur?
Posté par Guillaume POIRIER . Évalué à -3.
[^] # Re: Ordonnanceur?
Posté par Gaël Le Mignot . Évalué à 10.
[^] # Re: Ordonnanceur?
Posté par Code34 (site web personnel) . Évalué à 10.
[^] # Re: Ordonnanceur?
Posté par François Romieu (site web personnel) . Évalué à 0.
dans la rubrique bibliographie:
UNIX Systems for Modern Architectures: Symmetric Multiprocessing and Caching
par Kurt Schimmel chez Addison-Wesley.
A lire avant de coder avec des threads ou en environnement multitache.
--
Ueimor
[^] # Re: Ordonnanceur?
Posté par Anonyme . Évalué à -4.
[^] # Re: Ordonnanceur?
Posté par Code34 (site web personnel) . Évalué à 3.
[^] # Re: Ordonnanceur?
Posté par Stephane Marchesin (site web personnel) . Évalué à 8.
[^] # Re: Ordonnanceur?
Posté par Code34 (site web personnel) . Évalué à -2.
Tout ça me fait penser au bel écran bleu ...
J'ai fais un superbe screenshot hier sur une box slack/kde, je vais vous laisser le soin de l'apprecier:
http://membres.lycos.fr/code34/images/winxp.png(...)
@+
code34
[^] # Re: Ordonnanceur?
Posté par tene . Évalué à 10.
Stop 0x0000007B or INACCESSIBLE_BOOT_DEVICE
This Stop message, also known as Stop 0x7B, indicates that Windows 2000 lost access to the system partition during the startup process. This error always occurs while the system is starting and cannot be debugged because it generally occurs before the operating system has loaded the debugger.
[-1 parce que HS, y'a pas de scheduler chargé quand on est arrivé que là...;-)]
[^] # Re: Ordonnanceur?
Posté par Code34 (site web personnel) . Évalué à -5.
"Comme windows ne gère pas le bug, il n'a pas démarré et tu as un beau message d'erreur de type 0x0000007B ..."
Heureusement, tout est bien expliqué sur la page bleue: "Pour résoudre le bug, démarrez windows".
En clair, si vous voyez cette page et que vous ne tournez pas sous autre chose que Xp: vous êtes mal ;))
[-1 parce que HS, y'a pas de scheduler chargé quand on est arrivé que là...;-)]
Et oui, tout le monde le sait: l'ordonnanceur sous xp est directement intégré dans internet explorer.
@+
Code34
[^] # Re: Ordonnanceur?
Posté par wismerhill . Évalué à 4.
Si les win 9x étaient préemptifs, alors il y avait un appel système qui permet à un programme de bloquer tout le système en l'appellant.
</sarcasme>
[^] # Multitâche préemptif
Posté par Moby-Dik . Évalué à 6.
Et quelques années d'avance sur Macintosh ;-).....
# rappel: les native threads clone() existent deja et sont très rapides
Posté par free2.org . Évalué à 10.
[^] # Re: rappel: les native threads clone() existent deja et sont très rapides
Posté par Samuel Pajilewski . Évalué à 9.
[^] # Re: NOUVELLE FAQ
Posté par free2.org . Évalué à 1.
http://www.tldp.org/FAQ/Threads-FAQ/(...)
On peut y trouver de nombreuses bibliotheques de threads dont plusieurs sont compatibles POSIX:
http://www.tldp.org/FAQ/Threads-FAQ/ThreadLibs.html(...)
Certaines implémentent leur propre ordonnanceur dans le user space pour assurer une compatibilité totale avec POSIX.
Mais actuellement les plus rapides sont obligées de passer par les kernel-threads et donc clone()
http://www.tldp.org/FAQ/Threads-FAQ/Comparison.html(...)
[^] # Re: rappel: les native threads clone() existent deja et sont très rapides
Posté par Guillaume POIRIER . Évalué à 9.
# 100 000 en parallele !
Posté par Benjamin . Évalué à 10.
[^] # Re: 100 000 en parallele !
Posté par zeDek . Évalué à 10.
[^] # Re: 100 000 en parallele !
Posté par wismerhill . Évalué à 10.
[^] # Re: 100 000 en parallele !
Posté par zeDek . Évalué à 10.
[^] # Re: 100 000 en parallele !
Posté par Billou57 . Évalué à 10.
[^] # Re: 100 000 en parallele !
Posté par Guillaume POIRIER . Évalué à 10.
[^] # Re: 100 000 en parallele !
Posté par fasthm . Évalué à -4.
La gent féminine, pas la "gente", pas de "e" ! La gent féminine ! Et ça se prononce comme "gens". Pas "jante".
# Le free a peur du proprio
Posté par matiasf . Évalué à 10.
[^] # Re: Le free a peur du proprio
Posté par Beretta_Vexee . Évalué à 10.
[^] # Re: Le free a peur du proprio
Posté par Marc (site web personnel) . Évalué à -3.
[^] # Re: Le free a peur du proprio
Posté par Yusei (Mastodon) . Évalué à 10.
[^] # Re: Le free a peur du proprio
Posté par matiasf . Évalué à 10.
[^] # Re: Le free a peur du proprio
Posté par jeanmarc . Évalué à 7.
D'où le nouveau combat inutile dans lequel MDI engage une bonne partie de la communauté.
D'un côté, tu as un attrapesourcenigaud que tu ne dois absolument pas lire et de l'autre tu permets à tout le monde d'étudier les tiennes. Qu'est-ce qui empêche microsoft d'intenter un procés dés qu'il voit quelquechose de ressemblant dans les sources de mono? Pas les sous ni l'honnêteté en tout cas.
De plus, une personne qui apprécierait mono sous linux ne sera-t-elle pas tentée d'aller voir chez le créateur de l'original pour aller plus loin?
[^] # Re: Le free a peur du proprio
Posté par pasBill pasGates . Évalué à 1.
[^] # Re: Le free a peur du proprio
Posté par Yusei (Mastodon) . Évalué à 0.
Sans ces détails je ne peux pas trop te répondre. Si l'interdiction concerne la GPL ou autres licences avec copyleft ça se comprend, de peur que du code sous copyleft se retrouve dans leurs softs à leur insu. Si ça ne concerne pas le copyleft c'est différent.
[^] # Re: Le free a peur du proprio
Posté par zeDek . Évalué à 10.
# [HS ?] Ordre de complexité d'un alogrithme
Posté par zeDek . Évalué à 10.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Benjamin . Évalué à 10.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par zeDek . Évalué à 5.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Benjamin . Évalué à 3.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Manuel Menal . Évalué à 8.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Nicolas Boulay (site web personnel) . Évalué à -4.
Essait plutot, "algorythme en C" de je ne sais plus trop qui très didactique.
nicO
"La première sécurité est la liberté"
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Manuel Menal . Évalué à 7.
Bien entendu, ça n'est probablement pas le bouquin le plus adapté pour un étudiant qui commence juste l'algorithmique, ou un autodidacte qui veut apprendre quelques algorithmes classiques qu'il pourrait employer dans ses programmes personnels. Pas plus que ce n'est adapté pour quelqu'un intéressé par la "théorie des algorithmes". Mais en revanche, pour quelqu'un qui veut comprendre parfaitement l'analyse des algorithmes - et dispose d'un niveau de maths correct, c'est très adapté. Et zeDek m'avait l'air motivé .. :-)
[^] # Commentaire supprimé
Posté par Anonyme . Évalué à 1.
Ce commentaire a été supprimé par l’équipe de modération.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par RB . Évalué à 10.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par zeDek . Évalué à 3.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par PLuG . Évalué à 3.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Gaël Le Mignot . Évalué à 10.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Alan_T . Évalué à 8.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Gaël Le Mignot . Évalué à 7.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Alan_T . Évalué à 2.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par PLuG . Évalué à 5.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par boubou (site web personnel) . Évalué à 4.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Gaël Le Mignot . Évalué à 9.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Alan_T . Évalué à -2.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par harbort . Évalué à 7.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Stephane Marchesin (site web personnel) . Évalué à 9.
Et si on veut un tri basé sur des comparaisons on a les tris qui s'occupent d'abord des bits de poids fort puis des bits de poids faibles de ton entier, ça donne des complexités comme O(n*log(log(n))), ça doit aussi se trouver sur google.
En fait, le tri O(n*log(n)) est optimal avec quelques hypothèses :
- tu fais le tri in-situ
- tu as une fonction de comparaison dont tu ne connais pas les propriétés à priori
- tu as juste le droit de modifier ton tableau avec une fonction inverse(a,b) qui... inverse a et b.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par »-(¯`v´¯)-» . Évalué à 2.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Manuel Menal . Évalué à 10.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Alan_T . Évalué à 10.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par zeDek . Évalué à 3.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par harbort . Évalué à 8.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par harbort . Évalué à -3.
[^] # celui la je lai compris
Posté par snurpsss . Évalué à 2.
mon avis est que Alan_T merite un point de plus pour avoir expliquer a un neuneu un algo de base ( tu veux pas m expliquer le quicksort maintenant steup .
Enfin sans rire c vrai que c passionnat .
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Antoine . Évalué à 4.
[^] # PS : Heapsort
Posté par Antoine . Évalué à 6.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Alan_T . Évalué à -4.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Gaël Le Mignot . Évalué à 10.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Alan_T . Évalué à -2.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Gaël Le Mignot . Évalué à 3.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Alan_T . Évalué à -2.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Gaël Le Mignot . Évalué à 4.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Pat _ . Évalué à 0.
O(f)=g signifie que f/g est borné... pas besoin de tendre vers quoi que ce soit.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Pat _ . Évalué à 1.
g=O(f) , g/f borné.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Alan_T . Évalué à 6.
Par exemple, le test de primalité est P-complet(polynomial), le problème du voyageur de commerce est NP-complet (non polynomial), le problème de l'accessibilité dans un automate temporisé est P-space complet (polynomial en espace, on se fiche du temps), la résolution d'un système d'inéquations Diophantiennes est EXP-Time complet (exponentielle en temps), etc...
Tous ces problèmes peuvent avoir des algorithmes différents mais aucun algorithme ne peut avoir une complexité plus basse que la classe de complexité à laquelle appartient le problème. Maintenant, si tu considères le nombre d'opérations au pire cas, les algorithmes varient beaucoup, mais l'intéret est de considérer des problèmes et non des algorithmes. Évidemment, lorsque tu résouds un problème avec un algorithme calculer la complexité de ton algorithme te permet de voir si tu résoud de façon 'efficace' ou non ton problème (en gros, ton algorithme doit appartenir à la même classe de complexité que ton problème).
Par exemple, résoudre le problème du tri par bubble sort est une mauvaise idée car tu est au-dessus de la complexité du problème du tri (sans hypothèse sur les données).
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par boubou (site web personnel) . Évalué à 10.
Pour mémoire, NP veut dire nondeterministe polynomial...
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Alan_T . Évalué à 4.
J'ai dit ça pour aller plus vite.
Pour info, la classe NP regroupe l'ensemble des problèmes dont une entrée donnée peut être validée ou invalidée en temps polynomial.
par exemple, pour SAT (satisfiabilité d'une formule logique), si on se donne un ensemble de valeur booléennes, on peut savoir si la réponse est 0 (false) ou 1 (true) en temps polynomial. Par contre, si on se retrouve avec 0 (false), il est difficile de savoir si la formule est satisfiable ou non.
Là, tu ne pourra pas dire que je n'ai pas été précis, mais va écrire ça dans des parenthèses !!! :-)
J'ai l'impression que les gens sont vachement sensibles ici ! 8-)
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Antoine . Évalué à 1.
[^] # Turing
Posté par Antoine . Évalué à 2.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par matiasf . Évalué à -2.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Alan_T . Évalué à -3.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par matiasf . Évalué à -2.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Gaël Le Mignot . Évalué à 5.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par ldng . Évalué à 2.
extrait :
"Les notation que nous utilisons pour décrire le temps d'execution asymptotique d'un algorithme sont définies en termes de fonctions, dont le domaine est l'ensemble des entiers naturels. De telles notations sont pratique pour décrire la fonction T(n) du temps d'executiondans le pire des cas, qui n'est en général définique sur des tailles d'entrées entières. Cependant, il est parfois avantageux d'étendre abusivement la notation asymptotique, et ce de plusieurs manières différentees(...) Mais il est important de comprendre la signification précise de la notation, de sorte q'en en abusant, on n'en mésus pas.
(...)
La notation \Theta borne une fonction asymptotique à la fois par excès et par défaut. (...) De même que la notation O (grand ô) fournit une borne asymptotique supérieur pour une fonction, la notation \Omega fournit une borne asymptotique inférieur.(...) La borne supérieur asymptotique fournie par la notation O peut être ou non asymptotiquement approchée.(...)On utilise la notation o pour signifier que la borne supérieure n'est pas asymptotiquement approchée.(...) Par analogie, la notation \omega est à la notation \Omega ce que la notation o est à la notation O. On utilise la notation /omega pour indiquer une borne inférieure qui n'est pas approchée asymptotiquement."
Même en étant nul en math et en ne connaissant pas cet outil (comme moi), après avoir lu ce que je viens de citer, je pense que tu as tord et qu'Alan_T à raison quand il dit que tu confond complexité et développement limité. Le second est un outil utilisé par le premier.
Le bouquin est évidement bien plus détaillé, j'ai coupé pour mettre les choses en valeur.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par oliv . Évalué à 10.
ou bien ça a quelque chose à voir avec un mec qui s'appelait Landau:
http://mathworld.wolfram.com/LandauSymbols.html(...)
C'est vous qui voyez.
-1 car complètement con ce que je raconte
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Marc (site web personnel) . Évalué à 6.
http://dmawww.epfl.ch/rose.mosaic/fr/cours/algorithmique/index.html(...)
Ce sont des notes de cours fortement inspiré de 'Algorithms in C" de R.Sedgwick; regarde en particulier le cours 11 :)
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.