Une optimisation pour un accès aléatoire sur un très grand tableau lorsque la valeur dans 95% des cas est 0 ou 1?

Y a-t-il une optimisation possible pour l'accès aléatoire sur un très grand tableau (j'utilise actuellement uint8_t, et je demande ce qui est mieux)

uint8_t MyArray[10000000];

lorsque la valeur à n'importe quelle position dans le tableau est

• 0 ou 1 pour 95% de tous les cas,
• 2 dans 4% des cas,
• entre 3 et 255 dans l'autre 1% des cas?

Alors, y a-t-il quelque chose de mieux qu'un uint8_ttableau à utiliser pour cela? Il devrait être aussi rapide que possible de boucler sur l'ensemble de la matrice dans un ordre aléatoire, et cela est très lourd sur la bande passante de la RAM, donc lorsque plus de quelques threads font cela en même temps pour différentes baies, actuellement toute la bande passante de la RAM est vite saturé.

Je demande car il semble très inefficace d'avoir un si grand tableau (10 Mo) quand on sait en fait que presque toutes les valeurs, à l'exception de 5%, seront soit 0 ou 1. Donc, lorsque 95% de toutes les valeurs du tableau n'aurait en fait besoin que de 1 bit au lieu de 8 bits, ce qui réduirait l'utilisation de la mémoire de presque un ordre de grandeur. On a l'impression qu'il doit y avoir une solution plus efficace en mémoire qui réduirait considérablement la bande passante RAM requise pour cela et, par conséquent, serait également beaucoup plus rapide pour un accès aléatoire.

Une possibilité simple qui vient à l'esprit est de conserver un tableau compressé de 2 bits par valeur pour les cas courants, et un tableau séparé de 4 octets par valeur (24 bits pour l'index de l'élément d'origine, 8 bits pour la valeur réelle, donc (idx << 8) | value)) un tableau trié pour le autres.

Lorsque vous recherchez une valeur, vous effectuez d'abord une recherche dans le tableau 2bpp (O (1)); si vous trouvez 0, 1 ou 2, c'est la valeur que vous voulez; si vous trouvez 3, cela signifie que vous devez le rechercher dans le tableau secondaire. Ici, vous effectuerez une recherche binaire pour rechercher l' indice de votre intérêt décalé à gauche de 8 (O (log (n) avec un petit n, car cela devrait être le 1%), et extrayez la valeur de 4- byte thingie.

std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;

uint8_t lookup(unsigned idx) {
    // extract the 2 bits of our interest from the main array
    uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
    // usual (likely) case: value between 0 and 2
    if(v != 3) return v;
    // bad case: lookup the index<<8 in the secondary array
    // lower_bound finds the first >=, so we don't need to mask out the value
    auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
    // some coherency checks
    if(ptr == sec_arr.end()) std::abort();
    if((*ptr >> 8) != idx) std::abort();
#endif
    // extract our 8-bit value from the 32 bit (index, value) thingie
    return (*ptr) & 0xff;
}

void populate(uint8_t *source, size_t size) {
    main_arr.clear(); sec_arr.clear();
    // size the main storage (round up)
    main_arr.resize((size+3)/4);
    for(size_t idx = 0; idx < size; ++idx) {
        uint8_t in = source[idx];
        uint8_t &target = main_arr[idx>>2];
        // if the input doesn't fit, cap to 3 and put in secondary storage
        if(in >= 3) {
            // top 24 bits: index; low 8 bit: value
            sec_arr.push_back((idx << 8) | in);
            in = 3;
        }
        // store in the target according to the position
        target |= in << ((idx & 3)*2);
    }
}

Pour un tableau tel que celui que vous avez proposé, cela devrait prendre 10 000 000/4 = 2 500 000 octets pour le premier tableau, plus 10 000 000 * 1% * 4 B = 400 000 octets pour le deuxième tableau; d'où 2900000 octets, c'est-à-dire moins d'un tiers du tableau d'origine, et la partie la plus utilisée est gardée ensemble en mémoire, ce qui devrait être bon pour la mise en cache (elle peut même tenir L3).

