Hoy mediremos el rendimiento de diferentes implementaciones de la función toupper, porque esto es lo que hacen los martes.
En realidad, no me importa la función
toupper , acabo de escribir otra publicación recientemente y necesitaba algún tipo de núcleo de trama común, y
toupper parece ser un candidato bastante interesante e inofensivo para los puntos de referencia. Traté de elegir algo lo más simple posible que no me llevara a un lado, pero sucedió que en esta prueba me encontré con un problema extraño.
Esta publicación será pequeña: pronto se espera un artículo más completo sobre el tema original, quizás más interesante. Si quieres reproducir los resultados conmigo, puedes
tomar el código fuente
en github .
Por lo tanto, consideraremos tres implementaciones de la función
toupper , que convierte los caracteres de una matriz que consta de elementos de tipo
char a mayúsculas, es decir, toma una matriz como argumento y cambia directamente sus elementos para que todas las letras minúsculas estén en mayúscula.
En la primera implementación, simplemente llamamos a
la función toupper [1]
de la biblioteca estándar C y ejecutamos un bucle de estilo C:
void toupper_rawloop(char* buf, size_t size) { for (size_t i = 0; i < size; i++) { buf[i] = toupper(buf[i]); } }
En la segunda implementación, utilizamos un enfoque
más moderno con la sustitución del ciclo sin procesar con
std :: transform :
void toupper_transform(char* buf, size_t size) { std::transform(buf, buf + size, buf, ::toupper); }
Finalmente, en la tercera implementación, usamos un algoritmo especial que funciona con caracteres ASCII. Comprueba si el carácter está en el rango
a - z , y si tiene éxito, sustituye la misma letra en mayúscula, restando el número 32 del código de carácter [2]:
void toupper_branch(char* buf, size_t size) { for (size_t i = 0; i < size; i++) { char c = buf[i]; if (c >= 'a' && c <= 'z') { buf[i] = c - 32; } } }
Parece fácil, ¿verdad?
Ahora mediremos la velocidad de estas implementaciones en mi computadora portátil con el procesador Skylake i7-6700HQ en el compilador gcc 5.5 con la configuración predeterminada. Los resultados se dan en forma de un gráfico de dispersión [3]:
Inmediatamente trataremos tres preguntas que son irrelevantes para nuestra tarea.
Primero, mire la gráfica del algoritmo de ramificación (que se muestra en verde). Varía significativamente según el tamaño de los datos de entrada: los otros dos gráficos permanecen casi planos. Esto es en realidad solo un artefacto de prueba. Los caracteres ASCII de entrada se seleccionan aleatoriamente [4], por lo que el factor decisivo en el caso de la tercera implementación es la operación del algoritmo de predicción de rama. Con una pequeña cantidad de datos, memoriza completamente la secuencia de elementos a medida que se realiza la iteración, por lo que el número de errores es pequeño y la velocidad es alta,
como se muestra en esta nota . A medida que aumenta el tamaño de la secuencia de datos, el algoritmo de predicción recuerda cada vez menos hasta que finalmente comienza a fallar con cada letra mayúscula (0.27 errores por carácter), y luego el gráfico se nivela.
En segundo lugar, preste atención al grupo de puntos verdes en la
esquina superior izquierda, que corresponde a velocidades mucho más bajas de la variante con ramificación
toupper_branch :
Este no es un artefacto aislado: tales manchas aparecieron durante varios lanzamientos. Al mismo tiempo, no se pueden reproducir si prueba el algoritmo solo específicamente en estos tamaños de datos; aparecen solo cuando la prueba se ejecuta en todos los tamaños. Pero en este caso, no siempre aparecen. No profundicé en ello, pero puedo suponer que esto se debe a algunos conflictos de nombres o alias en el algoritmo de predicción de rama o al mapear páginas físicas de memoria de 4 kB a virtual (aunque la aleatorización del espacio de direcciones virtuales estaba desactivada).
En tercer lugar, la implementación de
toupper_rawloop (que se muestra en azul) en el gráfico parece dos líneas separadas: una ligeramente por encima de la marca de 2 medidas por carácter y la otra al nivel de 1,5 medidas por carácter. Estas dos líneas aparecieron en todos los probadores. La opción más rápida, con una velocidad de 1.57 caracteres por ciclo, en realidad se ralentiza en los puertos de descarga: la lectura de datos en los puertos 2 y 3 ocurre a una velocidad de 1.54 microoperaciones por ciclo, por lo que estarán ocupados al 98%. No pude establecer la razón del "régimen" más lento.
Mientras estaba lidiando con este problema, el "régimen" rápido desapareció repentinamente y solo permaneció el lento. Quizás el procesador se dio cuenta de lo que estaba tratando de hacer y descargó secretamente la actualización del microcódigo para eliminar la contradicción, pero (todavía) tengo pruebas: una imagen vectorial con gráficos.
¿Qué nos interesa entonces en este ejemplo?
Pero lo que nos interesa es que la versión con un ciclo "en bruto" es 3-4 veces más rápida que la versión con
std :: transform : 1.5-2 ciclos por carácter versus 7 con unos pocos ciclos por carácter.
¿Cuál es el problema aquí? ¿Me han fallado los algoritmos estándar? ¿
Std :: transform tiene algún defecto?
En realidad no Más precisamente, en absoluto.
Resulta que tales resultados aparecen cuando las funciones se compilan en
diferentes archivos . Si los coloca en el mismo archivo, su rendimiento se vuelve igualmente bajo.
Y no, la alineación no tiene nada que ver con eso.
Pero eso no es todo: la versión rápida con un ciclo "en bruto", cuando se compila en un archivo separado, se ralentiza si simplemente le adjunta el archivo de encabezado
<algorithm> . Sí, es cierto: solo conecte este archivo, que nunca se usa y no genera ningún código en el archivo de objeto final, y la velocidad del ciclo "en bruto" caerá 3-4 veces. Por el contrario, la versión con
std :: transform se acelera al límite si copia y pega la implementación de
std :: transform desde el archivo
<algorithm> , pero no incluye este archivo.
Las rarezas no terminan allí (no habrá más, lo prometo): incluir el archivo
<algorithm> no siempre conduce al efecto descrito. Se produce una caída de velocidad si
<algorithm> está conectado antes que
<ctype.h> , pero si los intercambia, entonces no:
Código lento #include <algorithm> #include <ctype.h>
Código rápido: #include <ctype.h> #include <algorithm>
En realidad, esta anomalía apareció en mí (en otro proyecto) cuando el formato clang clasificó automáticamente los archivos de encabezado incluidos y colocó el
<algoritmo> al comienzo de la lista, donde pertenece (de ahí el encabezado clickbait del artículo).
Naturalmente, tuvimos que sumergirnos en la lista de ensambladores tarde o temprano. No demoraremos este desagradable momento.
Las versiones
rápida y lenta de las funciones [5] se muestran a continuación, los bucles pequeños cuentan con anotaciones:
<algorithm> conecta primero: toupper_rawloop(char*, unsigned long): push rbp push rbx lea rbp, [rdi+rsi] sub rsp, 8 test rsi, rsi je .L1 mov rbx, rdi .L5: movsx edi, BYTE PTR [rbx] ; char- *buf add rbx, 1 ; buf++ call toupper ; toupper(c) mov BYTE PTR [rbx-1], al ; buf[-1] cmp rbp, rbx ; buf == buf_end jne .L5 ; .L1: add rsp, 8 pop rbx pop rbp ret
<algorithm> está conectado en segundo lugar: toupper_rawloop(char*, unsigned long): test rsi, rsi je .L7 push rbp push rbx mov rbp, rsi mov rbx, rdi sub rsp, 8 call __ctype_toupper_loc lea rsi, [rbx+rbp] mov rdi, rbx .L4: ; char- buf movsx rcx, BYTE PTR [rdi] ; toupper ; ( __ctype_toupper_loc) mov rdx, QWORD PTR [rax] ; buf++ add rdi, 1 ; toupper , ; mov edx, DWORD PTR [rdx+rcx*4] mov BYTE PTR [rdi-1], dl ; cmp rsi, rdi ; buf == end_buf jne .L4 ; add rsp, 8 pop rbx pop rbp .L7: rep ret
La principal diferencia es que en la versión lenta la función toupper simplemente se llama en un bucle, mientras que en la versión rápida las llamadas a funciones están completamente ausentes, y solo hay una búsqueda en la tabla de correspondencia [6], es decir el cuerpo de la función
std :: toupper se sustituye en el lugar de la llamada.
Si observa el
código fuente de la biblioteca glibc, encontramos la implementación de la función
toupper allí:
__extern_inline int
Como podemos ver,
toupper se define como una función en
línea externa que primero verifica que el tamaño del carácter char se ajuste a un byte [7], y luego busca el carácter en la tabla de correspondencia devuelta por la función
__ctype_toupper_loc () . Esta función devuelve un puntero de flujo local (de tipo
const int ** ), que, a su vez, apunta a una tabla de correspondencia, desde la cual, en respuesta a una solicitud de nuestro símbolo, se devuelve su versión en mayúscula [8].
Ahora está claro lo que está sucediendo en la lista. En la versión rápida del algoritmo, el compilador sustituye el cuerpo de la función
toupper , pero no puede sustituir la llamada a la función
__ctype_toupper_loc () [9]. Sin embargo, esta llamada se declara como
__attribute __ ((const)) , lo que significa que el valor de retorno depende solo de los argumentos (que no están aquí). El compilador sabe que esta función devuelve el mismo valor cada vez y, por lo tanto, lleva su llamada fuera del bucle, y en el bucle solo hay unas pocas operaciones de lectura asociadas con el acceso a la tabla de correspondencia, la escritura de un nuevo valor en el búfer y el control del bucle.
En la versión lenta, la llamada a
toupper () permanece en el cuerpo del bucle. El ciclo en sí mismo es más corto por un comando, pero, por supuesto, ahora todavía tiene que ejecutar todo el código dentro de la función
toupper . En mi sistema, se ve así:
lea edx,[rdi+0x80] ; edx = rdi + 0x80 movsxd rax,edi ; c cmp edx,0x17f ; , c -128 255 ja 2a ; , mov rdx,QWORD PTR [rip+0x395f30] ; ; mov rdx,QWORD PTR fs:[rdx] ; ; mov rdx,QWORD PTR [rdx] ; ; mov rdx,QWORD PTR [rdx+0x48] ; toupper mov eax,DWORD PTR [rdx+rax*4+0x200] ; c 2a: ret
Como se trata de una llamada no integrada, el programa realiza más trabajo. Hay al menos cinco operaciones consecutivas de acceso a la memoria (la llamada búsqueda de punteros, persecución de punteros). En la versión rápida, solo quedan dos, ya que todos los demás se eliminan del bucle. El retraso entre llamar a una función y salir de ella debería ser de aproximadamente 25 ciclos, y tenemos aproximadamente 7 ciclos saliendo, esto significa que el procesador pudo paralelizar la llamada, lo cual es bastante bueno, dadas las circunstancias.
¿Por qué es esto así?
En una larga cadena de archivos de inclusión, los archivos de encabezado C ++, como
<algorithm> , incluyen, a su vez, el archivo
<bits / os_defines.h> , que contiene la siguiente línea:
Cuando el archivo
<ctype.h> finalmente se conecta, debido a esta directiva, el código en el que
toupper se define como
externo en línea no se puede incluir:
#if !defined __NO_CTYPE # ifdef __isctype_f __isctype_f (alnum)
Tenga en cuenta que cuando se conecta
<ctype.h>, la versión C ++ de
toupper nunca se define como una macro, como máximo en
línea externa , ya que las definiciones de las macros están protegidas por la
comprobación! Defined __cplusplus y, por lo tanto, nunca surtirán efecto.
En general, no sé con certeza si
__NO_CTYPE en este caso debería excluir los cuerpos de las funciones
tolower y
toupper declaradas como en
línea externa , pero esto es exactamente lo que sucede, y por lo tanto, una caída significativa en la velocidad de nuestro ciclo. En conclusión, puedo decir que si incluye
<cctype> en lugar de
<ctype.h> (es decir, C ++ es la versión del archivo de encabezado C que pone funciones en el
espacio de nombres std ::) , entonces en este caso el código funcionará lentamente porque
<cctype> finalmente incluye
<bits / os_defines.h> .
¿Es tan importante? No no
La función
toupper no es adecuada para trabajos serios con caracteres de diferentes idiomas, por lo que si necesita procesar solo caracteres ASCII, puede escribir su propia implementación más rápida. Si necesita un trabajo serio con el texto, lo más probable es que use UTF-8 y tenga que usar algún tipo de UCI para admitir configuraciones regionales, o esperar hasta que aparezca el soporte Unicode en C ++ (puede tomar mucho tiempo esperar) . Por lo tanto, la declaración "el formato clang puede causar una caída del rendimiento 4x" solo es adecuada como encabezado de clickbait.
¿Se observa este efecto en todas las versiones de libc? Sí, en general, pero incluso aquí no es tan simple.
Los resultados mostrados anteriormente son verdaderos para gcc 5.5 y glibc 2.23, porque usé estas versiones, pero algo nuevo está sucediendo en las nuevas versiones (comenzando desde aproximadamente glibc 2.27). Allí, encender
<algorithm> antes de
<ctype.h> todavía da el mismo efecto, pero ahora
<stdlib.h> [10] también crea problemas: si lo enciende antes de
<ctype.h> , el rendimiento también disminuirá, lo que no es observado en versiones anteriores. Obviamente, en versiones más recientes, el archivo
<stdlib.h> también contiene la definición
__NO_CTYPE . Al menos, ahora no será posible culpar al formato clang por la clasificación, aquí solo puede ayudar a resolver el problema (si no hay otros archivos problemáticos en la lista de archivos conectados).
Publiqué
un informe de error en libc , por lo que es probable que este error se solucione, pero no hay duda de que los errores relacionados con el orden en que se conectan los archivos de encabezado nos molestarán aún más.
Comentarios
No tengo un sistema de comentarios en mi sitio, pero estoy trabajando en ello (es decir, quejándose periódicamente, lo cual es difícil de hacer comentarios en un sitio estático).
Mientras tanto, puede discutir este artículo en el sitio web de
Hacker News o
lobste.rs .
Agradecimientos
Gracias al usuario de ovnis con Hacker News, quien
señaló que no es necesario usar la función lambda para adaptar
std :: toupper para usar en
std :: transform , y también a Jonathan Muller, quien
explicó que la función lambda todavía es necesaria.
- Sí, la función toupper (3) del archivo de encabezado <ctype.h> no es adecuada para trabajar con la mayoría de los caracteres no ASCII, como no puede manejar caracteres de más de un byte, pero es adecuado para nuestra tarea, ya que solo le pasaremos cadenas de caracteres ASCII.
- En la tabla ASCII, los caracteres en mayúsculas y minúsculas están convenientemente ubicados, a una distancia de 32 posiciones entre sí, lo que significa que puede transferir caracteres de un caso a otro simplemente restando o sumando 32. En general, si supiéramos con certeza que todas las entradas los datos son letras ASCII, podríamos restablecer el quinto bit sin ninguna verificación (por ejemplo, c & 0b11011111 ) para convertir cualquier letra mayúscula en minúscula, mientras que esto no se reflejaría en letras minúsculas. Pero probablemente no lo sepamos, por lo que debemos verificar si el carácter es una letra, para no romper accidentalmente caracteres que no sean letras como char .
- Debería llamarse un diagrama de dispersión con la adición de "ruido" a la ubicación de los puntos. De hecho, este es un diagrama de dispersión ordinario en el que el parámetro de interés para nosotros (el tamaño de los datos de entrada) se traza en el eje x, y la velocidad de trabajo está en el eje y (medidas por símbolo: cuanto menor es el valor, mayor es la velocidad ). La característica principal de este diagrama es que para cada valor de parámetro en el eje x, el muestreo se realiza varias veces: en este caso, la prueba se repite 10 veces para cada tamaño de matriz.
- Es decir, los caracteres se seleccionan aleatoria y uniformemente del rango [32, 127], por lo que la condición en la función será verdadera en aproximadamente el 27% de los casos.
- Ambos listados se refieren a una implementación de ciclo sin procesar y difieren solo en el orden en que se incluyen los archivos <algorithm> y <ctype.h> . El código fuente generado es el mismo para todas las implementaciones, tanto en versiones rápidas como lentas. Por ejemplo, una implementación con std :: transform producirá el mismo código de ensamblador lento si incluye el archivo <algorithm> , y el mismo código rápido si copia solo la definición de función y no incluye el archivo.
- Sin embargo, este ciclo rápido es más lento de lo que podría debido a que el puntero a la tabla de correspondencia se lee demasiadas veces ( mov rdx, QWORD PTR [rax] ) dentro del ciclo. Este puntero puede ser diferente según la configuración regional, pero no se actualiza durante la ejecución del ciclo y, por lo tanto, podría moverse fuera del ciclo. Debe ser que el compilador cree que no hay suficientes razones para esto, ya que estamos escribiendo en una serie de elementos de tipo char , y en principio pueden usarse como alias para [rax] es decir puntero a la mesa. De todos modos, incluso __restrict__ no ayudará aquí. Pero en otra versión del ciclo, donde los valores de referencia simplemente se agregan y no se escribe nada en la matriz, se aplica esta optimización : el puntero se lee fuera del ciclo.
- Esta comprobación no se refleja en el código del ensamblador sustituible, ya que el compilador ya sabe que los valores de caracteres siempre están en el rango [-128, 255] . La verificación es necesaria solo porque la API de la función toupper © acepta un valor de tipo int en lugar de char , para que el usuario pueda pasar cualquier número familiar de tipo int , mientras que las tablas de correspondencia están diseñadas solo para valores de tipo char , por lo que la comprobación ayuda a evitar leer fuera del búfer .
- Por cierto, esto explica por qué los procedimientos std :: toupper son independientes del tamaño de los datos de entrada: no usan ramas (excepto para las comprobaciones de rango, que se predicen notablemente), sino que usan una tabla de correspondencia independiente de la rama. ↵
- La sustitución de esta llamada no funcionará incluso con un deseo muy fuerte: el cuerpo de la función no está disponible en el archivo de encabezado.
- De ninguna manera encuentro fallas en stdlib.h (o <algorithm> , para el caso): es muy posible que muchos otros archivos de encabezado C y todos los archivos de encabezado C ++ también causen este comportamiento, simplemente no los probé. Conecté stdlib.h solo para determinar size_t .
Nota Este artículo se publicó por primera vez en el sitio web de
Performance Matters . Los artículos de traducción se publican aquí con permiso del autor.