FALSE SHARING

Recientemente, decidí analizar la velocidad de algunos de mis proyectos en C para identificar áreas de mejora. En este proceso, me topé con un concepto que llamó mucho mi atención: el False Sharing.

El False Sharing es un problema de rendimiento que puede afectar programas concurrentes. Ocurre cuando varios hilos acceden y modifican variables distintas que, por casualidad, comparten la misma línea de caché. Este fenómeno provoca invalidaciones frecuentes de la caché, lo que ralentiza el programa, incluso si las variables no están lógicamente relacionadas entre sí.

Contexto Técnico#

Para entender mejor este problema, es útil considerar cómo los procesadores modernos manejan la memoria:

• Jerarquía de caché: Los procesadores tienen niveles de caché (L1, L2, L3) que minimizan la latencia al acceder a la memoria.
• Líneas de caché: La memoria principal está organizada en bloques denominados líneas de caché, que típicamente tienen 64 bytes (aunque este tamaño puede variar según la arquitectura).
• Acceso y coherencia: Cuando un hilo accede a una variable, la línea de caché que la contiene se carga en la caché de la CPU que ejecuta ese hilo. Si otro hilo modifica una variable diferente que se encuentra en la misma línea de caché, toda la línea se invalida en las demás cachés. Esto obliga a recargarla desde la memoria principal o desde la caché que realizó la modificación, impactando negativamente el rendimiento.

EJEMPLO#

#include <stdio.h>
#include <pthread.h>
#include <time.h>

#define iterations 1000

struct point{
    int x;
    int y;
}point;



pthread_mutex_t mutex_x = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex_y = PTHREAD_MUTEX_INITIALIZER;
void*
sum_x(void *arg)
{
    for (int i = 0; i < 1000; i++)
    {
        point.x++;
    }
}    
void*
sum_y(void *arg)
{
    for (int i = 0; i < 1000; i++)
    {
        point.y++;
    }
}

int main()
{
    pthread_t thread1, thread2;

    for (int iter = 0; iter < iterations; iter++)
    {
        point.x = 0;
        point.y = 0;

        pthread_create(&thread1, NULL, sum_x, NULL);

        pthread_create(&thread2, NULL, sum_y, NULL);

        pthread_join(thread1, NULL);

        pthread_join(thread2, NULL);
    }
    pthread_mutex_destroy(&mutex_x);
    pthread_mutex_destroy(&mutex_y);

    return 0;
}

• El hilo 1 actualiza point.x mientras el hilo 2 actualiza point.y.
• Aunque point.x e point.y son variables independientes, comparten la misma línea de caché.
• Cada vez que un hilo modifica su variable, la línea de caché se invalida en la caché del otro hilo, forzando costosas operaciones de sincronización entre las cachés.

Esto, trae 3 efectos principales

1. Degradación del rendimiento: Aumenta la latencia debido a las frecuentes invalidaciones de caché.
2. Mayor uso del bus de memoria: Se incrementa la comunicación entre los núcleos del procesador.
3. Dificultad para escalar: A medida que se añaden más hilos, el problema puede empeorar.

¿Como mitigar este efecto?#

Existen múltiples formas de mitigar el efecto de false sharing en C para este caso concreto. Aquí detallo tres opciones y sus resultados en rendimiento en diferentes optimizaciones:

1. Alinear las variables a 64 bytes:

struct point {
    int x;
    int y __attribute__((aligned(64)));
}point;

Esta solución separa las variables en distintas líneas de caché, eliminando el false sharing. Es eficiente en memoria y mejora significativamente el rendimiento.

2. Alinear el struct completo:

struct point {
    int x;
    int y;
} __attribute__((aligned(64))) point;

Alinea el struct a 64 bytes. Aunque mejora el acceso general, no elimina el false sharing entre x e y.

3. Agregar padding explícito:

struct point {
    int x;
    char padding[64];
    int y;
}point;

Separa físicamente x e y en memoria. Aunque elimina el false sharing, incrementa el uso de memoria y puede afectar negativamente el rendimiento.

4. Usar variables globales independientes:

int x;
int y;

Evita el false sharing, pero no siempre es práctico.

Análisis de Rendimiento#

Usando perf, analicé el impacto de cada solución:

perf record -o perf_programa1.data ./programa
perf report -i perf_programa1.data

Caso Base#

El reporte de perf se ve así:

8,72% prueba1 libc.so.6 [.] pthread_mutex_lock@@GLIBC_2.2.5
7,75% prueba1 [kernel.kallsyms] [k] memset
5,79% prueba1 libc.so.6 [.] __GI___pthread_mutex_unlock_usercnt
3,25% prueba1 [kernel.kallsyms] [k] clear_page_rep
2,78% prueba1 [kernel.kallsyms] [k] unmap_page_range
2,46% prueba1 [kernel.kallsyms] [k] native_queued_spin_lock_slowpath
2,11% prueba1 [kernel.kallsyms] [k] native_write_msr
1,45% prueba1 [kernel.kallsyms] [k] psi_group_change

Caso con alineación y#

Al alinear y a 64 bytes, el false sharing desaparece:

19,27% prueba2 libc.so.6 [.] pthread_mutex_lock@@GLIBC_2.2.5
19,15% prueba2 libc.so.6 [.] __GI___pthread_mutex_unlock_usercnt
10,31% prueba2 [kernel.kallsyms] [k] memset
9,63% prueba2 [kernel.kallsyms] [k] clear_page_rep
5,38% prueba2 [kernel.kallsyms] [k] native_write_msr
1,98% prueba2 [kernel.kallsyms] [k] __list_del_entry_valid
1,29% prueba2 [kernel.kallsyms] [k] copy_process
1,20% prueba2 [kernel.kallsyms] [k] __memcg_kmem_charge_page
1,20% prueba2 [kernel.kallsyms] [k] alloc_vmap_area
1,06% prueba2 [kernel.kallsyms] [k] memcpy
0,85% prueba2 prueba2 [.] sum_x
0,84% prueba2 [kernel.kallsyms] [k] try_charge_memcg

La sincronización explícita domina el uso de recursos, eliminando cuellos de botella en la caché.

Caso alineación struct completo#

Alinear el struct completo no elimina el false sharing entre x e y porque permanecen en la misma línea de caché:

19,74% prueba4 libc.so.6 [.] pthread_mutex_lock@@GLIBC_2.2.5
19,24% prueba4 libc.so.6 [.] __GI___pthread_mutex_unlock_usercnt
5,86% prueba4 [kernel.kallsyms] [k] native_write_msr
5,85% prueba4 [kernel.kallsyms] [k] memset
2,59% prueba4 [kernel.kallsyms] [k] clear_page_rep
2,05% prueba4 [kernel.kallsyms] [k] unmap_page_range
1,31% prueba4 [kernel.kallsyms] [k] psi_group_change
1,26% prueba4 [kernel.kallsyms] [k] memcpy
0,95% prueba4 [kernel.kallsyms] [k] copy_process
0,86% prueba4 [kernel.kallsyms] [k] native_read_msr
0,84% prueba4 [kernel.kallsyms] [k] memcg_slab_post_alloc_hook
0,84% prueba4 prueba4 [.] sum_x
0,83% prueba4 [kernel.kallsyms] [k] retbleed_return_thunk

Aunque mejora ligeramente el rendimiento general al optimizar el acceso global al struct, el false sharing persiste, limitando las ganancias.

Caso con Padding explícito#

Agregar padding explícito elimina el false sharing, pero introduce costos adicionales por el mayor tamaño del struct:

22,11% prueba5 libc.so.6 [.] pthread_mutex_lock@@GLIBC_2.2.5
21,95% prueba5 libc.so.6 [.] __GI___pthread_mutex_unlock_usercnt
7,58% prueba5 [kernel.kallsyms] [k] native_write_msr
5,12% prueba5 [kernel.kallsyms] [k] memset
2,57% prueba5 [kernel.kallsyms] [k] clear_page_rep
1,50% prueba5 [kernel.kallsyms] [k] copy_process
1,40% prueba5 [kernel.kallsyms] [k] psi_group_change
1,05% prueba5 [kernel.kallsyms] [k] native_read_msr
0,89% prueba5 prueba5 [.] sum_x
0,81% prueba5 [kernel.kallsyms] [k] retbleed_return_thunk
0,76% prueba5 [kernel.kallsyms] [k] ___slab_alloc
0,74% prueba5 [kernel.kallsyms] [k] _raw_spin_lock