Si vous avez besoin d'un adressage supérieur à 24 bits, vous devrez modifier le "stockage secondaire"; une manière simple de l'étendre est d'avoir un tableau de pointeurs de 256 éléments pour basculer sur les 8 premiers bits de l'index et transmettre à un tableau trié indexé 24 bits comme ci-dessus.

Benchmark rapide

#include <algorithm>
#include <vector>
#include <stdint.h>
#include <chrono>
#include <stdio.h>
#include <math.h>

using namespace std::chrono;

/// XorShift32 generator; extremely fast, 2^32-1 period, way better quality
/// than LCG but fail some test suites
struct XorShift32 {
    /// This stuff allows to use this class wherever a library function
    /// requires a UniformRandomBitGenerator (e.g. std::shuffle)
    typedef uint32_t result_type;
    static uint32_t min() { return 1; }
    static uint32_t max() { return uint32_t(-1); }

    /// PRNG state
    uint32_t y;

    /// Initializes with seed
    XorShift32(uint32_t seed = 0) : y(seed) {
        if(y == 0) y = 2463534242UL;
    }

    /// Returns a value in the range [1, 1<<32)
    uint32_t operator()() {
        y ^= (y<<13);
        y ^= (y>>17);
        y ^= (y<<15);
        return y;
    }

    /// Returns a value in the range [0, limit); this conforms to the RandomFunc
    /// requirements for std::random_shuffle
    uint32_t operator()(uint32_t limit) {
        return (*this)()%limit;
    }
};

struct mean_variance {
    double rmean = 0.;
    double rvariance = 0.;
    int count = 0;

    void operator()(double x) {
        ++count;
        double ormean = rmean;
        rmean     += (x-rmean)/count;
        rvariance += (x-ormean)*(x-rmean);
    }

    double mean()     const { return rmean; }
    double variance() const { return rvariance/(count-1); }
    double stddev()   const { return std::sqrt(variance()); }
};

std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;

uint8_t lookup(unsigned idx) {
    // extract the 2 bits of our interest from the main array
    uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
    // usual (likely) case: value between 0 and 2
    if(v != 3) return v;
    // bad case: lookup the index<<8 in the secondary array
    // lower_bound finds the first >=, so we don't need to mask out the value
    auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
    // some coherency checks
    if(ptr == sec_arr.end()) std::abort();
    if((*ptr >> 8) != idx) std::abort();
#endif
    // extract our 8-bit value from the 32 bit (index, value) thingie
    return (*ptr) & 0xff;
}

void populate(uint8_t *source, size_t size) {
    main_arr.clear(); sec_arr.clear();
    // size the main storage (round up)
    main_arr.resize((size+3)/4);
    for(size_t idx = 0; idx < size; ++idx) {
        uint8_t in = source[idx];
        uint8_t &target = main_arr[idx>>2];
        // if the input doesn't fit, cap to 3 and put in secondary storage
        if(in >= 3) {
            // top 24 bits: index; low 8 bit: value
            sec_arr.push_back((idx << 8) | in);
            in = 3;
        }
        // store in the target according to the position
        target |= in << ((idx & 3)*2);
    }
}

volatile unsigned out;

int main() {
    XorShift32 xs;
    std::vector<uint8_t> vec;
    int size = 10000000;
    for(int i = 0; i<size; ++i) {
        uint32_t v = xs();
        if(v < 1825361101)      v = 0; // 42.5%
        else if(v < 4080218931) v = 1; // 95.0%
        else if(v < 4252017623) v = 2; // 99.0%
        else {
            while((v & 0xff) < 3) v = xs();
        }
        vec.push_back(v);
    }
    populate(vec.data(), vec.size());
    mean_variance lk_t, arr_t;
    for(int i = 0; i<50; ++i) {
        {
            unsigned o = 0;
            auto beg = high_resolution_clock::now();
            for(int i = 0; i < size; ++i) {
                o += lookup(xs() % size);
            }
            out += o;
            int dur = (high_resolution_clock::now()-beg)/microseconds(1);
            fprintf(stderr, "lookup: %10d µs\n", dur);
            lk_t(dur);
        }
        {
            unsigned o = 0;
            auto beg = high_resolution_clock::now();
            for(int i = 0; i < size; ++i) {
                o += vec[xs() % size];
            }
            out += o;
            int dur = (high_resolution_clock::now()-beg)/microseconds(1);
            fprintf(stderr, "array:  %10d µs\n", dur);
            arr_t(dur);
        }
    }

    fprintf(stderr, " lookup |   ±  |  array  |   ±  | speedup\n");
    printf("%7.0f | %4.0f | %7.0f | %4.0f | %0.2f\n",
            lk_t.mean(), lk_t.stddev(),
            arr_t.mean(), arr_t.stddev(),
            arr_t.mean()/lk_t.mean());
    return 0;
}

