« Le plus vieux métier du mondeLa complainte du progrès »

Et paf, la racine du générateur aléatoire !

17.08.10 | par Le Grincheux | Catégories: Mauvaise humeur, Je hais l'informatique, Matheux pervers

Faire accroire à des informaticiens barbus qu'ils peuvent remplacer des matheux obtus à tendances perverses est une croyance trop répandue. Je me demandais depuis quelque temps pourquoi l'un des mes algorithmes ne donnait pas le même résultat selon qu'il était lancé avec un seul fil d'exécution ou avec plusieurs. En disséquant une bibliothèque mathématique — GSL 1.14 pour ne pas la citer —, je viens de m'apercevoir que les générateurs aléatoires ne résistent pas à la création de fils d'exécution parallèles. En relisant la documentation en long, en large et en travers, je n'arrive pas à trouver le moindre début d'information sur le fonctionnement des générateurs aléatoires dans un processus multithreadé. Visiblement, cela doit couler de source à moins que les concepteurs de ladite bibliothèque ne se soient jamais posé la question.

Pourtant, il serait de bon goût que les concepteurs de cette bibliothèque s'assurent que leurs générateurs suivent une statistique aléatoire connue et conforme quel que soit le nombre de fils d'exécution parallèles dans un processus et surtout quel que soit le nombre d'appel au générateur. En d'autres termes, il serait normal que la bibliothèque utilise un thread spécifique dans lequel tournerait ledit générateur et qui renverrait à chaque fil d'exécution effectuant une requête sur ce générateur une variable aléatoire correcte.

Ce n'est pas exactement comme cela qu'est codée cette bibliothèque. À chaque nouveau thread, c'est à l'utilisateur de cloner son générateur en le réinitialisant avec la valeur de la graine du thread père ou d'en réinitialiser un. Dans le premier cas, tous les threads fils risquent fort de tirer la même séquence, dans le second cas, le côté aléatoire sera limité par l'aléa disponible sur le choix de la graine lors de la réinitialisation. La qualité des variables aléatoires tirées dans des threads parallèles s'en ressent. À quoi sert donc l'utilisation d'un générateur aussi performant qu'un ranlux389 si l'utilisateur est contraint de le réinitialiser dans chaque thread ? Visiblement, cela ne semble pas gêner les concepteurs de GSL. Je ne suis même pas sûr qu'ils soient conscients de leur boulette. Ils ont dû sauter des pages dans leur manuel d'analyse numérique…

Pire, je serais assez curieux de connaître le niveau de compréhension mathématique de l'utilisateur de base de ces fonctions. J'ai comme l'affreuse impression que l'immense majorité d'entre eux ne se pose même pas la question, n'ayant pas la formation mathématique suffisante. J'ai trouvé le pot aux roses parce que j'ai une certaine habitude, une solide culture mathématique, que j'ai vu un résultat de calcul utilisant ces fonctions pour le moins étrange, et que j'ai la possibilité et les connaissances pour démonter la bibliothèque en question et en comprendre le fonctionnement.

Une fois le problème diagnostiqué, il fallait aussi corriger le programme utilisant ces fonctions, ce qui n'a pas été une mince affaire et s'est terminé par l'utilisation d'interruptions logicielles.

Nous avons donc d'une part une bibliothèque prise comme une boîte noire par la plupart des développeurs et un algorithme utilisant pour argent comptant un certain nombre des fonctions fournies par cette bibliothèque. Rien dans la documentation ne laisse entrevoir les limitations de ces fonctions en environnement parallèle ni ne met en garde l'utilisateur contre une mauvaise utilisation due à l'implantation de ces fonctions. Nous obtenons d'autre part des résultats de calculs complètement aberrants sans aucune raison apparente. Mais comme le développeur a pris soin de spécifier au début de son programme #define _REENTRANT, l'honneur est sauf.

L'utilisation de bibliothèques spécialisées n'est donc pas une chose aussi positive qu'on veut bien nous le faire croire. Le résultat d'un programme est autant lié à la propre qualité de son code qu'à celles des bibliothèques utiliseés. Il faut de plus ou avoir une confiance absolue en les concepteurs desdites bibliothèques, ou avoir assez de connaissances pour tester leurs différentes fonctions et les pousser dans leurs retranchements.

Le corrolaire immédiat est qu'on ne devrait utiliser une bibliothèque qu'à partir du moment où on pourrait l'écrire soi-même. Mais quel est le développeur qui agirait encore comme cela de nos jour ?

 

2 commentaires

Evaluations des utilisateurs
5 étoile:
 
(1)
4 étoile:
 
(0)
3 étoile:
 
(0)
2 étoile:
 
(0)
1 étoile:
 
(0)
1 note
Evaluation moyenne des utilisateurs:
5.0 stars
(5.0)
Naïf
5 stars

En lisant votre billet, je me pose une série de questions plus ou moins bêtes sur les suites de nombres aléatoires:
1. une suite extraite de manière aléatoire d’une suite de nombre aléatoire est-elle aléatoire avec la même loi?

2. la suite extraite qui complète la précédente est-elle aléatoire de même loi et indépendante de la précédente?

3. l’instanciation des valeurs aléatoires que vous préconisez produit-elle nécessairement des suites de nombres aléatoires indépendantes?

Je me pose ces questions parce qu’il me semble assez évident qu’il est possible d’extraire d’une suite de nombres aléatoires qui suit une loi normale sur [0,1] une suite strictement croissante dont la distribution ne suivrait pas la même loi normale.

17.08.10 @ 21:13
Commentaire de: Le Grincheux

Je n’ai pas réfléchi plus que ça au point numéro 1. Le résultat sera aléatoire, mais je ne vois pas pourquoi sa loi serait la même que celle de la variable initiale.

Je ne vois pas ce que vous voulez dire en parlant d’une “suite extraite qui complète la précédente".

Pour répondre au troisième point, il ne faut pas perdre de vue que la génération des nombres aléatoires est faite à l’aide de séquences pseudo-aléatoires qui sont des machines à états plus ou moins compliquées et satisfaisant à un certain nombre de lois statistiques. Ces générateurs sont déterministes. Utiliser le même générateur avec des graines différentes n’aboutit pas forcément à des suites indépendantes, surtout si on les regarde longtemps.

Quant à votre conclusion, le “assez évident” ne me semble pas du tout trivial parce que cette perforation n’est pas aléatoire mais corrélée au générateur initial. Je ne vais pas me lancer là tout de suite dans la démonstration parce que j’ai sur le feu un tas d’autres choses beaucoup plus urgentes à faire… Des histoires tournant autour de semget() foireux dans un code informatique…

18.08.10 @ 10:10


Formulaire en cours de chargement...