El aumento en el uso de memoria reduce la densidad de datos en caché, penalizando el prefetching y limitando las mejoras.

Caso con Variables Independientes#

El uso de variables globales independientes elimina el false sharing, pero el rendimiento no mejora significativamente:

32,54% prueba6 libc.so.6 [.] __GI___pthread_mutex_unlock_usercnt
21,81% prueba6 libc.so.6 [.] pthread_mutex_lock@@GLIBC_2.2.5
6,89% prueba6 [kernel.kallsyms] [k] memset
5,90% prueba6 prueba6 [.] sum_y
4,81% prueba6 [kernel.kallsyms] [k] native_write_msr
1,00% prueba6 [kernel.kallsyms] [k] _raw_spin_lock
0,97% prueba6 [kernel.kallsyms] [k] clear_page_rep

Esto se debe a la sobrecarga de sincronización explícita y a la latencia de acceso a memoria global.

Conclusión de perf#

El análisis de los resultados obtenidos con perf y los tiempos medidos para las diferentes configuraciones revela cómo afectan las estrategias de alineación y diseño de datos al rendimiento, explicando el impacto en cada caso.

En el caso base, las variables x e y están en el mismo struct sin ninguna alineación específica. Esto provoca que compartan la misma línea de caché, lo que genera false sharing cuando los hilos acceden concurrentemente a estas variables. El reporte de perf muestra un uso significativo de funciones relacionadas con la sincronización, como native_queued_spin_lock_slowpath y memset, indicando que los hilos están invalidando constantemente las líneas de caché. Este comportamiento explica el tiempo relativamente alto de ejecución (123.93 segundos), pues el false sharing genera una gran sobrecarga.

Cuando se alinea la variable y a 64 bytes, el false sharing se elimina, ya que x e y pasan a ocupar líneas de caché diferentes. Esto se traduce en una mejora notable en el tiempo de ejecución (83.21 segundos). El reporte de perf muestra que funciones como native_queued_spin_lock_slowpath desaparecen, mientras que pthread_mutex_lock y pthread_mutex_unlock dominan el consumo de ciclos, reflejando que la sincronización explícita es ahora el mayor costo. Esta configuración resulta ser la más eficiente, ya que elimina el cuello de botella del false sharing sin introducir una sobrecarga significativa.

En este caso, no hay evidencia de false sharing en el reporte de perf, ya que no aparece native_queued_spin_lock_slowpath ni otros indicadores claros de contención en la caché. Sin embargo, alinear el struct completo a 64 bytes no elimina el false sharing entre x e y, ya que ambas variables permanecen en la misma línea de caché. Esto mejora ligeramente el rendimiento global al optimizar el acceso al struct, pero el false sharing persiste, limitando las ganancias. El rendimiento es un poco peor que alinear solo las variables individuales, probablemente debido al mayor uso de memoria, lo que aumenta la presión sobre la caché. Además, las funciones de sincronización, como pthread_mutex_lock y pthread_mutex_unlock, son los principales cuellos de botella, indicando que el problema está más relacionado con la sincronización que con la organización de los datos.

Cuando se utiliza padding explícito para separar x e y en memoria, el false sharing desaparece. Sin embargo, esta estrategia introduce un costo adicional debido al aumento en el tamaño del struct, lo que reduce la densidad de datos en caché y dificulta el prefetching. Esto resulta en el peor rendimiento observado (127.01 segundos). El análisis de perf confirma que, aunque el false sharing se elimina, el tiempo sigue dominado por funciones de sincronización (pthread_mutex_lock y pthread_mutex_unlock), lo que limita las mejoras.