(code et données toujours mis à jour dans mon Bitbucket)

Le code ci-dessus remplit un tableau d'éléments 10M avec des données aléatoires distribuées comme OP spécifié dans leur message, initialise ma structure de données, puis:

• effectue une recherche aléatoire de 10 millions d'éléments avec ma structure de données
• fait de même avec le tableau d'origine.

(notez qu'en cas de recherche séquentielle, le tableau gagne toujours par une énorme mesure, car c'est la recherche la plus conviviale pour le cache que vous puissiez faire)

Ces deux derniers blocs sont répétés 50 fois et chronométrés; à la fin, la moyenne et l'écart type pour chaque type de recherche sont calculés et imprimés, avec l'accélération (lookup_mean / array_mean).

J'ai compilé le code ci-dessus avec g ++ 5.4.0 ( -O3 -static, plus quelques avertissements) sur Ubuntu 16.04, et l' ai exécuté sur certaines machines; la plupart utilisent Ubuntu 16.04, certains Linux plus anciens, certains Linux plus récents. Je ne pense pas que le système d'exploitation devrait être pertinent du tout dans ce cas.

            CPU           |  cache   |  lookup (µs)   |     array (µs)  | speedup (x)
Xeon E5-1650 v3 @ 3.50GHz | 15360 KB |  60011 ±  3667 |   29313 ±  2137 | 0.49
Xeon E5-2697 v3 @ 2.60GHz | 35840 KB |  66571 ±  7477 |   33197 ±  3619 | 0.50
Celeron G1610T  @ 2.30GHz |  2048 KB | 172090 ±   629 |  162328 ±   326 | 0.94
Core i3-3220T   @ 2.80GHz |  3072 KB | 111025 ±  5507 |  114415 ±  2528 | 1.03
Core i5-7200U   @ 2.50GHz |  3072 KB |  92447 ±  1494 |   95249 ±  1134 | 1.03
Xeon X3430      @ 2.40GHz |  8192 KB | 111303 ±   936 |  127647 ±  1503 | 1.15
Core i7 920     @ 2.67GHz |  8192 KB | 123161 ± 35113 |  156068 ± 45355 | 1.27
Xeon X5650      @ 2.67GHz | 12288 KB | 106015 ±  5364 |  140335 ±  6739 | 1.32
Core i7 870     @ 2.93GHz |  8192 KB |  77986 ±   429 |  106040 ±  1043 | 1.36
Core i7-6700    @ 3.40GHz |  8192 KB |  47854 ±   573 |   66893 ±  1367 | 1.40
Core i3-4150    @ 3.50GHz |  3072 KB |  76162 ±   983 |  113265 ±   239 | 1.49
Xeon X5650      @ 2.67GHz | 12288 KB | 101384 ±   796 |  152720 ±  2440 | 1.51
Core i7-3770T   @ 2.50GHz |  8192 KB |  69551 ±  1961 |  128929 ±  2631 | 1.85

Les résultats sont ... mitigés!

