next up previous contents index
Next: Caches Up: Utilisation de tables Previous: Utilisation de tables   Contents   Index

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.


next up previous contents index
Next: Caches Up: Utilisation de tables Previous: Utilisation de tables   Contents   Index
Robert STRANDH
2001-09-28