Tables simples

La performance de certaines applications peut être considérablement améliorée avec l'utilisation de tables. Il s'agit tout simplement de ne pas calculer le résultat à chaque fois, mais de précalculer le résultat une fois pour toutes.

Dans certaines applications d'informatique graphique, par exemple, il est souvent nécessaire de compter le nombre de bits à $1$ dans un octet. On peut bien sûr se servir de la fonction logcount (voir section 6.2.8). Mais celle-ci est trop générale pour l'application en question, car elle s'applique non seulement aux octets, mais à n'importe quel entier. Elle est donc obligée d'utiliser une méthode générale pour compter le nombre de bits à $1$. Une façon plus rapide est de calculer, une fois pour toutes, un tableau de $256$ éléments dont l'élément numéro $i$ contient le nombre de bits à $1$ de l'octet ayant la valeur $i$. La taille d'un tel tableau est environ $1000$ octets si les valeurs qu'il contient sont des entiers de $32$ bits. Voici un exemple de ce que cela peut donner en terme de performance :

* (time (let ((x 0))
          (dotimes (i 100000)
            (dotimes (j 256)
              (incf x (logcount j))))
          x))
Compiling LAMBDA NIL:
Compiling Top-Level Form:

Evaluation took:
 3.02 seconds of real time
 3.02 seconds of user run time
 0.0 seconds of system run time
 0 page faults and
 0 bytes consed.
102400000
* (time (let ((table (make-array '(256))))
          (dotimes (i 256) (setf (aref table i) (logcount i)))
          (let ((x 0))
            (dotimes (i 100000)
              (dotimes (j 256)
                (incf x (aref table j))))
            x)))
Compiling LAMBDA NIL:
Compiling Top-Level Form:

Evaluation took:
 1.78 seconds of real time
 1.78 seconds of user run time
 0.0 seconds of system run time
 0 page faults and
 0 bytes consed.
102400000
*

Dans cet exemple, on calcule la somme du nombre de bits à $1$ dans tous les entiers de 0 à 255. Ce calcul est effectué $100000$ fois et la somme est renvoyée. Dans le premier cas, la fonction logcount est utilisée et le calcul nécessite environ $3$ secondes. Dans le deuxième cas, un tableau est utilisé, et le calcul nécessite environ $1,8$ secondes, soit une amélioration de $40\%$.

Si l'application n'a pas besoin de économiser la mémoire, il est même possible de créer un tableau contenant le nombre de bits à $1$ de tous les entiers de taille $16$ bits.