1. En général, sur la plupart de ces machines, il y a une sorte d'accélération, ou du moins elles sont sur un pied d'égalité.
2. Les deux cas où le tableau l'emporte vraiment sur la recherche de «structure intelligente» sont sur des machines avec beaucoup de cache et pas particulièrement occupées: le Xeon E5-1650 ci-dessus (15 Mo de cache) est une machine de construction de nuit, pour le moment assez inactive; le Xeon E5-2697 (35 Mo de mémoire cache) est une machine pour les calculs de haute performance, également dans un moment d'inactivité. Cela a du sens, le tableau d'origine s'intègre complètement dans son énorme cache, de sorte que la structure de données compacte ne fait qu'ajouter de la complexité.
3. À l'opposé du «spectre de performances» - mais là où le tableau est un peu plus rapide, il y a l'humble Celeron qui alimente mon NAS; il a si peu de cache que ni le tableau ni la "structure intelligente" n'y rentrent du tout. D'autres machines avec un cache suffisamment petit fonctionnent de la même manière.
4. Le Xeon X5650 doit être pris avec une certaine prudence - ce sont des machines virtuelles sur un serveur de machine virtuelle à double socket assez occupé; il se peut bien que, bien que nominalement il ait une quantité décente de cache, pendant le temps du test, il soit préempté plusieurs fois par des machines virtuelles totalement indépendantes.

Une autre option pourrait être

• vérifier si le résultat est 0, 1 ou 2
• sinon faites une recherche régulière

En d'autres termes, quelque chose comme:

unsigned char lookup(int index) {
    int code = (bmap[index>>2]>>(2*(index&3)))&3;
    if (code != 3) return code;
    return full_array[index];
}

où bmaputilise 2 bits par élément avec la valeur 3 signifiant «autre».

Cette structure est simple à mettre à jour, utilise 25% de mémoire en plus mais la grande partie n'est recherchée que dans 5% des cas. Bien sûr, comme d'habitude, si c'est une bonne idée ou non, cela dépend de beaucoup d'autres conditions, donc la seule réponse est d'expérimenter un usage réel.

C'est plus un "long commentaire" qu'une réponse concrète

À moins que vos données ne soient quelque chose de bien connu, je doute que quiconque puisse répondre DIRECTEMENT à votre question (et je ne suis au courant de rien qui correspond à votre description, mais alors je ne sais pas TOUT sur toutes sortes de modèles de données pour tous types de cas d'utilisation). Les données éparses sont un problème courant dans le calcul haute performance, mais c'est typiquement "nous avons un très grand tableau, mais seules certaines valeurs sont non nulles".

Pour les modèles pas bien connus comme ce que je pense être le vôtre, personne ne saura directement ce qui est le meilleur, et cela dépend des détails: à quel point l'accès aléatoire est-il aléatoire - le système accède-t-il à des grappes d'éléments de données, ou est-il complètement aléatoire comme à partir de un générateur de nombres aléatoires uniforme. Les données de la table sont-elles complètement aléatoires ou y a-t-il des séquences de 0 puis des séquences de 1, avec une dispersion d'autres valeurs? L'encodage de longueur d'exécution fonctionnerait bien si vous avez des séquences raisonnablement longues de 0 et 1, mais ne fonctionnera pas si vous avez un "damier de 0/1". De plus, vous devrez conserver un tableau des "points de départ", afin que vous puissiez vous rendre à l'endroit pertinent assez rapidement.

Je sais depuis longtemps que certaines grandes bases de données ne sont qu'une grande table en RAM (données d'abonné du central téléphonique dans cet exemple), et l'un des problèmes est que les caches et les optimisations de tables de pages dans le processeur sont assez inutiles. L'appelant est si rarement le même que celui qui a récemment appelé quelqu'un, qu'il n'y a pas de données pré-chargées d'aucune sorte, c'est purement aléatoire. Les grands tableaux de pages sont la meilleure optimisation pour ce type d'accès.

Dans de nombreux cas, faire un compromis entre «vitesse et petite taille» est l'une de ces choses que vous devez choisir entre l'ingénierie logicielle [dans d'autres ingénieurs, ce n'est pas nécessairement un compromis]. Ainsi, "gaspiller de la mémoire pour un code plus simple" est souvent le choix préféré. En ce sens, la solution "simple" est probablement meilleure pour la vitesse, mais si vous avez une "meilleure" utilisation de la RAM, l'optimisation de la taille de la table vous donnerait des performances suffisantes et une bonne amélioration de la taille. Il existe de nombreuses façons différentes d'y parvenir - comme suggéré dans un commentaire, un champ de 2 bits où les deux ou trois valeurs les plus courantes sont stockées, puis un autre format de données pour les autres valeurs - une table de hachage serait mon première approche, mais une liste ou un arbre binaire peut également fonctionner - encore une fois, cela dépend des modèles où se trouvent vos "pas 0, 1 ou 2". Encore une fois, cela dépend de la façon dont les valeurs sont «dispersées» dans le tableau - sont-elles en grappes ou sont-elles plus uniformément réparties?

