c - orden - lista de etiquetas html

¿Cuál es la forma más eficiente de representar valores pequeños en una estructura? (15)

A menudo me encuentro teniendo que representar una estructura que consiste en valores muy pequeños. Por ejemplo, Foo tiene 4 valores, a, b, c, d que van de 0 to 3 . Por lo general, no me importa, pero a veces, esas estructuras son

utilizado en un circuito cerrado;
sus valores se leen mil millones de veces / s, y ese es el cuello de botella del programa;
el programa completo consiste en una gran variedad de miles de millones de Foo ;

En ese caso, me resulta difícil decidir cómo representar a Foo eficiente. Básicamente tengo 4 opciones:

struct Foo { int a; int b; int c; int d; }; struct Foo { char a; char b; char c; char d; }; struct Foo { char abcd; }; struct FourFoos { int abcd_abcd_abcd_abcd; };

Usan 128, 32, 8, 8 bits respectivamente por Foo , desde dispersos a densos. El primer ejemplo es probablemente el más lingüístico, pero usarlo esencialmente aumentaría en 16 veces el tamaño del programa, lo cual no suena del todo bien. Además, la mayor parte de la memoria se rellenará con ceros y no se utilizará en absoluto, lo que me hace preguntarme si esto no es un desperdicio. Por otro lado, empaquetarlos densamente trae una carga adicional para leerlos.

¿Cuál es el método computacionalmente "más rápido" para representar valores pequeños en una estructura?

Foo tiene 4 valores, a, b, c, d, rango de 0 a 3. Por lo general, no me importa, pero a veces, esas estructuras son ...

Hay otra opción: dado que los valores 0 ... 3 probablemente indiquen algún tipo de estado, podrías considerar usar "banderas"

