Comment réaliser le calcul ?

Nous ne disposons que du champ contenant les identifiants des pages. Nous devons donc nous en servir pour en extraire les informations. La première idée est de se servir de la commande VALEURS DISTINCTES afin d'obtenir un tableau des identifiants uniques des pages visitées. Nous pouvons à présent construire un second tableau de même taille qui totalisera le nombre d'occurrences de chaque identifiant dans la table. Il ne nous restera alors qu'à trier les deux tableaux de manière synchronisée et décroissante (par rapport au nombre d'occurrences) avant de n'en retenir que les dix premières valeurs.

Tout le problème est donc d'obtenir le nombre d'occurrences. Il serait illusoire de vouloir boucler sur les enregistrements (cf. mes précédents billets) pour compter les occurrences. Evidemment, cela serait trop long pour l'objectif ciblé. Nous allons utiliser la commande SELECTION VERS TABLEAU pour pouvoir ensuite travailler uniquement en mémoire et donc sans nouvel accès au disque ou au réseau.
Les occurrences étant présentes dans un tableau, la fonction Compter dans tableau paraît être la bonne idée. Nous devons donc boucler sur le tableau des identifiants uniques pour compter à chaque pas les occurrences présentes et ainsi remplir le second tableau. Voici le code réalisant ce travail :
 

Notez que nous faisons ici une recherche initiale et non un TOUT SELECTIONNER afin de ne pas bénéficier de l'optimisation spéciale de la commande VALEURS DISTINCTES dans le cas de la globalité de la table. Ainsi nous nous plaçons dans le cas défavorable, ce qui est toujours important lorsqu'on parle d'optimisation.

Ce code, simple, est facilement compréhensible. Il est temps de le tester. Pour cela il nous faut un jeu de données. Supposons que notre site web compte actuellement 5.000 pages différentes pour un million de visites. Si vous ne disposez pas d'une telle table vous pouvez utiliser le code suivant pour en remplir une à titre d'essai :

