c++ - Implementar un bloqueo de ticket con atomics genera movimiento extra

multithreading x86

Question

Escribí una implementación ingenua de un simple bloqueo de ticket . La parte de bloqueo se ve como:

struct ticket {
    uint16_t next_ticket;
    uint16_t now_serving;
};

void lock(ticket* tkt) {
    const uint16_t my_ticket =
        __sync_fetch_and_add(&tkt->next_ticket, 1); 
    while (tkt->now_serving != my_ticket) {
        _mm_pause();
        __asm__ __volatile__("":::"memory");
    }   
}

Entonces me di cuenta de que, en lugar de usar un intrínseco gcc, puedo escribir esto con std::atomic s:

struct atom_ticket {
    std::atomic<uint16_t> next_ticket;
    std::atomic<uint16_t> now_serving;
};

void lock(atom_ticket* tkt) {
    const uint16_t my_ticket =
        tkt->next_ticket.fetch_add(1, std::memory_order_relaxed);
    while (tkt->now_serving.load(std::memory_order_relaxed) != my_ticket) {
        _mm_pause();
    }   
}

Estos generan un ensamblaje casi idéntico, pero este último genera una instrucción movzwl adicional. ¿Por qué hay este mov extra? ¿Hay una forma mejor y correcta de escribir lock() ?

Salida de ensamblaje con -march=native -O3 :

 0000000000000000 <lock(ticket*)>:
    0:   b8 01 00 00 00          mov    $0x1,%eax
    5:   66 f0 0f c1 07          lock xadd %ax,(%rdi)
    a:   66 39 47 02             cmp    %ax,0x2(%rdi)
    e:   74 08                   je     18 <lock(ticket*)+0x18>
   10:   f3 90                   pause  
   12:   66 39 47 02             cmp    %ax,0x2(%rdi)
   16:   75 f8                   jne    10 <lock(ticket*)+0x10>
   18:   f3 c3                   repz retq 
   1a:   66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)

 0000000000000020 <lock(atom_ticket*)>:
   20:   ba 01 00 00 00          mov    $0x1,%edx
   25:   66 f0 0f c1 17          lock xadd %dx,(%rdi)
   2a:   48 83 c7 02             add    $0x2,%rdi
   2e:   eb 02                   jmp    32 <lock(atom_ticket*)+0x12>
   30:   f3 90                   pause  
=> 32:   0f b7 07                movzwl (%rdi),%eax <== ???
   35:   66 39 c2                cmp    %ax,%dx
   38:   75 f6                   jne    30 <lock(atom_ticket*)+0x10>
   3a:   f3 c3                   repz retq 

¿Por qué no solo cmp (%rdi),%dx directamente?

Answer 1

En primer lugar, creo que necesitas usar std::memory_order_acquire , ya que estás adquiriendo un bloqueo. Si usa mo_relaxed , podría ver datos obsoletos antes de algunas de las tiendas que el titular de bloqueo anterior. El blog de Jeff Preshing es excelente , y tiene una publicación sobre semántica de adquisición / adquisición .

En x86, esto solo puede suceder si el compilador reordena las cargas y almacena, lo que mo_relaxed le dice que está permitido. Una carga adquirida compila lo mismo que una carga relajada en x86, pero sin reordenar. Cada carga de x86 asm ya es una adquisición. En las arquitecturas poco ordenadas que lo necesitan, obtendrá las instrucciones necesarias para una adquisición de carga. (Y en x86, solo detendrás la ordenación del compilador).

Puse una versión del código en godbolt para mirar el asm con varios compiladores.