Mais un problème avec cela est que vous lisez toujours les données de la RAM. Vous dépensez alors plus de code pour traiter les données, y compris du code pour faire face au "ce n'est pas une valeur commune".

Le problème avec les algorithmes de compression les plus courants est qu'ils sont basés sur des séquences de décompression, vous ne pouvez donc pas y accéder de manière aléatoire. Et la surcharge de fractionner vos données volumineuses en morceaux de, par exemple, 256 entrées à la fois, et de décompresser les 256 dans un tableau uint8_t, de récupérer les données que vous voulez, puis de jeter vos données non compressées, est très peu susceptible de vous donner du bon. performances - en supposant que cela ait une certaine importance, bien sûr.

En fin de compte, vous devrez probablement implémenter une ou plusieurs des idées dans les commentaires / réponses pour tester, voir si cela aide à résoudre votre problème, ou si le bus mémoire est toujours le principal facteur limitant.

Ce que j'ai fait dans le passé, c'est d'utiliser un hashmap devant un ensemble de bits.

Cela divise par deux l'espace par rapport à la réponse de Matteo, mais peut être plus lent si les recherches "d'exception" sont lentes (c'est-à-dire qu'il existe de nombreuses exceptions).

Souvent, cependant, «le cache est roi».

À moins qu'il n'y ait un modèle dans vos données, il est peu probable qu'il y ait une optimisation raisonnable de la vitesse ou de la taille, et - en supposant que vous ciblez un ordinateur normal - 10 Mo n'est pas si grave de toute façon.

Il y a deux hypothèses dans vos questions:

1. Les données sont mal stockées car vous n'utilisez pas tous les bits
2. Le stocker mieux rendrait les choses plus rapides.

Je pense que ces deux hypothèses sont fausses. Dans la plupart des cas, la manière appropriée de stocker des données est de stocker la représentation la plus naturelle. Dans votre cas, c'est celui que vous avez choisi: un octet pour un nombre compris entre 0 et 255. Toute autre représentation sera plus complexe et donc - toutes choses égales par ailleurs - plus lente et plus sujette aux erreurs. Pour avoir besoin de détourner de ce principe général, vous avez besoin d'une raison plus forte que potentiellement six bits "gaspillés" sur 95% de vos données.

Pour votre deuxième hypothèse, ce sera vrai si, et seulement si, la modification de la taille de la matrice entraîne beaucoup moins d'erreurs de cache. Que cela se produise ne peut être définitivement déterminé que par le profilage du code de travail, mais je pense qu'il est très peu probable que cela fasse une différence substantielle. Étant donné que vous accéderez de manière aléatoire au tableau dans les deux cas, le processeur aura du mal à savoir quels bits de données mettre en cache et conserver dans les deux cas.

Si les données et les accès sont uniformément distribués de manière aléatoire, les performances dépendront probablement de la fraction des accès qui évite un échec du cache de niveau externe. Pour optimiser cela, il faudra savoir quelle taille de tableau peut être logée de manière fiable dans le cache. Si votre cache est suffisamment grand pour accueillir un octet pour cinq cellules, l'approche la plus simple peut être d'avoir un octet contenant les cinq valeurs codées en base trois dans la plage 0-2 (il y a 243 combinaisons de 5 valeurs, de sorte que place dans un octet), avec un tableau de 10 000 000 octets qui serait interrogé chaque fois qu'une valeur de base 3 indique «2».

