C - Comment créer un cache pour des lectures externes coûteuses?

Le tri répété me semble cher. Je voudrais implémenter le cache comme une table de hachage sur l'adresse. Pour garder les choses simples, je ne commencerais même pas même de compter des hits, mais plutôt d'expulser de vieilles entrées immédiatement sur une collision de hachage: xxx

si cela ne s'avère pas suffisamment efficace, je commencerais par tripoter la fonction de hachage.

N'ayez pas peur de faire plus de calculs, dans la plupart des cas, les E / S sont plus lentes. C'est la mise en œuvre la plus simple que je puisse penser:

#define CACHE_SIZE 50

something   cached_vals[CACHE_SIZE];
short int   cached_item_num[CACHE_SIZE];    
char        cache_hits[CACHE_SIZE]; // 0 means free.


void inc_hits(char index){
    if (cache_hits[index] > 127){
        for (int i = 0; i < CACHE_SIZE; i++)
            cache_hits[i] <<= 1;
            cache_hits[i]++;    // 0 is reserved as "free" marker
    };
    cache_hits[index]++;
}:

int get_new_space(short int item){
    for (int i = 0; i < CACHE_SIZE; i++)
        if (!cache_hits[i]) {
            inc_hits(i);
            return i;   
        };
    // no free values, dropping the one with lowest count
    int min_val = 0;
    for (int i = 1; i < CACHE_SIZE; i++)
        min_val = min(cache_hits[min_val], cache_hits[i]);
    cache_hits[min_val] = 2; // just to give new values more chanches to "survive"
    cached_item_num[min_val] = item;
    return min_val;
};


something* get_item(short int item){
    for (int i = 0; i < CACHE_SIZE; i++){
        if (cached_item_num[i] == item){    
            inc_hits(i);
            return cached_vals + i;
        };
    };
    int new_item = get_new_space(item);
    read_from_eeprom(item, cached_vals + new_item);
    return chached_vals + new_item; 
};

Vous avez dit que quelle entrée dont vous avez besoin de la table est liée à la température et que la température a tendance à rester stable. Tant que la température ne change pas trop rapidement, il est peu probable que vous ayez besoin d'une entrée de la table à plus d'une entrée de l'entrée précédemment nécessaire.

Vous devriez être capable d'accomplir votre objectif en gardant seulement 3 entrées dans la RAM. La première entrée est celle que vous venez d'utiliser. La prochaine entrée est celle correspondant à la température juste en dessous de la dernière mesure de la température, et l'autre est la température juste au-dessus de la dernière mesure de la température. Lorsque la température change, l'une de ces entrées devient probablement le nouveau courant actuel. Vous pouvez ensuite préformer quelle que soit la tâche dont vous avez besoin d'utiliser ces données, puis d'aller de l'avant et de lire l'entrée dont vous avez besoin (plus haut ou inférieur à la température actuelle) après avoir terminé d'autres travaux (avant de lire la mesure de température suivante).

Comme il n'y a que 3 entrées dans la RAM à la fois, vous n'avez pas besoin d'être intelligente sur la structure de données que vous devez stocker pour les accéder efficacement, ou même les garder triés car ce ne sera jamais aussi long.

Si les températures peuvent déplacer plus rapidement que 1 unité par période d'examen, vous pouvez simplement augmenter la taille de votre cache et avoir quelques entrées d'anticipation supplémentaires (dans la direction que la température semble être en direct) que vous ne ferez que les entrées de fuite. Ensuite, vous voudrez peut-être stocker les entrées dans une structure efficace. Je ne m'inquiéterais pas de la façon dont vous avez accédé à une entrée récemment, car les prévisions de la distribution de probabilité de température suivantes basées sur la température actuelle seront généralement très bonnes. Vous devrez vous assurer que vous gérez le cas où vous êtes de côté et que vous avez besoin de lire dans l'entrée pour une température de lecture juste immédiatement, cependant.

Les données de tri et de déménagement semble être une mauvaise idée, et il n'est pas clair que vous gagnez quelque chose d'utile.

Je suggérerais une approche beaucoup plus simple. Allouer 4 * N (pour certains n ) octets de données, en tant que tableau de structures de 4 octets contenant chacune une adresse et des données. Pour rechercher une valeur à l'adresse a , vous examinez la structure à l'index un mod n ; Si son adresse stockée est celle que vous souhaitez, utilisez les données associées, sinon recherchez les données de l'EEPROM et stockez-la ainsi avec l'adresse A . Simple, facile à mettre en œuvre, facile à tester et facile à comprendre et à déboguer plus tard.

Si l'emplacement de votre recherche actuelle a tendance à être proche de l'emplacement des recherches précédentes, cela devrait fonctionner assez bien - à tout moment que vous expulsez des données, il va être d'au moins N emplacements loin dans la table, qui signifie que vous n'êtes probablement pas susceptible de le vouloir bientôt à tout moment - je suppose que c'est au moins une bonne heuristique comme "combien de fois ai-je récemment utilisé cela". (Si votre EEPROM stocke plusieurs tables de données différentes, vous pouvez probablement simplement faire du cache pour chacun le plus simple d'éviter les collisions.)