c++ - convertidor - convertir c en asm

Comparación ''correcta'' de enteros sin signo

Question

Entonces, todos sabemos las reglas de comparación firmadas / no firmadas de C / C ++ donde -1 > 2u == true , y tengo una situación en la que deseo implementar comparaciones ''correctas'' de manera eficiente.

Mi pregunta es, que es más eficiente con consideraciones para tantas arquitecturas como las personas estén familiarizadas. Obviamente Intel y ARM tienen mayor peso.

Dado:

int x;
unsigned int y;
if (x < y) {}

¿Es mejor promocionar?

x < y  =>  (int64)x < (int64)y

o es mejor realizar 2 comparaciones, es decir:

x < y  =>  (x < 0 || x < y)

El primero implica una rama de extensión cero, extensión de señal y una rama de comparación +, y la última no requiere operaciones de extensión de señal, sino 2 ramas cmp + consecutivas.
La sabiduría tradicional sugiere que las ramas son más costosas que el signo se extiende, que ambas tenderán a la deriva, pero hay un bloqueo entre las extensiones y la comparación única en el primer caso, mientras que en el segundo caso puedo imaginar que algunas arquitecturas canalizarán las 2 comparaciones , pero luego seguido de 2 ramas condicionales?

Existe otro caso, donde el valor sin signo es un tipo más pequeño que el tipo con signo, lo que significa que se puede hacer con un solo extender cero a la longitud del tipo firmado, y luego una comparación única ... en ese caso, ¿es preferible? para usar la versión extend + cmp, o es el método de comparación 2 aún preferido?

Intel? ¿BRAZO? ¿Otros? No estoy seguro de si hay una respuesta correcta aquí, pero me gustaría escuchar que la gente tome. El rendimiento de bajo nivel es difícil de predecir en estos días, especialmente en Intel y cada vez más en ARM.

Editar:

Debo agregar, hay una resolución obvia, donde los tipos tienen el mismo tamaño que la arquitectura int ancho; en ese caso, es obvio que se prefiere la solución de comparación 2, ya que la promoción en sí misma no se puede realizar de manera eficiente. Claramente, mi ejemplo int cumple con esta condición para las arquitecturas de 32 bits, y puede transponer el experimento mental a short para el ejercicio aplicado a las plataformas de 32 bits.

Editar 2:

Lo siento, ¡me olvidé de u en -1 > 2u ! > _ <

Editar 3:

Quiero enmendar la situación para suponer que el resultado de la comparación es una rama real, y el resultado NO se devuelve como un booleano. Así es como preferiría el aspecto estructural; aunque esto plantea un punto interesante de que existe otro conjunto de permutaciones cuando el resultado es un bool vs una rama.

int g;
void fun(int x, unsigned in y) { if((long long)x < (long long)y) g = 10; }
void gun(int x, unsigned in y) { if(x < 0 || x < y) g = 10; }

Esto produce la rama deseada típicamente implícita cuando encuentras un if ;)

Answer 1

Bueno, ha tipificado correctamente la situación: C / C ++ no tiene forma de hacer una comparación int total firmada / sin firmar con una sola comparación.

Me sorprendería si la promoción a int64 fuera más rápida que haciendo dos comparaciones. En mi experiencia, los compiladores son bastante buenos al darse cuenta de que una subexpresión como esa es pura (no tiene efectos secundarios) y, por lo tanto, no hay necesidad de una segunda rama. (También puede optar por desconectarse de cortocircuito utilizando bitwise o: (x < 0) | (x < y) .) En contraste, mi experiencia es que los compiladores tienden a NO hacer mucha optimización de casos especiales en enteros mayores que el tamaño de la palabra nativa, por lo que (int64)x < (int64)y es bastante probable que haga una comparación int completa.

En pocas palabras, no hay encantamiento que garantice producir el mejor código de máquina posible en cualquier procesador, pero para los compiladores más comunes en los procesadores más comunes, supongo que la forma de dos comparaciones no sería más lenta que la promoción: -int64 forma.

EDITAR: Algunos bloqueos en Godbolt confirman que en ARM32, GCC pone demasiada maquinaria en el enfoque int64. VC hace lo mismo en x86. Sin embargo, con x64, el enfoque int64 es en realidad una instrucción más corta (ya que la promoción y la comparación de 64 bits son triviales). Sin embargo, la canalización podría hacer que el rendimiento real sea de cualquier manera. https://godbolt.org/g/wyG4yC

Answer 2

Con una pequeña plantilla de jiggery-pokery, creo que podemos obtener el resultado óptimo en todos los escenarios de forma automática:

#include<iostream>
#include<cassert>


template<class T> auto make_unsigned(T i) -> T { return i; }

auto make_unsigned(int i) -> unsigned int {
    assert(i >= 0);
    return static_cast<unsigned int>(i);
}

auto make_unsigned(short i) -> unsigned short {
    assert(i >= 0);
    return static_cast<unsigned short>(i);
}

auto make_unsigned(long long i) -> unsigned long long {
    assert(i >= 0);
    return static_cast<unsigned long long>(i);
}