Finalmente, al usar variables globales independientes en lugar de un struct, el false sharing debería desaparecer. Sin embargo, el rendimiento obtenido (124.81 segundos) es comparable al caso base. El reporte de perf indica que la alta proporción de tiempo en pthread_mutex_lock y pthread_mutex_unlock refleja la sobrecarga de sincronización explícita. Además, aunque se elimina la invalidación de caché, el acceso global puede introducir pequeñas penalizaciones debido a la latencia de acceso a memoria, lo que explica la falta de mejora significativa.

Resultados#

En este apartado muestro los resultados de la velocidad en segundos que tardo el programa con las diferentes formas de declarar las variables en 1000000 de iteraciones y con distintos tipos de optimización.

-O0:

-O1:

-O2:

-O3:

¿Por qué las optimizaciones desde -O1 mejoran el tiempo de ejecución?#

Cuando un programa se compila con optimizaciones a partir de -O1, el compilador comienza a realizar ajustes fundamentales que mejoran significativamente el rendimiento. En este nivel, se eliminan cálculos redundantes, se reorganizan las instrucciones para aprovechar mejor los recursos de la CPU y se optimizan los accesos a memoria, reduciendo la latencia. Estos cambios automáticos complementan las optimizaciones manuales, como la alineación de datos, al permitir que el hardware trabaje con mayor eficiencia, especialmente en casos donde problemas como el false sharing han sido mitigados.

A niveles más altos de optimización, como -O2 y -O3, el compilador introduce técnicas más avanzadas, como la vectorización, la eliminación agresiva de ramas y el inlining de funciones, que reducen aún más la sobrecarga asociada a la ejecución. Sin embargo, el impacto en tiempos de ejecución se estabiliza, ya que el cuello de botella principal (como la sincronización explícita en programas multihilo) no siempre puede eliminarse solo con optimización del código. Esto destaca la importancia de combinar un diseño cuidadoso de datos con las capacidades del compilador para lograr el mejor rendimiento posible.

Reflexión Final#

El rendimiento en aplicaciones concurrentes está profundamente ligado a la forma en que los datos se estructuran y acceden en memoria. Como hemos visto, problemas como el False Sharing pueden surgir de pequeños descuidos en el diseño de estructuras de datos, pero tienen un impacto desproporcionado en el desempeño. Afortunadamente, con un enfoque metódico y herramientas como perf, es posible identificar estos problemas y abordarlos con optimizaciones simples pero efectivas.

Este artículo refleja mi entendimiento actual sobre el tema y mi intención de compartir conocimientos útiles. Sin embargo, si hay algo que pueda mejorarse, corregirse o ampliarse, estaré encantado de recibir tu retroalimentación. No dudes en contactarme por correo para compartir tus comentarios, experiencias o cualquier corrección que consideres necesaria.

Sumario de términos:#

• False Sharing: Ocurre cuando múltiples hilos acceden a variables diferentes que comparten la misma línea de caché. Esto genera conflictos innecesarios en la memoria caché, degradando el rendimiento.
• Línea de caché: Unidad mínima de datos que la caché de la CPU intercambia con la memoria principal. Su tamaño suele ser de 64 bytes en la mayoría de los procesadores modernos.
• Alineación de datos: Técnica que organiza los datos en memoria de manera que coincidan con los límites de línea de caché, minimizando conflictos entre hilos.
• Padding: Proceso de agregar bytes adicionales entre elementos de una estructura de datos para evitar que compartan líneas de caché.
• Optimización del compilador: Ajustes automáticos realizados por el compilador en diferentes niveles (-O1, -O2, -O3) para mejorar el rendimiento de un programa sin alterar su funcionalidad.
• Prefetching: Técnica usada por los procesadores para cargar datos en caché antes de que sean necesarios, reduciendo la latencia de acceso.
• Sincronización explícita: Uso de primitivas como mutex o semáforos para coordinar el acceso a recursos compartidos entre hilos.
• Densidad de datos en caché: Cantidad de datos útiles que pueden ser almacenados en la caché simultáneamente; afecta el rendimiento general en sistemas que dependen de la velocidad de acceso a la memoria.