sirve - string en c++
¿Por qué strcmp no SIMD optimizado? (8)
Intenté compilar este programa en una computadora x64:
#include <cstring>
int main(int argc, char* argv[])
{
return ::std::strcmp(argv[0],
"really really really really really really really really really"
"really really really really really really really really really"
"really really really really really really really really really"
"really really really really really really really really really"
"really really really really really really really really really"
"really really really really really really really really really"
"really really really really really really really really really"
"really really really really really really really really really"
"really really really really really really really long string"
);
}
Lo compilé así:
g++ -std=c++11 -msse2 -O3 -g a.cpp -o a
Pero el desensamblaje resultante es así:
0x0000000000400480 <+0>: mov (%rsi),%rsi
0x0000000000400483 <+3>: mov $0x400628,%edi
0x0000000000400488 <+8>: mov $0x22d,%ecx
0x000000000040048d <+13>: repz cmpsb %es:(%rdi),%ds:(%rsi)
0x000000000040048f <+15>: seta %al
0x0000000000400492 <+18>: setb %dl
0x0000000000400495 <+21>: sub %edx,%eax
0x0000000000400497 <+23>: movsbl %al,%eax
0x000000000040049a <+26>: retq
¿Por qué no se usa SIMD? Supongo que podría ser para comparar, digamos, 16 caracteres a la vez. ¿Debo escribir mi propia SIMD strcmp , o es una idea sin sentido por alguna razón?
AVX 2.0 sería más rápido en realidad
Editar: está relacionado con registros e IPC
En lugar de confiar en 1 gran instrucción, puedes usar una plétora de instrucciones SIMD con 16 registros de 32 bytes, bueno, en UTF16 ¡te da 265 caracteres para jugar!
¡duplique eso con avx512 en pocos años!
Las instrucciones AVX también tienen alto rendimiento.
Según este blog: https://blog.cloudflare.com/improving-picohttpparser-further-with-avx2/
Hoy, en los últimos procesadores Haswell, tenemos las potentes instrucciones AVX2. Las instrucciones AVX2 operan en 32 bytes, y la mayoría de las instrucciones booleanas / lógicas tienen un rendimiento de 0.5 ciclos por instrucción. Esto significa que podemos ejecutar aproximadamente 22 instrucciones AVX2 en el mismo tiempo que lleva ejecutar un solo PCMPESTRI. ¿Por qué no darle una oportunidad?
Las unidades de edición 2.0 SSE / AVX tienen alimentación automática, y mezclar las instrucciones de SSE y / o AVX con las normales implica un cambio de contexto con una penalización de rendimiento, que no debería tener con la instrucción strcmp.
Cuando se diseñó la biblioteca estándar para C, las implementaciones de los métodos de string.h que fueron más eficientes cuando se trata de grandes cantidades de datos serían razonablemente eficientes para pequeñas cantidades, y viceversa. Si bien puede haber algunos escenarios de comparación de cadenas, el uso sofisticado de las instrucciones SIMD podría producir un mejor rendimiento que una "implementación ingenua", en muchos escenarios del mundo real las cadenas que se comparan difieren en los primeros caracteres. En tales situaciones, la implementación ingenua puede producir un resultado en menos tiempo del que un enfoque "más sofisticado" pasaría decidiendo cómo se debería realizar la comparación. Tenga en cuenta que incluso si el código SIMD puede procesar 16 bytes a la vez y detener cuando se detecta una condición de desajuste o fin de cadena, todavía tendría que hacer un trabajo adicional equivalente al uso del enfoque ingenuo en los últimos 16 caracteres escaneados. . Si coinciden muchos grupos de 16 bytes, poder escanearlos rápidamente puede favorecer el rendimiento. Pero en los casos en que los primeros 16 bytes no coinciden, sería más eficiente comenzar con la comparación carácter por carácter.
Por cierto, otra ventaja potencial del enfoque "ingenuo" es que sería posible definirlo en línea como parte del encabezado (o un compilador podría considerarse a sí mismo como que tiene un "conocimiento" especial sobre él). Considerar:
int strcmp(char *p1, char *p2)
{
int idx=0,t1,t2;
do
{
t1=*p1; t2=*p2;
if (t1 != t2)
{
if (t1 > t2) return 1;
return -1;
}
if (!t1)
return 0;
p1++; p2++;
} while(1);
}
...invoked as:
if (strcmp(p1,p2) > 0) action1();
if (strcmp(p3,p4) != 0) action2();
Si bien el método sería un poco grande para alinearse, el forro interno podría permitir en el primer caso que un compilador elimine el código para verificar si el valor devuelto fue mayor que cero, y en el segundo eliminar el código que verifica si t1 fue mayor que t2. Tal optimización no sería posible si el método se enviara por medio de un salto indirecto.
Depende de tu implementación. En MacOS X, las funciones como memcpy, memmove y memset tienen implementaciones optimizadas según el hardware que esté utilizando (la misma llamada ejecutará un código diferente según el procesador, configurado en el momento del arranque); estas implementaciones usan SIMD y para grandes cantidades (megabytes) utilizan algunos trucos bastante sofisticados para optimizar el uso de la memoria caché. Nada para strcpy y strcmp por lo que sé.
Es difícil convencer a la biblioteca estándar de C ++ para usar ese tipo de código.
En una implementación de SSE2, ¿cómo debería asegurarse el compilador de que no haya accesos de memoria al final de la cadena? Tiene que conocer la longitud primero y esto requiere escanear la cadena para el byte cero de terminación.
Si busca la longitud de la cadena, ya ha realizado la mayor parte del trabajo de una función strcmp. Por lo tanto, no hay ningún beneficio para usar SSE2.
Sin embargo, Intel agregó instrucciones para el manejo de cadenas en el conjunto de instrucciones SSE4.2. Estos manejan el problema del cero de terminación. Para una buena reseña sobre ellos, lea esta publicación de blog:
GCC en este caso está usando un strcmp incorporado. Si desea que use la versión de glibc use -fno-builtin . Pero no debes asumir que la versión strcmp de strcmp de strcmp o la implementación de strcmp de strcmp es eficiente. Sé por experiencia que la memcpy GCC y la memcpy de glibc no son tan eficientes como podrían ser .
Sugiero que mires el asmlib de Agner Fog . Él ha optimizado varias de las funciones de biblioteca estándar en ensamblaje. Vea el archivo strcmp64.asm . Esto tiene dos versiones: una versión genérica para CPU sin SSE4.2 y una versión para CPU con SSE4.2. Aquí está el ciclo principal para la versión SSE4.2
compareloop:
add rax, 16 ; increment offset
movdqu xmm1, [rs1+rax] ; read 16 bytes of string 1
pcmpistri xmm1, [rs2+rax], 00011000B ; unsigned bytes, equal each, invert. returns index in ecx
jnbe compareloop ; jump if not carry flag and not zero flag
Para la versión genérica, escribe
Esta es una solución muy simple. No se gana mucho usando SSE2 o algo complicado
Aquí está el ciclo principal de la versión genérica:
_compareloop:
mov al, [ss1]
cmp al, [ss2]
jne _notequal
test al, al
jz _equal
inc ss1
inc ss2
jmp _compareloop
Compararía el rendimiento del strcmp incorporado de strcmp , el strcmp de strcmp y el strmlmp strcmp . Debería ver el desmontaje para asegurarse de obtener el código incorporado. Por ejemplo, memcpy de GCC no utiliza la versión integrada de tamaños superiores a 8192.
Editar: Con respecto a la longitud de la cadena, la versión SSE4.2 de Agner lee hasta 15 bytes más allá de la cadena. Él argumenta que esto rara vez es un problema ya que nada está escrito. No es un problema para las matrices asignadas a la pila. Para arreglos asignados estáticamente, podría ser un problema para los límites de la página de memoria. Para evitar esto, agrega 16 bytes a la sección .bss después de la sección .data. Para obtener más información, consulte la sección 1.7 Instrucciones de cadena y precauciones de seguridad en el manaul del asmlib .
Hacer una versión SSE2 de strcmp fue un desafío interesante para mí.
Realmente no me gustan las funciones intrínsecas del compilador debido a la obstrucción del código, así que decidí elegir el enfoque de auto-vectorización. Mi enfoque se basa en plantillas y se aproxima al registro SIMD como una matriz de palabras de diferentes tamaños.
Traté de escribir una implementación de auto-vectorización y probarla con los compiladores GCC y MSVC ++.
Entonces, lo que aprendí es:
1. El auto-vectorizador de GCC es bueno (¿impresionante?)
2. El autovectorizador de MSVC es peor que GCC (no vectoriza mi función de embalaje)
3. Todos los compiladores rechazaron generar la instrucción PMOVMSKB, es realmente triste
Resultados:
La versión compilada por GCC en línea gana ~ 40% con la auto-vectorización de SSE2. En mi máquina Windows con arquitectura Bulldozer, el código auto-vectorizado de la CPU es más rápido que el compilador en línea y los resultados coinciden con la implementación nativa de strcmp . Pero lo mejor de la idea es que se puede compilar el mismo código para cualquier conjunto de instrucciones SIMD, al menos en ARM & X86.
Nota:
Si alguien encuentra la manera de hacer que el compilador genere la instrucción PMOVMSKB, el rendimiento general debería recibir un impulso significativo.
Opciones de línea de comando para GCC: -std = c ++ 11 -O2 -m64 -mfpmath = sse -march = native -ftree-vectorize -msse2 -march = native -Wall -Wextra
Campo de golf:
Código fuente compilado por el compilador en línea de Coliru
Asamblea + código fuente (compilador Explorer)
@ PeterCordes, gracias por la ayuda.
No veo el sentido de "optimizar" una función como strcmp .
Necesitará encontrar la longitud de las cadenas antes de aplicar cualquier tipo de procesamiento paralelo, lo que lo forzará a leer la memoria al menos una vez. Mientras lo hace, también podría usar los datos para realizar la comparación sobre la marcha.
Si quieres hacer algo rápido con cadenas, necesitarás herramientas especializadas como máquinas de estados finitos ( lexx viene a la mente para un analizador).
En cuanto a C ++ std::string , son ineficientes y lentos por una gran cantidad de razones, por lo que la ganancia de la longitud de comprobación en las comparaciones es descuidada.
Sospecho que simplemente no tiene sentido en las versiones SIMD de las funciones de la biblioteca con muy poco cálculo. Imagino que funciones como strcmp , memcpy y similares están realmente limitadas por el ancho de banda de la memoria y no por la velocidad de la CPU.