Ornthalas.net

Si vous me connaissez, le titre vous a peut-être mis la puce à l’oreille.

En effet je me suis remis à coder, après des mois et des mois d’abstinence, alors que je faisais principalement de la photo. Non je ne vais pas devenir photographe pro : ma vocation est dans l’informatique, mes compétences principales aussi.

Bien évidemment je continue la photo comme hobby, mais j’ai recentré mes priorités. J’ai des rêves, j’ai des idées. Je rêve un jour de pouvoir les concrétiser. Hélas, ca demande du temps, beaucoup de temps. Je suis intraitable sur la partie « réalisation technique » et je ne supporte pas le travail mal fait, instable et peu fiable. Je suis un maniaque de la complétion et je ne peux pas imaginer qu’une de mes réalisations ne fasse pas au moins le café (les geeks comprendront).

Je me suis donc remis sur un projet fondamental qui végétait depuis trop longtemps, la brique de base de tous mes projets rêvés, celle qui selon moi est indispensable : MPR. MPR pour Meta-Portable Runtime (et non pas multi-purpose room) se veut être une couche d’abstraction pas simplement au dessus du système, mais carrément au dessus des bibliothèques system-dependant ou simplement fondamentales.

Prenons un exemple. Il est selon moi inconcevable de développer un logiciel quelconque s’il n’est pas multilingue dès le  départ. Qui dit « multilingue » dit « utilisation de strings Unicode ». Quelle implémentation de strings Unicode semble solide et multi-plateforme ? Celle d’IBM peut-être : ICU. Oui mais voilà, si un jour ICU n’est plus supporté ? Si un jour ICU pose fondamentalement un problème dans son utilisation ? Si un jour sa licence change et qu’ICU devient proprio ? Si je veux porter mon appli sur une plateforme totalement exotique (prenons la PlayStation 1 pas exemple) alors qu’ICU ne la prend pas en charge ?

Dans ce cas, je vais devoir utiliser autre chose qu’ICU pour cette plateforme, voire me désolidariser entièrement d’ICU. La première solution semble être la moins douloureuse, mais quid des interfaces de cette bibliothèque qui sont utilisées partout dans le projet à porter ? Il faut repasser sur tout ? Tout modifier ?

C’est la que se situe MPR. Si l’application est développée au dessus de MPR, celle-ci fait office de couche d’abstraction et dissocie le code important (le logiciel) des interfaces des bibliothèques utilisées (les bibliothèques système, les strings Unicode, etc…).

Une fois que l’on a compris ca, on se rend compte de l’immensité du projet MPR, mais surtout du nombre incroyable d’interfaces à écrire pour tout abstraire. Ne parlons même pas de la documentation. C’est beaucoup trop long, surtout compte tenue de la verbosité du C++. Je travaille donc actuellement sur un générateur de C++ qui parse en entrée un fichier ayant une syntaxe plus simple et bien moins verbeuse pour en sortir du beau C++ bien rangé, optimisé et documenté.

MPR devrait (je pense) être rendue publique dans quelques temps sous une première forme ne gérant que quelques fonctionnalités indispensables (strings Unicode, fichiers et streams, interfaçage avec Python, threads), et ce sous une licence permissive (genre BSD ou quelque chose de proche).

Je mettrai surement de temps en temps des bouts de code ici, histoire d’avoir des avis. Stay tuned

Plusieurs personnes me contactent (comme tous les ans, je trouve ca rigolo) pour avoir des infos sur la bistromathique. Aujourd’hui, au milieu des Tek1 en panique, j’ai eu un étudiant en commerce qui m’a demandé plus de renseignements sur le  sujet de la bistro. Histoire que ca profite à tout le monde je vais répondre ici :

Alors, la bistro c’est pas un programme très simple à faire, du moins ca ne se code pas en une soirée. C’est demandé à des Epitech 1ère puis 2è année et des Epita 1ère année d’ingénierie. Ca demande de l’acharnement (chercher continuellement à faire plus performant, plus rapide, etc…). J’ai passé un mois dessus en me concentrant quasi à plein temps pour arriver à un truc fonctionnel et rapide.

Globalement il s’agit de faire une calculatrice qui fonctionne sur des nombres très grands (des millions de caractères) et sur toutes les bases jusqu’à 255 si je me souviens bien.

On prend un gros fichier en paramètre du programme avec un grand calcul, genre 123451821*4894/(12354+4813) , mais avec des nombres bien plus grands et des milliers d’opérations (genre on a des fichiers de plusieurs gigas à traiter) et on doit trouver le résultat le plus rapidement possible.

C’est à coder en C pur, C99 autorisé, toutes optimisations du compilateur autorisées aussi.

On doit donc tout d’abord lire le fichier d’input pour le stocker en ram, puis le parser (avec les 5 operations +-*/% et les deux parenthèses). On doit bien évidemment gérer les priorités. Une fois ceci fait, il faut résoudre le calcul et l’afficher (ou l’enregistrer dans un fichier).

Voila pour le sujet, bonne chance si vous voulez travailler dessus. C’est un projet passionnant et extrêmement formateur, mais il demande un peu de temps et de recherches.

J’avais fait un bel article sur mon ancien blog, avec toutes les idées que j’avais eues à la fin du projet d’Ing1 : Bistromathique. Comme plusieurs personnes m’ont demandé des infos sur le projet, je vais refaire cet article ici à partir des bribes trouvées dans la base de données que j’ai gardée.

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 en C sans Valgrind tellement c’est utile).

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