cmpxchg para WORD más rápido que para BYTE

Question

Ayer publiqué this question sobre cómo escribir un spinlock rápido. Gracias a Cory Nelson parece haber encontrado un método que supera a los otros métodos discutidos en mi pregunta. Utilizo la instrucción CMPXCHG para verificar si el bloqueo es 0 y, por lo tanto, es gratis. CMPXCHG funciona en'BYTE', WORD y DWORD. Supongo que la instrucción funcionaría más rápido en BYTE. Pero escribí un bloqueo de la implementación de cada uno de los tipos de datos:

inline void spin_lock_8(char* lck) 
{ 
    __asm 
    { 
     mov ebx, lck      ;move lck pointer into ebx 
     xor cl, cl       ;set CL to 0 
     inc cl        ;increment CL to 1 
     pause        ; 
     spin_loop: 
     xor al, al       ;set AL to 0 
     lock cmpxchg byte ptr [ebx], cl  ;compare AL to CL. If equal ZF is set and CL is loaded into address pointed to by ebx 
     jnz spin_loop      ;jump to spin_loop if ZF 
    } 
} 
inline void spin_lock_16(short* lck) 
{ 
    __asm 
    { 
     mov ebx, lck 
     xor cx, cx 
     inc cx 
     pause 
     spin_loop: 
     xor ax, ax 
     lock cmpxchg word ptr [ebx], cx 
     jnz spin_loop 
    } 
} 
inline void spin_lock_32(int* lck) 
{ 
    __asm 
    { 
     mov ebx, lck 
     xor ecx, ecx 
     inc ecx 
     pause 
     spin_loop: 
     xor eax, eax 
     lock cmpxchg dword ptr [ebx], ecx 
     jnz spin_loop 
    } 
} 
inline spin_unlock(<anyType>* lck) 
{ 
    __asm 
    { 
     mov ebx, lck 
     mov <byte/word/dword> ptr [ebx], 0 
    } 
} 

El bloqueo a continuación, se puso a prueba utilizando el siguiente pseudo-código (tenga en cuenta que la LCM-puntero siempre señalará a una divisible dirección por 4):

<int/short/char>* lck; 
threadFunc() 
{ 
    loop 10,000,000 times 
    { 
     spin_lock_8/16/32 (lck); 
     spin_unlock(lck); 
    } 
} 
main() 
{ 
    lck = (char/short/int*)_aligned_malloc(4, 4);//Ensures memory alignment 
    start 1 thread running threadFunc and measure time; 
    start 2 threads running threadFunc and measure time; 
    start 4 threads running threadFunc and measure time; 
    _aligned_free(lck); 
} 

He obtenido los siguientes resultados medidos en mseg en un procesador con 2 núcleos físicos capaces de ejecutar 4 hilos (Ivy Bridge).

  1 thread 2 threads  4 threads 
8-bit  200   700   3200 
16-bit  200   500   1400 
32-bit  200   900   3400 

Los datos sugieren que todas las funciones tardan la misma cantidad de tiempo en ejecutarse. Pero cuando múltiples hilos tienen que verificar si lck == 0 usando un 16-bit puede ser significativamente más rápido. ¿Porqué es eso? Supongo que no tiene nada que ver con la alineación del lck?

Gracias de antemano.

Answer 1

Por lo que recuerdo, el bloqueo funciona en una palabra (2 bytes). Fue escrito de esa manera cuando se introdujo por primera vez en el 486.

Si llevas un candado en un tamaño diferente, en realidad genera el equivalente de 2 candados (palabra de bloqueo A y palabra B para una palabra doble). Para un byte probablemente tenga que evitar el bloqueo del segundo byte, que es algo similar a 2 bloqueos ...

Por lo tanto, sus resultados están en línea con las optimizaciones de la CPU.

Answer 2

