Optimiser les données partagées

Quand vous pouvez voir la lenteur, mesurer la lenteur, dénicher quelle partie est lente, vous devez tout de même trouver une solution. Dans cet article, je vais vous expliquer un cas où j’ai vu, mesuré et localisé un problème. J’ai ensuite réglé ce problème et je vais maintenant vous expliquer comment j’ai procédé.

Une première mise en garde. Je ne présenterai pas le genre de technique étonnante, de bas niveau, bien documentée et mathématiquement prouvée, comme celle de Daniel Lemire. Pour voir un exemple de ce type d’optimisation, allez voir par exemple : “How fast can you parse JSON?”.

Ici, nous ne comptons pas les cycles du CPU. Dans cet article, je parle uniquement des optimisations simples qu’un programmeur de logiciels moyen peut faire au quotidien.

Voir le problème

Le programme sur lequel je travaillais était un filtre pour les gros fichiers texte organisés en arbre. C’est-à-dire que l’indentation de chaque ligne dans le fichier représentait le niveau d’imbrication. Quand je parle de gros fichiers, je veux dire traiter couramment 100 Mo à 1 Go de données de journal. Ce programme a été écrit en C++.

La 1^re approche a consisté à lire le texte dans un vecteur de wstring (std::vector<std::wstring>). La raison de ce choix de départ est basée sur des principes bien connus sur la façon de choisir un conteneur en C++. Le premier principe est le suivant :

Utilisez toujours un std::vector.

(Le deuxième principe est “utilisez un vecteur trié” et le troisième est “êtes-vous vraiment sûr qu’un vecteur ne fera pas l’affaire ?”)

Il était maintenant évident, lors de tests avec des fichiers de grande taille, que la lecture et le filtrage d’un si grand vecteur de chaînes de caractères étaient lents. Lorsque votre chronomètre est suffisant pour savoir que la performance n’est pas au rendez-vous, vous pouvez commencer à jeter un coup d’œil.

Mesurer le problème

Heureusement, il est très facile de jeter un coup d’œil grâce à Visual Studio. Même l’édition communautaire est livrée avec un très bon profileur CPU. Juste sous le menu “Debug”, l’entrée “Performance Profiler…” (raccourci : Alt+F2) ouvrira une fenêtre avec votre cible de projet déjà sélectionnée pour le profilage. De là, il vous suffit de cliquer sur le bouton “Start” et votre programme s’exécutera sous le profileur CPU. Faites simplement l’opération que vous souhaitez mesurer et quittez. Mesure effectuée !

Voici à quoi ressemble la fenêtre du profileur lorsqu’il enregistre les activités de votre programme :

Localiser le problème

Le profileur analysera les données et vous présentera une liste des fonctions où votre programme passe le plus de temps. Par défaut, cette liste est organisée en fonction du temps total du CPU, comme ceci :

Si cela vous donne une vue d’ensemble, cela signifie également que vous voyez beaucoup de données non pertinentes. Vous pouvez toujours trouver facilement la zone problématique en recherchant des sauts importants dans le pourcentage de temps passé. De ce cas-ci, il s’avère que beaucoup de temps est passé à copier des chaînes de texte et à allouer de la mémoire. Les allocations de mémoire proviennent des chaînes de texte et du redimensionnement du vecteur. Il y a également un temps important passé dans les entrées/sorties des fichiers lors de la lecture du texte.

Nous disposons maintenant de quelques emplacements, nous sommes donc en mesure de trouver une solution au problème de performance.

Emprunter quelques trucs

Une bonne idée pour optimiser est de connaître les astuces que d’autres ont utilisées. Une réalisation importante est que lors du filtrage, le texte lui-même ne change pas. Seul ce qui est conservé ou non change. Ceci signifie que nous pouvons emprunter quelques astuces aux langages fonctionnels :

• Les constantes peuvent être partagées.
• Éviter de déplacer les données.
• Déléguer la gestion de la mémoire.

L’idée est donc de rendre le texte partageable, de l’extraire le plus directement possible du disque et de lui ôter la gestion de la mémoire dans laquelle il réside. Nous allons donc faire ce qui suit :

1. Les constantes peuvent être partagées : lire les données du disque dans de grandes mémoires tampon de données non modifiables.
2. Évitez de déplacer les données : recherchez des lignes de texte dans ces tampons et gardez des pointeurs directement dans le tampon.
3. Évitez de déplacer les données : partagez ces tampons et ces lignes de texte dans le résultat du filtrage.
4. Déléguer la gestion de la mémoire : partager ces tampons lors de la copie du texte.

En bref, nous sommes passés du code :

struct VectorOfWStringTextHolder
    {
    using Line = std::wstring;

    std::vector<Line> Lines;
    };

À ce code:

struct VectorOfSharedBuffersTextHolder
    {
    using Buffer = vector<wchar_t>;
    using BufferPtr = shared_ptr<Buffer>;
    using Buffers = vector<BufferPtr>;

    Buffers TextBuffers;

    using Line = wchar_t *;

    std::vector<Line> Lines;

L’idée ici est qu’en utilisant un vecteur de tampons partagés, les adresses des tampons ne changent jamais et peuvent être facilement partagées entre plusieurs instances.

Bien sûr, ces changements ont rendu le code plus complexe. La complexité peut cependant être cachée, car les tampons peuvent rester privés et seul un vecteur de lignes peut être exposé publiquement. Le code a été simplifié ici pour s’assurer que les benchmarks mesurent ce que nous voulons mesurer.

Les résultats

Oui, des benchmarks ! Après tout, il est inutile d’optimiser si vous ne pouvez pas vérifier l’amélioration. En général, il suffit de réutiliser le profileur CPU et de voir les nouveaux résultats. Mais pour cet article, je suis allé plus loin et j’ai extrait l’essentiel de l’ancien et du nouveau code et j’ai écrit un petit programme de référence qui charge un gros fichier et fait des copies partielles des lignes de texte pour imiter le filtrage.

L’avantage d’écrire un benchmark explicite est que vous pouvez placer les mesures de temps exactement là où vous le souhaitez. De cette façon, vous ne mesurez que ce qui est prévu. Avec le profilage du CPU, l’ensemble du programme est mesuré et il est plus difficile d’en extraire les données pertinentes.

Voici les résultats. (J’ai exclu les temps d’entrée/sortie, mais la lecture dans de grands tampons et l’analyse directe des tampons ont donné un gain similaire.)

Comme on peut le voir, nous avons obtenu une accélération d’un facteur de plus de 10. (En fait, nous avons obtenu une amélioration encore plus importante sur les fichiers plus volumineux, car la réallocation d’un très grand vecteur est très coûteuse).

Le code

J’ai fourni le code montrant divers benchmarks et une autre approche utilisant std::deque. J’avais également fait quelques benchmarks dans une structure arborescente dont je n’ai pas parlé ici. (Le changement n’a pas amélioré les performances dans ce cas, mais il a permis d’éviter un autre problème sans rapport avec la profondeur de récursion et le débordement de pile lors de la destruction de structures profondément liées de pointeurs partagés).

Vous pouvez trouver le code sur GitHub.

Notez que l’utilisation réelle de cette technique se trouvait dans mon projet de filtrage d’arbre de texte, également disponible sur GitHub. L’optimisation a été faite dans TextTree et la façon dont il contient les données de texte à travers un TextHolder. Il utilise également une astuce similaire pour pouvoir avoir des adresses stables pour ses nœuds d’arbre en utilisant le fait souvent négligé qu’un std ::deque n’invalide pas les pointeurs lorsqu’on ajouter des données. Le code se trouve ici.