Lecciones generales derivadas de aumentar 7 veces la ingesta de datos en la caja de fuego de rango
Gracias a Ben Lichtman (B3NNY) en Seattle Rust Meetup por indicarme la dirección correcta sobre SIMD.
Esta es la Parte 2 de un artículo sobre la creación de código SIMD en Rust. (Ver Parte 1.) Veremos las reglas 7 a 9:
- 7. Utilice la evaluación comparativa de criterios para elegir un algoritmo y descubrir que LANES debería (casi) siempre ser 32 o 64.
- 8. Integre su mejor algoritmo SIMD en su proyecto con as_simd, código especial para i128/u128 y evaluaciones comparativas adicionales en contexto.
- 9. Saque su mejor algoritmo SIMD de su proyecto (por ahora) con una función de carga opcional.
Recuerde las reglas 1 a 6:
- Utilice Rust y core::simd todas las noches, el módulo SIMD estándar experimental de Rust.
- CCC: verifique, controle y elija las capacidades SIMD de su computadora.
- Aprenda core::simd, pero de forma selectiva.
- Lluvia de ideas sobre algoritmos candidatos.
- Utilice Godbolt y AI para comprender el ensamblador de su código, incluso si no conoce el lenguaje ensamblador.
- Generalice a todos los tipos y LANES con genéricos en línea, (y cuando eso no funcione) macros y (cuando eso no funcione) rasgos.
Estas reglas se basan en mi experiencia al intentar acelerar alcance-prendido-incendiouna caja de Rust para manipular conjuntos de números enteros “grumosos”.
Recordemos que la Regla 6, de Parte 1, muestra cómo hacer que los algoritmos Rust SIMD sean completamente genéricos en todos los tipos y LANES. Lo siguiente que debemos hacer es elegir nuestro algoritmo y configurar LANES.
Regla 7: utilice la evaluación comparativa de criterios para elegir un algoritmo y descubrir que LANES debería (casi) siempre ser 32 o 64.
En esta regla veremos cómo utilizar el popular criterio crate para comparar y evaluar nuestros algoritmos y opciones. En el contexto de range-set-blaze, evaluaremos:
- 5 algoritmos: Regular, Splat0, Splat1, Splat2, Rotar
- 3 niveles de extensión SIMD: sse2 (128 bits), avx2 (256 bits), avx512f (512 bits)
- 10 tipos de elementos: i8, u8, i16, u16, i32, u32, i64, u64, isize, usize
- 5 números de carril: 4, 8, 16, 32, 64
- 4 longitudes de entrada: 1024; 10.240; 102.400; 1.024.000
- 2 CPU: AMD 7950X con avx512f, Intel i5–8250U con avx2
El punto de referencia mide el tiempo promedio para ejecutar cada combinación. Luego calculamos el rendimiento en Mbytes/seg.
Mira esto nuevo artículo complementario sobre cómo empezar con Criterion. Ese artículo también muestra cómo impulsar (¿abusar?) el criterio para medir los efectos de la configuración del compilador, como el nivel de extensión SIMD.
La ejecución de los puntos de referencia da como resultado un archivo *.csv de 5000 líneas que comienza:
Group,Id,Parameter,Mean(ns),StdErr(ns)
vector,regular,avx2,256,i16,16,16,1024,291.47,0.080141
vector,regular,avx2,256,i16,16,16,10240,2821.6,3.3949
vector,regular,avx2,256,i16,16,16,102400,28224,7.8341
vector,regular,avx2,256,i16,16,16,1024000,287220,67.067
vector,regular,avx2,256,i16,16,32,1024,285.89,0.59509
...
Este archivo es adecuado para el análisis mediante tablas dinámicas de hojas de cálculo o herramientas de marco de datos como Polares.
Algoritmos y carriles
Aquí hay una tabla dinámica de Excel que muestra, para cada algoritmo, el rendimiento (MBytes/seg) frente a los carriles SIMD. La tabla promedia el rendimiento entre niveles de extensión SIMD, tipos de elementos y longitud de entrada.
En mi máquina de escritorio AMD:
En una computadora portátil Intel:
Las tablas muestran que Splat1 y Splat2 obtienen los mejores resultados. También muestran que más carriles siempre es mejor hasta 32 o 64.
¿Cómo puede, por ejemplo,sse2 (128 bits de ancho) procesa 64 carriles de i64 (4096 bits de ancho)? El óxido núcleo::simd El módulo hace posible esta magia al dividir automática y eficientemente los 4096 bits en 32 fragmentos de 128 bits cada uno. Procesar los 32 fragmentos de 128 bits juntos (aparentemente) permite optimizaciones más allá del procesamiento de los fragmentos de 128 bits de forma independiente.
Niveles de extensión SIMD
Configuremos LANES en 64 y comparemos diferentes niveles de extensión SIMD en la máquina AMD. La tabla promedia el rendimiento según el tipo de elemento y la longitud de entrada.
En mi máquina AMD, cuando uso 64 carriles, sse2 es el más lento. Comparando avx2 con avx512f, los resultados son mixtos. Nuevamente, los algoritmos Splat1 y Splat2 funcionan mejor.
Tipos de elementos
A continuación, configuremos nuestro nivel de extensión SIMD en avx512f y comparemos diferentes tipos de elementos. Mantenemos LANES en 64 y un rendimiento promedio en toda la longitud de entrada.
Vemos que los elementos bit por bit, 32 bits y 64 bits se procesan más rápido. (Sin embargo, por elemento, los tipos más pequeños son más rápidos). Splat1 y Splat2 son los algoritmos más rápidos, siendo Splat1 ligeramente mejor.
Longitud de entrada
Finalmente, configuremos nuestro tipo de elemento en i32 y veamos la longitud de entrada versus el rendimiento.
Vemos que todos los algoritmos SIMD hacen aproximadamente lo mismo con 1 millón de entradas. Splat1 aparentemente funciona mejor que otros algoritmos en entradas cortas.
También parece que lo más corto es más rápido que lo largo. Esto podría ser el resultado del almacenamiento en caché o podría ser un artefacto de los puntos de referencia que desechan datos no alineados.
Conclusiones de los puntos de referencia
Según estos puntos de referencia, usaremos el algoritmo Splat1. Por ahora, configuraremos LANES en 32 o 64, pero consulte la siguiente regla para solucionar una complicación. Finalmente, aconsejaremos a los usuarios que establezcan su nivel de extensión SIMD al menos en avx2.
Regla 8: Integre su mejor algoritmo SIMD en su proyecto con as_simd, código especial para i128/u128 y evaluaciones comparativas adicionales en contexto.
as_simd
Antes de agregar soporte SIMD, el constructor principal de RangeSetBlaze era from_iter:
let a = RangeSetBlaze::from_iter([1, 2, 3]);
Sin embargo, las operaciones SIMD funcionan mejor en matrices, no en iteradores. Además, construir un RangeSetBlaze a partir de una matriz suele ser algo natural, por lo que agregué un nuevo constructor from_slice:
#[inline]
pub fn from_slice(slice: impl AsRef<[T]>) -> Self {
T::from_slice(slice)
}
El nuevo constructor realiza una llamada en línea al método from_slice de cada entero. Para todos los tipos de enteros, excepto i128/u128, lo siguiente llama:
let (prefix, middle, suffix) = slice.as_simd();
El método nocturno as_simd de Rust transmuta de forma segura y rápida el segmento en:
- un prefijo no alineado, que procesamos con from_iter, como antes.
- en el medio, una matriz alineada de fragmentos de estructura Simd
- Un sufijo no alineado, que procesamos con from_iter, como antes.
Piense en el medio como dividir nuestros números enteros de entrada en fragmentos de tamaño 16 (o cualquier tamaño en el que esté configurado LANES). Luego iteramos los fragmentos a través de nuestra función is_consecutive, buscando ejecuciones verdaderas. Cada ejecución se convierte en un rango único. Por ejemplo, una serie de 160 enteros consecutivos individuales del 1000 al 1159 (inclusive) se identificaría y reemplazaría con un único Rust RangeInclusive 1000..=1159. Luego, from_iter procesa este rango mucho más rápido de lo que from_iter habría procesado los 160 enteros individuales. Cuando is_consecutive devuelve falso, volvemos a procesar los enteros individuales del fragmento con from_iter.
i128/u128
¿Cómo manejamos matrices de tipos que core::simd no maneja, es decir, i128/u128? Por ahora, simplemente los proceso con el from_iter más lento.
Puntos de referencia en contexto
Como paso final, compare su código SIMD en el contexto de su código principal, idealmente con datos representativos.
La caja de fuego de rango ya incluye puntos de referencia. Un punto de referencia mide el rendimiento al ingerir 1.000.000 de números enteros con varios niveles de aglomeración. El tamaño promedio de los grupos varía de 1 (sin grupos) a 100.000 grupos. Ejecutemos ese punto de referencia con LANES configurado en 4, 8, 16, 32 y 64. Usaremos el algoritmo Splat1 y el nivel de extensión SIMD avx512f.
Para cada tamaño de grupo, las barras muestran la velocidad relativa de ingerir 1.000.000 de números enteros. Para cada tamaño de grupo, los LANES más rápidos se establecen en 100%.
Vemos que para grupos de tamaño 10 y 100, LANES=4 es lo mejor. Sin embargo, con grupos de tamaño 100.000, LANES=4 es 4 veces peor que el mejor. En el otro extremo, LANES=64 se ve bien con grupos de tamaño 100.000, pero es 1,8 y 1,5 veces peor que el mejor en 100 y 1000, respectivamente.
Decidí configurar LANES en 16. Es el mejor para grupos de tamaño 1000. Además, nunca es más de 1,25 veces peor que el mejor.
Con esta configuración, podemos ejecutar otros puntos de referencia. El siguiente cuadro muestra varias bibliotecas de conjuntos de rangos (incluida range-set-blaze) que trabajan en la misma tarea: ingerir 1.000.000 de números enteros de distintos grados de grumos. El eje y es milisegundos y cuanto menor es mejor.
Con grupos de tamaño 1000, el método RangeSetBlaze::into_iter (rojo) existente ya era 30 veces más rápido que HashSet (naranja). Tenga en cuenta que la escala es logarítmica. Con avx512f, el nuevo algoritmo RangeSetBlaze::into_slice (azul claro) con tecnología SIMD es 230 veces más rápido que HashSet. Con sse2 (azul oscuro), es 220 veces más rápido. Con avx2 (amarillo), es 180 veces más rápido. En este punto de referencia, en comparación con RangeSetBlaze::into_iter, avx512f RangeSetBlaze::into_slice es 7 veces más rápido.
También deberíamos considerar el peor de los casos, es decir, la ingesta de datos sin grupos. Ejecuté ese punto de referencia. Mostró que el RangeSetBlaze::into_iter existente es aproximadamente 2,2 veces más lento que HashSet. El nuevo RangeSetBlaze::into_slice es 2,4 veces más lento que HashSet.
Entonces, en definitiva, el nuevo código SIMD ofrece una gran ventaja para los datos que se supone que están agrupados. Si la suposición es errónea, será más lento, pero no de manera catastrófica.
Con el código SIMD integrado en nuestro proyecto, estamos listos para realizar el envío, ¿verdad? Tristemente no. Debido a que nuestro código depende de Rust todas las noches, deberíamos hacerlo opcional. Veremos cómo hacerlo en la siguiente regla.
Regla 9: Extraiga su mejor algoritmo SIMD de su proyecto (por ahora) con una función de carga opcional.
Nuestro nuevo y hermoso código SIMD depende de Rust todas las noches, que puede cambiar y de hecho cambia todas las noches. Exigir a los usuarios que dependan de Rust todas las noches sería cruel. (Además, recibir quejas cuando algo se estropea sería molesto). La solución es ocultar el código SIMD detrás de una función de carga.
Característica, característica, característica: en el contexto de trabajar con SIMD y Rust, la palabra “función” se usa de tres maneras diferentes. Primero, “CPU/características de destino”: describen las capacidades de una CPU, incluidas las extensiones SIMD que admite. Ver característica-objetivo y is_x86_feature_detected!. En segundo lugar, “puertas de funciones nocturnas”: Rust controla la visibilidad de las nuevas funciones del lenguaje en Rust todas las noches con puertas de características. Por ejemplo, #![feature(portable_simd)]. Tercero, “características de carga”: permiten que cualquier caja o biblioteca de Rust ofrezca/limite el acceso a parte de sus capacidades. Los ves en tu carga.toml cuando, por ejemplo, agrega una dependencia a itertools/use_std.
Estos son los pasos que sigue la caja de encendido de rango para hacer que el código SIMD dependiente de la noche sea opcional:
- En Cargo.toml, defina una característica de carga relacionada con el código SIMD:
[features]
from_slice = []
- En el archivo lib.rs superior, haga que la puerta de funciones nightly portable_simd dependa de la función from_slice y cargo:
#![cfg_attr(feature = "from_slice", feature(portable_simd))]
- Utilice el atributo de compilación condicional, por ejemplo, #[cfg(feature = “from_slice”)], para incluir el código SIMD de forma selectiva. Esto incluye pruebas.
/// Creates a [`RangeSetBlaze`] from a collection of integers. It is typically many
/// times faster than [`from_iter`][1]/[`collect`][1].
/// On a representative benchmark, the speed up was 6×.
///
/// **Warning: Requires the nightly compiler. Also, you must enable the `from_slice`
/// feature in your `Cargo.toml`. For example, with the command:**
/// ```bash
/// cargo add range-set-blaze --features "from_slice"
/// ```
///
/// **Caution**: Compiling with `-C target-cpu=native` optimizes the binary for your current CPU architecture,
/// which may lead to compatibility issues on other machines with different architectures.
/// This is particularly important for distributing the binary or running it in varied environments.
/// [1]: struct.RangeSetBlaze.html#impl-FromIterator<T>-for-RangeSetBlaze<T>
#[cfg(feature = "from_slice")]
#[inline]
pub fn from_slice(slice: impl AsRef<[T]>) -> Self {
T::from_slice(slice)
}
- Como se muestra en los documentos anteriores, agregue advertencias y precauciones a la documentación.
- Utilice –features from_slice para verificar o probar su código SIMD.
cargo check --features from_slice
cargo test --features from_slice
- Utilice –all-features para ejecutar todas las pruebas, generar toda la documentación y publicar todas las funciones de carga:
cargo test --all-features --doc
cargo doc --no-deps --all-features --open
cargo publish --all-features --dry-run
Conclusión
Ahí lo tienes: nueve reglas para agregar operaciones SIMD a tu código Rust. La facilidad de este proceso refleja el excelente diseño de la biblioteca core::simd. ¿Debería utilizar siempre SIMD cuando corresponda? Con el tiempo, sí, cuando la biblioteca pase de Rust todas las noches al establo. Por ahora, utilice SIMD cuando sus beneficios de rendimiento sean cruciales, o haga que su uso sea opcional.
¿Ideas para mejorar la experiencia SIMD en Rust? La calidad de core::simd ya es alta; la principal necesidad es estabilizarlo.
Gracias por acompañarme en este viaje hacia la programación SIMD. Espero que si tienes un problema relacionado con SIMD, estos pasos te ayuden a acelerarlo.
Por favor sigue a Carl en Medium. Escribo sobre programación científica en Rust y Python, aprendizaje automático y estadística. Tiendo a escribir alrededor de un artículo por mes.
Nueve reglas para la aceleración SIMD de su código Rust (Parte 2) fue publicado originalmente en Hacia la ciencia de datos en Medium, donde las personas continúan la conversación resaltando y respondiendo a esta historia.