Un code propre est plus utile qu'un code efficace

Il fut un temps, avant que le développement de logiciels ne devienne mon métier, où la qualité d'un programme se jugeait, à mes yeux, à son efficacité : rapidité d'exécution, faible occupation mémoire, compacité du code[1]... Mais ça c'était avant. Je suis depuis longtemps convaincu que la clarté et la lisibilité sont des critères incomparablement supérieurs.
Est-ce un changement de point de vue dû à l'expérience ?

Dans une discussion sur le groupe google "Software Craftsmanship" intitulée "Optimizing for code readability vs efficiency", l'auteur initial explique que ses étudiants sont beaucoup plus attachés à l'efficacité et que faire passer le message d'une meilleure lisibilité n'est pas une tache aisée. Et pourtant, une meilleure lisibilité est souvent un passage obligé vers une meilleure efficacité comme le confirment plusieurs intervenants de la discussion.
Pourquoi ce message est-il si difficile à faire passer ?

Je voudrais apporter ici ma pierre à l'édifice. Je suis parti d'un défi de programmation sur codingame.com, celui de janvier 2013 nommé "La résistance"[2], et j'ai essayé de l'implémenter en pilotant mon développement par les tests, en favorisant la clarté de la conception et sans jamais essayer d'optimiser prématurément.

Il s'agit de décoder un message en morse, potentiellement très long (plusieurs milliers de signes 'point' et 'tiret') et dont les séparateurs entre les mots ne sont pas connus. On dispose pour cela d'un lexique des mots possibles (là aussi potentiellement plusieurs milliers de mots différents). Et on s'attend bien évidemment à ce que ce décodage soit très rapide.
Une précision s'impose avant d'entrer dans le sujet. La résolution de ce problème nécessite un choix de stratégie algorithmique. Ce n'est pas le TDD qui va me faire découvrir comme par magie la bonne stratégie à adopter.[3] La création d'algorithmes, ça relève du domaine de l'informatique théorique, pas du développement logiciel. Le TDD, lui, va me permettre d'implémenter le plus proprement possible l'approche que je choisirai.
Ceci étant acquis, mon choix se porte sur la stratégie la plus intuitive et faisant l'usage minimal de notions compliquées : parcourir de gauche à droite le message morse en recherchant toutes les solutions possibles.

Je commence par implémenter quelques fonctions utilitaires pour représenter une séquence morse et faire les conversions adéquates avec les chaînes de caractères. Rien de passionnant.
Le vrai boulot démarre en top-down. Je définis l'abstraction qui va me permettre de décoder un message morse : renvoyer un ensemble de toutes les séquences de mots correspondant à un message morse donné.

public enum Morse
{
  Dot,
  Dash
}

public interface IDecodeMessage
{
  IEnumerable<IEnumerable<string>> Decode (IEnumerable<Morse> message);
}

Je commence à piloter l'implémentation en utilisant les jeux de tests fournis par codingame.com. Il est important d'écrire les tests en utilisant des notions stables, en l'occurrence mes tests portent uniquement sur le contrat "I Decode Message" et ne font jamais appel à des détails d'implémentation. J'avais expliqué cette approche dans "Chacun cherche son TDD".
En faisant évoluer la méthode "Decode", je vois très rapidement un autre concept apparaître. C'est dû à l'aspect "organique" de la conception émergente (évoqué par ailleurs dans "Le logiciel, un organisme multicellulaire ?"). Une opération élémentaire de mon implémentation consiste à rechercher tous les mots du dictionnaire qui sont des candidats potentiels pour débuter une séquence morse donnée. Cette opération devient donc un contrat "I Find Words" dont l'implémentation sera découplée du décodage.
A cet instant je me retrouve avec un jeu d'interfaces qui restera stable pour le reste du développement (mais ça je ne le saurai qu'à la fin) :

public interface IDecodeMessage
{
  IEnumerable<IEnumerable<string>> Decode (IEnumerable<Morse> message, IFindWords thesaurus); 
  long Count (IEnumerable<Morse> message, IFindWords thesaurus);
}

public struct Starting
{
  public string Word;
  public int MorseLength;
}
  
public interface IFindWords
{
  IEnumerable<Starting> GetWordsStarting (IEnumerable<Morse> sequence);
}

On notera deux choses :

  • J'ai rajouté une méthode "Count" dans "I Decode Message". L'énoncé du défi ne porte que sur la détermination du nombre de solutions. Toutefois, dans la vraie vie, on sera plus intéressé par les résultats du décodage. Je fais donc le choix d'implémenter les deux aspects du problème.
  • La méthode "GetWordsStarting" du contrat "I Find Words" renvoie l'ensemble des mots qui pourraient se trouver au début de la séquence de morse donnée. Pour chacun de ces mots, elle renvoie aussi le nombre de signaux morse consommés dans la séquence.

A partir de là il faut faire un choix de priorité : continuer sur l'implémentation du décodage ou se focaliser sur la recherche de mots.
Je choisis une solution intermédiaire. Je vais écrire une implémentation simpliste de "I Find Words". Si elle est assez efficace, tant mieux, sinon elle me servira de fake pour écrire le décodage.
Je transforme ma panoplie de tests pour en créer une adaptée à "I Find Words" et j'écris une implémentation basique. Elle contient la liste des mots du dictionnaire et, pour chacun d'entre eux, la chaîne de caractères correspondant au code morse. A chaque appel de "GetWordsStarting", la liste entière est parcourue et les mots sont détectés par simple comparaison de chaînes de caractères morse. On peut sûrement faire plus efficace mais c'est simple et ça fonctionne - et c'est tout ce qui m'importe pour l'instant.

