c++ - indicadores - matriz de confusion precision

¿Alguna optimización para el acceso aleatorio en una matriz muy grande cuando el valor en el 95% de los casos es 0 o 1?

Question

¿Existe alguna optimización posible para el acceso aleatorio en una matriz muy grande (actualmente uso uint8_t , y estoy preguntando qué es mejor)

uint8_t MyArray[10000000];

cuando el valor en cualquier posición en la matriz es

• 0 o 1 para el 95% de todos los casos,
• 2 en el 4% de los casos,
• ¿Entre 3 y 255 en el otro 1% de los casos?

Entonces, ¿hay algo mejor que una matriz uint8_t para usar para esto? Debería ser lo más rápido posible recorrer todo el arreglo en un orden aleatorio, y esto es muy pesado en el ancho de banda de la RAM, por lo que al tener más de unos pocos subprocesos al mismo tiempo para diferentes arreglos, actualmente todo el ancho de banda de la RAM se satura rapidamente

Estoy preguntando porque se siente muy ineficiente tener una matriz tan grande (10 MB) cuando se sabe que casi todos los valores, aparte del 5%, serán 0 o 1. Entonces, cuando el 95% de todos los valores de la matriz en realidad solo necesitaría 1 bit en lugar de 8 bit, esto reduciría el uso de memoria en casi un orden de magnitud. Se siente como que tiene que haber una solución más eficiente en memoria que reduciría en gran medida el ancho de banda de RAM requerido para esto, y como resultado también será significativamente más rápido para el acceso aleatorio.

Answer 1

Como menciona Mats en su comentario-respuesta, es difícil decir cuál es realmente la mejor solución sin saber específicamente qué tipo de datos tiene (por ejemplo, si hay tiradas largas de 0, etc.) y cuál es su patrón de acceso. like (significa "aleatorio" significa "en todo el lugar" o simplemente "no estrictamente de manera completamente lineal" o "cada valor exactamente una vez, solo aleatorio" o ...).

Dicho esto, hay dos mecanismos que vienen a la mente:

• Arreglos de bits; es decir, si solo tuvieras dos valores, podrías comprimir tu matriz trivialmente por un factor de 8; Si tiene 4 valores (o "3 valores + todo lo demás") puede comprimir por un factor de dos. Lo que podría no valer la pena y necesitaría puntos de referencia, especialmente si tiene patrones de acceso realmente aleatorios que escapan de sus cachés y, por lo tanto, no cambian el tiempo de acceso en absoluto.
• (index,value) o (value,index) tablas. Es decir, tener una tabla muy pequeña para el caso del 1%, tal vez una tabla para el caso del 5% (que solo necesita almacenar los índices, ya que todos tienen el mismo valor), y una gran matriz de bits comprimidos para los dos casos finales. Y con "tabla" me refiero a algo que permite una búsqueda relativamente rápida; es decir, tal vez un hash, un árbol binario, etc., dependiendo de lo que tenga disponible y sus necesidades reales. Si estas subtablas encajan en sus cachés de 1º / 2º nivel, es posible que tenga suerte.

Answer 2

No estoy muy familiarizado con C, pero en C ++ puede usar caracteres sin signo para representar un número entero en el rango de 0 a 255.

Comparado con el int normal (de nuevo, vengo del mundo Java y C ++ ) en el que se requieren 4 bytes (32 bits), un carácter sin signo requiere 1 byte (8 bits). por lo que podría reducir el tamaño total de la matriz en un 75%.

Answer 3

Usted ha descrito sucintamente todas las características de distribución de su matriz; tirar la matriz .

Puede reemplazar fácilmente la matriz con un método aleatorio que produce la misma salida probabilística que la matriz.

Si la consistencia importa (produciendo el mismo valor para el mismo índice aleatorio), considere usar un filtro de floración y / o un mapa hash para rastrear los hits de repetición. Sin embargo, si los accesos de su matriz son realmente aleatorios, esto es totalmente innecesario.

Answer 4

Viendo esto, podrías dividir tus datos, por ejemplo:

• un conjunto de bits que se indexa y representa el valor 0 (aquí sería útil std :: vector)
• un conjunto de bits que se indexa y representa el valor 1
• a std :: vector para los valores de 2, que contiene los índices que se refieren a este valor
• un mapa para los otros valores (o std :: vector>)

En este caso, todos los valores aparecen hasta un índice determinado, por lo que incluso podría eliminar uno de los conjuntos de bits y representar el valor que falta en los otros.

Esto le ahorrará algo de memoria para este caso, aunque empeoraría el peor de los casos. También necesitarás más potencia de CPU para hacer las búsquedas.

