rendimiento - ¿Conversión de enteros saturada y rápida?

CorePress2024-01-25  251

Me pregunto si hay algún truco rápido para hacer una conversión saturada de un valor sin signo de 64 bits a un valor sin signo de 32 bits (sería bueno si se generalizara a otros anchos, pero ese es el principal ancho que me importa). La mayoría de los recursos que he podido encontrar buscando en Google han sido para saturar operaciones aritméticas.

Una conversión de saturación tomaría un valor sin signo de 64 bits y devolvería el valor sin modificar como un valor de 32 bits o 2^32-1 si el valor de entrada es mayor que 2^32-1. Tenga en cuenta que esto no es lo que hace el comportamiento de truncamiento de conversión de C predeterminado.

Me imagino haciendo algo como:

Pruebe si la mitad superior tiene algún bit configurado Si es así, cree una máscara de 32 bits con todos los bits configurados; de lo contrario, cree una máscara con todos los bits sin configurar. Bit a bit o bajoes la mitad con máscara

Pero no sé cómo generar rápidamente la máscara. Probé implementaciones de ramificación sencillas en Godbolt para ver si el compilador generaba una implementación inteligente sin ramificaciones, pero no tuve suerte.

Ejemplo de implementación aquí.

#include <stdint.h>
#include <limits.h>

// Type your code here, or load an example.
uint32_t square(uint64_t num) {
    return num > UINT32_MAX ? UINT32_MAX : num;
}

Editar: mi error, el problema fue que Godbolt no estaba configurado para usar optimizaciones

@trentcl ambos están compilados con AOT y admiten operaciones bit a bit, una solución para uno se puede convertir trivialmente al otro

- Joseph Garvin

28/03/2021 a las 17:58

Si hola son los 32 bits altos y lo los 32 bits bajos, ¿tal vez máscara = hola? ~lo : 0; lo ^= máscara; podría compilarse sin ramas

- dmuir

28/03/2021 a las 18:00

@KamilCuk editado para incluir

- Joseph Garvin

28/03/2021 a las 18:03

@JosephGarvin Con respecto al enlace de godbolt: debes habilitar la optimización del compilador para que el compilador genere código óptimo.

-G. deslizarse

28/03/2021 a las 18:03



------------------------------------

No necesitas hacer ningún truco sofisticado para hacer esto. La siguiente función debería ser suficiente para que los compiladores generen código eficiente:

uint32_t saturate(uint64_t value) {
    return value > UINT32_MAX ? UINT32_MAX : value;
}

Esto contiene una declaración condicional, pero las CPU más comunes, como las de AMD/Intel y Arm, tienen instrucciones de movimiento condicionales. Entonces probarán el valor para detectar 32 bits desbordados y, según la prueba, lo reemplazarán con UINT32_.MAX, de lo contrario déjelo en paz. Por ejemplo, en procesadores Arm de 64 bits esta función será compilada por GCC (para:

saturate:
  mov x1, 4294967295
  cmp x0, x1
  csel x0, x0, x1, ls
  ret

Tenga en cuenta que debe habilitar las optimizaciones del compilador para obtener el resultado anterior.

2

Hmm, clang no parece ser lo suficientemente inteligente: godbolt.org/z/81oz1PYzd

- Joseph Garvin

28/03/2021 a las 18:03

Error mío, Godbolt no estaba configurado para tener opciones habilitadas

- Joseph Garvin

28/03/2021 a las 18:06



------------------------------------

Una forma de hacer esto sin depender de movimientos condicionales es

((-(x >> 32)) | (x << 32)) >> 32

Su guía para un futuro mejor - libreflare
Su guía para un futuro mejor - libreflare