Je peux alors attaquer la partie décodage. A partir du jeu de tests initié précédemment, j'écris un décodeur qui procède par recherche en profondeur. Un curseur définit la profondeur courante et des appels récursifs permettent d'explorer les profondeurs suivantes. Un mécanisme de typage générique me permet de factoriser le code de recherche qui est désormais commun au décodage complet et à leur simple dénombrement.

Exemple : ......-...-..---.-----.-..-..-.. avec les mots HELL, HELLO, OWORLD, WORLD

Niveau 1
| ......-...-..---.-----.-..-..-..
| H   EL   L       ==> 2a
| H   EL   L   O   ==> 2b

Niveau 2a
| ......-...-.. | ---.-----.-..-..-..
| H   EL   L    | O  W  O  R  L   D

Niveau 2b
| ......-...-..--- | .-----.-..-..-..
| H   EL   L   O   | W  O  R  L   D

Sur des petits tests, tout cela fonctionne parfaitement. Cela se complique lorsque j'écris un test qui dénombre 65536 solutions car celui-ci prend près de 4 secondes pour sortir le résultat. J'ai deux pistes possibles d'optimisation : la recherche des mots ou le parcours en profondeur.
Je choisis de rester sur ce dernier car il me vient l'idée de mémoriser les résultats obtenus pour éviter de nombreux appels récursifs[4]. Pour cela j'écris une classe d'implémentation différente pour le même contrat "I Decode Message" mais cette fois en ajoutant un mécanisme de cache. Au fil de l'écriture, j'arriverai à mettre en commun une majorité de code entre les deux implémentations de parcours en profondeur.

Ce choix fait des merveilles. Le test qui passait en 4 secondes[5] tombe à 35 millisecondes[6]. Je peux alors attaquer le plus gros test fourni par le défi. Il contient un dictionnaire d'environ 10000 mots et il demande le décodage d'une séquence morse d'environ 10000 signes pour trouver un total de 57330892800 combinaisons.
Et là c'est la claque : le test passe en plus de 40 secondes. Heureusement que je n'ai pas commencé par ce test avec l'implémentation sans cache car elle serait probablement encore en train de tourner...

Il me reste une dernière piste d'amélioration : la recherche de mots. J'essaie d'utiliser une structure de donnée classique lorsqu'on veut avoir des recherches plus rapides : l'arbre.
Comme le montre le diagramme ci-dessous, je place les mots du dictionnaire dans une structure où, en partant de la racine, peuvent être rapidement trouvés tous les mots commençant une séquence de morse donnée. Par exemple, une séquence "dash dot" me donnera les mots "T", "TE" et "N" (s'ils font partie du dictionnaire, bien évidemment). Arbre

Ce dictionnaire en arbre est donc une implémentation alternative de "I Find Words".
Et le test qui prenait plus de 40 secondes[7] tombe à 130 millisecondes[8].

La démarche et les chiffres parlent d'eux-mêmes.
Une stratégie algorithmique étant fixée, le TDD et une approche du code systématiquement claire et lisible mettent en évidence les concepts importants d'un logiciel. Et en se basant sur ces concepts et les tests qui y sont associés, on peut bâtir, lorsqu'elle devient nécessaire, une stratégie d'optimisation pour rendre le logiciel plus efficace.
Cette approche est d'autant plus importante que

  • un logiciel évolue rarement dans un environnement figé. Dans l'exemple que l'on vient de voir, on pourrait, par exemple, imaginer un dictionnaire initialement chargé en mémoire à partir d'un fichier qui, du fait de sa mise à jour continuelle, évolue en un dictionnaire stocké dans une base de données. L'implémentation de "I Find Words" serait alors spécifique à notre base de données et indépendante des avancées réalisées sur la partie parcours en profondeur.
  • un logiciel n'a que rarement des fonctionnalités immuables. Toujours dans le logiciel ici présent, on pourrait imaginer un décodage des phrases qui tiendrait compte d'un contexte sémantique (par exemple, tel mot ne peut pas être suivi de tel ou tel autre mot). Là encore, il faudrait envisager des modifications qui seront d'autant plus aisées que les composants présents sont faiblement couplés.

Ecrire un logiciel ce n'est pas écrire un algorithme. On a besoin des fondements théoriques que la science informatique peut nous apporter sur les divers types d'algorithmes, sur leur complexité... Mais écrire un logiciel c'est se placer dans un contexte mouvant en vue de réaliser et faire évoluer un produit pour un utilisateur.
La plupart du temps cela nécessite de donner la priorité absolue à la maintenabilité du code. Il faut donc le garder propre car, dans la durée, c'est le seul moyen pour qu'il reste efficace.

Le code source complet en C# utilisé dans le billet est disponible sur github à l'adresse https://github.com/Oaz/Resistance/tree/code_propre.
Le schéma ci-dessous présente les principales interfaces et classes de ce code source. UML

Notes

[1] A titre d'exemple, voici un bout de code écrit en 1985

[2] Merci à Jérôme pour m'en avoir indirectement donné l'idée

[3] Rappelons-nous cette comparaison entre le TDD de Ron Jeffries et le code (difficile à lire et impossible à maintenir) de Peter Norvig qui utilise une toute autre approche pour résoudre un sudoku.

[4] un langage de programmation qui se rendrait compte que je n'utilise que des fonctions pures et des objets non mutables m'aurait peut être évité cette étape car il ne relancerait pas le calcul d'une même fonction avec les mêmes paramètres

[5] voir test DeepSearch/3c/Dumb

[6] voir test CachedDeepSearch/3c/Dumb

[7] voir test CachedDeepSearch/4/Dumb

[8] voir test CachedDeepSearch/4/Tree