Asegúrese de medir!

Answer 5

A menos que haya un patrón en sus datos, es poco probable que exista una velocidad sensible o una optimización de tamaño y, suponiendo que esté apuntando a una computadora normal, de todos modos, 10 MB no es tan importante.

Hay dos suposiciones en sus preguntas:

1. Los datos se almacenan de forma deficiente porque no está utilizando todos los bits
2. Guardarlo mejor haría las cosas más rápido.

Creo que ambas suposiciones son falsas. En la mayoría de los casos, la forma adecuada de almacenar datos es almacenar la representación más natural. En su caso, este es el que ha elegido: un byte para un número entre 0 y 255. Cualquier otra representación será más compleja y, por lo tanto, todas las demás cosas serán iguales, más lentas y más propensas a errores. Para desviarse de este principio general, necesita una razón más sólida que potencialmente seis bits "desperdiciados" en el 95% de sus datos.

Para su segunda suposición, será cierto si, y solo si, cambiar el tamaño de la matriz da como resultado un número sustancialmente menor de fallos de caché. Si esto sucederá solo se puede determinar de manera definitiva perfilando el código de trabajo, pero creo que es muy poco probable que marque una diferencia sustancial. Debido a que accederá a la matriz de forma aleatoria en cualquier caso, el procesador tendrá dificultades para saber qué bits de datos se almacenarán en la caché y se guardarán en cualquier caso.

Answer 6

Esto es más un "comentario largo" que una respuesta concreta.

A menos que sus datos sean algo bien conocido, dudo que alguien pueda contestar DIRECTAMENTE su pregunta (y no conozco nada que coincida con su descripción, pero entonces no sé TODO sobre todo tipo de patrones de datos para todos tipos de casos de uso). Los datos dispersos son un problema común en la computación de alto rendimiento, pero por lo general "tenemos una matriz muy grande, pero solo algunos valores son distintos de cero".

Para patrones no conocidos como lo que creo que es tuyo, nadie SABERá directamente cuál es mejor, y depende de los detalles: qué tan aleatorio es el acceso aleatorio - es el sistema que accede a grupos de elementos de datos, o es completamente aleatorio, como desde un generador de números aleatorios uniforme. ¿Los datos de la tabla son completamente aleatorios, o hay secuencias de 0 y luego secuencias de 1, con una dispersión de otros valores? La codificación de longitud de ejecución funcionaría bien si tiene secuencias razonablemente largas de 0 y 1, pero no funcionará si tiene un "tablero de ajedrez de 0/1". Además, tendría que mantener una tabla de "puntos de partida", de modo que pueda trabajar en el lugar correspondiente de manera razonablemente rápida.

Sé desde hace mucho tiempo que algunas grandes bases de datos son solo una tabla grande en la RAM (datos de suscriptor de central telefónica en este ejemplo), y uno de los problemas es que los cachés y las optimizaciones de la tabla de páginas en el procesador son bastante inútiles. La persona que llama es tan raramente la misma que alguien que llama recientemente, que no hay datos precargados de ningún tipo, es simplemente aleatorio. Las tablas de páginas grandes son la mejor optimización para ese tipo de acceso.

En muchos casos, comprometerse entre "velocidad y tamaño pequeño" es una de esas cosas entre las que debe elegir en ingeniería de software [en otra ingeniería no es necesariamente tanto un compromiso]. Por lo tanto, "la pérdida de memoria para un código más simple" es a menudo la opción preferida. En este sentido, es probable que la solución "simple" sea mejor para la velocidad, pero si tiene un uso "mejor" para la RAM, entonces la optimización del tamaño de la tabla le dará un rendimiento suficiente y una buena mejora en el tamaño. Hay muchas formas diferentes de lograrlo, como se sugiere en un comentario, un campo de 2 bits donde se almacenan los dos o tres valores más comunes, y luego algún formato de datos alternativo para los otros valores: una tabla hash sería mi primer acercamiento, pero una lista o un árbol binario también puede funcionar; de nuevo, depende de los patrones de dónde se encuentre su "no 0, 1 o 2". De nuevo, depende de cómo están "dispersos" los valores en la tabla: ¿están en grupos o son más un patrón distribuido de manera uniforme?

Pero un problema con eso es que todavía estás leyendo los datos de la memoria RAM. Entonces está gastando más código en el procesamiento de los datos, incluido un código para hacer frente al "este no es un valor común".

