Caches

Parfois, le tableau requis nécessite trop d'espace mémoire. Prenons l'exemple, encore tiré de l'informatique graphique, de la conversion de la couleur de chaque pixel d'une image en une autre couleur déterminée qui nécessite un calcul assez gourmand en temps de calcul. Souvent, un pixel est codé sur $3$ octets, un octet pour chaque couleur de base. Un tableau pour stocker l'ensemble des résultats de ce calcul nécessite au moins $12$ méga octets, probablement $16$ (selon les règles d'alignement de la machine). Dans ce type de situation, il vaut mieux utiliser un cache.

Un cache est une table qui mémorise des résultats au fur et à mesure qu'ils sont calculés. L'avantage d'un cache par rapport à une table simple est qu'il n'est pas nécessaire de calculer l'ensemble des éléments de la table au préalable. Un cache est donc utilisable même dans une situation où relativement peu d'éléments sont utilisés. L'inconvénient d'un cache par rapport à une table simple est que dans une table simple, on peut supposer que l'élément cherché existe, alors que pour un cache, il faut tester si l'élément existe dans la table, et le calculer s'il n'existe pas. Ce test peut s'avérer prohibitif pour certaines applications.

Un cache est donc utilisable même s'il y a assez d'espace pour une table simple, lorsqu'on ne souhaite pas précalculer l'ensemble des éléments. Dans ce cas, une table de hachage peut fonctionner. Le surcoût en espace d'une table de hachage est non négligeable (de $8$ à $16$ octets par élément environ). Cette solution n'est donc envisageable que dans les situations où relativement peu d'éléments sont en jeu.

Plus souvent, le nombre d'éléments requis est trop important pour qu'on puisse les maintenir dans une table d'une quelconque organisation. Dans ce cas, il est nécessaire d'implémenter une méthode pour supprimer un élément de la table lorsqu'on pense ne pas en avoir besoin dans un avenir proche. Le même problème existe dans les systèmes d'exploitation pour déterminer quelles pages sur disque doivent être stockées en mémoire vive pour un accès plus rapide, ou quels mots de la mémoire vive doivent être stockés dans la mémoire cache. La grosse différence entre les solutions d'un système d'exploitation et nos exemples, est que le système d'exploitation dispose de l'assistance du matériel (table des pages, mémoire cache) très rapide, alors qu'une application doit implémenter ces mécanismes sous forme logicielle.

Le problème est donc le suivant : pour calculer une valeur, on doit d'abord tester si la valeur est dans la table. Si c'est le cas, il n'y a pas de problème. Sinon, il faut calculer l'élément et l'insérer dans la table. S'il y a de la place dans la table, il n'y a pas de problème. Sinon, il faut supprimer un élément. Mais lequel ? Et comment organiser la table pour trouver cet élément ?

La réponse à la première question dépend de la stratégie de remplacement. La stratégie la plus souvent utilisée dans le domaine des systèmes d'exploitation est de supprimer l'élément le mois récemment utilisé conformément à l'idée que le temps écoulé depuis la dernière utilisation d'un élément est une bonne indication de la probabilité que celui-ci ne soit pas réutilisé dans un proche avenir. Malheureusement, il est très difficile d'implémenter une telle stratégie sans assistance matérielle.

Une meilleure idée pour une implémentation logicielle est de créer un cache à correspondance directe (en Anglais : direct-mapped cache). Un tel cache est similaire à une table de hachage de taille fixe et sans gestion de synonymes, à savoir qu'un seul élément avec une valeur de hachage donnée peut être présent dans la table. Lorsqu'un élément doit être calculé et qu'un autre élément existe avec la même valeur de hachage, l'autre élément est simplement supprimé. Il est donc important de créer une fonction de hachage telle que la probabilité pour que deux éléments nécessaires simultanément aient la même valeur de hachage soit faible. Cette fonction dépend donc intimement de l'application.

Pour notre exemple de traduction de couleurs dans une image, on peut peut-être dans certains cas supposer que l'image contient des zones d'une même couleur ou de couleurs voisines (ayant des valeurs similaires pour l'ensemble des couleurs de base). Dans ce cas, il faut s'assurer que la valeur de hachage de deux couleurs voisines ne soit pas la même. On peut par exemple calculer cette valeur en calculant le ou exclusif entre la valeur de la couleur rouge, la valeur de la couleur vert décalée à gauche de trois positions et la valeur de la couleur bleu décalée à gauche de six positions. Cela donne une valeur de hachage de $14$ bits, nécessitant un tableau de $16000$ éléments environ.