Bistromathique

Nous avons planché sur plusieurs projets en langage C depuis le début de l'année, mais un seul a réellement retenu mon attention : il s'agit de la Bistromathique. Qu'est ce que cela ? Il s'agit d'une calculatrice capable de travailler sur des grandes bases (ici on a implémenté jusqu'à la base 249) et sur des nombres entiers signés potentiellement infinis (nous nous sommes limités à une expression ayant pour taille maximale 4 294 967 295 caractères).

J'ai commencé par travailler sur une représentation en tableaux de caractères (tableaux d'entiers 8 bits non signés : des unsigned char* sur archi 32 bits), en implémentant l'addition, la soustraction et la multiplication scolaire, ainsi qu'un algorithme proche de celui de Knuth pour la division et le modulo. J'ai utilisé les tableaux en Big Endian pour faciliter les opérations commençant sur les poids faibles, et pour éliminer rapidement les 0 non-significatifs. De plus, le décalage à gauche étant plus souvent utilisé que le décalage à droite, cette représentation de chiffres était doublement intéressante.

Ma première grosse optimisation a été de récupérer les buffers déjà alloués pour les stocker dans une chaine de buffers vides. Mine de rien, j'ai multiplié par au moins 50 la vitesse de ma bistro avec cette astuce ! En effet, j'allouais pour chaque opérande de mon expression, ce qui faisait des milliers de mallocs ! Grâce à cette technique, sans même me casser la tête à trier les buffers vides dans la liste chainée, je suis descendu entre 10 et 25 mallocs sur tout le programme ! (Mes tests étaient composés d'expressions de 10 Mo et d'opérandes de 1 ko à 10 ko.)

J'ai ensuite transformé le programme pour qu'il utilise des tableaux d'entiers 32 bits non signés (unsigned long* ou unsigned int* sur archi 32 bits) et j'ai adapté l'addition et la soustraction. Voyant que les résultats étaient plus lents sur ceux-ci, j'ai abandonné cette voie de recherche (mauvaise pioche, j'aurais du continuer) : en effet, cette implémentation nécessite 3 parcours linéaires pour les additions et soustractions, mais accélère considérablement les multiplications !

Ensuite, pour accélérer ma multiplication, j'ai travaillé sur l'algorithme de Karatsuba. Malgré mes efforts sur la gestion mémoire, je n'ai pas pu empêcher l'allocation de deux structures de nombres et des chaines de caractères les accompagnant à chaque récursion de l'algorithme, ce qui a multiplié par 12 le nombre d'appels systèmes de mon programme sur mes tests. La conséquence de cela a été qu'en utilisant Karatsuba plutôt que la multiplication naïve, je doublais le temps de calcul.

Pressé par le temps, je me suis rabattu sur une optimisation de la multiplication naïve en utilisant seulement pour elle la représentation en tableaux d'unsigned long. Le gros point faible est qu'à chaque multiplication, je fais trois conversions : deux pour passer les deux opérandes en unsigned long*, et une pour repasser le résultat en unsigned char*. Malgré cela, mes résultats sur la multiplication naïve on été fulgurants (division par 9 à 18 du temps de calcul)

J'ai ensuite été contraint à rendre mon travail, timeout projet oblige.

Mes idées restantes si j'avais encore eu du temps :

• Repasser entièrement sur des tableaux d'unsigned long, tellement plus rapides pour les opérations complexes (multiplication, division et modulo).
• Retravailler Karatsuba notamment en allouant sur la pile plutôt que sur le tas à l'aide des tableaux dynamiques apportés par le C99 auquel nous avions droit
• Trouver une astuce pour calculer rapidement l'heuristique de mon algorithme de Knuth modifié avec la nouvelle représentation des nombres.
• Pouvoir gérer l'expression originale comme un buffer utilisable, donc pour cela déterminer les parties d'expression traitées pour utiliser cet espace mémoire obsolète : celui-ci était alloué à 10 Mo minimum, ca aurait été un gain considérable !
• Permettre deux représentations de nombres en parallèle avec conversion éventuelle selon le type d'opération à effectuer pour accélérer les calculs type addition/soustraction seulement lorsque les opérandes viennent de l'expression originale)

Au final, je peux dire que ce projet m'a énormément appris, tant sur la gestion mémoire que sur de nouveaux algos (parseur LL d'expression mathématique, Karatsuba, Knuth...) ou sur l'expérience du debug (maintenant je ne peux plus travailler sans Valgrind tellement c'est utile).

Note : Je ne peux pas donner le code source ici, simplement parce que d'autres épitéens ont des chances de tomber sur cette page alors qu'ils ont le projet a coder. Si certaines personnes veulent voir mon travail, qu'elles me contactent.

October 07

1