El problema con la mayoría de los algoritmos de compresión comunes es que se basan en secuencias de desempaquetado, por lo que no puede acceder a ellos al azar. Y la sobrecarga de dividir su big data en trozos de, digamos, 256 entradas a la vez, y descomprimir 256 en una matriz uint8_t, obtener los datos que desea y luego desechar los datos sin comprimir, es muy poco probable que le brinde una buena idea. desempeño - asumiendo que eso es de alguna importancia, por supuesto.

Al final, probablemente tendrá que implementar una o algunas de las ideas en los comentarios / respuestas para probar, ver si ayuda a resolver su problema o si el bus de memoria sigue siendo el principal factor limitante.

Answer 7

Hace mucho tiempo, solo puedo recordar ...

En la universidad conseguimos una tarea para acelerar un programa de trazador de rayos, que tiene que leer por algoritmo una y otra vez desde arreglos de búferes. Un amigo me dijo que siempre usara lecturas RAM que son múltiplos de 4Bytes. Así que cambié la matriz de un patrón de [x1, y1, z1, x2, y2, z2, ..., xn, yn, zn] a un patrón de [x1, y1, z1,0, x2, y2, z2 , 0, ..., xn, yn, zn, 0]. Significa que agrego un campo vacío después de cada coordenada 3D. Después de algunas pruebas de rendimiento: fue más rápido. Tan larga historia corta: lea múltiples de 4 bytes de su matriz desde la RAM, y tal vez también desde la posición de inicio correcta, de modo que lea un pequeño grupo donde se encuentra el índice buscado y lea el índice buscado de este pequeño grupo en la CPU. (En su caso, no necesitará insertar campos de relleno, pero el concepto debería ser claro)

Quizás también otros múltiplos podrían ser la clave en los sistemas más nuevos.

No sé si esto funcionará en su caso, así que si no funciona: Lo siento. Si funciona, me encantaría saber sobre los resultados de algunas pruebas.

PD: Ah, y si hay algún patrón de acceso o índices de acceso cercanos, puede reutilizar el clúster en caché.

PPS: Podría ser que el factor múltiple se pareciera más a 16Bytes o algo así, hace mucho tiempo, que puedo recordar exactamente.

Answer 8

Lo agregaré a la respuesta de @ o11c , ya que su redacción puede ser un poco confusa. Si necesito comprimir el último bit y el ciclo de la CPU, haría lo siguiente.

Comenzaremos por construir un árbol de búsqueda binario equilibrado que contenga el 5% de los casos de "otra cosa". Por cada búsqueda, caminas por el árbol rápidamente: tienes 10000000 elementos, de los cuales el 5% está en el árbol: por lo tanto, la estructura de datos del árbol contiene 500000 elementos. Caminar esto en tiempo O (log (n)), le da 19 iteraciones. No soy un experto en esto, pero creo que hay algunas implementaciones de memoria eficiente por ahí. Vamos a estimar:

• Árbol equilibrado, por lo que se puede calcular la posición del subárbol (los índices no necesitan almacenarse en los nodos del árbol). De la misma manera se almacena un montón (estructura de datos) en la memoria lineal.
• Valor de 1 byte (2 a 255)
• 3 bytes para el índice (10000000 toma 23 bits, que se ajusta a 3 bytes)

Total, 4 bytes: 500000 * 4 = 1953 kB. Se ajusta a la caché!

Para todos los otros casos (0 o 1), puede usar un bitvector. Tenga en cuenta que no puede omitir el 5% de otros casos para acceso aleatorio: 1.19 MB.

La combinación de estos dos utiliza aproximadamente 3.099 MB. Usando esta técnica, ahorrará un factor 3.08 de memoria.

Sin embargo, esto no supera la respuesta de @Matteo Italia (que usa 2.76 MB), una pena. ¿Hay algo que podamos hacer extra? La parte que más consume memoria es los 3 bytes del índice en el árbol. Si pudiéramos reducir esto a 2, ahorraríamos 488 kB y el uso total de memoria sería: 2.622 MB, ¡que es más pequeño!

Cómo hacemos esto? Tenemos que reducir la indexación a 2 bytes. De nuevo, 10000000 toma 23 bits. Necesitamos poder caer 7 bits. Podemos hacerlo simplemente dividiendo el rango de 10000000 elementos en 2 ^ 7 (= 128) regiones de 78125 elementos. Ahora podemos construir un árbol equilibrado para cada una de estas regiones, con un promedio de 3906 elementos. La selección del árbol correcto se realiza mediante una división simple del índice objetivo por 2 ^ 7 (o un cambio de bits >> 7 ). Ahora el índice requerido para almacenar puede representarse por los 16 bits restantes. Tenga en cuenta que hay algunos gastos generales para la longitud del árbol que debe almacenarse, pero esto es insignificante. También tenga en cuenta que este mecanismo de división reduce el número requerido de iteraciones para recorrer el árbol, esto ahora se reduce a 7 iteraciones menos, porque eliminamos 7 bits: solo quedan 12 iteraciones.