enum{ A_1 = 1<<0, A_2 = 1<<1, A_3 = A_1|A_2, B_1 = 1<<2, B_2 = 1<<3, B_3 = B_1|B_2, C_1 = 1<<4, C_2 = 1<<5, C_3 = C_1|C_2, D_1 = 1<<6, D_2 = 1<<7, D_3 = D_1|D_2, //you could continue to ... D7_3 for 32/64 bits if it makes sense }

Esto no es muy diferente de usar bitfields para la mayoría de las situaciones, pero puede reducir drásticamente su lógica condicional.

if ( a < 2 && b < 2 && c < 2 && d < 2) // .... (4 comparisons) //vs. if ( abcd & (A_2|B_2|C_2|D_2) !=0 ) //(bitop with constant and a 0-compare)

Dependiendo del tipo de operaciones que vaya a realizar con los datos, puede tener sentido utilizar 4 u 8 conjuntos de abcd y rellenar el extremo con 0 según sea necesario. Eso podría permitir que se reemplacen hasta 32 comparaciones con un bitop y 0-compare. Por ejemplo, si quiere establecer el "1 bit" en los 8 conjuntos de 4 en una variable de 64 bits, puede hacer uint64_t abcd8 = 0x5555555555555555ULL; luego, para establecer los 2 bits que podría hacer abcd8 |= 0xAAAAAAAAAAAAAAAAULL; haciendo todos los valores ahora 3

Adición: En consideración adicional, podría usar una unión como su tipo y hacer una unión con los campos de bits de char y @dbush (estas operaciones de indicador aún funcionarían en la char sin firmar) o usar tipos de caracteres para cada a, b, c, d y unirlos con unsigned int. Esto permitiría una representación compacta y operaciones eficientes dependiendo de qué miembro del sindicato utilice.

union Foo { char abcd; //Note: you can use flags and bitops on this too struct { unsigned char a:2; unsigned char b:2; unsigned char c:2; unsigned char d:2; }; };

O incluso se extendió más

union Foo { uint64_t abcd8; //Note: you can use flags and bitops on these too uint32_t abcd4[2]; uint16_t abcd2[4]; uint8_t abcd[8]; struct { unsigned char a:2; unsigned char b:2; unsigned char c:2; unsigned char d:2; } _[8]; }; union Foo myfoo = {0xFFFFFFFFFFFFFFFFULL}; //assert(myfoo._[0].a == 3 && myfoo.abcd[0] == 0xFF);

Este método introduce algunas diferencias de endianness, lo que también sería un problema si utiliza una unión para cubrir cualquier otra combinación de sus otros métodos.

union Foo { uint32_t abcd; uint32_t dcba; //only here for endian purposes struct { //anonymous struct char a; char b; char c; char d; }; };

Puede experimentar y medir con diferentes tipos de unión y algoritmos para ver qué partes de las uniones valen la pena, luego descartar aquellas que no son útiles. Puede encontrar que operar en varios tipos de char / short / int se optimiza automáticamente para una combinación de instrucciones AVX / simd, mientras que usar bitfields no lo hace a menos que los desenrolle manualmente ... no hay forma de saberlo hasta que los pruebe y mida. .

Matrices masivas y errores de falta de memoria

el programa completo consiste en una gran variedad de miles de millones de Foos;

Lo primero es lo primero, para el n. ° 2, es posible que usted o sus usuarios (si otros ejecutan el software) a menudo no puedan asignar esta matriz con éxito si abarca gigabytes. Un error común aquí es pensar que los errores de falta de memoria significan "no hay más memoria disponible" , cuando en su lugar a menudo significa que el sistema operativo no pudo encontrar un conjunto contiguo de páginas no utilizadas que coinciden con el tamaño de memoria solicitado. Es por esta razón que las personas a menudo se confunden cuando solicitan asignar un bloque de un gigabyte solo para que falle aunque tengan 30 gigabytes de memoria física libre, por ejemplo, una vez que comienzas a asignar memoria en tamaños que abarcan más de, por ejemplo, 1 % de la cantidad típica de memoria disponible, a menudo es hora de considerar evitar una matriz gigante para representar todo.

Entonces, quizás lo primero que debe hacer es reconsiderar la estructura de datos. En lugar de asignar una única matriz de miles de millones de elementos, a menudo reducirá significativamente las probabilidades de tener problemas asignando en fragmentos más pequeños (matrices más pequeñas agregadas juntas). Por ejemplo, si su patrón de acceso es únicamente de naturaleza secuencial, puede usar una lista desenrollada (matrices vinculadas entre sí). Si se necesita acceso aleatorio, puede usar algo así como una matriz de punteros a las matrices, que abarcan 4 kilobytes cada una. Esto requiere un poco más de trabajo para indexar un elemento, pero con este tipo de escala de miles de millones de elementos, a menudo es una necesidad.

Patrones de acceso

Una de las cosas no especificadas en la pregunta son los patrones de acceso a la memoria. Esta parte es crítica para guiar tus decisiones.

Por ejemplo, ¿se atraviesa la estructura de datos secuencialmente o se necesita acceso aleatorio? ¿Son necesarios todos estos campos: a , b , c , d , todo el tiempo, o se puede acceder a ellos uno, dos o tres a la vez?

Tratemos de cubrir todas las posibilidades. En la escala de la que estamos hablando, esto:

struct Foo { int a1; int b1; int c1; int d1 };

... es poco probable que sea útil. En este tipo de escala de entrada, y accedido en bucles ajustados, sus tiempos generalmente estarán dominados por los niveles superiores de la jerarquía de la memoria (paginación y memoria caché de la CPU). Ya no se vuelve tan crítico centrarse en el nivel más bajo de la jerarquía (registros e instrucciones asociadas). Para decirlo de otra manera, con miles de millones de elementos para procesar, lo último que debe preocuparse es el costo de mover esta memoria de las líneas de caché L1 a los registros y el costo de las instrucciones bit a bit, por ejemplo (no diciendo que no es una preocupación todo, simplemente diciendo que es una prioridad mucho menor).

En una escala suficientemente pequeña donde la totalidad de los datos candentes se ajustan a la caché de la CPU y la necesidad de acceso aleatorio, este tipo de representación directa puede mostrar una mejora en el rendimiento debido a las mejoras en el nivel más bajo de la jerarquía (registros e instrucciones) , sin embargo, requeriría una entrada a una escala drásticamente más pequeña de lo que estamos hablando.

Así que incluso esto es probable que sea una mejora considerable:

struct Foo { char a1; char b1; char c1; char d1; };

... y esto aún más:

// Each field packs 4 values with 2-bits each. struct Foo { char a4; char b4; char c4; char d4; };

_{* Tenga en cuenta que puede usar bitfields para lo anterior, pero los bitfields tienden a tener advertencias asociadas con ellos dependiendo del compilador que se use.} _{A menudo he tenido cuidado de evitarlos debido a los problemas de portabilidad descritos comúnmente, aunque esto puede ser innecesario en su caso.} _{Sin embargo, a medida que nos aventuramos en SoA y en los territorios de división de campos fríos / calientes a continuación, llegaremos a un punto en el que los campos de bit no se podrán usar de todos modos.}

Este código también se centra en la lógica horizontal, que puede comenzar a facilitar la exploración de otras rutas de optimización (por ejemplo, la transformación del código para usar SIMD), ya que se encuentra en una miniatura SoA.

Datos "Consumo"

Especialmente en este tipo de escala, y más aún cuando el acceso a la memoria es de naturaleza secuencial, ayuda a pensar en términos de "consumo" de datos (qué tan rápido la máquina puede cargar datos, hacer la aritmética necesaria y almacenar los resultados) . Una imagen mental simple que encuentro útil es imaginar que la computadora tiene una "gran boca". Va más rápido si le damos suficientes cucharadas de datos a la vez, no pequeñas cucharaditas de té, y con datos más relevantes empacados en una cucharada contigua.

División de campo caliente / frío

Hasta el momento, el código anterior asume que todos estos campos son igualmente candentes (se accede con frecuencia) y se accede juntos. Es posible que tenga algunos campos o campos fríos a los que solo se accede en rutas de código críticas por pares. Digamos que rara vez accedes a d , o que tu código tiene un ciclo crítico que accede b , y otro que accede a d . En ese caso, puede ser útil dividirlo en dos estructuras:

struct Foo1 { char a4; char b4; }; struct Foo2 { char c4; char d4; };

De nuevo, si estamos "alimentando" los datos de la computadora, y nuestro código solo está interesado en los campos b en este momento, podemos empacar más en cucharadas de los campos a y b si tenemos bloques contiguos que solo contienen los campos a y b , y no los campos d . En tal caso, los campos d serían datos que la computadora no puede digerir en este momento, pero se mezclarían en las regiones de memoria entre los campos a y b . Si queremos que la computadora consuma datos lo más rápido posible, solo deberíamos proporcionarle los datos relevantes de interés en este momento, por lo que vale la pena dividir las estructuras en estos escenarios.

SIMD SoA para acceso secuencial

Avanzando hacia la vectorización, y asumiendo el acceso secuencial, la velocidad más rápida a la que la computadora puede consumir datos a menudo será paralela usando SIMD. En tal caso, podríamos terminar con una representación como esta:

struct Foo1 { char* a4n; char* b4n; };

... prestando especial atención a la alineación y el relleno (el tamaño / alineación debe ser un múltiplo de 16 o 32 bytes para AVX o incluso 64 para AVX-512 futurista) necesario para usar movimientos alineados más rápidos en los registros XMM / YMM (y posiblemente con Instrucciones de AVX en el futuro).

AoSoA para acceso aleatorio / multicampo

Desafortunadamente, la representación anterior puede comenzar a perder muchos de los beneficios potenciales si a y b se acceden frecuentemente juntos, especialmente con un patrón de acceso aleatorio. En tal caso, una representación más óptima puede comenzar a verse así:

struct Foo1 { char a4x32[32]; char b4x32[32]; };

... donde ahora estamos agregando esta estructura. Esto hace que los campos a y b ya no estén tan separados, lo que permite que grupos de 32 campos a y b quepan en una única línea de caché de 64 bytes y que se acceda a ellos rápidamente. También podemos colocar 128 o 256 elementos a b en un registro XMM / YMM.

Perfilado

Normalmente trato de evitar el consejo de sabiduría general en las preguntas de rendimiento, pero noté que este parece evitar los detalles que alguien que tiene un perfilador en la mano suele mencionar. Así que me disculpo si esto sale un poco como condescendiente o si un generador de perfiles ya se está utilizando activamente, pero creo que la pregunta garantiza esta sección.

Como anécdota, a menudo he hecho un mejor trabajo (¡no debería!) En la optimización del código de producción escrito por personas que tienen un conocimiento mucho mejor que yo sobre la arquitectura de la computadora (trabajé con mucha gente que vino de la tarjeta perforada era y puede entender el código ensamblador de un vistazo), y a menudo se llamaba para optimizar su código (que se sentía realmente extraño). Es por una simple razón: "hice trampa" y usé un generador de perfiles (VTune). Mis compañeros a menudo no (tenían alergia y pensaban que entendían los puntos de acceso tan bien como un generador de perfiles y consideraban la creación de perfiles como una pérdida de tiempo).

Por supuesto, lo ideal es encontrar a alguien que tenga la experiencia en arquitectura de la computadora y un perfilador en la mano, pero al carecer de uno u otro, el perfilador puede darle la ventaja más grande. La optimización aún recompensa una mentalidad de productividad que depende de la priorización más efectiva, y la priorización más efectiva es optimizar las partes que realmente importan más. El generador de perfiles nos proporciona desgloses detallados de cuánto tiempo se gasta exactamente y dónde, junto con métricas útiles como errores de caché y errores de predicción de ramas que ni siquiera los humanos más avanzados pueden predecir en un lugar tan preciso como un perfilador puede revelar. Además, la creación de perfiles a menudo es la clave para descubrir cómo funciona la arquitectura de la computadora a un ritmo más rápido al buscar puntos de acceso e investigar por qué existen. Para mí, la creación de perfiles fue el último punto de entrada para comprender mejor cómo funciona realmente la arquitectura de la computadora y no cómo me imaginaba que funcionaba. Fue solo entonces que las escrituras de alguien tan experimentado en este sentido como Mysticial comenzaron a tener más y más sentido.

Diseño de interfaz

Una de las cosas que podría comenzar a ser evidente aquí es que hay muchas posibilidades de optimización. Las respuestas a este tipo de preguntas van a ser estrategias más que enfoques absolutos. Aún hay que descubrir mucho en retrospectiva después de probar algo, y aún iterar hacia soluciones cada vez más óptimas a medida que las necesite.

One of the difficulties here in a complex codebase is leaving enough breathing room in the interfaces to experiment and try different optimization techniques, to iterate and iterate towards faster solutions. If the interface leaves room to seek these kinds of optimizations, then we can optimize all day long and often get some marvelous results if we''re measuring things properly even with a trial and error mindset.

To often leave enough breathing room in an implementation to even experiment and explore faster techniques often requires the interface designs to accept data in bulk . This is especially true if the interfaces involve indirect function calls (ex: through a dylib or a function pointer) where inlining is no longer an effective possibility. In such scenarios, leaving room to optimize without cascading interface breakages often means designing away from the mindset of receiving simple scalar parameters in favor of passing pointers to whole chunks of data (possibly with a stride if there are various interleaving possibilities). So while this is straying into a pretty broad territory, a lot of the top priorities in optimizing here are going to boil down to leaving enough breathing room to optimize implementations without cascading changes throughout your codebase, and having a profiler in hand to guide you the right way.

TL; DR

Anyway, some of these strategies should help guide you the right way. There are no absolutes here, only guides and things to try out, and always best done with a profiler in hand. Yet when processing data of this enormous scale, it''s always worth remembering the image of the hungry monster, and how to most effectively feed it these appropriately-sized and packed spoonfuls of relevant data.

Ajustar su conjunto de datos en la memoria caché es fundamental. Más pequeño siempre es mejor, porque hyperthreading comparte de manera competitiva las cachés por núcleo entre los subprocesos de hardware (en las CPU de Intel). Los comentarios sobre esta respuesta incluyen algunos números para los costos de errores de caché.

En x86 , cargar valores de 8 bits con signo o extensión cero en registros de 32 o 64 bits ( movzx o movsx ) es literalmente tan rápido como el mov simple de un byte o dword de 32 bits. Almacenar el byte bajo de un registro de 32 bits tampoco tiene sobrecarga. (Consulte las tablas de instrucciones de Agner Fog y las guías de optimización C / asm aquí ).

Todavía específico de x86: [u]int8_t temporales también son correctos, pero evite los [u]int16_t temporales. (Cargar / almacenar desde / hasta [u]int16_t en la memoria está bien, pero trabajar con valores de 16 bits en registros tiene grandes penalizaciones desde el decodificador de prefijo de tamaño de operando lentamente en las CPU de Intel). Los temporales de 32 bits serán más rápidos si desea usarlos como un índice de matriz. (El uso de registros de 8 bits no pone a cero el valor alto de 24/56 bits, por lo que se necesita una instrucción adicional para poner en cero o extender, usar un registro de 8 bits como un índice de matriz o una expresión con un tipo más amplio (como agregarlo a un int .)

No estoy seguro de qué ARM u otras arquitecturas pueden hacer en cuanto a la extensión eficiente de cero / signo a partir de cargas de un solo byte, o para almacenes de un solo byte.

Dado esto, mi recomendación es paquete para almacenamiento, uso int para temporales . (O long , pero eso aumentará ligeramente el tamaño del código en x86-64, porque se necesita un prefijo REX para especificar un tamaño de operando de 64 bits). Por ejemplo,

int a_i = foo[i].a; int b_i = foo[i].b; ...; foo[i].a = a_i + b_i;

campos de bit

Empacar en bitfields tendrá más sobrecarga, pero aún puede valer la pena. Probar una posición de bit de constante de tiempo de compilación (o varios bits) en un byte o en un fragmento de 32 bits de 64 bits de memoria es rápido. Si realmente necesita descomprimir algunos campos de bits en int y pasarlos a una llamada de función no en línea o algo así, eso requerirá un par de instrucciones adicionales para cambiar y enmascarar. Si esto da incluso una pequeña reducción en errores de caché, esto puede valer la pena.

Probar, establecer (a 1) o borrar (a 0) un bit o grupo de bits se puede hacer eficientemente con OR o AND , pero asignar un valor booleano desconocido a un campo de bits requiere más instrucciones para fusionar los nuevos bits con los bits para otra campos. Esto puede aumentar significativamente el código si asigna una variable a un campo de bits con mucha frecuencia. Así que usar int foo:6 y cosas así en tus estructuras, porque sabes que foo no necesita los dos primeros bits, probablemente no sea útil. Si no está guardando muchos bits en comparación con poner cada cosa en su propio byte / short / int, entonces la reducción en errores de caché no superará las instrucciones adicionales (que pueden sumarse a carencias de I-cache / uop-cache, así como la latencia extra directa y el trabajo de las instrucciones).

Las extensiones del conjunto de instrucciones x86 BMI1 / BMI2 (Bit-Manipulation) harán que la copia de datos de un registro en algunos bits de destino (sin tropezar con los bits que la rodean) sea más eficiente. BMI1: Haswell, Piledriver. BMI2: Haswell, Excavator (inédito). Tenga en cuenta que, al igual que SSE / AVX, esto significa que necesitará versiones de BMI de sus funciones y versiones de recuperación de versiones anteriores a BMI para las CPU que no son compatibles con esas instrucciones. AFAIK, los compiladores no tienen opciones para ver patrones de estas instrucciones y usarlas automáticamente. Solo se pueden usar a través de intrinsics (o asm).

La respuesta de Dbush , empaquetar en bitfields es probablemente una buena opción, dependiendo de cómo uses tus campos. Su cuarta opción (de empaquetar cuatro valores abcd separados en una estructura) es probablemente un error, a menos que pueda hacer algo útil con cuatro valores abcd secuenciales (estilo vectorial).

código genéricamente, prueba ambas formas

Para una estructura de datos que su código utiliza ampliamente, tiene sentido configurar las cosas para que pueda pasar de una implementación a otra, y punto de referencia. La respuesta de Nir Friedman, con getters / setters es una buena forma de hacerlo. Sin embargo, solo usar int temporaries y trabajar con los campos como miembros separados de struct debería funcionar bien. Depende del compilador generar código para probar los bits correctos de un byte, para los campos de bits empaquetados.

prepararse para SIMD, si está justificado

Si tiene algún código que verifique solo uno o un par de campos de cada estructura, esp. haciendo un bucle sobre los valores de estructura secuencial, entonces la respuesta de struct-of-arrays dada por cmaster será útil. Las instrucciones vectoriales x86 tienen un solo byte como la granularidad más pequeña, por lo que una estructura de matrices con cada valor en un byte separado le permitirá escanear rápidamente el primer elemento donde a == something , usando PCMPEQB / PTEST .

Codifíquelo con int s

tratar los campos como int s.

blah.x en todo tu código, excepto que la declaración será todo lo que harás. La promoción integral se ocupará de la mayoría de los casos.

Cuando haya terminado, tenga 3 archivos de inclusión equivalentes: un archivo de inclusión usando int s, uno usando char y otro usando bitfields.

Y luego perfil. No se preocupe en este momento, porque su optimización prematura y nada más que su archivo de inclusión elegido cambiará.

Creo que la única respuesta real puede ser escribir tu código genéricamente y luego perfilar el programa completo con todos ellos. No creo que esto tome mucho tiempo, aunque puede parecer un poco más incómodo. Básicamente, haría algo como esto:

template <bool is_packed> class Foo; using interface_int = char; template <> class Foo<true> { char m_a, m_b, m_c, m_d; public: void setA(interface_int a) { m_a = a; } interface_int getA() { return m_a; } ... } template <> class Foo<false> { char m_data; public: void setA(interface_int a) { // bit magic changes m_data; } interface_int getA() { // bit magic gets a from m_data; } }

Si solo escribe su código de esta manera en lugar de exponer los datos brutos, será fácil cambiar las implementaciones y el perfil. Las llamadas a funciones se incluirán en línea y no afectarán el rendimiento. Tenga en cuenta que acabo de escribir setA y getA en lugar de una función que devuelve una referencia, esto es más complicado de implementar.

Empaquelos solo si el espacio es una consideración, por ejemplo, una matriz de 1,000,000 de estructuras. De lo contrario, el código necesario para hacer cambios y enmascaramiento es mayor que el ahorro en espacio para los datos. Por lo tanto, es más probable que tenga un error de caché en el I-cache que el D-cache.

No hay una respuesta definitiva, y no ha dado suficiente información para permitir que se haga una elección "correcta". Hay intercambios.

Su afirmación de que su "objetivo principal es la eficiencia de tiempo" es insuficiente, ya que no ha especificado si el tiempo de E / S (por ejemplo, para leer datos del archivo) es más preocupante que la eficiencia computacional (por ejemplo, cuánto tiempo tarda un conjunto de cálculos después de que un usuario presione el botón "Ir").

Por lo tanto, podría ser apropiado escribir los datos como un único carácter (para reducir el tiempo de lectura o escritura) pero descomprímalo en un conjunto de cuatro int (para que los cálculos posteriores sean más rápidos).

Además, no hay garantía de que un int sea de 32 bits (lo que ha asumido en su declaración de que el primer empaque usa 128 bits). Un int puede ser de 16 bits.

Para el empaque denso que no implica una gran sobrecarga de lectura, recomendaría una estructura con bitfields. En su ejemplo, donde tiene cuatro valores que van de 0 a 3, debe definir la estructura de la siguiente manera:

struct Foo { unsigned char a:2; unsigned char b:2; unsigned char c:2; unsigned char d:2; }

Tiene un tamaño de 1 byte y se puede acceder a los campos de manera simple, es decir, foo.b , foo.b , etc.

Al hacer su estructura más densamente empaquetada, eso debería ayudar con la eficiencia de la caché.

Editar:

Para resumir los comentarios:

Todavía hay un poco de violín sucediendo en un campo de bits, sin embargo lo hace el compilador y probablemente sea más eficiente que lo que escribirías a mano (sin mencionar que hace que tu código fuente sea más conciso y menos propenso a introducir errores). Y dada la gran cantidad de estructuras con las que se enfrentará, la reducción de las fallas de caché obtenidas mediante el uso de una estructura empaquetada como esta probablemente compensará la sobrecarga de manipulación de bits que impone la estructura.

Primero, defina con precisión lo que quiere decir con "más eficiente". Mejor uso de memoria? ¿Mejor presentación?

Luego, implemente su algoritmo en ambos sentidos y, de hecho, perfilelo en el hardware real en el que pretende ejecutarlo bajo las condiciones reales en las que pretende ejecutarlo una vez que se entregue.

Elija el que mejor se adapte a su definición original de "más eficiente".

Cualquier otra cosa es solo una suposición. Lo que sea que elija probablemente funcione bien, pero sin medir la diferencia en las condiciones exactas en las que usaría el software, nunca sabrá qué implementación sería "más eficiente".

Getting back to the question asked :

used in a tight loop;
their values are read a billion times/s, and that is the bottleneck of the program;
the whole program consists of a big array of billions of Foos;

This is a classic example of when you should write platform specific high performance code that takes time to design for each implementation platform, but the benefits outweigh that cost.

As it''s the bottleneck of the entire program you don''t look for a general solution, but recognize that this needs to have multiple approaches tested and timed against real data, as the best solution will be platform specific .

It is also possible, as it is a large array of billion of foos, that the OP should consider using OpenCL or OpenMP as potential solutions so as to maximize the exploitation of available resources on the runtime hardware. This is a little dependent on what you need from the data, but it''s probably the most important aspect of this type of problem - how to exploit available parallelism.

But there is no single right answer to this question, IMO.

I did video decompression for a while. The fastest thing to do is something like this:

short ABCD; //use a 16 bit data type for your example

and set up some macros. Maybe:

#define GETA ((ABCD >> 12) & 0x000F) #define GETB ((ABCD >> 8) & 0x000F) #define GETC ((ABCD >> 4) & 0x000F) #define GETD (ABCD & 0x000F) // no need to shift D

In practice you should try to be moving 32 bit longs or 64 bit long long because thats the native MOVE size on most modern processors.

Using a struct will always create the overhead in your compiled code of extra instructions from the base address of you struct to the field. So get away from that if you really want to tighten your loop.

Edit: Above example gives you 4 bit values. If you really just need values of 0..3 then you can do the same things to pull out your 2 bit numbers so,,,GETA might look like this:

GETA ((ABCD >> 14) & 0x0003)

And if you are really moving billions of things things, and I don''t doubt it, just fill up a 32bit variable and shift and mask your way through it.

Espero que esto ayude.

If what you''re after is efficiency of space, then you should consider avoiding struct s altogether. The compiler will insert padding into your struct representation as necessary to make its size a multiple of its alignment requirement, which might be as much as 16 bytes (but is more likely to be 4 or 8 bytes, and could after all be as little as 1 byte).

If you use a struct anyway, then which to use depends on your implementation. If @dbush''s bitfield approach yields one-byte structures then it''s hard to beat that. If your implementation is going to pad the representation to at least four bytes no matter what, however, then this is probably the one to use:

struct Foo { char a; char b; char c; char d; };

Or I guess I would probably use this variant:

struct Foo { uint8_t a; uint8_t b; uint8_t c; uint8_t d; };

Since we''re supposing that your struct is taking up a minimum of four bytes, there is no point in packing the data into smaller space. That would be counter-productive, in fact, because it would also make the processor do the extra work packing and unpacking the values within.

For handling large amounts of data, making efficient use of the CPU cache provides a far greater win than avoiding a few integer operations. If your data usage pattern is at least somewhat systematic (eg if after accessing one element of your erstwhile struct array, you are likely to access a nearby one next) then you are likely to get a boost in both space efficiency and speed by packing the data as tightly as you can. Depending on your C implementation (or if you want to avoid implementation dependency), you might need to achieve that differently -- for instance, via an array of integers. For your particular example of four fields, each requiring two bits, I would consider representing each "struct" as a uint8_t instead, for a total of 1 byte each.

Maybe something like this:

#include <stdint.h> #define NUMBER_OF_FOOS 1000000000 #define A 0 #define B 2 #define C 4 #define D 6 #define SET_FOO_FIELD(foos, index, field, value) / ((foos)[index] = (((foos)[index] & ~(3 << (field))) | (((value) & 3) << (field)))) #define GET_FOO_FIELD(foos, index, field) (((foos)[index] >> (field)) & 3) typedef uint8_t foo; foo all_the_foos[NUMBER_OF_FOOS];

The field name macros and access macros provide a more legible -- and adjustable -- way to access the individual fields than would direct manipulation of the array (but be aware that these particular macros evaluate some of their arguments more than once). Every bit is used, giving you about as good cache usage as it is possible to achieve through choice of data structure alone.

Let''s say, you have a memory bus that''s a little bit older and can deliver 10 GB/s. Now take a CPU at 2.5 GHz, and you see that you would need to handle at least four bytes per cycle to saturate the memory bus. As such, when you use the definition of

struct Foo { char a; char b; char c; char d; }

and use all four variables in each pass through the data, your code will be CPU bound. You can''t gain any speed by a denser packing.

Now, this is different when each pass only performs a trivial operation on one of the four values. In that case, you are better off with a struct of arrays:

struct Foo { size_t count; char* a; //a[count] char* b; //b[count] char* c; //c[count] char* d; //d[count] }

The most efficient, performance / execution, is to use the processor''s word size. Don''t make the processor perform extra work of packing or unpacking.

Some processors have more than one efficient size. Many ARM processors can operate in 8/32 bit mode. This means that the processor is optimized for handling 8 bit quantities or 32-bit quantities. For a processor like this, I recommend using 8-bit data types.

Your algorithm has a lot to do with the efficiency. If you are moving data or copying data you may want to consider moving data 32-bits at a time (4 8-bit quantities). The idea here is to reduce the number of fetches by the processor.

For performance, write your code to make use of registers , such as using more local variables. Fetching from memory into registers is more costly than using registers directly.

Best of all, check out your compiler optimization settings. Set your compile for the highest performance (speed) settings. Next, generate assembly language listings of your functions. Review the listing to see how the compiler generated code. Adjust your code to improve the compiler''s optimization capabilities.

You''ve stated the common and ambiguous C/C++ tag.

Assuming C++, make the data private and add getters/ setters. No, that will not cause a performance hit - providing the optimizer is turned on.

You can then change the implementation to use the alternatives without any change to your calling code - and therefore more easily finesse the implementation based on the results of the bench tests.

For the record, I''d expect the struct with bit fields as per @dbush to be most likely the fastest given your description.

Note all this is around keeping the data in cache - you may also want to see if the design of the calling algorithm can help with that.