c++ - ¿Puedo insinuar el optimizador dando el rango de un entero?

gcc flags

Question

Estoy usando un tipo int para almacenar un valor. Según la semántica del programa, el valor siempre varía en un rango muy pequeño (0 - 36), y int (no un char ) se usa solo debido a la eficiencia de la CPU.

Parece que muchas optimizaciones aritméticas especiales se pueden realizar en un rango tan pequeño de enteros. Muchas llamadas de función en esos enteros pueden optimizarse en un pequeño conjunto de operaciones "mágicas", y algunas funciones pueden incluso optimizarse en búsquedas de tablas.

Entonces, ¿es posible decirle al compilador que este int siempre está en ese rango pequeño, y es posible que el compilador haga esas optimizaciones?

Answer 1

Hay soporte estándar para esto. Lo que debe hacer es incluir stdint.h ( cstdint ) y luego usar el tipo uint_fast8_t .

Esto le dice al compilador que solo está usando números entre 0 y 255, pero que es libre de usar un tipo más grande si eso proporciona un código más rápido. Del mismo modo, el compilador puede suponer que la variable nunca tendrá un valor superior a 255 y luego realizar optimizaciones en consecuencia.

Answer 2

La respuesta actual es buena para el caso cuando sabe con certeza cuál es el rango, pero si aún desea un comportamiento correcto cuando el valor está fuera del rango esperado, entonces no funcionará.

Para ese caso, descubrí que esta técnica puede funcionar:

if (x == c)  // assume c is a constant
{
    foo(x);
}
else
{
    foo(x);
}

La idea es una compensación de datos de código: está moviendo 1 bit de datos (ya sea x == c ) a la lógica de control .
Esto sugiere al optimizador que x es, de hecho, una constante c conocida, lo que lo alienta a alinear y optimizar la primera invocación de foo separado del resto, posiblemente en gran medida.

Sin embargo, asegúrese de factorizar el código en una sola subrutina, no duplique el código.

Ejemplo:

Para que esta técnica funcione, debe ser un poco afortunado: hay casos en los que el compilador decide no evaluar las cosas estáticamente, y son algo arbitrarios. Pero cuando funciona, funciona bien:

#include <math.h>
#include <stdio.h>

unsigned foo(unsigned x)
{
    return x * (x + 1);
}

unsigned bar(unsigned x) { return foo(x + 1) + foo(2 * x); }

int main()
{
    unsigned x;
    scanf("%u", &x);
    unsigned r;
    if (x == 1)
    {
        r = bar(bar(x));
    }
    else if (x == 0)
    {
        r = bar(bar(x));
    }
    else
    {
        r = bar(x + 1);
    }
    printf("%#x/n", r);
}

Simplemente use -O3 y observe las constantes 0x30e 0x20 y 0x30e en la salida del ensamblador .

Answer 3

Sí, es posible. Por ejemplo, para gcc puede usar __builtin_unreachable para decirle al compilador sobre condiciones imposibles, de esta manera:

if (value < 0 || value > 36) __builtin_unreachable();

Podemos envolver la condición anterior en una macro:

#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)

Y úsalo así:

assume(x >= 0 && x <= 10);

Como puede ver , gcc realiza optimizaciones basadas en esta información:

#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)

int func(int x){
    assume(x >=0 && x <= 10);

    if (x > 11){
        return 2;
    }
    else{
        return 17;
    }
}

Produce:

func(int):
    mov     eax, 17
    ret

Sin embargo, una desventaja es que si su código alguna vez rompe tales suposiciones, obtendrá un comportamiento indefinido .

No le notifica cuando esto sucede, incluso en las versiones de depuración. Para depurar / probar / detectar errores con suposiciones más fácilmente, puede usar una macro híbrida de asumir / afirmar (créditos a @David Z), como esta:

#if defined(NDEBUG)
#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)
#else
#include <cassert>
#define assume(cond) assert(cond)
#endif

En las compilaciones de depuración (con NDEBUG no definido), funciona como una NDEBUG ordinaria, imprime un mensaje de error y abort el programa, y ​​en las compilaciones de lanzamiento utiliza una suposición, produciendo código optimizado.

Tenga en cuenta, sin embargo, que no es un sustituto de la assert regular; las condiciones permanecen en las versiones de lanzamiento, por lo que no debe hacer algo como assume(VeryExpensiveComputation()) .

Answer 4

Solo estoy diciendo que si quieres una solución que sea más estándar en C ++, puedes usar el atributo [[noreturn]] para escribir tu propia unreachable .

Así que volveré a utilizar el excelente ejemplo de Deniss para demostrar:

namespace detail {
    [[noreturn]] void unreachable(){}
}

#define assume(cond) do { if (!(cond)) detail::unreachable(); } while (0)

int func(int x){
    assume(x >=0 && x <= 10);

    if (x > 11){
        return 2;
    }
    else{
        return 17;
    }
}

Lo que, como puede ver , da como resultado un código casi idéntico:

detail::unreachable():
        rep ret
func(int):
        movl    $17, %eax
        ret

La desventaja es, por supuesto, que recibe una advertencia de que una función [[noreturn]] , de hecho, regresa.