template<
        class I1,
        class I2,
        std::enable_if_t<(std::is_signed<I1>::value and std::is_signed<I2>::value)
                         or (not std::is_signed<I1>::value and not std::is_signed<I2>::value)>* = nullptr
>
bool unsigned_less(I1 i1, I2 i2) {

    return i1 < i2;
};

template<
        class I1,
        class I2,
        std::enable_if_t<std::is_signed<I1>::value and not std::is_signed<I2>::value>* = nullptr
>
bool unsigned_less(I1 i1, I2 i2) {

    return (i1 < 0) or make_unsigned(i1) < i2;
};

template<
        class I1,
        class I2,
        std::enable_if_t<not std::is_signed<I1>::value and std::is_signed<I2>::value>* = nullptr
>
bool unsigned_less(I1 i1, I2 i2) {

    return not (i2 < 0) and i1 < make_unsigned(i2);
};



int main() {

    short a = 1;
    unsigned int b = 2;

    std::cout << unsigned_less(a, b) << std::endl;

    using uint = unsigned int;
    using ushort = unsigned short;
    std::cout << unsigned_less(ushort(1), int(3)) << std::endl;

    std::cout << unsigned_less(int(-1), uint(0)) << std::endl;
    std::cout << unsigned_less(int(1), uint(0)) << std::endl;

    return 0;
}

Answer 3

Dada la configuración específica que presentó:

int x;
unsigned int y;

y su intento aparente de evaluar si el valor de x es numéricamente menor que el de y , respetando el signo de x , me inclinaría a escribirlo como

if ((x < 0) || (x < y)) {}

es decir, tu segunda alternativa. Expresa el intento claramente, y es extensible a tipos más amplios, siempre que el valor máximo representable del tipo de y sea al menos tan grande como el valor máximo representable del tipo de x . Por lo tanto, si está dispuesto a estipular que los argumentos tendrán esa forma, entonces podría incluso escribirlo como - evite sus ojos, adherentes de C ++ - una macro.

La conversión de ambos argumentos en un tipo entero de 64 bits firmado no es una solución portátil, porque no hay garantía de que sea una promoción de int o unsigned int . Tampoco es extensible a tipos más amplios.

En cuanto al rendimiento relativo de sus dos alternativas, dudo que haya mucha diferencia, pero si le importa, entonces querrá escribir un punto de referencia cuidadoso. Podría imaginarme la alternativa portátil que requiere una instrucción de máquina más que la otra, y también puedo imaginar que requiera una menos. Solo si tales comparaciones dominan el rendimiento de su aplicación, una instrucción única haría una diferencia notable en un sentido u otro.

Por supuesto, esto es específico de la situación que presentaste. Si desea manejar comparaciones combinadas con signo / sin signo en cualquier orden, para muchos tipos diferentes, como resuelto en tiempo de compilación, un contenedor basado en plantilla podría ayudarle con eso (y eso dejaría de lado la cuestión de usar una macro), pero lo tomo para que pregunte específicamente sobre los detalles de la comparación en sí.

Answer 4

Eche un vistazo a la presentación de Andrei Alexandrescus en la reciente conferencia D en Berlín sobre Diseño por introspección.

En él, muestra cómo diseñar una clase int marcada en el momento del diseño y una de las características que se le ocurre es exactamente esto: cómo comparar firmado y sin firmar.

Básicamente, necesitas realizar 2 comparaciones

If (signed_var <0) luego return unsigned_var else promueve / lanza signed_var a unsigned_var y luego compara

Answer 5

La versión de dos ramas sería ciertamente más lenta, pero en realidad nada de eso es dos ramas ... ni una sola rama ... en x86.

Por ejemplo x86 gcc 7.1 will para fuente C ++:

bool compare(int x, unsigned int y) {
    return (x < y); // "wrong" (will emit warning)
}

bool compare2(int x, unsigned int y) {
    return (x < 0 || static_cast<unsigned int>(x) < y);
}

bool compare3(int x, unsigned int y) {
    return static_cast<long long>(x) < static_cast<long long>(y);
}

Produzca este ensamblaje ( demo en vivo de godbolt ):

compare(int, unsigned int):
        cmp     edi, esi
        setb    al
        ret

compare2(int, unsigned int):
        mov     edx, edi
        shr     edx, 31
        cmp     edi, esi
        setb    al
        or      eax, edx
        ret

compare3(int, unsigned int):
        movsx   rdi, edi
        mov     esi, esi
        cmp     rdi, rsi
        setl    al
        ret

Y si intentas usar estos dentro de un código más complejo, se incluirán en el 99% de los casos. Sin perfilar es solo adivinar, pero "por instinto" iría con compare3 como "más rápido", especialmente cuando se ejecuta fuera de orden dentro de algún código (algo gracioso hace la correcta promoción de 32-> 64 incluso para el argumento uint, mientras requeriría bastante esfuerzo producir llamadas codificadas que se comparen con algún desorden en la parte superior 32b de esi ... pero probablemente se deshaga de él cuando se incluya en un cálculo más complejo, donde notaría que el argumento también ya no se extiende, entonces la compare3 es aún más simple + más corta).

