On voit encore régulièrement des optimisations pour des algorithmes de calcul, de compression, de rendu 2D et 3D, ... mais en ce qui concerne des techniques d'optimisation pour du code classique et non spécifique à des algorithmes particuliers, cela est beaucoup plus rare. C'est donc avec une certaine fierté que je vous présente la technique nommée D-loop dont votre humble serviteur est l'auteur :).

L'optimisation des boucles a fait l'objet de nombreuses études et plus particulièrement les boucles imbriquées (calcul matriciel, vectoriel, ...) où des méthodes permettant d'optimiser les accès mémoire ont été développées. Les boucles simples ont aussi fait l'objet de beaucoup d'attention afin d'optimiser le niveau de parallélisme, optimisations internes au microprocesseur et des compilateurs. Mais très peu a été fait ou tout simplement trouvé concernant les boucles contenant des conditions de branchement.

Cet article étant un peu spécial, il a la particularité que toutes les informations techniques et mathématiques concernant la technique D-loop se trouvent dans un fichier au format PDF. La raison en est que ce format est adapté pour diffuser D-loop à travers internet. Son autre particularité est qu'il est en anglais. Oui je sais, mais ainsi va le monde lorsqu'on veut communiquer à grande échelle. Toutefois si la demande d'une version française était très forte (quelques centaines) j'en ferais la traduction.

Toutefois je vais vous donner quelques infos qui ne se trouvent pas dans le PDF et qui sont donc spécifiques à la communauté francophone :).

Je travaille depuis plusieurs années sur des technologies temps réel et en particulier sur un analyseur syntaxique assez perfectionné et surtout d'une rapidité époustouflante. Pour parvenir à de tels résultats, j'ai du 1000 fois remettre l'ouvrage sur mon bureau, le triturer, le tordre et ce dans tous les sens. Au final j'ai mis au point quelques techniques d'optimisation de programmation qui m'ont permis d'avoir accès à des vitesses de traitement inconnues à ce jour. La technique D-loop est une de ces techniques

Maintenant ceux qui pensent que j'ai pu avoir une illumination quant à cette technique se tromperont lourdement. J'étais en train de chercher à optimiser une fonction destinée au script cgi d'Onversity. Manquant d'idées, j'ai commencé à relire tout le code d'Onversity pour voir si la lumière ne viendrait pas. Je suis tombé sur une forme de boucle que j'utilisais dans l'analyseur syntaxique. je l'ai appliquée et cela à fonctionné, cela a même très bien fonctionné avec un gain de près de 40%. Mais à ce moment là je n'avais toujours pas conscience d'avoir découvert une nouvelle technique d'optimisation. Ceci me fait d'ailleurs penser qu'il doit nécessairement exister à travers le monde d'autres développeurs qui ont pu utiliser cette forme de programmation, mais qui comme moi n'ont pas vu la possibilité de sa généralisation.

Ce n'est que par divers concours de circonstance que j'ai commencé à utiliser de plus en plus cette technique jusqu'au jour où, suite à une conversation avec des auteurs d'Onversity, je me suis aperçu que la technique que j'utilisais semblait s'appliquer étrangement à de nombreux problèmes. Pour en avoir le coeur net, je décidais de prendre une fonction aussi vieille que le langage C et sur laquelle existent de nombreuses recherches, la fonction Strstr(). Ma surprise a été totale quand les premiers résultats de vitesse d'exécution sont tombés. Ma fonction écrite dans un simple langage compilé battait des fonctions écrites et optimisées en assembleur.

Je décidais de voir si l'on pouvait la généraliser d'un point de vue théorique et de ce travail est née la technique D-loop. Voilà comment est née D-loop. De mon analyseur syntaxique puis de concours de circonstance ;).

Tout n'est pas dit dans le PDF, par exemple certains noteront la présence d'un chapitre 7.1 mais pas de 7.2 pourtant ce chapitre existe, mais pour des raisons de clarté (pour le pdf) je l'ai supprimé. Il concerne plusieurs astuces de programmation afin d'optimiser les codes utilisant la technique D-loop. D'autres aspects ne sont pas abordés dans le pdf, comme des exemples d'utilisation de D-loop pour d'autres fonctions très connues, comme les filtres de buffer de données ou encore l'exploitation de D-loop dans des cas particuliers qui peuvent amener à des gains atteignant dans tous les cas 50%.

Si vous souhaitez que je fasse une présentation de la technique D-loop dans votre fac ou école, n'hésitez pas ce sera avec plaisir que je me déplacerais. De même, si dans le cadre d'une entreprise cerains souhaitent que je forme des développeurs aux subtilités de cette technique j'en serais ravi.

En tant qu'auteur de cette technique et utilisateur acharné ;), je suis convaincu de son intérêt. Je prends donc mon baton de pélerin pour prêcher la bonne parole et je vous invite à en faire de même. Si vous n'êtes pas convaincu, contactez-moi et laissez-moi vous convaincre ;). Bien sûr, D-loop n'est pas universelle, mais lorsqu'elle est applicable les gains moyens dépassent à coup sûr les 10%.

Je tiens à remercier ici Julien Sebot, Patrice Arrighi, Frédéric Panico et Tanguy Fautré.