Le code de calcul proposé plus haut prend sur ma machine de l'ordre de 7 secondes pour s'exécuter (en mode compilé cela va de soi si l'on cherche la performance !). Clairement ce n'est pas compatible avec notre objectif. Avant d'imaginer une autre solution, étudions les causes de ce temps de calcul important.
Les premiers appels aux commandes permettant de remplir les tableaux sont peu gourmands en temps. Nous pouvons aisément le vérifier en utilisant le log de débogage que nous activons de la manière suivante :

Dans le fichier obtenu, nous pouvons vérifier que le temps de calcul est de l'ordre de quelques millisecondes pour le code situé avant la boucle. Prenez soin de faire exécuter le code une première fois avant d'enregistrer le log afin d'éliminer les phénomènes de cache dans votre étude.

1 p=3 puid=22 Log level: 1
1 p=3 puid=22     (0) cmd: CHERCHER (Test 1).
1 p=3 puid=22     (0) cmd: VALEURS DISTINCTES (Test 1).
54 p=3 puid=22     (0) cmd: SELECTION VERS TABLEAU (Test 1).
173 p=3 puid=22     (0) cmd: Taille tableau (Test 1).
173 p=3 puid=22     (0) cmd: TABLEAU ENTIER LONG (Test 1).
173 p=3 puid=22     (0) cmd: Taille tableau (Test 1).
173 p=3 puid=22     (0) cmd: Compter dans tableau (Test 1).
174 p=3 puid=22     (0) cmd: Compter dans tableau (Test 1).
176 p=3 puid=22     (0) cmd: Compter dans tableau (Test 1).
177 p=3 puid=22     (0) cmd: Compter dans tableau (Test 1).
178 p=3 puid=22     (0) cmd: Compter dans tableau (Test 1).
180 p=3 puid=22     (0) cmd: Compter dans tableau (Test 1).
181 p=3 puid=22     (0) cmd: Compter dans tableau (Test 1).
183 p=3 puid=22     (0) cmd: Compter dans tableau (Test 1).
...

Si l'on continue l'étude du fichier de log, nous voyons clairement que la perte de temps est liée à l'exécution de la boucle et plus particulièrement à l'appel répétitif de la fonction Compter dans tableau.
Effectivement avec le code proposé, nous appelons la fonction Compter dans tableau autant de fois qu'il y a de valeurs d'identifiant. Or pour réaliser sa mission, cette fonction doit parcourir à chaque appel le tableau des occurrences, c'est à dire un tableau d'un million de lignes. Ce n'est pas un calcul anodin et surtout il est répété près de cinq mille fois. Nous pouvons lire dans le fichier de logs que la commande Compter dans tableau prend entre 1 et 2 millisecondes, et cela cinq mille fois. Soit entre 5 et 10 secondes.
Nous tenons là le coupable !

Revenir aux fondamentaux pour aller plus vite

Une fois n'est pas coutume, pour la bonne cause, je vais vous inviter à complexifier votre code ! En effet, je prêche régulièrement pour vous rappeler que le code simple est souvent le plus rapide ; mais souvent ne veut pas dire toujours ! Aujourd'hui nous sommes en face d'un cas où le code simple n'est pas suffisant.

Nous venons de voir que le problème de vitesse est lié au parcours répété du tableau des occurrences. Nous allons donc chercher à réduire cette répétition. Pour cela nous allons inverser notre approche. Au lieu de chercher les occurrences d'une valeur en bouclant sur le tableau des identifiants, nous allons compter les occurrences en bouclant sur le tableau qui les contient et alimenter le tableau au fur et à mesure.
Le code révisé se trouve dans la méthode suivante :

Le temps nécessaire pour compléter l'exécution du code est de 3,5 secondes, soit un gain de 50%.

Cependant il est possible de faire bien mieux. En effet avec la méthode précédente nous avons gagné du temps mais le nombre d'affectations successives reste encore très important. Il y en a autant que de lignes dans le tableau des occurrences; soit un million.
De plus, l'appel de la commande Chercher dans tableau est effectué un million de fois, ce n'est pas forcément l'optimum.

Essayons de limiter le nombre d'affectations et d'appels aux commandes. Pour cela, nous allons commencer par trier le tableau des occurrences. Bien que le tableau ait une dimension de un million de lignes, le tri est très rapide, la commande étant exécutée directement par 4D avec du code proche du système. Mais surtout elle n'est appelée qu'une seule fois !
Reste ensuite à parcourir le tableau pour y lire et compter les valeurs les unes après les autres. Le code se présente alors ainsi  :

Par rapport au premier code proposé, celui-ci est d'une lecture moins directe et nécessite un peu plus d'attention pour le comprendre. Cependant il ne prend que 800 millisecondes pour mener à bien sa tâche. Le gain est à présent de 89% ; cela demande quelques éclaircissements ...

Explication des gains

Dans le dernier code proposé, nous avons réduit au strict nécessaire le code effectué au sein de la boucle, mais surtout nous n'y avons appelé aucune fonction 4D nécessitant un retour dans le moteur de 4D. En procédant ainsi, le code compilé que nous obtenons sera le plus proche possible du processeur sans retour dans le moteur de la base de données. En soi, un retour dans le moteur de la base de données ne prend pas beaucoup de temps et n'est pas facilement mesurable, mais cela n'est plus le cas si les retours sont au nombre d'un million. Pour vous en persuader comparez les temps des deux boucles suivantes :

et

Sur ma machine de test et en mode compilé, nous sommes près de 1000 fois plus rapide avec l'utilisation de l'opérateur % et pourtant les résultats sont identiques.

Que se passe-t-il si l'on utilise une méthode générique ?

Révisons donc notre code pour l'écrire de la manière suivante :

Avec la méthode Incrementer_compteur :

Le temps d'exécution est de 900 millisecondes soit une augmentation de 12 % par rapport au meilleur code.
Les différences ne sont pas énormes, mais n'oublions pas que nous venons de faire un million d'appels à la sous routine, et dans le cas qui nous préoccupe aujourd'hui, la différence est suffisamment grande pour ne pas s'autoriser le luxe de cette méthode générique.

Regardons de la même manière le code utilisant une méthode générique acceptant des pointeurs en paramètres :

Avec la méthode Incrementer_compteur2 :

Cette fois le temps nécessaire est de 1 700 millisecondes, soit plus du double du meilleur temps. Autant dire que la combinaison méthode générique et pointeurs n'est pas à conseiller si vous êtes en recherche de vitesse.


Typer les variables

Le code est exécuté en compilé ; quelle est l'influence du typage des variables de compteur sur le temps d'exécution de notre code. Jusqu'à présent nous avions les réglages suivants dans les préférences de compilation :

Les compteurs sont donc typés en réel car ils ne sont pas explicitement déclarés. Déclarons-les en entier long, comme il se doit, surtout pour 1 million d'itérations pour voir ce que cela change :

Nous gagnons environ 30 millisecondes, ce qui est faible mais non négligeable !

Pour aller au bout des déclarations, déclarons à présent les tableaux utilisés :

Ici le temps d'exécution reste inchangé. En effet les tableaux $_ids et $_id étaient au préalable déclarés en entier long par 4D pour être en accord avec le champ auquel ils étaient associés dans les commandes VALEURS DISTINCTES et SELECTION VERS TABLEAU. Il est donc logique de ne rien gagner ici en déclarant les tableaux, si ce n'est en lisibilité.

Règles d'or

A la lumière de ces explications, il est temps de vous livrer mes règles d'or en matière d'optimisation d'un code demandant un grand nombre d'itérations.

La première règle est de mesurer le temps des différentes parties et de le mettre en regard des volumes présents (votre jeu d'essai) et à venir (ce que sera votre base après quelques temps de mise en production). Vous aurez alors les clefs pour décider des parties nécessitant tous vos soins.

La deuxième règle est de ne pas considérer que moins d'itérations sera toujours plus rapide. Dans notre exemple la boucle principale est passée de cinq mille à un million d'itérations avec un gain de performance considérable. Ce qui compte n'est pas la boucle, mais ce qui est « dans » la boucle !

La troisième règle est de faire le plus de chose possible soi-même. Non pas que 4D produise du code lent mais simplement à cause des appels au moteur et à la redondance de calculs que vous imposez en utilisant des commandes de manière trop répétitive. Dans le premier exemple l'utilisation de la commande Compter dans tableau montrait bien les conséquences du non respect de cette règle. Une commande doit s'adapter à toutes les situations et ne peut tirer bénéfice d'éléments déjà calculés ; votre code peut (et doit) le faire !

La quatrième règle est de déclarer les variables de compteur (ou assimilées) en entier long ; le gain ne sera pas énorme, mais cela sera toujours cela de pris et ce sans trop d'efforts !

Enfin la dernière règle est de bannir les méthodes génériques a fortiori dans ce cadre. Il ne peut y avoir de code rapide utilisant des méthodes génériques appelées de manière répétitive. La décision de supprimer des appels aux méthodes génériques pour les remplacer par du code spécifique sera souvent salvatrice. Lorsque je présente cette dernière règle, on m'oppose souvent les arguments de la maintenance du code plus difficile, et dont la relecture est moins aisée. Certes, mais comme le dit l'adage on ne fait pas d'omelette sans casser d'oeufs. J'ajouterais que faire une bonne omelette demande de l'expérience afin d'optimiser sa cuisson et son assaisonnement ! De plus rien ne vous interdit de commenter votre code afin de faciliter sa relecture et d'aider l'éventuelle maintenance.
 

Lorsque vous aurez goûté aux joies de l'optimisation des performances de vos bases, en ne modifiant que quelques lignes, dans des proportions aussi importantes que présentées dans ce billet, vous saurez où porter le plus grand soin dans vos boucles et parfois réviserez de fond en comble vos habitudes de programmation dans 4D.