ENIB LANG-C Tr_04 - Entraînement sur les chapitres 10_Maths, 11_FnctPtr et 12

{1} Organisation

{2} Génération pseudo-aléatoire dans une plage de valeurs entières

Le module random sert à fournir quelques fonctionnalités autour de la génération pseudo-aléatoire.

La fonction Random_seed() n'attend aucun paramètre et ne renvoie aucun résultat.
Elle se charge d'initialiser la graine du générateur pseudo-aléatoire standard à partir de la seconde courante.

La fonction Random_int() attend deux paramètres entiers qui sont considérés comme les limites basse et haute d'une plage de valeurs et doit renvoyer un entier choisi aléatoirement dans cette plage (dont les bornes sont incluses). Elle doit tout d'abord s'assurer, uniquement lors de la phase de mise au point du programme, que la limite haute est bien supérieure ou égale à la limite basse.

Le programme principal doit réaliser le test des fonctionnalités précédentes.
La fonction Random_seed() sera invoquée une fois pour toutes depuis la fonction principale.
Une fonction test_random() sera réalisée et sera invoquée depuis la fonction principale ; après avoir affiché son nom, elle servira dans un premier temps à tester la fonction Random_int().
Pour ce faire, elle doit tirer quelques dizaines de valeurs dans une plage facilement identifiable et en afficher le résultat.
Une inversion des bornes de la plage de valeurs doit provoquer la détection de l'incohérence ; après avoir vérifié que c'est bien le cas il faudra conserver (pour mémoire) cette incohérence sous forme de commentaires.

Consignes :

Les règles de mise en œuvre et d'écriture recommandées dans toutes nos réalisations doivent impérativement être respectées.
Seules les fonctions de test produisent des affichages ; les fonctions du module rendent leur service silencieusement.

Aide pour l'entraînement

{3} Permutation aléatoire d'un tableau

Le module random doit être complété par une nouvelle fonction Random_shuffle() dont le rôle sera de permuter les éléments d'un tableau de manière aléatoire.
Ce tableau peut contenir des éléments d'un type quelconque ; son adresse sera donc transmise par un pointeur de type indéterminé et, en plus de son nombre d'éléments, il faudra transmettre un autre entier indiquant la taille en octets des éléments.

La réalisation de cette fonction consiste à utiliser l'arithmétique des pointeurs pour progresser dans le tableau selon le nombre d'octets constitutifs d'un élément.
Pour chaque position dans le tableau, selon une progression croissante, il faut choisir aléatoirement quel élément viendra y prendre place.
Ce choix se fait parmi tous les éléments compris entre la position courante et la position du dernier élément du tableau, grâce à la fonction Random_int().
Une fois l'élément choisi, il faut le permuter avec celui se trouvant à la position courante.
Pour ceci, une fonction à usage interne au module pourra être réalisée et invoquée afin de faciliter la permutation des octets constitutifs des deux éléments à permuter.

Le programme principal doit réaliser le test de cette nouvelle fonctionnalité en complétant la fonction test_random().
Pour ce faire, elle doit :

