glibc manual
¿Por qué este código 6.5x es más lento con las optimizaciones habilitadas? (2)
Probar su código en el Compilador Explorer de Godbolt proporciona esta explicación:
-
en
-O0
o sin optimizaciones, el código generado llama a la función de biblioteca Cstrlen
-
en
-O1
el código generado utiliza una expansión simple en línea usando una instrucciónrep scasb
. -
en
-O2
y superior, el código generado utiliza una expansión en línea más elaborada.
La evaluación comparativa de su código repetidamente muestra una variación sustancial de una ejecución a otra, pero el aumento del número de iteraciones muestra que:
-
el código
-O1
es mucho más lento que la implementación de la biblioteca C:32240
vs3090
-
-O2
código-O2
es más rápido que el-O1
pero aún es sustancialmente más lento que el código de biblioteca C:8570
vs3090
.
Este comportamiento es específico de
gcc
y el
glibc
.
La misma prueba en OS / X con
clang
y Libc de Apple no muestra una diferencia significativa, lo cual no es una sorpresa, ya que Godbolt muestra que
clang
genera una llamada al
strlen
biblioteca C en todos los niveles de optimización.
Esto podría considerarse un error en gcc / glibc, pero una evaluación comparativa más extensa podría mostrar que la sobrecarga de llamar a
strlen
tiene un impacto más importante que la falta de rendimiento del código en línea para cadenas pequeñas.
Las cadenas en las que realiza pruebas comparativas son excepcionalmente grandes, por lo que enfocarlas en cadenas ultra largas podría no dar resultados significativos.
He mejorado este punto de referencia y probado varias longitudes de cadena.
En las pruebas comparativas en linux con gcc (Debian 4.7.2-5) 4.7.2 ejecutándose en una CPU Intel (R) Core (TM) i3-2100 @ 3.10GHz, el código en línea generado por
-O1
siempre es más lento, tanto como un factor de
10
para cadenas moderadamente largas, mientras que
-O2
es solo un poco más rápido que el libc strlen para cadenas muy cortas y la mitad de rápido para cadenas más largas.
A partir de estos datos, la versión de la biblioteca GNU C de
strlen
es bastante eficiente para la mayoría de las cadenas, al menos en mi hardware específico.
También teniendo en cuenta que el almacenamiento en caché tiene un gran impacto en las mediciones de referencia.
Aquí está el código actualizado:
#include <stdlib.h>
#include <string.h>
#include <time.h>
void benchmark(int repeat, int minlen, int maxlen) {
char *s = malloc(maxlen + 1);
memset(s, ''A'', minlen);
long long bytes = 0, calls = 0;
clock_t clk = clock();
for (int n = 0; n < repeat; n++) {
for (int i = minlen; i < maxlen; ++i) {
bytes += i + 1;
calls += 1;
s[i] = ''/0'';
s[strlen(s)] = ''A'';
}
}
clk = clock() - clk;
free(s);
double avglen = (minlen + maxlen - 1) / 2.0;
double ns = (double)clk * 1e9 / CLOCKS_PER_SEC;
printf("average length %7.0f -> avg time: %7.3f ns/byte, %7.3f ns/call/n",
avglen, ns / bytes, ns / calls);
}
int main() {
benchmark(10000000, 0, 1);
benchmark(1000000, 0, 10);
benchmark(1000000, 5, 15);
benchmark(100000, 0, 100);
benchmark(100000, 50, 150);
benchmark(10000, 0, 1000);
benchmark(10000, 500, 1500);
benchmark(1000, 0, 10000);
benchmark(1000, 5000, 15000);
benchmark(100, 1000000 - 50, 1000000 + 50);
return 0;
}
Aquí está la salida:
chqrlie> gcc -std=c99 -O0 benchstrlen.c && ./a.out average length 0 -> avg time: 14.000 ns/byte, 14.000 ns/call average length 4 -> avg time: 2.364 ns/byte, 13.000 ns/call average length 10 -> avg time: 1.238 ns/byte, 13.000 ns/call average length 50 -> avg time: 0.317 ns/byte, 16.000 ns/call average length 100 -> avg time: 0.169 ns/byte, 17.000 ns/call average length 500 -> avg time: 0.074 ns/byte, 37.000 ns/call average length 1000 -> avg time: 0.068 ns/byte, 68.000 ns/call average length 5000 -> avg time: 0.064 ns/byte, 318.000 ns/call average length 10000 -> avg time: 0.062 ns/byte, 622.000 ns/call average length 1000000 -> avg time: 0.062 ns/byte, 62000.000 ns/call chqrlie> gcc -std=c99 -O1 benchstrlen.c && ./a.out average length 0 -> avg time: 20.000 ns/byte, 20.000 ns/call average length 4 -> avg time: 3.818 ns/byte, 21.000 ns/call average length 10 -> avg time: 2.190 ns/byte, 23.000 ns/call average length 50 -> avg time: 0.990 ns/byte, 50.000 ns/call average length 100 -> avg time: 0.816 ns/byte, 82.000 ns/call average length 500 -> avg time: 0.679 ns/byte, 340.000 ns/call average length 1000 -> avg time: 0.664 ns/byte, 664.000 ns/call average length 5000 -> avg time: 0.651 ns/byte, 3254.000 ns/call average length 10000 -> avg time: 0.649 ns/byte, 6491.000 ns/call average length 1000000 -> avg time: 0.648 ns/byte, 648000.000 ns/call chqrlie> gcc -std=c99 -O2 benchstrlen.c && ./a.out average length 0 -> avg time: 10.000 ns/byte, 10.000 ns/call average length 4 -> avg time: 2.000 ns/byte, 11.000 ns/call average length 10 -> avg time: 1.048 ns/byte, 11.000 ns/call average length 50 -> avg time: 0.337 ns/byte, 17.000 ns/call average length 100 -> avg time: 0.299 ns/byte, 30.000 ns/call average length 500 -> avg time: 0.202 ns/byte, 101.000 ns/call average length 1000 -> avg time: 0.188 ns/byte, 188.000 ns/call average length 5000 -> avg time: 0.174 ns/byte, 868.000 ns/call average length 10000 -> avg time: 0.172 ns/byte, 1716.000 ns/call average length 1000000 -> avg time: 0.172 ns/byte, 172000.000 ns/call
Quería
strlen
función
strlen
glibc
por algún motivo y descubrí que aparentemente funciona
mucho
más lento con las optimizaciones habilitadas en GCC y no tengo idea de por qué.
Aquí está mi código:
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
int main() {
char *s = calloc(1 << 20, 1);
memset(s, 65, 1000000);
clock_t start = clock();
for (int i = 0; i < 128; ++i) {
s[strlen(s)] = ''A'';
}
clock_t end = clock();
printf("%lld/n", (long long)(end-start));
return 0;
}
En mi máquina sale:
$ gcc test.c && ./a.out
13336
$ gcc -O1 test.c && ./a.out
199004
$ gcc -O2 test.c && ./a.out
83415
$ gcc -O3 test.c && ./a.out
83415
De alguna manera, habilitar optimizaciones hace que se ejecute por más tiempo.
Los patrones de
strlen
línea de
strlen
son mucho más lentos de lo que podría hacer con SSE2
pcmpeqb
/
pmovmskb
y
bsf
, dada la alineación de 16 bytes del
calloc
.
Esta "optimización" es en realidad una pesimista.
Mi sencillo bucle escrito a mano que aprovecha la alineación de 16 bytes es 5 veces más rápido de lo que gcc -O3 en línea para búferes grandes, y ~ 2 veces más rápido para cadenas cortas. (Y más rápido que llamar a strlen para cadenas cortas). Agregué un comentario a gcc.gnu.org/bugzilla/show_bug.cgi?id=88809 para proponer esto para lo que gcc debería incluir en -O2 / -O3 cuando sea posible. (Con una sugerencia para la aceleración de hasta 16 bytes si solo conocemos la alineación de 4 bytes, para empezar).
Cuando gcc sabe que tiene una alineación de 4 bytes
para el búfer (garantizado por
calloc
), elige la función de línea en línea como un bithack escalar de 4 bytes a la vez que utiliza registros de enteros GP (
-O2
y superiores).
(La lectura de 4 bytes a la vez solo es segura si sabemos que no podemos cruzar a una página que no contenga ninguna cadena de bytes y, por lo tanto, podría estar sin asignar.
¿Es seguro leer más allá del final de un búfer dentro de la misma? ¿La página en x86 y x64?
(TL: DR sí, en asm es, por lo que los compiladores pueden emitir código que hace eso, incluso si hacerlo en la fuente C es UB.
strlen
implementaciones de libc
strlen
también aprovechan eso. Vea mi respuesta allí para enlaces a glibc
strlen
y un resumen de cómo se ejecuta tan rápido para cadenas grandes.)
En
-O1
, gcc
siempre
(incluso sin alineación conocida) opta por
strlen
línea como
repnz scasb
, que es muy lento
(aproximadamente 1 byte por ciclo de reloj en las modernas CPU de Intel).
Las "cadenas rápidas" solo se aplican a las
rep stos
y las
rep movs
, no a las instrucciones
repz
/
repnz
, desafortunadamente.
Su microcódigo es solo de 1 byte a la vez, pero todavía tienen algo de sobrecarga de inicio.
(
https://agner.org/optimize/
)
(Podemos probar esto "ocultando" el puntero del compilador almacenando / recargando
s
en un
volatile void *tmp
, por ejemplo. Gcc tiene que hacer cero suposiciones sobre el valor del puntero que se lee desde un
volatile
, destruyendo cualquier información de alineación .)
GCC tiene algunas
opciones de ajuste de x86
como
-mstringop-strategy=libcall
vs.
-mstringop-strategy=libcall
vs.
rep_byte
para las operaciones de cadenas en línea en general (no solo strlen;
memcmp
sería otra importante que se puede hacer con rep o un loop).
No he comprobado qué efecto tienen estos aquí.
Los documentos para otra opción también describen el comportamiento actual. Podríamos obtener esta incorporación (con código adicional para el manejo de la alineación) incluso en los casos en que lo quisiéramos con punteros no alineados. (Esto solía ser una ganancia real, especialmente para cadenas pequeñas, en objetivos donde el bucle en línea no era basura en comparación con lo que la máquina puede hacer).
-minline-all-stringops
De manera predeterminada, GCC integra las operaciones de cadena solo cuando se sabe que el destino está alineado al menos con un límite de 4 bytes. Esto permite una mayor inline y aumenta el tamaño del código, pero puede mejorar el rendimiento del código que depende de memcpy, strlen y memset rápidos para longitudes cortas.
GCC también tiene
atributos por función
que aparentemente puedes usar para controlar esto, como
__attribute__((no-inline-all-stringops)) void foo() { ... }
, pero no he jugado con eso.
(Eso es lo contrario de inline-all. No significa inline none, solo vuelve a alinear cuando se conoce la alineación de 4 bytes).
Ambas estrategias de
strlen
línea de gcc no logran aprovechar la alineación de 16 bytes, y son bastante malas para x86-64
A menos que el caso de cadena pequeña sea muy común, hacer un fragmento de 4 bytes, luego los segmentos de 8 bytes alineados irían aproximadamente el doble de rápido que los de 4 bytes.
Y la estrategia de 4 bytes tiene una limpieza mucho más lenta que la necesaria para encontrar el byte dentro de la palabra que contiene el byte cero.
Detecta esto buscando un byte con su conjunto de bits alto, por lo que solo debe enmascarar los otros bits y usar
bsf
(barrido de bits hacia adelante)
.
Eso tiene una latencia de 3 ciclos en las CPU modernas (Intel y Ryzen).
O los compiladores pueden usar
rep bsf
para que se ejecute como
tzcnt
en las CPU que admiten BMI1, que es más eficiente en AMD.
bsf
y
tzcnt
dan el mismo resultado para entradas que no son cero.
El bucle de 4 bytes de GCC parece que está compilado a partir de C puro, o alguna lógica independiente del objetivo, sin aprovechar el escaneo de bits.
gcc usa
andn
para optimizarlo al compilar x86 con BMI1, pero aún así es menos de 4 bytes por ciclo.
SSE2
pcmpeqb
+
bsf
es mucho mejor tanto para entradas cortas como largas
.
x86-64 garantiza que SSE2 está disponible, y el sistema V x86-64 tiene
alignof(maxalign_t) = 16
por lo que
calloc
siempre devolverá los punteros que estén alineados al menos con 16 bytes.
Escribí un reemplazo para el bloque
strlen
para probar el rendimiento.
Como era de esperar, es aproximadamente 4 veces más rápido en Skylake con 16 bytes a la vez en lugar de 4.
(Compilé la fuente original para asm con
-O3
, luego edité el asm para ver qué rendimiento debería haber tenido con esta estrategia para la expansión en línea de
strlen
. También la
strlen
en el asm en línea dentro de la fuente C;
vea esa versión en Godbolt
. )
# at this point gcc has `s` in RDX, `i` in ECX
pxor %xmm0, %xmm0 # zeroed vector to compare against
.p2align 4
.Lstrlen16: # do {
#ifdef __AVX__
vpcmpeqb (%rdx), %xmm0, %xmm1
#else
movdqa (%rdx), %xmm1
pcmpeqb %xmm0, %xmm1 # xmm1 = -1 where there was a 0 in memory
#endif
add $16, %rdx # ptr++
pmovmskb %xmm1, %eax # extract high bit of each byte to a 16-bit mask
test %eax, %eax
jz .Lstrlen16 # }while(mask==0);
# RDX points at the 16-byte chunk *after* the one containing the terminator
# EAX = bit-mask of the 0 bytes, and is known to be non-zero
bsf %eax, %eax # EAX = bit-index of the lowest set bit
movb $''A'', -16(%rdx, %rax)
Tenga en cuenta que optimicé parte de la limpieza de strlen en el modo de direccionamiento de la tienda: corrijo el rebasamiento con el desplazamiento
-16
, y esto es solo encontrar el final de la cadena, no calculando realmente la longitud y luego la indexación como GCC ya estaba haciendo después de alinear su bucle de 4 bytes a la vez.
Para obtener la
longitud
real de la cadena (en lugar de un puntero al final), debe restar rdx-start y luego agregar
rax-16
(quizás con un LEA para agregar 2 registros + una constante, pero el LEA de 3 componentes tiene más latencia).
Con AVX para permitir carga + comparar en una instrucción sin destruir el registro a cero, el bucle completo es solo 4 uops, menos que 5. (prueba / jz macro-fusibles en un uop tanto en Intel como en AMD.
vpcmpeqb
con un
no indexado
la fuente de memoria puede mantenerlo microfusionado a través de toda la tubería, por lo que es solo 1 uop de dominio fusionado para el front-end.)
(Tenga en cuenta que la mezcla de AVX de 128 bits con SSE
no
causa bloqueos incluso en Haswell, siempre y cuando se encuentre en estado de limpieza superior. Por lo tanto, no me molesté en cambiar las otras instrucciones a AVX, solo una Sin embargo, parecía que había un pequeño efecto donde
pxor
era un poco
mejor
que
vpxor
en mi escritorio, para un cuerpo de bucle AVX. Parecía algo repetible, pero es raro porque no hay diferencia de tamaño de código y, por lo tanto, no hay diferencia de alineación .)
pmovmskb
es una instrucción single-uop.
Tiene una latencia de 3 ciclos en Intel y Ryzen (peor en la familia Bulldozer).
Para cadenas cortas, el viaje a través de la unidad SIMD y de vuelta a entero es una parte importante de la cadena de dependencia de ruta crítica para la latencia desde los bytes de la memoria de entrada hasta la dirección de almacenamiento, ya que está lista.
Pero solo SIMD tiene comparaciones de enteros empaquetados, por lo que escalar tendría que hacer más trabajo.
Para el caso de cadena muy pequeña (como 0 a 3 bytes), podría ser posible lograr una latencia ligeramente menor para ese caso usando escalar puro (especialmente en la familia Bulldozer), pero teniendo todas las cadenas de 0 a 15 bytes tome la la misma ruta de rama (rama de bucle nunca tomada) es muy buena para la mayoría de los casos de uso de cadenas cortas .
Ser muy bueno para todas las cadenas de hasta 15 bytes parece una buena opción, cuando sabemos que tenemos una alineación de 16 bytes.
La ramificación más predecible es muy buena.
(Y tenga en cuenta que cuando se realiza un bucle, la latencia de
pmovmskb
solo afecta la rapidez con la que podemos detectar las predicciones erróneas de ramificaciones para salir del bucle; la predicción de ramificaciones + la ejecución especulativa oculta la latencia de las pmovmskb independientes en cada iteración.
Si esperábamos que las cadenas más largas sean comunes, podríamos desenrollarnos un poco, pero en ese momento solo debe llamar a la función libc para que pueda enviarse a AVX2 si está disponible en tiempo de ejecución. El desenrollamiento a más de 1 vector complica la limpieza, dañando los casos simples.
En mi máquina, i7-6700k Skylake a 4.2GHz máx turbo (y
energy_performance_preference
= performance), con gcc8.2 en Arch Linux, obtengo un tiempo de referencia bastante consistente porque la velocidad del reloj de mi CPU aumenta durante el memset.
Pero tal vez no siempre al máximo turbo;
La gestión de la potencia de hw de Skylake disminuye la velocidad cuando está enlazada a la memoria.
perf stat
rendimiento demostró que normalmente tenía una velocidad de alrededor de 4.0 GHz al ejecutar esto para promediar la salida de la salida estándar y ver el resumen de rendimiento en stderr.
perf stat -r 100 ./a.out | awk ''{sum+= $1} END{print sum/100;}''
Terminé copiando mi asm en una declaración en línea-asm de GNU C, por lo que pude poner el código en el explorador del compilador Godbolt .
Para cadenas grandes, la misma longitud que en la pregunta: tiempos en ~ 4GHz Skylake
-
~ 62100 unidades de tiempo
clock_t
:-O1
rep scas: (clock()
es un poco obsoleto, pero no me molesté en cambiarlo) -
~ 15900 unidades de tiempo
clock_t
:-O3
gcc estrategia de bucle de 4 bytes: promedio de 100 ejecuciones =. (O tal vez ~ 15800 con-march=native
paraandn
) -
~ 1880 unidades de tiempo
clock_t
:strlen
llamadas a la función glibcstrlen
, usando AVX2 -
~ 3190 unidades de tiempo
clock_t
: (AVX1 vectores de 128 bits, 4 uop loop) asm en línea escrito a mano que gcc podría / debería en línea. -
~ 3230 unidades de hora
clock_t
: (SSE2 5 uop loop) asm en línea escrita a mano que gcc podría / debería en línea.
Mi asm escrito a mano también debería ser muy bueno para cuerdas cortas, porque no es necesario que se ramifique especialmente. La alineación conocida es muy buena para strlen, y libc no puede aprovecharla.
Si esperamos que las cadenas grandes sean raras, 1.7x más lento que libc para ese caso. La longitud de 1M bytes significa que no se mantendrá caliente en la caché L2 (256k) o L1d (32k) en mi CPU, por lo que incluso con el cuello de botella L3 la versión libc fue más rápida. (Probablemente, un bucle desenrollado y vectores de 256 bits no obstruyan el ROB con tantos uops por byte, por lo que los ejecutivos de OoO pueden ver más adelante y obtener más paralelismo de memoria, especialmente en los límites de la página).
Pero el ancho de banda del caché L3 es probablemente un cuello de botella que impide que la versión 4-uop se ejecute a 1 iteración por reloj, por lo que estamos viendo menos beneficios de que AVX nos ahorre un uop en el bucle. Con los datos activos en el caché L1d, deberíamos obtener 1,25 ciclos por iteración frente a 1.
Pero una buena implementación de AVX2 puede leer hasta 64 bytes por ciclo (2x 32 bytes de carga) usando
vpminub
para combinar pares antes de verificar los ceros y volver a encontrar dónde estaban.
La brecha entre esto y libc se abre más para tamaños de ~ 2k a ~ 30 kiB o para que permanezcan calientes en L1d.
Algunas pruebas de solo lectura con longitud = 1000 indican que glibc
strlen
realmente es 4 veces más rápido que mi bucle para cadenas de tamaño mediano en caché L1d
.
Eso es lo suficientemente grande como para que AVX2 se acelere hasta el gran bucle desenrollado, pero aún así cabe fácilmente en el caché L1d.
(Solo lectura evita las paradas de reenvío de la tienda, por lo que podemos hacer muchas iteraciones)
Si sus cadenas son tan grandes, debería usar cadenas de longitud explícita en lugar de tener que
strlen
, por lo que la alineación de un bucle simple todavía parece una estrategia razonable, siempre y cuando sea realmente
buena
para cadenas cortas y no como basura total en el medio. (como 300 bytes) y cadenas muy largas (> tamaño de caché).
Benchmarking cadenas pequeñas con esto:
Me encontré con algunas rarezas al tratar de obtener los resultados que esperaba:
Intenté que
s[31] = 0
para truncar la cadena antes de cada iteración (permitiendo una longitud constante corta).
Pero entonces mi versión SSE2 fue casi la misma velocidad que la versión de GCC.
¡Los puestos de envío de tiendas eran el cuello de botella!
Un almacén de bytes seguido de una carga más amplia hace que el reenvío de tiendas tome la ruta lenta que combina los bytes del búfer de la tienda con los bytes de la memoria caché L1d.
Esta latencia adicional forma parte de una cadena de depresiones en bucle a través del último fragmento de 4 bytes o 16 bytes de la cadena, para calcular el índice de la tienda para la siguiente iteración.
El código de 4 bytes a la vez más lento de GCC podría continuar procesando los fragmentos de 4 bytes anteriores a la sombra de esa latencia. (La ejecución fuera de orden es bastante fantástica: el código lento a veces no puede afectar la velocidad general de su programa).
Finalmente, lo resolví haciendo una versión de solo lectura y utilizando inline asm para evitar que el compilador saliera del bucle.
Pero el reenvío de tiendas es un problema potencial con el uso de cargas de 16 bytes. Si otras variables de C se almacenan más allá del final de la matriz, podríamos llegar a un bloqueo de SF debido a la carga del extremo de la matriz más lejos que con tiendas más estrechas. Para los datos copiados recientemente, estamos bien si se copiaron con almacenes alineados de 16 bytes o más, pero glibc memcpy para copias pequeñas hace 2x cargas superpuestas que cubren todo el objeto, desde el principio y el final del objeto. Luego almacena ambos, una vez más superpuestos, manejando el memmove src superpone el caso dst de forma gratuita. Por lo tanto, el segundo fragmento de 16 bytes o 8 bytes de una cadena corta que se acaba de recordar podría darnos un puesto de SF para leer el último fragmento. (El que tiene la dependencia de datos para la salida.)
Simplemente correr más lento para que no llegues al final antes de que esté listo no es bueno en general, así que no hay una gran solución aquí.
Creo que la
mayoría
de las veces no vas a usar un búfer que acabas de
escribir
,
por lo general vas a
strlen
una entrada que solo estás leyendo, por lo que las paradas de reenvío de tiendas no son un problema
.
Si algo más simplemente lo escribió, entonces un código eficiente con suerte no habría descartado la longitud y habría llamado a una función que requería recalcularlo.
Otras rarezas que no he descubierto totalmente:
La alineación del código hace una diferencia de 2 para la lectura, tamaño = 1000 (
s[1000] = 0;
).
Pero el bucle de asm más interno está alineado con
.p2align 4
o
.p2align 5
.
¡Aumentar la alineación del bucle puede ralentizarlo en un factor de 2!
# slow version, with *no* extra HIDE_ALIGNMENT function call before the loop.
# using my hand-written asm, AVX version.
i<1280000 read-only at strlen(s)=1000 so strlen time dominates the total runtime (not startup overhead)
.p2align 5 in the asm inner loop. (32-byte code alignment with NOP padding)
gcc -DUSE_ASM -DREAD_ONLY -DHIDE_ALIGNMENT -march=native -O3 -g strlen-microbench.c &&
time taskset -c 3 perf stat -etask-clock,context-switches,cpu-migrations,page-faults,cycles,branches,branch-misses,instructions,uops_issued.any,uops_executed.thread -r 100 ./a.out |
awk ''{sum+= $1} END{print sum/100;}''
Performance counter stats for ''./a.out'' (100 runs):
40.92 msec task-clock # 0.996 CPUs utilized ( +- 0.20% )
2 context-switches # 0.052 K/sec ( +- 3.31% )
0 cpu-migrations # 0.000 K/sec
313 page-faults # 0.008 M/sec ( +- 0.05% )
168,103,223 cycles # 4.108 GHz ( +- 0.20% )
82,293,840 branches # 2011.269 M/sec ( +- 0.00% )
1,845,647 branch-misses # 2.24% of all branches ( +- 0.74% )
412,769,788 instructions # 2.46 insn per cycle ( +- 0.00% )
466,515,986 uops_issued.any # 11401.694 M/sec ( +- 0.22% )
487,011,558 uops_executed.thread # 11902.607 M/sec ( +- 0.13% )
0.0410624 +- 0.0000837 seconds time elapsed ( +- 0.20% )
40326.5 (clock_t)
real 0m4.301s
user 0m4.050s
sys 0m0.224s
La rama de la nota definitivamente no es cero, frente a casi exactamente cero para la versión rápida. Y uops emitido es mucho más alto que la versión rápida: puede estar especulando por el camino incorrecto durante mucho tiempo en cada una de esas faltas de rama.
Probablemente las ramas internas y externas del bucle se están alias entre sí, o no.
El recuento de instrucciones es casi idéntico, simplemente diferente por algunos NOP en el bucle externo antes del bucle interno. Pero IPC es muy diferente: sin problemas, la versión rápida ejecuta un promedio de 4.82 instrucciones por reloj para todo el programa. (La mayor parte de eso se encuentra en el bucle más interno ejecutando 5 instrucciones por ciclo, gracias a una prueba / jz que macro-fusiona 2 instrucciones en 1 uop). Y tenga en cuenta que uops_executed es mucho más alto que uops_issued: eso significa que la microfusión es trabajando bien para obtener más uops a través del cuello de botella front-end.
fast version, same read-only strlen(s)=1000 repeated 1280000 times
gcc -DUSE_ASM -DREAD_ONLY -UHIDE_ALIGNMENT -march=native -O3 -g strlen-microbench.c &&
time taskset -c 3 perf stat -etask-clock,context-switches,cpu-migrations,page-faults,cycles,branches,branch-misses,instructions,uops_issued.any,uops_executed.thread -r 100 ./a.out |
awk ''{sum+= $1} END{print sum/100;}''
Performance counter stats for ''./a.out'' (100 runs):
21.06 msec task-clock # 0.994 CPUs utilized ( +- 0.10% )
1 context-switches # 0.056 K/sec ( +- 5.30% )
0 cpu-migrations # 0.000 K/sec
313 page-faults # 0.015 M/sec ( +- 0.04% )
86,239,943 cycles # 4.094 GHz ( +- 0.02% )
82,285,261 branches # 3906.682 M/sec ( +- 0.00% )
17,645 branch-misses # 0.02% of all branches ( +- 0.15% )
415,286,425 instructions # 4.82 insn per cycle ( +- 0.00% )
335,057,379 uops_issued.any # 15907.619 M/sec ( +- 0.00% )
409,255,762 uops_executed.thread # 19430.358 M/sec ( +- 0.00% )
0.0211944 +- 0.0000221 seconds time elapsed ( +- 0.10% )
20504 (clock_t)
real 0m2.309s
user 0m2.085s
sys 0m0.203s
Creo que es solo la predicción de la rama, no otras cosas de front-end que es un problema. Las instrucciones de prueba / rama no se dividen en un límite que impida la macro-fusión.
Cambiar
.p2align 5
a
.p2align 4
revierte:
-UHIDE_ALIGNMENT
vuelve lento.
Este enlace binario de Godbolt
reproduce el mismo relleno que estoy viendo con gcc8.2.1 en Arch Linux para ambos casos: 2x 11 bytes
nopw
+ un
nopw
3 bytes dentro del bucle externo para el caso rápido.
También tiene la fuente exacta que estaba usando localmente.
pequeños puntos de referencia de strlen de lectura corta:
Probado con cosas elegidas para que no sufra de errores de predicción de sucursales o reenvío de la tienda, y puede probar repetidamente la misma longitud corta en busca de iteraciones suficientes para obtener datos significativos.
strlen=33
, por lo que el terminador está cerca del inicio del tercer vector de 16 bytes.
(Hace que mi versión se vea tan mal como sea posible en comparación con la versión de 4 bytes).
-DREAD_ONLY
, e
i<1280000
como un bucle de repetición del bucle externo.
-
1933 clock_t: my asm
: agradable y coherente en el mejor de los casos (no ruidoso / rebotando cuando se vuelve a ejecutar el promedio).
-DHIDE_ALIGNMENT
igual con / sin-DHIDE_ALIGNMENT
, a diferencia del strlen más largo. La rama del bucle es mucho más fácil de predecir con un patrón mucho más corto. (strlen = 33, no 1000). -
3220 clock_t: gcc
strlen
. (-DHIDE_ALIGNMENT
) - 6100 clock_t: gcc -O3 bucle de 4 bytes
- 37200 clock_t: gcc -O1 repz scasb
Así que para cadenas cortas, mi simple bucle en línea
supera
una llamada de la función de biblioteca a
strlen
que tiene que pasar por el PLT (call +
jmp [mem]
), luego ejecuta la sobrecarga de inicio de strlen que no depende de la alineación.
Hubo errores de predicción insignificantes, como 0.05% para todas las versiones con
strlen(s)=33
.
La versión de repz scasb tuvo un 0,46%, pero eso es un número menor de sucursales.
No hay bucle interno para acumular muchas ramas predichas correctamente.
Con los predictores de ramificación y el caché de código
repz scasb
,
repz scasb
es más de 10 veces peor que llamar a glibc
strlen
para una cadena de 33 bytes.
Sería menos malo en los casos de uso real en los que
strlen
podría
strlen
o incluso fallar en el caché de código y el bloqueo, pero en la línea
repz scasb
no lo haría el
repz scasb
.
Pero 10x es enorme, y eso es para una cadena bastante corta.