Si le cache n'est pas si grand, mais peut accueillir un octet par 8 cellules, il ne serait pas possible d'utiliser une valeur d'octet pour sélectionner parmi les 6561 combinaisons possibles de huit valeurs de base 3, mais puisque le seul effet de changer un 0 ou 1 en un 2 entraînerait une recherche autrement inutile, l'exactitude ne nécessiterait pas de prendre en charge les 6 561. Au lieu de cela, on pourrait se concentrer sur les 256 valeurs les plus «utiles».

Surtout si 0 est plus courant que 1, ou vice versa, une bonne approche pourrait être d'utiliser 217 valeurs pour encoder les combinaisons de 0 et 1 qui contiennent 5 ou moins de 1, 16 valeurs pour encoder xxxx0000 à xxxx1111, 16 pour encoder 0000xxxx à travers 1111xxxx et un pour xxxxxxxx. Quatre valeurs resteraient pour toute autre utilisation que l'on pourrait trouver. Si les données sont distribuées aléatoirement comme décrit, une légère majorité de toutes les requêtes toucheraient des octets qui ne contenaient que des zéros et des uns (dans environ 2/3 de tous les groupes de huit, tous les bits seraient des zéros et des uns, et environ 7/8 de ceux-ci auraient six bits ou moins 1); la grande majorité de ceux qui ne le font pas atterriraient dans un octet contenant quatre x et auraient 50% de chances d'atterrir sur un zéro ou un un. Ainsi, seulement environ une requête sur quatre nécessiterait une recherche sur un grand tableau.

Si les données sont distribuées aléatoirement mais que le cache n'est pas assez grand pour gérer un octet pour huit éléments, on pourrait essayer d'utiliser cette approche avec chaque octet gérant plus de huit éléments, mais à moins qu'il n'y ait un fort biais vers 0 ou vers 1 , la fraction des valeurs qui peuvent être gérées sans avoir à faire une recherche dans le grand tableau diminuera à mesure que le nombre géré par chaque octet augmentera.

J'ajouterai à la réponse de @ o11c , car son libellé peut être un peu déroutant. Si j'ai besoin de presser le dernier bit et le cycle du processeur, je ferais ce qui suit.

Nous commencerons par construire un arbre de recherche binaire équilibré contenant les 5% de cas «autre chose». Pour chaque recherche, vous parcourez rapidement l'arborescence: vous avez 10 000 000 éléments dont 5% dans l'arborescence: la structure de données arborescente contient donc 500 000 éléments. Marcher ceci en temps O (log (n)), vous donne 19 itérations. Je ne suis pas un expert en la matière, mais je suppose qu'il existe des implémentations économes en mémoire. Faisons une estimation:

• Arbre équilibré, ainsi la position du sous-arbre peut être calculée (les indices n'ont pas besoin d'être stockés dans les nœuds de l'arbre). De la même manière qu'un tas (structure de données) est stocké dans la mémoire linéaire.
• Valeur de 1 octet (2 à 255)
• 3 octets pour l'index (10000000 prend 23 bits, ce qui correspond à 3 octets)

Total, 4 octets: 500000 * 4 = 1953 ko. Convient au cache!

Pour tous les autres cas (0 ou 1), vous pouvez utiliser un bitvector. Notez que vous ne pouvez pas omettre les 5% autres cas d'accès aléatoire: 1,19 Mo.

La combinaison de ces deux utilise environ 3 099 Mo. En utilisant cette technique, vous économiserez un facteur 3,08 de mémoire.

Cependant, cela ne bat pas la réponse de @Matteo Italia (qui utilise 2,76 Mo), dommage. Y a-t-il quelque chose que nous pouvons faire de plus? La partie la plus consommatrice de mémoire est constituée des 3 octets d'index dans l'arborescence. Si nous pouvons ramener cela à 2, nous économiserions 488 Ko et l'utilisation totale de la mémoire serait de: 2,622 Mo, ce qui est plus petit!

Comment faisons-nous cela? Nous devons réduire l'indexation à 2 octets. Encore une fois, 10000000 prend 23 bits. Nous devons pouvoir supprimer 7 bits. Nous pouvons simplement le faire en partitionnant la plage de 10000000 éléments en 2 ^ 7 (= 128) régions de 78125 éléments. Nous pouvons maintenant construire un arbre équilibré pour chacune de ces régions, avec 3906 éléments en moyenne. Le choix du bon arbre se fait par une simple division de l'index cible par 2 ^ 7 (ou un décalage de bits >> 7). L'index requis à stocker peut maintenant être représenté par les 16 bits restants. Notez qu'il y a une surcharge pour la longueur de l'arbre qui doit être stockée, mais c'est négligeable. Notez également que ce mécanisme de fractionnement réduit le nombre d'itérations nécessaires pour parcourir l'arbre, cela se réduit désormais à 7 itérations de moins, car nous avons laissé tomber 7 bits: il ne reste que 12 itérations.

Notez que vous pourriez théoriquement répéter le processus pour couper les 8 bits suivants, mais cela vous obligerait à créer 2 ^ 15 arbres équilibrés, avec ~ 305 éléments en moyenne. Cela donnerait 2,143 Mo, avec seulement 4 itérations pour parcourir l'arbre, ce qui représente une accélération considérable par rapport aux 19 itérations avec lesquelles nous avons commencé.

En guise de conclusion finale: cela bat la stratégie vectorielle 2 bits par un tout petit peu d'utilisation de la mémoire, mais c'est tout un combat à mettre en œuvre. Mais si cela peut faire la différence entre l'installation du cache ou non, cela vaut peut-être la peine d'essayer.

Si vous n'effectuez que des opérations de lecture, il est préférable de ne pas affecter de valeur à un seul index mais à un intervalle d'index.

Par exemple:

[0, 15000] = 0
[15001, 15002] = 153
[15003, 26876] = 2
[25677, 31578] = 0
...

Cela peut être fait avec un struct. Vous pouvez également définir une classe similaire à celle-ci si vous aimez une approche OO.

class Interval{
  private:
    uint32_t start; // First element of interval
    uint32_t end; // Last element of interval
    uint8_t value; // Assigned value

  public:
    Interval(uint32_t start, uint32_t end, uint8_t value);
    bool isInInterval(uint32_t item); // Checks if item lies within interval
    uint8_t getValue(); // Returns the assigned value
}

Maintenant, il vous suffit de parcourir une liste d'intervalles et de vérifier si votre index se trouve dans l'un d'entre eux, ce qui peut être beaucoup moins gourmand en mémoire en moyenne mais coûte plus de ressources CPU.

Interval intervals[INTERVAL_COUNT];
intervals[0] = Interval(0, 15000, 0);
intervals[1] = Interval(15001, 15002, 153);
intervals[2] = Interval(15003, 26876, 2);
intervals[3] = Interval(25677, 31578, 0);
...

uint8_t checkIntervals(uint32_t item)

    for(int i=0; i<INTERVAL_COUNT-1; i++)
    {
        if(intervals[i].isInInterval(item) == true)
        {
            return intervals[i].getValue();
        }
    }
    return DEFAULT_VALUE;
}

Si vous triez les intervalles par taille décroissante, vous augmentez la probabilité que l'élément que vous recherchez soit trouvé tôt, ce qui diminue encore votre utilisation moyenne de la mémoire et des ressources du processeur.

Vous pouvez également supprimer tous les intervalles d'une taille de 1. Mettez les valeurs correspondantes dans une carte et ne les vérifiez que si l'élément que vous recherchez n'a pas été trouvé dans les intervalles. Cela devrait également augmenter un peu les performances moyennes.

Il y a longtemps, je me souviens juste ...

À l'université, nous avons eu la tâche d'accélérer un programme de traceur de rayons, qui doit lire par algorithme encore et encore à partir de tableaux de tampons. Un ami m'a dit de toujours utiliser des lectures de RAM qui sont des multiples de 4 octets. J'ai donc changé le tableau d'un modèle de [x1, y1, z1, x2, y2, z2, ..., xn, yn, zn] à un modèle de [x1, y1, z1,0, x2, y2, z2 , 0, ..., xn, yn, zn, 0]. Cela signifie que j'ajoute un champ vide après chaque coordonnée 3D. Après quelques tests de performances: c'était plus rapide. Si longue histoire courte: lisez plusieurs de 4 octets de votre tableau à partir de la RAM, et peut-être aussi à partir de la bonne position de départ, vous lisez donc un petit cluster où se trouve l'index recherché et lisez l'index recherché à partir de ce petit cluster dans le processeur. (Dans votre cas, vous n'aurez pas besoin d'insérer des champs de remplissage, mais le concept doit être clair)

