Une possibilité simple qui me 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'indice de l'élément d'origine, 8 bits pour la valeur réelle, soit (idx << 8) | value) ) trié pour les 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 la rechercher dans le tableau secondaire. Ici, vous allez effectuer une recherche binaire pour trouver la valeur 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 extraire la valeur du bidule de 4 octets.
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 comme celui que vous proposez, cela devrait prendre 10000000 / 4 = 2500000 octets pour le premier tableau, plus 10000000 * 1% * 4 B = 400000 octets pour le second tableau ; donc 2900000 octets, c'est-à-dire moins d'un tiers du tableau original, et la partie la plus utilisée est conservée ensemble en mémoire, ce qui devrait être bon pour la mise en cache (cela peut même convenir à L3).
Si vous avez besoin de plus d'un adressage de 24 bits, vous devrez modifier le "stockage secondaire" ; une façon triviale de l'étendre est d'avoir un tableau de pointeurs de 256 éléments pour basculer les 8 premiers bits de l'index et les transmettre à un tableau trié indexé de 24 bits comme ci-dessus.
Comparaison 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 de 10M éléments avec des données aléatoires distribuées comme OP l'a spécifié dans son post, initialise ma structure de données et ensuite :
- effectue une recherche aléatoire de 10M éléments avec ma structure de données
- fait la même chose à travers le tableau original.
(remarquez que dans le cas d'une recherche séquentielle, le tableau est toujours largement gagnant, car il s'agit de la recherche la plus respectueuse de la mémoire 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 consultation sont calculés et imprimés, ainsi que la vitesse (moyenne de la consultation/moyenne du tableau).
J'ai compilé le code ci-dessus avec g++ 5.4.0 ( -O3 -static et quelques avertissements) sur Ubuntu 16.04, et je l'ai exécuté sur quelques machines ; la plupart d'entre elles fonctionnent sous Ubuntu 16.04, certaines sous des Linux plus anciens, d'autres sous des Linux plus récents. Je ne pense pas que le système d'exploitation devrait être pertinent 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 !
- En général, sur la plupart de ces machines, il y a une sorte de gain de vitesse, ou du moins, elles sont sur un pied d'égalité.
- Les deux cas où le tableau l'emporte vraiment sur le lookup de la "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, en ce moment plutôt inactive ; le Xeon E5-2697 (35 Mo de cache) est une machine pour les calculs de haute performance, dans un moment d'inactivité aussi. C'est logique, le tableau original tient entièrement dans leur énorme cache, donc la structure de données compacte ne fait qu'ajouter de la complexité.
- De l'autre côté du "spectre des performances" - mais là encore, la matrice est légèrement plus rapide - il y a l'humble Celeron qui alimente mon NAS ; il a si peu de cache que ni la matrice ni la "structure intelligente" n'y trouvent leur place. D'autres machines avec un cache suffisamment petit ont des performances similaires.
- Le Xeon X5650 doit être pris avec une certaine prudence - il s'agit de machines virtuelles sur un serveur de machines virtuelles à deux sockets très occupé ; il se peut que, bien qu'il dispose nominalement d'une quantité décente de mémoire cache, il ait été préempté plusieurs fois par des machines virtuelles sans aucun rapport pendant la durée du test.
