Parece que la ingenuidad de GCC sobre los puestos de reenvío de tiendas está perjudicando su estrategia de vectorización automática aquí. Consulte también Reenvío de tienda por ejemplo para conocer algunos puntos de referencia prácticos en Intel con contadores de rendimiento de hardware y ¿Cuáles son los costos del reenvío fallido de tienda a carga en x86? También las guías de optimización x86 de Agner Fog .

( gcc -O3 -O3 habilita -ftree-vectorize y algunas otras opciones no incluidas en -O2 , por ejemplo, if -conversion to branchless cmov , que es otra forma en que -O3 puede dañar patrones de datos que GCC no esperaba. En comparación, Clang habilita vectorización automática incluso en -O2 , aunque algunas de sus optimizaciones aún están activas en -O3 ).

Está haciendo cargas de 64 bits (y ramificando para almacenar o no) en pares de enteros. Esto significa que, si intercambiamos la última iteración, la mitad de esta carga proviene de esa tienda, la otra mitad de la memoria nueva, por lo que obtenemos un bloqueo de reenvío de la tienda después de cada intercambio . Pero la ordenación de burbujas a menudo tiene largas cadenas de intercambio de cada iteración a medida que un elemento burbujea lejos, por lo que esto es realmente malo.

( La ordenación de burbujas es mala en general , especialmente si se implementa de manera ingenua sin mantener el segundo elemento de la iteración anterior en un registro. Puede ser interesante analizar los detalles de asm de por qué apesta exactamente, por lo que es lo suficientemente justo como para querer intentarlo).

De todos modos, esto es claramente una anti-optimización que debe informar en GCC Bugzilla con la palabra clave "optimización perdida" . Las cargas escalares son baratas y los puestos de reenvío de tiendas son costosos. ( ¿Pueden las implementaciones x86 modernas almacenar hacia adelante desde más de una tienda anterior? No, ni las microarquitecturas que no sean Atom en orden pueden cargarse de manera eficiente cuando se superpone parcialmente con una tienda anterior, y en parte a partir de datos que deben provenir de la memoria caché L1d. )

Aún mejor sería mantener buf[x+1] en un registro y usarlo como buf[x] en la próxima iteración, evitando almacenar y cargar. (Al igual que buenos ejemplos de ordenación de burbujas de ASM escritos a mano, algunos de los cuales existen en Stack Overflow).

Si no fuera por los puestos de reenvío de tiendas (que AFAIK GCC no conoce en su modelo de costos), esta estrategia podría ser un punto de equilibrio. SSE 4.1 para un comparador pmind / pmaxd sin sucursales podría ser interesante, pero eso significaría almacenar siempre y la fuente C no hace eso.

Si esta estrategia de carga de doble ancho tuviera algún mérito, sería mejor implementarla con enteros puros en una máquina de 64 bits como x86-64, donde puede operar solo en los 32 bits bajos con basura (o datos valiosos) en el mitad superior. P.ej,

 ## What GCC should have done, ## if it was going to use this 64-bit load strategy at all movsx rax, edx # apparently it wasn't able to optimize away your half-width signed loop counter into pointer math lea rcx, [rdi+rax*4] # Usually not worth an extra instruction just to avoid an indexed load and indexed store, but let's keep it for easy comparison. .L4: mov rax, [rcx] # into RAX instead of XMM0 add edx, 1 # pshufd xmm2, xmm0, 0xe5 # movd esi, xmm0 # movd eax, xmm2 # pshufd xmm1, xmm0, 225 mov rsi, rax rol rax, 32 # swap halves, just like the pshufd cmp esi, eax # or eax, esi? I didn't check which is which jle .L2 movq QWORD PTR [rcx], rax # conditionally store the swapped qword

(O con BMI2 disponible desde -march=native , rorx rsi, rax, 32 pueden copiar e intercambiar en una uop. Sin mov , mover e intercambiar el original en lugar de la copia ahorra latencia si se ejecuta en una CPU sin eliminación de movimiento , como Ice Lake con microcódigo actualizado ).

Entonces, la latencia total de la carga para comparar es solo una carga de enteros + una operación ALU (rotar). contra Carga XMM -> movd . Y sus menos ALU uops. Sin embargo, esto no ayuda en nada con el problema del estancamiento del envío de tiendas, que sigue siendo un problema. Esta es solo una implementación SWAR de enteros de la misma estrategia, reemplazando 2x pshufd y 2x movd r32, xmm con solo mov + rol .

En realidad, no hay razón para usar 2x pshufd aquí. Incluso si usa registros XMM, GCC podría haber hecho una mezcla que intercambió los dos elementos bajos, configurando tanto store como movd . Entonces, incluso con los registros XMM, esto no fue óptimo. Pero claramente dos partes diferentes de GCC emitieron esas dos instrucciones pshufd ; ¡uno incluso imprimió la constante aleatoria en hexadecimal mientras que el otro usó decimal! Supongo que uno intercambia y el otro solo intenta obtener vec[1] , el elemento alto de qword.

más lento que ninguna bandera en absoluto

El valor predeterminado es -O0 , modo de depuración consistente que derrama todas las variables en la memoria después de cada instrucción C , por lo que es bastante horrible y crea grandes cuellos de botella de latencia en el almacenamiento. (Algo así como si todas las variables volatile ). Pero es un reenvío de almacenamiento exitoso , no se detiene, por lo que "solo" ~ 5 ciclos, pero aún mucho peor que 0 para los registros. (Algunas microarquitecturas modernas, incluido Zen 2 , tienen algunos casos especiales que tienen una latencia más baja ). Las instrucciones adicionales de almacenamiento y carga que tienen que pasar por la canalización no ayudan.

Por lo general, no es interesante comparar -O0 . -O1 o -Og deben ser su línea de base de referencia para que el compilador realice la cantidad básica de optimización que una persona normal esperaría, sin nada sofisticado, pero sin alterar intencionalmente el asm omitiendo la asignación de registros.

Semi-relacionado: la optimización de la ordenación de burbujas por tamaño en lugar de velocidad puede implicar la rotación del destino de la memoria (crear paradas de reenvío de almacenamiento para intercambios consecutivos) o un xchg del destino de la memoria (prefijo de lock implícito -> muy lento). Vea esta respuesta de Code Golf .