Peut-être que d'autres multiples pourraient également être la clé des systèmes plus récents.

Je ne sais pas si cela fonctionnera dans votre cas, donc si cela ne fonctionne pas: Désolé. Si cela fonctionne, je serais heureux d'entendre les résultats de certains tests.

PS: Oh et s'il y a un modèle d'accès ou des index accessibles à proximité, vous pouvez réutiliser le cluster mis en cache.

PPS: Il se pourrait que le facteur multiple ressemble plus à 16 octets ou quelque chose comme ça, il y a trop longtemps, dont je me souviens exactement.

En regardant cela, vous pouvez diviser vos données, par exemple:

• un ensemble de bits qui est indexé et représente la valeur 0 (std :: vector serait utile ici)
• un ensemble de bits qui est indexé et représente la valeur 1
• un std :: vector pour les valeurs de 2, contenant les index qui font référence à cette valeur
• une carte pour les autres valeurs (ou std :: vector>)

Dans ce cas, toutes les valeurs apparaissent jusqu'à un index donné, vous pouvez donc même supprimer l'un des ensembles de bits et représenter la valeur car elle est manquante dans les autres.

Cela vous fera économiser de la mémoire pour ce cas, mais aggraverait le pire des cas. Vous aurez également besoin de plus de puissance de processeur pour effectuer les recherches.

Assurez-vous de mesurer!

Comme Mats le mentionne dans son commentaire-réponse, il est difficile de dire quelle est réellement la meilleure solution sans savoir précisément quel type de données vous avez (par exemple, y a-t-il de longues séries de 0, etc.), et à quoi ressemble votre modèle d'accès comme (est-ce que "aléatoire" signifie "partout" ou simplement "pas strictement de façon complètement linéaire" ou "chaque valeur exactement une fois, juste aléatoire" ou ...).

Cela dit, deux mécanismes me viennent à l'esprit:

• Tableaux de bits; c'est-à-dire que si vous n'aviez que deux valeurs, vous pourriez compresser trivialement votre tableau d'un facteur 8; si vous avez 4 valeurs (ou "3 valeurs + tout le reste"), vous pouvez compresser par un facteur de deux. Ce qui pourrait ne pas valoir la peine et nécessiterait des repères, surtout si vous avez des modèles d'accès vraiment aléatoires qui échappent à vos caches et ne modifient donc pas du tout le temps d'accès.
• (index,value)ou des (value,index)tables. Par exemple, ayez une très petite table pour le cas 1%, peut-être une table pour le cas 5% (qui n'a besoin que de stocker les index car tous ont la même valeur), et un grand tableau de bits compressés pour les deux derniers cas. Et avec "table", je veux dire quelque chose qui permet une recherche relativement rapide; c'est-à-dire, peut-être un hachage, un arbre binaire, etc., en fonction de ce dont vous disposez et de vos besoins réels. Si ces sous-tables correspondent à vos caches de 1er / 2ème niveau, vous pourriez avoir de la chance.

Je ne suis pas très familier avec C, mais en C ++, vous pouvez utiliser des caractères non signés pour représenter un entier compris entre 0 et 255.

Comparé à un int normal (encore une fois, je viens du monde Java et C ++ ) dans lequel 4 octets (32 bits) sont requis, un caractère non signé nécessite 1 octet (8 bits). il peut donc réduire la taille totale de la baie de 75%.

Vous avez décrit succinctement toutes les caractéristiques de distribution de votre tableau; lancez le tableau .

Vous pouvez facilement remplacer le tableau par une méthode aléatoire qui produit la même sortie probabiliste que le tableau.

Si la cohérence est importante (produire la même valeur pour le même index aléatoire), envisagez d'utiliser un filtre de floraison et / ou une carte de hachage pour suivre les hits répétés. Si les accès à votre tableau sont vraiment aléatoires, cela est totalement inutile.