Imagine que hay 1234 subprocesos y 16 CPU. Un hilo adquiere el spinlock, luego el sistema operativo realiza un cambio de tarea. Ahora tienes 16 CPUs, cada una ejecutando una de las 1233 subprocesos restantes, todas girando de una manera notablemente sin sentido por el tiempo que le lleva al sistema operativo devolver tiempo de CPU al único hilo que puede liberar el spinlock. Esto significa que todo el sistema operativo puede bloquearse básicamente (con todas las CPU funcionando a la perfección) durante unos segundos. Esto es muy retrasado; ¿Entonces, cómo lo arreglas?

Lo arregla al no usar spinlocks en espacio de usuario. Los spinlocks solo deben usarse siempre y cuando los interruptores de tareas puedan desactivarse; y solo el núcleo debería poder deshabilitar los interruptores de tareas.

Más específicamente, necesita usar un mutex. Ahora el mutex puede girar inicialmente antes de darse por vencido y hacer que el hilo espere el bloqueo, y (para casos de conflicto típico/bajo) esto ayuda, pero seguirá siendo un mutex y no es un spinlock.

Siguiente; para un software sensato, lo que importa (para el rendimiento) es evitar la contención del bloqueo y luego asegurarse de que el caso no detectado sea rápido (y un buen mutex no provocará un cambio de tarea si no hay contención). Está midiendo el caso contencioso/irrelevante.

Finalmente; tu cerradura es mala Para evitar el uso excesivo del prefijo lock, debe probar si puede adquirir sin ningún prefijo lock, y solo cuando pueda adquirirlo si usa el prefijo lock. Intel (y probablemente muchas otras personas) llaman a esta estrategia "prueba; luego (prueba y configuración)".Además, no ha comprendido el propósito de pause (o "rep nop" para ensambladores que son tan malos que no admiten instrucciones de hace 10 años).

Un medio spinlock decente podría ser algo como:

acquire: 
    lock bts dword [myLock],0 ;Optimistically attempt to acquire 
    jnc .acquired    ;It was acquired! 
.retry: 
    pause 
    cmp dword [myLock],0  ;Should we attempt to acquire again? 
    jne .retry     ; no, don't use `lock` 
    lock bts dword [myLock],0 ;Attempt to acquire 
    jc .retry     ;It wasn't acquired, so go back to waiting 
.acquired: 
    ret 

release: 
    mov dword [myLock],0  ;No lock prefix needed here as "myLock" is aligned 
    ret 

También tenga en cuenta que si usted ha fallado de manera adecuada para reducir al mínimo las posibilidades de contención de bloqueo, entonces usted no necesita preocuparse por la "justicia" y no debe estar usando un spinlock. El problema con los spinlocks "injustos" es que algunas tareas pueden ser afortunadas y siempre obtienen el bloqueo, y algunas tareas pueden ser desafortunadas y nunca obtener el bloqueo porque las tareas afortunadas siempre lo tienen. Esto siempre ha sido un problema para las cerraduras fuertemente disputadas, pero para los sistemas NUMA modernos se ha convertido en un problema mucho más probable. En este caso, como mínimo debe usar un bloqueo de boletos.

La idea básica de un bloqueo de tickets es garantizar que las tareas adquieran el bloqueo en el orden en que llegan (y no un orden aleatorio "posiblemente extremadamente malo"). Para completar, una cerradura billete podría tener este aspecto:

acquire: 
    mov eax,1 
    lock xadd [myLock],eax   ;myTicket = currentTicket, currentTicket++ 

    cmp [myLock+4],eax    ;Is it my turn? 
    je .acquired      ; yes 
.retry: 
    pause 
    cmp [myLock+4],eax    ;Is it my turn? 
    jne .retry      ; no, wait 
.acquired: 
    ret 

release: 
    lock inc dword [myLock+4] 
    ret 

tl; dr; No debe utilizar la herramienta incorrecta para el trabajo (spinlocks) para empezar; pero si insistes en usar la herramienta incorrecta, al menos haz que la herramienta incorrecta se implemente correctamente ... :-)