La jerarquía de memoria es la verdadera frontera del rendimiento en la arquitectura moderna. Aunque el procesador sea capaz de ejecutar múltiples instrucciones por ciclo, la brecha de memoria (memory wall) impone una latencia devastadora: mientras que una operación en la L1 tarda apenas un par de ciclos, una petición a la RAM puede demorar cientos de ciclos de espera. El hardware mitiga esto mediante una jerarquía de memorias caché (L1, L2, L3) que funciona bajo el principio de localidad espacial: cuando el CPU solicita una dirección de memoria, no trae un solo byte, sino que carga una cache line completa (típicamente de 64 bytes) en la caché más cercana.
Si tu algoritmo accede a la dirección N y luego a la N+1, la segunda petición es casi gratuita porque ya reside en la caché (cache hit). Sin embargo, si el acceso es aleatorio, cada salto de dirección puede forzar una recarga desde la RAM (cache miss), dejando al pipeline del CPU ocioso. Por ello, el diseño de datos es más crítico que la optimización de algoritmos per se.
Para aprovechar esto, debemos elegir entre dos patrones principales: AoS (Array of Structs) y SoA (Struct of Arrays). En AoS, agrupas todos los atributos de un objeto en una estructura (ej. struct { float x, y, z; }), lo cual es intuitivo y excelente para la localidad temporal si procesas un objeto completo a la vez. Pero si solo necesitas procesar la componente z de un millón de objetos, AoS es ineficiente: la caché se llenará de x e y que no usas, desperdiciando ancho de banda. En cambio, SoA separa cada atributo en su propio array continuo, permitiendo que la caché se llene exclusivamente con los datos de interés (ideal para SIMD y escaneo masivo).
En entornos multihilo, surge un problema sutil: el false sharing. Si dos hilos modifican dos variables distintas que casualmente residen en la misma cache line, el protocolo de coherencia de caché (como MESI) invalidará la línea completa para todos los núcleos cada vez que un hilo escriba, obligando a recargas constantes de memoria. Para evitarlo, debemos forzar el alineamiento de los datos al tamaño de la línea de caché.
¿Qué ocurre si ignoras esto? No verás errores de segmentación ni resultados incorrectos, pero tu código sufrirá un degradado de rendimiento masivo que será casi imposible de depurar con herramientas estándar, ya que la lógica es correcta pero el patrón de acceso al hardware es desastroso.
#define _POSIX_C_SOURCE=200809L
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#include <pthread.h>
#define N 100000000
#define CACHE_LINE 64
// --- AoS: Array of Structs ---
// Ideal para acceder a todos los campos de UN solo elemento.
typedef struct {
float x, y, z, w;
} ParticleAoS;
// --- SoA: Struct of Arrays ---
// Ideal para procesar un campo de MUCHOS elementos (mejor ancho de banda).
typedef struct {
float *x;
float *y;
float *z;
float *w;
} ParticleSoA;
// --- False Sharing Demo ---
// Estructura sin padding: 'a' y 'b' comparten la misma cache line.
typedef struct {
volatile uint64_t a;
volatile uint64_t b;
} UnalignedCounters;
// Estructura con alineación: 'a' y 'b' están en líneas de caché distintas.
typedef struct {
volatile uint64_t a __attribute__((aligned(CACHE_LINE)));
volatile uint64_t b __attribute__((aligned(CACHE_LINE)));
} AlignedCounters;
void* task_unaligned(void* arg) {
UnalignedCounters* c = (UnalignedCounters*)arg;
for (uint64_t i = 0; i < 100000000; ++i) {
c->a++; // Escribe en línea A
c->b--; // Escribe en línea A (causa conflicto)
}
return NULL;
}
void* task_aligned(void* arg) {
AlignedCounters* c = (AlignedCounters*)arg;
for (uint64_t i = 0; i < 100000000; ++i) {
c->a++; // Escribe en línea A
c->b--; // Escribe en línea B (sin conflicto)
}
return NULL;
}
double get_time() {
struct timespec ts;
clock_gettime(CLOCK_MONOTONIC, &ts);
return ts.tv_sec + ts.tv_nsec * 1e-9;
}
int main(void) {
// 1. Test AoS vs SoA (Localidad Espacial)
ParticleAoS* aos = malloc(N * sizeof(ParticleAoS));
ParticleSoA soa;
soa.x = aligned_alloc(CACHE_LINE, N * sizeof(float));
soa.y = aligned_alloc(CACHE_LINE, N * sizeof(float));
soa.z = aligned_alloc(CACHE_LINE, N * sizeof(float));
soa.w = aligned_alloc(CACHE_LINE, N * sizeof(float));
for (uint64_t i = 0; i < N; ++i) {
aos[i] = (ParticleAoS){1.0f, 2.0f, 3.0f, 4.0f};
soa.w[i] = 4.0f;
}
double start = get_time();
double sum_aos = 0;
for (uint64_t i = 0; i < N; ++i) sum_aos += aos[i].w;
printf("AoS (Suma w): %f (Tiempo: %.4f s)\n", sum_aos, get_time() - start);
start = get_time();
double sum_soa = 0;
// El compilador puede vectorizar este bucle (SIMD) mucho mejor que el de AoS.
for (uint64_t i = 0; i < N; ++i) sum_soa += soa.w[i];
printf("SoA (Suma w): %f (Tiempo: %.4f s)\n", sum_soa, get_time() - start);
// 2. Test False Sharing (Coherencia de Caché)
pthread_t t1, t2;
UnalignedCounters unaligned = {0, 0};
AlignedCounters aligned = {0, 0};
start = get_time();
pthread_create(&t1, NULL, task_unaligned, &unaligned);
pthread_create(&t2, NULL, task_unaligned, &unaligned);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
printf("Unaligned (False Sharing): %ld (Tiempo: %.4f s)\n", unaligned.a + unaligned.b, get_time() - start);
start = get_time();
pthread_create(&t1, NULL, task_aligned, &aligned);
pthread_create(&t2, NULL, task_aligned, &aligned);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
printf("Aligned (No False Sharing): %ld (Tiempo: %.4f s)\n", aligned.a + aligned.b, get_time() - start);
free(aos);
free(soa.x); free(soa.y); free(soa.z); free(soa.w);
return 0;
}
Desglose del código
En el benchmark de AoS vs SoA, observamos cómo el acceso a aos[i].w requiere cargar la estructura completa de 16 bytes. Como la unidad de transferencia es la cache line de 64 bytes, cada carga trae los campos x, y y z que no necesitamos, desperdiciando el 75% del ancho de banda de memoria. En cambio, en soa.w[i], los valores de w son contiguos en memoria. Esto permite que el hardware realice un prefetching agresivo y que el compilador utilice instrucciones SIMD para procesar múltiples valores en un solo ciclo de reloj.
En la sección de False Sharing, el experimento con UnalignedCounters muestra cómo dos hilos pelean por la misma línea de caché. Aunque t1 solo toca a y t2 solo toca b, el hardware detecta que ambos escriben en la misma línea de 64 bytes y fuerza una sincronización constante entre núcleos. Al usar __attribute__((aligned(64))) en AlignedCounters, garantizamos que a y b residan en líneas de caché físicamente distintas, permitiendo que cada núcleo trabaje de forma independiente sin interferencias de coherencia.
El error frecuente
Un error común es optimizar la complejidad algorítmica (ej. reducir de $O(N^2)$ a $O(N \log N)$) pero mantener una estructura de datos que destruye la localidad de caché. Un algoritmo de búsqueda binaria sobre un árbol binario basado en nodos dispersos en la heap será drásticamente más lento que una búsqueda lineal sobre un array contiguo si el tamaño de la caché es pequeño, debido a los constantes cache misses.
Además, el False Sharing es un error silencioso: tu programa no fallará, ni siquiera fallará con un error de ejecución. Simplemente, tu escalabilidad multihilo será nula o incluso negativa (el código con dos hilos será más lento que el de uno solo). Herramientas como Valgrind con el plugin cachegrind pueden ayudarte a detectar esto, pero AddressSanitizer no lo hará, ya que no hay acceso ilegal a memoria, solo una disputa de coherencia en el hardware.
N° 124