... como dije en el comentario, no llego a las tareas donde lo necesitaría, por ejemplo, no puedo imaginar trabajar en algo donde el rango válido de datos es desconocido, entonces para la tarea que trabajo en la C / C ++ es perfecto y aprecio exactamente la forma en que funciona (que < para tipos firmados vs no firmados está bien definido y da como resultado el código más corto / más rápido, además se emite una advertencia para que yo sea el programador responsable de validarlo, y en caso de necesita cambiar la fuente apropiadamente).

Answer 6

Tienes que juzgar esto caso por caso. Existen varios motivos por los cuales se usarán tipos firmados en un programa:

1. Porque realmente necesita tener números negativos en los cálculos o resultados.
2. "Mecanografía descuidada", lo que significa que el programador simplemente teclea int todo su programa sin pensarlo mucho.
3. Accidentalmente firmado. El programado en realidad no quería números con signo, pero terminó con ellos por accidente, ya sea a través de promociones de tipo implícito o mediante el uso de constantes enteras como 0 , que es de tipo int .

En el caso de 1), entonces la aritmética debe llevarse a cabo con aritmética firmada. A continuación, debe convertir al tipo más pequeño posible que se necesita para contener los valores máximos esperados.

Supongamos, por ejemplo, que un valor puede tener un rango de -10000 a 10000 . Luego deberá usar un tipo firmado de 16 bits para representarlo. El tipo correcto para usar entonces, platform-independent, es int_fast16_t .

Los tipos int_fastn_t y uint_fastn_t requieren que el tipo sea al menos tan grande como n pero el compilador puede elegir un tipo más grande si proporciona un código más rápido / una mejor alineación.

2) se cura estudiando stdint.h y stdint.h de ser flojo. Como programador, uno siempre debe considerar el tamaño y la firma de cada una de las variables declaradas en el programa . Esto tiene que hacerse en el momento de la declaración. O si obtiene algún tipo de revelación más tarde, regrese y cambie el tipo.

Si no considera los tipos con cuidado, con absoluta certeza terminará escribiendo numerosos errores, a menudo sutiles. Esto es particularmente importante en C ++, que es más exigente con la corrección de tipos que C.

Cuando se utiliza "tipeo descuidado", el tipo real previsto generalmente no está firmado en lugar de firmado. Considere este ejemplo de tipeo descuidado:

for(int i=0; i<n; i++)

No tiene ningún sentido utilizar int registrado aquí, ¿por qué lo harías? Lo más probable es que esté iterando sobre una matriz o contenedor y luego el tipo correcto para usar es size_t .

O bien, si conoce el tamaño máximo que puede contener n , por ejemplo 100, puede usar el tipo más adecuado para eso:

for(uint_fast8_t i=0; i<100; i++)

3) también se cura estudiando. En particular, las diversas reglas para las promociones implícitas que existen en estos idiomas, como las conversiones aritméticas habituales y la promoción de enteros .

Answer 7

Un truco portátil que puede hacer es verificar si puede ampliar ambos argumentos a intmax_t desde <stdint.h> , que es el tipo integral más amplio que admite una implementación. Puede verificar (sizeof(intmax_t) > sizeof(x) && sizeof(intmax_t) >= sizeof(y)) y, si es así, hacer una conversión de ampliación. Esto funciona en el caso muy común donde int tiene 32 bits de ancho y long long int tiene 64 bits de ancho.

En C ++, puede hacer cosas inteligentes donde tiene una plantilla de comparación segura que comprueba std::numeric_limits<T> en sus argumentos. Aquí hay una versión. (Compila con -Wno-sign-compare en gcc o clang!)

#include <cassert>
#include <cstdint>
#include <limits>

using std::intmax_t;
using std::uintmax_t;

template<typename T, typename U>
  inline bool safe_gt( T x, U y ) {
    constexpr auto tinfo = std::numeric_limits<T>();
    constexpr auto uinfo = std::numeric_limits<U>();
    constexpr auto maxinfo = std::numeric_limits<intmax_t>();

    static_assert(tinfo.is_integer, "");
    static_assert(uinfo.is_integer, "");

    if ( tinfo.is_signed == uinfo.is_signed )
      return x > y;
    else if ( maxinfo.max() >= tinfo.max() &&
              maxinfo.max() >= uinfo.max() )
      return static_cast<intmax_t>(x) > static_cast<intmax_t>(y);
    else if (tinfo.is_signed) // x is signed, y unsigned.
      return x > 0 && x > y;
    else // y is signed, x unsigned.
      return y < 0 || x > y;      
  }

int main()
{
  assert(-2 > 1U);
  assert(!safe_gt(-2, 1U));
  assert(safe_gt(1U, -2));
  assert(safe_gt(1UL, -2L));
  assert(safe_gt(1ULL, -2LL));
  assert(safe_gt(1ULL, -2));
}

Se podría conocer el punto flotante cambiando dos líneas.