Tenga en cuenta que, en teoría, podría repetir el proceso para cortar los siguientes 8 bits, pero esto requerirá que cree 2 ^ 15 árboles balanceados, con ~ 305 elementos en promedio. Esto daría como resultado 2.143 MB, con solo 4 iteraciones para caminar por el árbol, lo cual es una aceleración considerable, en comparación con las 19 iteraciones con las que comenzamos.

Como conclusión final: esto supera la estrategia de vector de 2 bits por un poco de uso de memoria, pero es una lucha total para implementar. Pero si puede hacer la diferencia entre ajustar el caché o no, puede valer la pena intentarlo.

Answer 9

Lo que he hecho en el pasado es usar un hashmap delante de un conjunto de bits.

Esto reduce a la mitad el espacio en comparación con la respuesta de Matteo, pero puede ser más lento si las búsquedas de "excepción" son lentas (es decir, hay muchas excepciones).

A menudo, sin embargo, "el caché es el rey".

Answer 10

Otra opción podría ser

• Comprueba si el resultado es 0, 1 o 2.
• si no hacer una búsqueda regular

En otras palabras, algo como:

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

donde bmap usa 2 bits por elemento con el valor 3 que significa "otro".

Esta estructura es trivial de actualizar, usa un 25% más de memoria, pero la gran parte se busca solo en el 5% de los casos. Por supuesto, como de costumbre, si es una buena idea o no, depende de muchas otras condiciones, por lo que la única respuesta es experimentar con el uso real.

Answer 11

Si los datos y los accesos se distribuyen de manera uniforme y aleatoria, el rendimiento probablemente dependerá de qué fracción de accesos evite una falla de caché de nivel externo. La optimización requerirá saber qué tamaño de matriz se puede acomodar de manera confiable en la memoria caché. Si su caché es lo suficientemente grande para acomodar un byte por cada cinco celdas, el enfoque más simple puede ser tener un byte que contenga los cinco valores codificados de tres bases en el rango 0-2 (hay 243 combinaciones de 5 valores, por lo que encajar en un byte), junto con una matriz de 10,000,000 byte que se consultaría siempre que el valor de base-3 indique "2".

Si el caché no es tan grande, pero podría acomodar un byte por 8 celdas, entonces no sería posible usar un valor de byte para seleccionar entre todas las 6,561 combinaciones posibles de ocho valores de base-3, pero ya que el único efecto de cambiar un 0 o un 1 a un 2 sería causar una búsqueda innecesaria, la corrección no requeriría el soporte de todos los 6,561. En su lugar, uno podría centrarse en los 256 valores más "útiles".

Especialmente si 0 es más común que 1, o viceversa, un buen enfoque podría ser usar 217 valores para codificar las combinaciones de 0 y 1 que contienen 5 o menos 1, 16 valores para codificar xxxx0000 hasta xxxx1111, 16 para codificar 0000xxxx hasta 1111xxxx, y uno para xxxxxxxx. Cuatro valores permanecerían para cualquier otro uso que uno pudiera encontrar. Si los datos se distribuyen aleatoriamente como se describe, una ligera mayoría de todas las consultas alcanzaría bytes que contenían solo ceros y unos (en aproximadamente 2/3 de todos los grupos de ocho, todos los bits serían ceros y unos, y aproximadamente 7/8 de esos tendrían seis o menos 1 bits); la gran mayoría de los que no lo hicieron aterrizarían en un byte que contenía cuatro x, y tendrían un 50% de posibilidades de aterrizar en un cero o en uno. Por lo tanto, solo una de cada cuatro consultas necesitaría una búsqueda de gran tamaño.

Si los datos se distribuyen aleatoriamente pero la memoria caché no es lo suficientemente grande como para manejar un byte por ocho elementos, se podría intentar usar este enfoque con cada byte que maneja más de ocho elementos, pero a menos que haya una fuerte inclinación hacia 0 o hacia 1 , la fracción de valores que se pueden manejar sin tener que hacer una búsqueda en la gran matriz se reducirá a medida que aumenta el número manejado por cada byte.

Answer 12

Si solo realiza operaciones de lectura, sería mejor no asignar un valor a un solo índice sino a un intervalo de índices.

Por ejemplo:

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

Esto se puede hacer con una estructura. También es posible que desee definir una clase similar a esta si le gusta un enfoque 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
}

