Pour nuancer un peu :
Le problème de la ROC est complexe, certes, et a mis des années à progresser. Mais aujourd'hui on peut dire que la reconnaissance des caractères imprimées est fiable -- pour un document de qualité bien évidemment, ce qui n'est pas toujours le cas, et jamais à 100%. Essaie un jour un logiciel comme abbyy fineReader, tu constateras des performances très bonnes, bien supérieures à celles de l'ancien logiciel hp aujourd'hui libéré.
Maintenant il est clair que je ne vois pas trop l'usage qu'on peut faire de la ROC dans un bureau de PME : scanner des pages manuellement n'est pas pensable ; les gains n'apparaissent qu'en automatisant toute la numérisation/reconnaissance, ce qui nécessite des investissements importants.
Je pense que la complexité du domaine et l'étroitesse des applications a limité les ambitions des programmeurs du libre. Rien que la construction d'une base d'apprentissage est un projet en soi. L'analyse du layout est un vaste domaine également, et si on se penche sur la segmentation (décomposer une ligne en mots, un mot en lettres), on sent vite des problèmes complexes apparaître... Finalement, la reconnaissance des lettres prises une par une paraît bien simple quand on prend la mesure du projet complet.
Quant à la reconnaissance des partitions musicales, le problème est là encore plus complexe qu'il n'y paraît, sans doute davantage même que la reconnaissance de texte (mais tout dépend de la complexité et de la qualité de la partition). La thèse de Bertrand Couäsnon était en ligne autrefois, j'en conseille sa lecture aux intéressés : http://www.irisa.fr/imadoc/HTML/B..Couasnon.fr.html mais impossible de remettre un lien dessus ?!
Tous ces problèmes sont résolus facilement par l'homme car ils nécessitent l'agrégation d'informations redondantes et disparates : toutes choses difficiles à formaliser pour l'ordinateur. La plupart des erreurs commises par les logiciels paraissent évidentes à l'humain ; pourtant si celui-ci doit expliquer les raisons de l'erreur, il va voir que ses explications vont chercher, au final, bien plus loin que ne peuvent "voir" les programmes.
> En tout cas on est bien d'accord que dans ce contexte la prédiction de branchement ne permettra pas d'optimiser le fork(), celui-ci n'apparaîssant pas assez souvent
La prédiction dynamique est dans ce cas inutile : le programmeur sait bien mieux que n'importe qui qu'une allocation mémoire a très peu de chances d'échouer. Ceci explique la mise en forme du code ci-dessus, extrait du noyau.
> Mais comment le dire au compilo ? Même après instrumentation ? Le compilo ne pouvant pas le deviner lui-même (c'est une info dynamique), il faut faire l'optimisation à la main ? (en gros changer nous même la condition ?)
C'est prévu : on instrumente le code, on exécute --> ceci génère un fichier de statistiques, et le compilateur sait relire ce fichier de statistiques lors d'une seconde compilation du même source.
Un exemple d'optimisation sur lequel j'étais tombé une fois : http://h21007.www2.hp.com/dspp/files/unprotected/linux/Optimization(...)
> dans la plupart des cas le programmeur met naturellement le test dans le "bon sens" (sous entend : on effectue un jmp si pas normal)
Oui, enfin je ne sais pas si tous les cpus suppose la condition vraie avant de l'évaluer, ou s'il la suppose fausse ? Et tout dépend aussi du code généré par le compilateur : il est libre d'inverser le test s'il inverse également les clauses then et else, etc.
> Bah me semble qu'il y a des architectures qui cherchent à prédire un branchement en fonction des instructions précédentes
Les processeurs récents contiennent un cache de prédiction, contenant des hash des adresses PC pour les instructions de branchement conditionnel, et pour chaque hash, le résultat précédent du test (sur 1 bit), voire le résultat "moyen" du test (compteur incrémenté / décrementé selon le résultat du test). Ainsi lorsqu'on retrouve l'intruction de branchement on peut choisir la bonne branche. Très utile pour une boucle effectivement : i=0 ; i<100 ; i++ : le résultat du test est le même 99 fois / 100. Notons qu'il peut y avoir une pollution du cache de prédicition si une autre instruction de branchement tombe dans la même case après la fonction de hashage... mais bon c'est mieux que rien.
Je ne pense pas qu'une fonction exécutée "rarement" [exemple de fork() ] n'aille pas en cache. En revanche, elle en sera évincée rapidement, car le code ne sera plus jamais lu.
Il est possible de "dire" au cpu quel est le résultat probable du test : le compilateur connait le processeur pour lequel il compile. Il sait donc, en cas de branchement conditionnel, quelle hypothèse est la plus rapidement exécutée par le cpu. En disant au compilateur qu'une condition est souvent réalisée, il génère le code qui va bien pour que le cpu, sans autre information (cf. branch prediction ci-dessus), prenne la branche la plus probable par défaut (avant d'avoir evalué le résultat du test). Si une condition est rarement réalisée, le compilateur pose test à l 'envers.
[ Note qu'on peut instrumenter le code pour déterminer automatiquement si une condition est souvent ou rarement réalisée, puis recompiler le code à partir de là, pour optimiser le binaire produit ].
Il y a moult publications sur le thème du "branch prediction", c'est important pour les perfos, quoique tu en penses.
Enfin, j'en reviens à mon message précédent auquel tu as répondu je trouve rapidement. Je persiste : si pour tous les tests les bonnes hypothèses sont prises par le cpu, et si le code traitant les branches non exécutées est rejeté "loin" du PC, donc non lu par le chipset de gestion de la ram, il n'y a pas de branchements lointains, et effectivement le cpu peut aller "tout droit", càd avoir toujours un pipeline rempli et des instructions à exécuter.
Je pense qu'on pourrait faire un petit programme de test qui montre les différences de perf en procédant ainsi. Si ça te tente, tiens-nous informé...
> Enfin comme quoi c'est possible de s'en passer de ces goto, c'est souvent plus verbeux mais on ne perd rien en duplication et pas grand chose en perfs.
Il faut voir aussi, dans l'exemple de code de copy_process() ci-dessus, que l'utilisation des goto permet de placer une quantité de code ~négligeable pour la gestion des erreurs ("goto xxx", instruction normalement jamais exécutée). Ainsi, le cache d'instructions cpu ne se remplit pas avec du code ~jamais exécuté : on gagne effectivement en performances.
Il est d'ailleurs prévu de pouvoir aider le compilateur en lui donnant le résultat probable du test, avec les macros "likely" ou "unlikely". Et ainsi le code s'exécute "tout droit" (mais ce n'est pas fait ici).
Linus encourage le goto dans les normes de codage du noyau. Mais bon, un noyau, c'est pas du code "normal", l'exemple est peut-être un peu mal choisi.
Pour en revenir au débat, je pense qu'un bon goto n'a pas son pareil, mais qu'il doit être utilisé avec parcimonie. De fait, à part le traitement des erreurs, je n'ai pas d'exemple où un goto est nécessaire.
La couche IDE a également été revue en profondeur.
Un commentaire sur le site du bench signale pertinemment que les améliorations peuvent provenir essentiellement de cette amélioration, dans la mesure où ce sont justement les tests qui sollicitent les I/O disques qui montrent les plus grands gains de performance.
Il aurait été intéressant de refaire le bench avec des disques SCSI, la supériorité du 2.6 pourrait être bien moindre.
[^] # Re: Très peu significatif
Posté par Laurent Morel . En réponse à la dépêche État des lieux de la reconnaissance de caractères libre (OCR). Évalué à 2.
Le problème de la ROC est complexe, certes, et a mis des années à progresser. Mais aujourd'hui on peut dire que la reconnaissance des caractères imprimées est fiable -- pour un document de qualité bien évidemment, ce qui n'est pas toujours le cas, et jamais à 100%. Essaie un jour un logiciel comme abbyy fineReader, tu constateras des performances très bonnes, bien supérieures à celles de l'ancien logiciel hp aujourd'hui libéré.
Maintenant il est clair que je ne vois pas trop l'usage qu'on peut faire de la ROC dans un bureau de PME : scanner des pages manuellement n'est pas pensable ; les gains n'apparaissent qu'en automatisant toute la numérisation/reconnaissance, ce qui nécessite des investissements importants.
Je pense que la complexité du domaine et l'étroitesse des applications a limité les ambitions des programmeurs du libre. Rien que la construction d'une base d'apprentissage est un projet en soi. L'analyse du layout est un vaste domaine également, et si on se penche sur la segmentation (décomposer une ligne en mots, un mot en lettres), on sent vite des problèmes complexes apparaître... Finalement, la reconnaissance des lettres prises une par une paraît bien simple quand on prend la mesure du projet complet.
Quant à la reconnaissance des partitions musicales, le problème est là encore plus complexe qu'il n'y paraît, sans doute davantage même que la reconnaissance de texte (mais tout dépend de la complexité et de la qualité de la partition). La thèse de Bertrand Couäsnon était en ligne autrefois, j'en conseille sa lecture aux intéressés : http://www.irisa.fr/imadoc/HTML/B..Couasnon.fr.html mais impossible de remettre un lien dessus ?!
Tous ces problèmes sont résolus facilement par l'homme car ils nécessitent l'agrégation d'informations redondantes et disparates : toutes choses difficiles à formaliser pour l'ordinateur. La plupart des erreurs commises par les logiciels paraissent évidentes à l'humain ; pourtant si celui-ci doit expliquer les raisons de l'erreur, il va voir que ses explications vont chercher, au final, bien plus loin que ne peuvent "voir" les programmes.
[^] # Re: Hmm :/
Posté par Laurent Morel . En réponse au journal Entretient du noyau Linux. Évalué à 2.
La prédiction dynamique est dans ce cas inutile : le programmeur sait bien mieux que n'importe qui qu'une allocation mémoire a très peu de chances d'échouer. Ceci explique la mise en forme du code ci-dessus, extrait du noyau.
> Mais comment le dire au compilo ? Même après instrumentation ? Le compilo ne pouvant pas le deviner lui-même (c'est une info dynamique), il faut faire l'optimisation à la main ? (en gros changer nous même la condition ?)
C'est prévu : on instrumente le code, on exécute --> ceci génère un fichier de statistiques, et le compilateur sait relire ce fichier de statistiques lors d'une seconde compilation du même source.
Un exemple d'optimisation sur lequel j'étais tombé une fois :
http://h21007.www2.hp.com/dspp/files/unprotected/linux/Optimization(...)
> dans la plupart des cas le programmeur met naturellement le test dans le "bon sens" (sous entend : on effectue un jmp si pas normal)
Oui, enfin je ne sais pas si tous les cpus suppose la condition vraie avant de l'évaluer, ou s'il la suppose fausse ? Et tout dépend aussi du code généré par le compilateur : il est libre d'inverser le test s'il inverse également les clauses then et else, etc.
[^] # Re: Hmm :/
Posté par Laurent Morel . En réponse au journal Entretient du noyau Linux. Évalué à 1.
Les processeurs récents contiennent un cache de prédiction, contenant des hash des adresses PC pour les instructions de branchement conditionnel, et pour chaque hash, le résultat précédent du test (sur 1 bit), voire le résultat "moyen" du test (compteur incrémenté / décrementé selon le résultat du test). Ainsi lorsqu'on retrouve l'intruction de branchement on peut choisir la bonne branche. Très utile pour une boucle effectivement : i=0 ; i<100 ; i++ : le résultat du test est le même 99 fois / 100. Notons qu'il peut y avoir une pollution du cache de prédicition si une autre instruction de branchement tombe dans la même case après la fonction de hashage... mais bon c'est mieux que rien.
Je ne pense pas qu'une fonction exécutée "rarement" [exemple de fork() ] n'aille pas en cache. En revanche, elle en sera évincée rapidement, car le code ne sera plus jamais lu.
Il est possible de "dire" au cpu quel est le résultat probable du test : le compilateur connait le processeur pour lequel il compile. Il sait donc, en cas de branchement conditionnel, quelle hypothèse est la plus rapidement exécutée par le cpu. En disant au compilateur qu'une condition est souvent réalisée, il génère le code qui va bien pour que le cpu, sans autre information (cf. branch prediction ci-dessus), prenne la branche la plus probable par défaut (avant d'avoir evalué le résultat du test). Si une condition est rarement réalisée, le compilateur pose test à l 'envers.
[ Note qu'on peut instrumenter le code pour déterminer automatiquement si une condition est souvent ou rarement réalisée, puis recompiler le code à partir de là, pour optimiser le binaire produit ].
Il y a moult publications sur le thème du "branch prediction", c'est important pour les perfos, quoique tu en penses.
Enfin, j'en reviens à mon message précédent auquel tu as répondu je trouve rapidement. Je persiste : si pour tous les tests les bonnes hypothèses sont prises par le cpu, et si le code traitant les branches non exécutées est rejeté "loin" du PC, donc non lu par le chipset de gestion de la ram, il n'y a pas de branchements lointains, et effectivement le cpu peut aller "tout droit", càd avoir toujours un pipeline rempli et des instructions à exécuter.
Je pense qu'on pourrait faire un petit programme de test qui montre les différences de perf en procédant ainsi. Si ça te tente, tiens-nous informé...
[^] # Re: Hmm :/
Posté par Laurent Morel . En réponse au journal Entretient du noyau Linux. Évalué à 1.
Il faut voir aussi, dans l'exemple de code de copy_process() ci-dessus, que l'utilisation des goto permet de placer une quantité de code ~négligeable pour la gestion des erreurs ("goto xxx", instruction normalement jamais exécutée). Ainsi, le cache d'instructions cpu ne se remplit pas avec du code ~jamais exécuté : on gagne effectivement en performances.
Il est d'ailleurs prévu de pouvoir aider le compilateur en lui donnant le résultat probable du test, avec les macros "likely" ou "unlikely". Et ainsi le code s'exécute "tout droit" (mais ce n'est pas fait ici).
Linus encourage le goto dans les normes de codage du noyau. Mais bon, un noyau, c'est pas du code "normal", l'exemple est peut-être un peu mal choisi.
Pour en revenir au débat, je pense qu'un bon goto n'a pas son pareil, mais qu'il doit être utilisé avec parcimonie. De fait, à part le traitement des erreurs, je n'ai pas d'exemple où un goto est nécessaire.
[^] # Re: Comparaison entre les noyaux 2.4.25 et 2.6.4
Posté par Laurent Morel . En réponse à la dépêche Comparaison entre les noyaux 2.4.25 et 2.6.4. Évalué à 2.
Un commentaire sur le site du bench signale pertinemment que les améliorations peuvent provenir essentiellement de cette amélioration, dans la mesure où ce sont justement les tests qui sollicitent les I/O disques qui montrent les plus grands gains de performance.
Il aurait été intéressant de refaire le bench avec des disques SCSI, la supériorité du 2.6 pourrait être bien moindre.