Función de piso entero eficiente en C++
performance x86-64 (5)
Casting a int es notoriamente lento.
Tal vez usted ha estado viviendo bajo una roca desde x86-64, o se ha perdido de alguna manera que esto no ha sido cierto durante un tiempo en x86. :)
SSE / SSE2 tiene una instrucción para convertir con truncamiento (en lugar del modo de redondeo predeterminado). La ISA admite esta operación de manera eficiente precisamente porque la conversión con semántica de C no es rara en las bases de código reales. El código x86-64 utiliza los registros XMM SSE / SSE2 para matemáticas FP escalares, no x87, debido a esto y otras cosas que lo hacen más eficiente. Incluso el código moderno de 32 bits utiliza registros XMM para matemáticas escalares.
Cuando se compila para x87 (sin la
fisttp
SSE3), los compiladores solían tener que cambiar el modo de redondeo x87 al truncamiento, el almacenamiento de FP a la memoria y luego volver a cambiar el modo de redondeo.
(Y luego vuelva a cargar el entero desde la memoria, generalmente desde un local en la pila, si está haciendo más cosas con él). X87 fue
terrible
para esto.
Sí, eso fue terriblemente lento, por ejemplo, en 2006, cuando se escribió el enlace en @ Kirjain, si todavía tenía una CPU de 32 bits o estaba usando una CPU x86-64 para ejecutar el código de 32 bits.
La conversión con un modo de redondeo distinto del truncamiento o el valor predeterminado (el más cercano) no se admite directamente, y hasta que las
roundps
roundpd
roundps
/
roundpd
SSE4.1
roundps
trucos de números mágicos, como en
el enlace de 2006
de @ Kirjain.
Algunos trucos agradables allí, pero solo para el
double
-> entero de 32 bits.
Es poco probable que valga la pena expandirse al
double
si tienes
float
.
O más generalmente, simplemente agregue un número de gran magnitud para desencadenar el redondeo, luego reste de nuevo para volver al rango original.
Esto puede funcionar para
float
sin expandirse al
double
, pero no estoy seguro de lo fácil que es hacer que el
floor
funcione.
De todos modos, la solución obvia aquí es
_mm256_floor_ps()
y
_mm256_cvtps_epi32
(
vroundps
y
vcvtps2dq
).
Una versión no AVX de esto puede funcionar con SSE4.1.
No estoy seguro de si podemos hacerlo aún mejor;
Si tuviera que procesar una gran matriz (y no pudo intercalar este trabajo con otro trabajo),
podría establecer el modo de redondeo MXCSR en "Hacia -Inf" (piso) y simplemente usar
vcvtps2dq
(que usa el modo de redondeo actual ).
Entonces ponlo de vuelta.
Pero es probable que sea mejor bloquear en caché la conversión o hacerlo sobre la marcha a medida que genera los datos, probablemente de otros cálculos de PF que necesitan que el modo de redondeo de PF esté configurado en el valor Más cercano predeterminado.
roundps
/ pd / ss / sd es 2 uops en las CPU Intel, pero solo 1 uop (por carril de 128 bits) en AMD Ryzen.
cvtps2dq
también es 1 uop.
empaquetado doble -> conversión int también incluye un shuffle.
La conversión escalar de FP-> int (que se copia a un registro entero) generalmente también cuesta un uop adicional para eso.
Así que hay espacio para la posibilidad de que los trucos con números mágicos sean una victoria en algunos casos;
quizás valga la pena investigar si
_mm256_floor_ps()
+ cvt es parte de un cuello de botella crítico (o más probablemente si tiene doble y quiere int32).
El
int foo = floorf(f)
Cássio Renan en realidad se auto-vectoriza si se compila con
gcc -O3 -fno-trapping-math
(o
-ffast-math
), con
-march=
algo que tiene SSE4.1 o AVX.
https://godbolt.org/z/ae_KPv
Esto puede ser útil si está usando esto con otro código escalar que no se ha vectorizado manualmente. Especialmente si esperas que el compilador auto-vectorice todo el asunto.
Quiero definir una función de piso de enteros eficiente, es decir, una conversión de float o double que realice el truncamiento hacia el infinito menos.
Podemos suponer que los valores son tales que no se produce un desbordamiento de enteros. Hasta ahora tengo algunas opciones.
-
casting a int; esto requiere un manejo especial de los valores negativos, ya que la conversión se trunca hacia cero;
I= int(F); if (I < 0 && I != F) I--; -
echando el resultado del piso a int;
int(floor(F)); -
lanzar a int con un gran cambio para obtener resultados positivos (esto puede devolver resultados erróneos para valores grandes);
int(F + double(0x7fffffff)) - 0x7fffffff;
Casting a int es notoriamente lento. Así son si las pruebas. No he cronometrado la función de piso, pero he visto publicaciones que afirman que también es lenta.
¿Puedes pensar en mejores alternativas en términos de velocidad, precisión o rango permitido? No necesita ser portátil. Los objetivos son las arquitecturas recientes x86 / x64.
¿Por qué no usar esto?
#include <cmath>
auto floor_(float const x) noexcept
{
int const t(x);
return t - (t > x);
}
Aquí hay una modificación de la excelente respuesta de Cássio Renan. Reemplaza todas las extensiones específicas del compilador con C ++ estándar y es, en teoría, portátil a cualquier compilador conforme. Además, verifica que los argumentos estén alineados correctamente en lugar de suponerlo. Optimiza al mismo código.
#include <assert.h>
#include <cmath>
#include <stddef.h>
#include <stdint.h>
#define ALIGNMENT alignof(max_align_t)
using std::floor;
// Compiled with: -std=c++17 -Wall -Wextra -Wpedantic -Wconversion -fno-trapping-math -O -march=cannonlake -mprefer-vector-width=512
void testFunction(const float in[], int32_t out[], const ptrdiff_t length)
{
static_assert(sizeof(float) == sizeof(int32_t), "");
assert((uintptr_t)(void*)in % ALIGNMENT == 0);
assert((uintptr_t)(void*)out % ALIGNMENT == 0);
assert((size_t)length % (ALIGNMENT/sizeof(int32_t)) == 0);
alignas(ALIGNMENT) const float* const input = in;
alignas(ALIGNMENT) int32_t* const output = out;
// Do the conversion
for (int i = 0; i < length; ++i) {
output[i] = static_cast<int32_t>(floor(input[i]));
}
}
Esto no se optimiza tan bien en GCC como el original, que usaba extensiones no portátiles.
El estándar de C ++ admite un especificador
alignas
, referencias a matrices alineadas y una función
std::align
que devuelve un rango alineado dentro de un búfer.
Sin embargo, ninguno de estos, hace que el compilador que he probado genere alineados en lugar de cargas y almacenes vectoriales no alineados.
Aunque
alignof(max_align_t)
es solo 16 en x86_64, y es posible definir
ALIGNMENT
como la constante 64, esto no ayuda a ningún compilador a generar un mejor código, así que opté por la portabilidad.
Lo más parecido a una forma portátil de forzar al compilador a asumir que un poitner está alineado sería utilizar los tipos de
<immintrin.h>
, que la mayoría de los compiladores admiten x86, o definir una
struct
con un especificador
alignas
.
Al marcar macros predefinidas, también puede expandir una macro a
__attribute__ ((aligned (ALIGNMENT)))
en compiladores de Linux, o
__declspec (align (ALIGNMENT))
en compiladores de Windows, y algo seguro en un compilador que no conocemos, pero GCC necesita el atributo en un
tipo
para generar realmente cargas y almacenes alineados.
Además, el ejemplo original llamó a un bulit-in para decirle a GCC que era imposible que la
length
no fuera un múltiplo de 32. Si
assert()
esto o llama a una función estándar como
abort()
, ni GCC, Clang ni ICC Hará la misma deducción.
Por lo tanto, la mayoría del código que generan manejará el caso donde la
length
no sea un múltiplo redondo agradable del ancho del vector.
Una razón probable para esto es que ninguna optimización le proporciona tanta velocidad: las instrucciones de memoria no alineadas con direcciones alineadas son rápidas en las CPU de Intel, y el código para manejar el caso en el que la
length
no es un buen número redondo es de unos pocos bytes y se ejecuta en tiempo constante
Como nota al pie, GCC puede optimizar las funciones en línea desde
<cmath>
mejor que las macros implementadas en
<math.c>
.
GCC 9.1 necesita un conjunto particular de opciones para generar el código AVX512.
De manera predeterminada, incluso con
-march=cannonlake
, preferirá vectores de 256 bits.
Necesita el
-mprefer-vector-width=512
para generar un código de 512 bits.
(Gracias a Peter Cordes por señalar esto). Sigue el bucle vectorizado con código desenrollado para convertir cualquier elemento sobrante de la matriz.
Aquí está el bucle principal vectorizado, menos un código de inicialización constante, comprobación de errores y limpieza que solo se ejecutará una vez:
.L7:
vrndscaleps zmm0, ZMMWORD PTR [rdi+rax], 1
vcvttps2dq zmm0, zmm0
vmovdqu32 ZMMWORD PTR [rsi+rax], zmm0
add rax, 64
cmp rax, rcx
jne .L7
El águila observará dos diferencias con el código generado por el programa de Cássio Renan: utiliza% zmm en lugar de% ymm registros, y almacena los resultados con un
vmovdqu32
no
vmovdqu32
lugar de un
vmovdqa64
alineado.
Clang 8.0.0 con las mismas banderas hace diferentes elecciones sobre el desenrollado de los bucles. Cada iteración opera en ocho vectores de 512 bits (es decir, 128 flotadores de precisión simple), pero el código para recoger las sobras no se desenrolla. Si quedan al menos 64 flotadores después de eso, usa otras cuatro instrucciones AVX512 para esos, y luego limpia los extras con un bucle no vectorizado.
Si compila el programa original en Clang ++, lo aceptará sin quejarse, pero no realizará las mismas optimizaciones: aún no asumirá que la
length
sea un múltiplo del ancho del vector, ni que los punteros estén alineados.
Prefiere el código AVX512 a AVX256, incluso sin
-mprefer-vector-width=512
.
test rdx, rdx
jle .LBB0_14
cmp rdx, 63
ja .LBB0_6
xor eax, eax
jmp .LBB0_13
.LBB0_6:
mov rax, rdx
and rax, -64
lea r9, [rax - 64]
mov r10, r9
shr r10, 6
add r10, 1
mov r8d, r10d
and r8d, 1
test r9, r9
je .LBB0_7
mov ecx, 1
sub rcx, r10
lea r9, [r8 + rcx]
add r9, -1
xor ecx, ecx
.LBB0_9: # =>This Inner Loop Header: Depth=1
vrndscaleps zmm0, zmmword ptr [rdi + 4*rcx], 9
vrndscaleps zmm1, zmmword ptr [rdi + 4*rcx + 64], 9
vrndscaleps zmm2, zmmword ptr [rdi + 4*rcx + 128], 9
vrndscaleps zmm3, zmmword ptr [rdi + 4*rcx + 192], 9
vcvttps2dq zmm0, zmm0
vcvttps2dq zmm1, zmm1
vcvttps2dq zmm2, zmm2
vmovups zmmword ptr [rsi + 4*rcx], zmm0
vmovups zmmword ptr [rsi + 4*rcx + 64], zmm1
vmovups zmmword ptr [rsi + 4*rcx + 128], zmm2
vcvttps2dq zmm0, zmm3
vmovups zmmword ptr [rsi + 4*rcx + 192], zmm0
vrndscaleps zmm0, zmmword ptr [rdi + 4*rcx + 256], 9
vrndscaleps zmm1, zmmword ptr [rdi + 4*rcx + 320], 9
vrndscaleps zmm2, zmmword ptr [rdi + 4*rcx + 384], 9
vrndscaleps zmm3, zmmword ptr [rdi + 4*rcx + 448], 9
vcvttps2dq zmm0, zmm0
vcvttps2dq zmm1, zmm1
vcvttps2dq zmm2, zmm2
vcvttps2dq zmm3, zmm3
vmovups zmmword ptr [rsi + 4*rcx + 256], zmm0
vmovups zmmword ptr [rsi + 4*rcx + 320], zmm1
vmovups zmmword ptr [rsi + 4*rcx + 384], zmm2
vmovups zmmword ptr [rsi + 4*rcx + 448], zmm3
sub rcx, -128
add r9, 2
jne .LBB0_9
test r8, r8
je .LBB0_12
.LBB0_11:
vrndscaleps zmm0, zmmword ptr [rdi + 4*rcx], 9
vrndscaleps zmm1, zmmword ptr [rdi + 4*rcx + 64], 9
vrndscaleps zmm2, zmmword ptr [rdi + 4*rcx + 128], 9
vrndscaleps zmm3, zmmword ptr [rdi + 4*rcx + 192], 9
vcvttps2dq zmm0, zmm0
vcvttps2dq zmm1, zmm1
vcvttps2dq zmm2, zmm2
vcvttps2dq zmm3, zmm3
vmovups zmmword ptr [rsi + 4*rcx], zmm0
vmovups zmmword ptr [rsi + 4*rcx + 64], zmm1
vmovups zmmword ptr [rsi + 4*rcx + 128], zmm2
vmovups zmmword ptr [rsi + 4*rcx + 192], zmm3
.LBB0_12:
cmp rax, rdx
je .LBB0_14
.LBB0_13: # =>This Inner Loop Header: Depth=1
vmovss xmm0, dword ptr [rdi + 4*rax] # xmm0 = mem[0],zero,zero,zero
vroundss xmm0, xmm0, xmm0, 9
vcvttss2si ecx, xmm0
mov dword ptr [rsi + 4*rax], ecx
add rax, 1
cmp rdx, rax
jne .LBB0_13
.LBB0_14:
pop rax
vzeroupper
ret
.LBB0_7:
xor ecx, ecx
test r8, r8
jne .LBB0_11
jmp .LBB0_12
ICC 19 también genera instrucciones AVX512, pero muy diferentes de
clang
.
Realiza más configuraciones con constantes mágicas, pero no desenrolla ningún bucle, sino que opera en vectores de 512 bits.
Este código también funciona en otros compiladores y arquitecturas.
(Aunque MSVC solo admite ISA hasta AVX2 y no puede auto-vectorizar el bucle). En ARM con
-march=armv8-a+simd
, por ejemplo, genera un bucle vectorizado con
frintm v0.4s, v0.4s
y
fcvtzs v0.4s, v0.4s
.
Echa un vistazo a los números mágicos . El algoritmo propuesto en la página web debería ser mucho más eficiente que el simple casting. Nunca lo he usado, pero esta es la comparación de rendimiento que ofrecen en el sitio (xs_ToInt y xs_CRoundToInt son las funciones propuestas):
Performing 10000000 times:
simple cast 2819 ms i.e. i = (long)f;
xs_ToInt 1242 ms i.e. i = xs_ToInt(f); //numerically same as above
bit-twiddle(full) 1093 ms i.e. i = BitConvertToInt(f); //rounding from Fluid
fistp 676 ms i.e. i = FISTToInt(f); //Herf, et al x86 Assembly rounding
bit-twiddle(limited) 623 ms i.e. i = FloatTo23Bits(f); //Herf, rounding only in the range (0...1]
xs_CRoundToInt 609 ms i.e. i = xs_CRoundToInt(f); //rounding with "magic" numbers
Además, el xs_ToInt se modifica aparentemente para que el rendimiento mejore:
Performing 10000000 times:
simple cast convert 3186 ms i.e. fi = (f*65536);
fistp convert 3031 ms i.e. fi = FISTToInt(f*65536);
xs_ToFix 622 ms i.e. fi = xs_Fix<16>::ToFix(f);
Breve explicación de cómo funciona el método de los ''números mágicos'':
"Básicamente, para agregar dos números de punto flotante, su procesador" alinea "los puntos decimales de los números para que pueda agregar fácilmente los bits. Esto lo hace" normalizando "los números de modo que se conserven los bits más significativos. , es decir, el número más pequeño "se normaliza" para coincidir con el más grande. Por lo tanto, el principio de la conversión del "número mágico" que usa xs_CRoundToInt () es el siguiente: agregamos un número de punto flotante lo suficientemente grande (un número que es tan grande que hay los dígitos significativos solo HACIA ARRIBA hasta el punto decimal, y ninguno después de él) al que está convirtiendo, de manera que: (a) el número se normaliza por el procesador a su equivalente entero y (b) al agregar los dos no se borra la integral bits significativos en el número que estaba intentando convertir (es decir, XX00 + 00YY = XXYY) ".
La cita está tomada de la misma página web.
Si está haciendo esto por lotes, el compilador puede autovectorizarlo, si sabe lo que está haciendo. Por ejemplo, aquí hay una pequeña implementación que autovectoriza la conversión de flotantes a enteros, en GCC:
#include <cmath>
// Compile with -O3 and -march=native to see autovectorization
__attribute__((optimize("-fno-trapping-math")))
void testFunction(float* input, int* output, int length) {
// Assume the input and output are aligned on a 32-bit boundary.
// Of course, you have to ensure this when calling testFunction, or else
// you will have problems.
input = static_cast<float*>(__builtin_assume_aligned(input, 32));
output = static_cast<int*>(__builtin_assume_aligned(output, 32));
// Also assume the length is a multiple of 32.
if (length & 31) __builtin_unreachable();
// Do the conversion
for (int i = 0; i < length; ++i) {
output[i] = floor(input[i]);
}
}
Este es el ensamblado generado para x86-64 (con instrucciones AVX512):
testFunction(float*, int*, int):
test edx, edx
jle .L5
lea ecx, [rdx-1]
xor eax, eax
.L3:
# you can see here that the conversion was vectorized
# to a vrndscaleps (that will round the float appropriately)
# and a vcvttps2dq (thal will perform the conversion)
vrndscaleps ymm0, YMMWORD PTR [rdi+rax], 1
vcvttps2dq ymm0, ymm0
vmovdqa64 YMMWORD PTR [rsi+rax], ymm0
add rax, 32
cmp rax, rdx
jne .L3
vzeroupper
.L5:
ret
Si su objetivo no es compatible con AVX512, aún se autovectorizará utilizando las instrucciones SSE4.1, asumiendo que las tiene.
Esta es la salida con
-O3 -msse4.1
:
testFunction(float*, int*, int):
test edx, edx
jle .L1
shr edx, 2
xor eax, eax
sal rdx, 4
.L3:
roundps xmm0, XMMWORD PTR [rdi+rax], 1
cvttps2dq xmm0, xmm0
movaps XMMWORD PTR [rsi+rax], xmm0
add rax, 16
cmp rax, rdx
jne .L3
.L1:
ret