Bien visto, esto parece un error de optimización de gcc, todavía presente al menos en 6.0 (verificada con Wandbox , usando un main que return execlp("objdump", "objdump", "-Mintel", "-d", argv[0], NULL); para volcar la salida del desensamblador de sí mismo, incluidas las funciones que nos interesan.

Parece que el clang 3.7 hace aún peor con esto. Hace una carga de 16 bits, luego se extiende a cero, luego se compara.

gcc trata las cargas atómicas especialmente, y aparentemente no se da cuenta de que puede doblarlas en la comparación. Probablemente el paso de optimización que podría haber hecho que sucedió mientras la carga atómica todavía se representaba de manera diferente a las cargas regulares, o algo así. No soy un hacker de gcc, así que esto es sobre todo conjeturas.

Sospecho que tienes un gcc antiguo (4.9.2 o más antiguo), o estás construyendo en / para AMD, porque tu compilador usó rep ret incluso con -march=native . Debe hacer algo al respecto si le importa generar un código óptimo. He notado que gcc5 hace mejor código que gcc 4.9 a veces. (No es que ayude en este caso, sin embargo: /)

Intenté usar uint32_t, sin suerte.

El impacto en el rendimiento de hacer la carga y la comparación por separado es probablemente irrelevante, ya que esta función es un ciclo de espera ocupado.

La ruta rápida (caso desbloqueado, donde la condición del bucle es falsa en la primera iteración) sigue siendo solo una rama tomada, y una ret. Sin embargo, en la versión estándar: atómica, la ruta rápida pasa por la rama del bucle. Entonces, en lugar de dos entradas separadas de predictor de rama (una para la ruta rápida y otra para el ciclo de giro), ahora la rotación probablemente causará un error de predicción de rama en el próximo caso desbloqueado. Probablemente esto no sea un problema, y ​​el nuevo código toma una menos entradas de predictor de rama.

IDK si saltar a la mitad de un bucle tuvo algún efecto negativo en el caché uop de las microarquitecturas de la familia SnB de Intel. Es una especie de caché de rastreo. Las pruebas de Agner Fog encontraron que la misma pieza de código puede tener múltiples entradas en el caché uop si tiene múltiples puntos de entrada de salto. Esta función ya es algo uop-cache hostil, ya que comienza con un mov r, imm / lock xadd . El bloqueo xadd tiene que ir solo en una línea de caché uop, porque está microcodificado (más de 4 uops. 9 de hecho). Un salto incondicional siempre termina una línea de caché uop. No estoy seguro de una rama condicional tomada, pero supongo que un jcc tomado termina una línea de caché si se predijo que se tomó cuando se decodificó. (Por ejemplo, la entrada del predictor de ramificación sigue siendo buena, pero se ha desalojado la entrada de caché uop antigua).

Entonces, la primera versión es potencialmente 3 líneas de caché uops para la ruta rápida: un mov (y si está en línea, ojalá esté lleno con instrucciones previas), un lock xadd solo, una macro-fusionada cmp/je al siguiente código (si está en línea). De lo contrario, el salto se dirige a la ret , que puede terminar como una cuarta línea de caché para este bloque de código de 32 bytes, lo que no está permitido. ¿Entonces la versión no en línea de esta siempre tendrá que volver a decodificarse cada vez?)

La versión estándar :: atómica es de nuevo una línea uop-cache para el mov imm inicial (y las instrucciones anteriores), luego lock xadd , luego add / jmp , luego ... uh oh, la cuarta línea de caché necesaria para el movzx / compare-and-branch uops. Por lo tanto, es más probable que esta versión tenga un cuello de botella de decodificación incluso cuando esté en línea.

Afortunadamente, la interfaz aún puede ganar algo de terreno y obtener instrucciones en cola para el núcleo de OOO mientras se ejecuta este código, porque el lock xadd es 9 uops. Eso es suficiente para cubrir un ciclo o dos o menos uops desde la interfaz, y un cambio entre la decodificación y la captura de caché uop.

El problema principal aquí es simplemente el tamaño del código, ya que usted probó. quiero esto en línea. En cuanto a la velocidad, el camino rápido es solo un poco peor, y el camino no rápido es un bucle de giro de todos modos, así que no importa.

La ruta rápida es 11 uops de dominio fusionado para la versión anterior (1 mov imm , 9 lock xadd , 1 cmp/je macro fusionada). El cmp/je incluye un operando de memoria microfusada.

La ruta rápida es de uops de dominio fusionado para la nueva versión (1 mov imm , 9 lock xadd , 1 add , 1 jmp , 1 movzx , 1 cmp/je macro fusionada).

Usar un add lugar de usar un desplazamiento de 8 movzx en el modo de direccionamiento de movzx es realmente dispararse en el pie, OMI. IDK si gcc piensa de antemano lo suficiente como para hacer elecciones como esa para que el objetivo de la rama del bucle salga en un límite 16B, o si eso fue una mera suerte.

Experimento de identificación del compilador en godbolt usando el código del OP:

• gcc 4.8 y anteriores: siempre use rep ret cuando sea un objetivo de rama, incluso con -march=native -mtune=core2 (en un Haswell), o con solo -march=core2 .
• gcc 4.9: utiliza rep ret con -march=native en Haswell, probablemente porque Haswell es demasiado nuevo para ello. -march=native -mtune=haswell usa solo ret , por lo que sabe el nombre de haswell .
• gcc 5.1 y versiones posteriores: usa ret con -march=native (en Haswell). Todavía se usa rep ret cuando no se especifica -march .

Answer 2

En primera

12:   66 39 47 02             cmp    %ax,0x2(%rdi)

cmp es una instrucción combinada de mov y cmp (es muy probable que genere dos instrucciones en el conjunto de instrucciones de microarquitectura)

La variante atómica está haciendo una lectura separada para now_serving with

32:   0f b7 07                movzwl (%rdi),%eax

y luego hace lo mismo en comparación con

35:   66 39 c2                cmp    %ax,%dx