créer un tableau d'entiers qui soient initialisés d'une manière remarquable (dans l'ordre croissant par exemple),
en afficher le contenu,
invoquer la fonction Random_shuffle() sur ce tableau,
en afficher à nouveau le contenu pour vérifier que ses éléments ont bien été permutés aléatoirement.

La même vérification doit également être effectuée avec un autre tableau contenant des éléments d'une taille différente (des réels en double-précision par exemple).

Consignes :

Les règles de mise en œuvre et d'écriture recommandées dans toutes nos réalisations doivent impérativement être respectées.
Seules les fonctions de test produisent des affichages ; les fonctions du module rendent leur service silencieusement.

Aide pour l'entraînement

{4} Mesure de performances

Le module timing sert à effectuer des mesures de performances sur des opérations élémentaires.
Il s'agit de répéter un très grand nombre de fois des opérations qui concernent les éléments de tableaux, tout en mesurant la durée écoulée.
Nous prévoyons de manipuler des données de différents types avec des opérations variées mais dans tous les cas la démarche de mesure des performances est similaire : un algorithme générique sera donc réalisé.

Tous les traitements à mesurer seront réalisés par des fonctions qui consultent un tableau servant de source, en combinent éventuellement les éléments avec un argument désigné par un pointeur, et inscrivent le résultat de chaque opération dans un tableau servant de destination.
Les pointeurs en question seront transmis comme des pointeurs génériques que chaque fonction concernée convertira vers le type de données qu'elle manipule.
Inventez alors, dans le fichier d'en-tête timing.h, un type nommé Timing_Function désignant un pointeur sur fonction attendant les trois pointeurs évoqués précédemment, ainsi qu'un entier indiquant le nombre d'éléments des tableaux, et ne renvoyant aucun résultat.

Le module timing définira la fonction suivante qui nous servira à relever le temps afin de calculer des durées moyennes de traitement (en relevant le temps avant et après).

#include <stdio.h>
#include <sys/time.h>

double // seconds (1e-6 precision) since 1970/01/01 00:00:00 UTC
Timing_now(void)
{
  struct timeval tv;
  gettimeofday(&tv, NULL);
  return (double)tv.tv_sec+1e-6*(double)tv.tv_usec;
}

Ce même module doit maintenant réaliser une fonction Timing_measure() recevant en paramètres :

un pointeur sur fonction correspondant au type Timing_Function,
toutes les informations qui devront lui être transmises lors de l'usage d'un tel pointeur de fonction,
le nombre de répétitions des invocations de la fonction désignée à effectuer entre chaque mesure du temps,
la durée en secondes (sous la forme d'un réel) jugée significative pour arrêter la répétition des mesures.

Cette fonction renverra comme résultat une performance exprimée sous la forme d'un réel indiquant le nombre moyen de giga-opérations par seconde constaté.
Son algorithme sera le suivant :

• tant que la durée choisie n'est pas écoulée :
  | • pour le nombre de répétitions choisi :
  |   | • invoquer la fonction passée par pointeur
  | • incrémenter le nombre d'itérations
• milliards_d_opérations = 1e-9 × nombre_de_répétitions × nombre_d_itérations × nombre_d_élements_des_tableaux
• performance = milliards_d_opérations / durée_effectivement_écoulée

De telles mesures de performances moyennes n'ont de sens que si le nombre d'opérations exécutées est suffisamment grand ; c'est pour cette raison que les opérations sont effectuées pendant une durée assez longue.
La mesure du temps prend elle-même du temps et est susceptible de perturber la mesure ; c'est pour cette raison que nous répétons de nombreuses fois l'invocation de la fonction entre chaque mesure du temps.

Pour être en mesure de vérifier le bon fonctionnement de la fonction Timing_measure(), il faudra également compléter le module timing avec une fonction compatible avec le type Timing_Function.
Celle-ci peut par exemple lire les valeurs d'un tableau d'entiers servant de source, additionner chacun d'eux à l'argument entier désigné par le pointeur avant de stocker chaque résultat dans le tableau d'entiers servant de destination.
Cette fonction prendra bien entendu soin de convertir explicitement les pointeurs qu'elle reçoit en paramètres vers les bons types.

Le programme principal doit réaliser le test de cette fonctionnalité dans une fonction test_timing() invoquée depuis la fonction principale.
Après avoir affiché son nom, elle doit mettre en place les données nécessaires à l'utilisation de Timing_measure() sur l'opération que vous souhaitez mesurer.
Voici des ordres de grandeurs raisonnables pour effectuer ces mesures :

les tableaux devront contenir quelques centaines d'éléments,
le nombre de répétitions sera d'un millier,
la durée minimale de mesure sera d'une demi-seconde.

Relevez les performances après avoir réalisé le programme pour la mise au point, et recommencez en le compilant pour l'optimisation (make rebuild opt=1).

Consignes :

Les règles de mise en œuvre et d'écriture recommandées dans toutes nos réalisations doivent impérativement être respectées.
Seules les fonctions de test produisent des affichages ; les fonctions du module rendent leur service silencieusement.

Aide pour l'entraînement

{5} Comparaison des performances

Il s'agit maintenant de réaliser des mesures pour une variété d'opérations sur des entiers et des réels.
Ces opérations pourront être arithmétiques, logiques, bit-à-bit, mathématiques, et utiliser ou non un second argument (un pointeur nul sera transmis lorsque aucun second argument ne sera nécessaire).
Sans être nécessairement exhaustif, il faut chercher à mettre en œuvre des entiers et des réels sur des opérations qui illustrent des durées d'exécution assez nettement distinctes.

L'usage du préprocesseur pourra apporter une aide précieuse à la déclaration et à la définition de ces multiples fonctions que nous cherchons à mesurer ; elles sont en effet très semblables les unes aux autres.

La fonction test_timing() aura tout intérêt à être organisée pour systématiser l'invocation des multiples mesures en évitant de copier/coller le code (ce qui le rend difficilement modifiable).

Il est généralement recommandé de procéder à une courte mesure de performances dont on ignore le résultat avant chaque mesure dont on relèvera les performances ; on s'assure ainsi que la plateforme matérielle est dans l'état significatif pour la mesure dès le début de celle-ci (sortie d'un éventuel mode de repos...).

Consignes :

Les règles de mise en œuvre et d'écriture recommandées dans toutes nos réalisations doivent impérativement être respectées.
Seules les fonctions de test produisent des affichages ; les fonctions du module rendent leur service silencieusement.
Le relevés de performances doivent être effectués en activant les optimisations : make rebuild opt=1.

Aide pour l'entraînement

{6} Accès indirect aux données

Les conditions dans lesquelles nous avons effectué les mesures précédentes étaient assez particulière dans le sens où les opérations concernaient systématiquement des éléments contigus dans les tableaux.
Le processeurs modernes disposent généralement d'instructions dédiées (SIMD) qui permettent d'appliquer la même opération simultanément à des données contiguës.
Lorsque le compilateur peut prouver qu'il est correct de procéder ainsi (c'était le cas dans nos tests précédents) il reformule la boucle de traitement en en faisant usage (vectorisation) afin d'améliorer les performances globales (plusieurs opérations réalisées simultanément plutôt que séquentiellement).
Nous nous proposons ici de remanier légèrement les traitements pour que le compilateur ne puisse plus supposer que les données qu'il manipule sont contiguës et constater ainsi la différence de performance obtenue.

Le prototype du type de pointeur sur fonction Timing_Function doit maintenant être complété pour qu'une telle fonction puisse consulter en plus un tableau d'entiers.
Ce nouveau tableau désigne l'indice auquel doit avoir lieu l'opération (dans le tableau source comme le tableau destination).
Bien entendu, toutes les fonctions pouvant être désignées par un tel pointeur et la fonction Timing_measure() doivent être modifiées en conséquence.
Toutes les fonctions qui réalisent les opérations que l'on cherche à mesurer doivent désormais contenir deux algorithmes distincts :

si le tableau d'indices est un pointeur nul, il faut conserver l'ancien fonctionnement (tous les éléments dans l'ordre),
si au contraire le tableau d'indice est transmis, il faudra y lire à chaque itération l'indice des données concernées par l'opération courante.

Pour mettre en place ce tableau d'indices il faut :

lui donner le même nombre d'éléments que les tableaux de données,
l'initialiser dans la fonction de test en numérotant ses éléments dans l'ordre croissant,
le soumettre à la fonction Random_shuffle() afin de permuter aléatoirement cet ordre.

L'ensemble des mesures doit désormais être effectué avec et sans ce tableau d'indices afin de constater la différence de performances.

Consignes :

Les règles de mise en œuvre et d'écriture recommandées dans toutes nos réalisations doivent impérativement être respectées.
Seules les fonctions de test produisent des affichages ; les fonctions du module rendent leur service silencieusement.
Le relevés de performances doivent être effectués en activant les optimisations : make rebuild opt=1.

Aide pour l'entraînement