Ahora solo tiene que recorrer una lista de intervalos y comprobar si su índice se encuentra dentro de uno de ellos, lo que puede ser mucho menos intensivo en memoria en promedio pero cuesta más recursos de 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 ordena los intervalos por tamaño descendente, aumenta la probabilidad de que el elemento que está buscando se encuentre temprano, lo que disminuye aún más su uso de recursos de CPU y memoria promedio.

También puede eliminar todos los intervalos con un tamaño de 1. Coloque los valores correspondientes en un mapa y verifíquelos solo si el elemento que está buscando no se encontró en los intervalos. Esto también debería elevar un poco el rendimiento promedio.

Answer 13

Una posibilidad simple que viene a la mente es mantener una matriz comprimida de 2 bits por valor para los casos comunes, y un byte separado de 4 bytes por valor (24 bits para el índice del elemento original, 8 bits para el valor real, por lo que (idx << 8) | value) ) arreglo ordenado para los otros.

Cuando busca un valor, primero realiza una búsqueda en la matriz de 2bpp (O (1)); si encuentra 0, 1 o 2 es el valor que desea; si encuentra 3 significa que debe buscarlo en la matriz secundaria. Aquí realizará una búsqueda binaria para buscar el índice de su interés desplazado a la izquierda en 8 (O (log (n) con una pequeña n, ya que debería ser el 1%), y extraer el valor del 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);
    }
}

Para una matriz como la que usted propuso, esto debería tomar 10000000/4 = 2500000 bytes para la primera matriz, más 10000000 * 1% * 4 B = 400000 bytes para la segunda matriz; por lo tanto, 2900000 bytes, es decir, menos de un tercio de la matriz original, y la parte más utilizada se mantienen juntas en la memoria, lo que debería ser bueno para el almacenamiento en caché (incluso puede ajustarse a L3).

Si necesita un direccionamiento de más de 24 bits, deberá modificar el "almacenamiento secundario"; una forma trivial de extenderlo es tener una matriz de punteros de 256 elementos para cambiar los 8 bits superiores del índice y reenviar a una matriz ordenada indexada de 24 bits como se indicó anteriormente.

Punto de referencia rápido

#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;
}

(Código y datos siempre actualizados en mi Bitbucket)

El código anterior llena una matriz de elementos de 10M con datos aleatorios distribuidos como OP especificado en su publicación, inicializa mi estructura de datos y luego:

• realiza una búsqueda aleatoria de elementos de 10M con mi estructura de datos
• hace lo mismo a través de la matriz original.

(Observe que en el caso de una búsqueda secuencial, la matriz siempre gana en gran medida, ya que es la búsqueda más fácil de usar que puede hacer).

Estos dos últimos bloques se repiten 50 veces y se cronometran; al final, se calculan e imprimen la media y la desviación estándar para cada tipo de búsqueda, junto con la aceleración (lookup_mean / array_mean).

Compilé el código anterior con g ++ 5.4.0 ( -O3 -static , más algunas advertencias) en Ubuntu 16.04, y lo ejecuté en algunas máquinas; la mayoría de ellos están ejecutando Ubuntu 16.04, algunos de algunos más antiguos de Linux, algunos más nuevos de Linux. No creo que el sistema operativo deba ser relevante en absoluto en este caso.

            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

Los resultados son ... mezclados!

1. En general, en la mayoría de estas máquinas hay algún tipo de aceleración, o al menos están a la par.
2. Los dos casos en los que la matriz realmente triunfa sobre la búsqueda de "estructura inteligente" se encuentran en máquinas con mucho caché y no están particularmente ocupadas: el Xeon E5-1650 anterior (15 MB de caché) es una máquina de construcción nocturna, en este momento bastante inactiva; El Xeon E5-2697 (caché de 35 MB) es una máquina para cálculos de alto rendimiento, también en un momento de inactividad. Tiene sentido, la matriz original encaja completamente en su enorme caché, por lo que la estructura de datos compacta solo agrega complejidad.
3. En el lado opuesto del "espectro de rendimiento", pero donde la matriz es un poco más rápida, está el humilde Celeron que alimenta mi NAS; tiene tan poco caché que ni la matriz ni la "estructura inteligente" encajan en ella. Otras máquinas con caché lo suficientemente pequeñas funcionan de manera similar.
4. El Xeon X5650 debe tomarse con precaución: son máquinas virtuales en un servidor de máquinas virtuales de doble socket bastante ocupado; bien puede ser que, aunque nominalmente tenga una cantidad decente de memoria caché, durante el tiempo de la prueba sea reemplazado por máquinas virtuales completamente no relacionadas varias veces.