¿Puedo cambiar esta macro a una función en línea sin un golpe de rendimiento?

Question

(EDIT:. El título de dejar que esto, "Lecciones de cómo las medidas pueden ir mal" Todavía no he descubierto exactamente lo que está causando la discrepancia aunque)

me encontré con un número entero muy rápido función de raíz cuadrada here por Mark Crowne. Al menos con GCC en mi máquina, es claramente la función de raíz cuadrada entera más rápida que he probado (incluidas las funciones en Hacker's Delight, this page y floor (sqrt()) de la biblioteca estándar).

Después de limpiar el formato un poco, cambiar el nombre de una variable, y el uso de tipos de ancho fijo, que se ve así:

static uint32_t mcrowne_isqrt(uint32_t val) 
{ 
    uint32_t temp, root = 0; 

    if (val >= 0x40000000) 
    { 
     root = 0x8000; 
     val -= 0x40000000; 
    } 

    #define INNER_ISQRT(s)        \ 
    do             \ 
    {             \ 
     temp = (root << (s)) + (1 << ((s) * 2 - 2)); \ 
     if (val >= temp)        \ 
     {            \ 
      root += 1 << ((s)-1);      \ 
      val -= temp;        \ 
     }            \ 
    } while(0) 

    INNER_ISQRT(15); 
    INNER_ISQRT(14); 
    INNER_ISQRT(13); 
    INNER_ISQRT(12); 
    INNER_ISQRT(11); 
    INNER_ISQRT(10); 
    INNER_ISQRT(9); 
    INNER_ISQRT(8); 
    INNER_ISQRT(7); 
    INNER_ISQRT(6); 
    INNER_ISQRT(5); 
    INNER_ISQRT(4); 
    INNER_ISQRT(3); 
    INNER_ISQRT(2); 

    #undef INNER_ISQRT 

    temp = root + root + 1; 
    if (val >= temp) 
     root++; 
    return root; 
} 

La macro INNER_ISQRT no está demasiado mal, ya que es local y de inmediato indefinido después de que ya no sea necesario. Sin embargo, me gustaría convertirlo en una función en línea por cuestión de principios. He leído afirmaciones en varios lugares (incluida la documentación de GCC) de que las funciones en línea son "tan rápidas" como las macros, pero he tenido problemas para convertirlas sin un golpe de velocidad.

Mi iteración actual es el siguiente (tenga en cuenta el atributo always_inline, que me tiró en una buena medida):

static inline void inner_isqrt(const uint32_t s, uint32_t& val, uint32_t& root) __attribute__((always_inline)); 
static inline void inner_isqrt(const uint32_t s, uint32_t& val, uint32_t& root) 
{ 
    const uint32_t temp = (root << s) + (1 << ((s << 1) - 2)); 
    if(val >= temp) 
    { 
     root += 1 << (s - 1); 
     val -= temp; 
    } 
} 

// Note that I just now changed the name to mcrowne_inline_isqrt, so people can compile my full test. 
static uint32_t mcrowne_inline_isqrt(uint32_t val) 
{ 
    uint32_t root = 0; 

    if(val >= 0x40000000) 
    { 
     root = 0x8000; 
     val -= 0x40000000; 
    } 

    inner_isqrt(15, val, root); 
    inner_isqrt(14, val, root); 
    inner_isqrt(13, val, root); 
    inner_isqrt(12, val, root); 
    inner_isqrt(11, val, root); 
    inner_isqrt(10, val, root); 
    inner_isqrt(9, val, root); 
    inner_isqrt(8, val, root); 
    inner_isqrt(7, val, root); 
    inner_isqrt(6, val, root); 
    inner_isqrt(5, val, root); 
    inner_isqrt(4, val, root); 
    inner_isqrt(3, val, root); 
    inner_isqrt(2, val, root); 

    const uint32_t temp = root + root + 1; 
    if (val >= temp) 
     root++; 
    return root; 
} 

No importa lo que haga, la función en línea es siempre más lento que la macro. La versión de macros suele durar alrededor de 2.92s para (2^28 - 1) iteraciones con una compilación -O2, mientras que la versión en línea suele ser de alrededor de 3.25 segundos. EDIT: dije 2^32 - 1 iteraciones antes, pero olvidé que lo había cambiado. Tardan bastante más para la gama completa.

Es posible que el compilador esté siendo estúpido y se niegue a alinearlo (¡tenga en cuenta una vez más el atributo always_inline!), Pero de ser así, la versión en general sería preferible de todos modos. (Intenté comprobar el ensamblaje para verlo, pero era demasiado complicado como parte de un programa. El optimizador omitió todo cuando traté de compilar solo las funciones, por supuesto, y tengo problemas para compilarlo como biblioteca debido a la falta de compatibilidad con GCC .)

En resumen, ¿hay alguna manera de escribir esto como en línea sin un golpe de velocidad? (No he hecho un perfil, pero sqrt es una de esas operaciones fundamentales que siempre se debe hacer rápido, ya que puedo usarlo en muchos otros programas aparte del que estoy interesado. Además, solo tengo curiosidad .)

Incluso he intentado usar plantillas para "hornear" el valor constante, pero tengo la sensación de que los otros dos parámetros son más propensos a causar el golpe (y la macro puede evitar eso, ya que utiliza variables locales directamente) ... bueno, o eso o el compilador se niega obstinadamente a alinearse.

---

ACTUALIZACIÓN: user1034749 continuación está recibiendo la misma salida de montaje de ambas funciones cuando se los pone en archivos separados y los compila. Probé su línea de comando exacta, y estoy obteniendo el mismo resultado que él. Para todos los efectos, esta pregunta está resuelta.

Sin embargo, todavía me gustaría saber por qué mis medidas salen de forma diferente. Obviamente, mi código de medición o el proceso de creación original estaba causando que las cosas fueran diferentes. Publicaré el código a continuación. ¿Alguien sabe cuál fue el trato? Tal vez mi compilador está en realidad incorporando toda la función mcrowne_isqrt() en el bucle de mi función main(), pero no está incorporando la totalidad de la otra versión.

ACTUALIZACIÓN 2 (exprimido antes del código de prueba): Tenga en cuenta que si cambio el orden de las pruebas y hago que la versión en línea sea lo primero, la versión en línea sale por la misma cantidad que la versión de macro. ¿Es esto un problema de almacenamiento en caché, o es el compilador inlining una llamada pero no la otra, o qué?

#include <iostream> 
#include <time.h>  // Linux high-resolution timer 
#include <stdint.h> 

/* Functions go here */ 

timespec timespecdiff(const timespec& start, const timespec& end) 
{ 
    timespec elapsed; 
    timespec endmod = end; 
    if(endmod.tv_nsec < start.tv_nsec) 
    { 
     endmod.tv_sec -= 1; 
     endmod.tv_nsec += 1000000000; 
    } 

    elapsed.tv_sec = endmod.tv_sec - start.tv_sec; 
    elapsed.tv_nsec = endmod.tv_nsec - start.tv_nsec; 
    return elapsed; 
} 


int main() 
{ 
    uint64_t inputlimit = 4294967295; 
    // Test a wide range of values 
    uint64_t widestep = 16; 

    timespec start, end; 

    // Time macro version: 
    uint32_t sum = 0; 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start); 
    for(uint64_t num = (widestep - 1); num <= inputlimit; num += widestep) 
    { 
     sum += mcrowne_isqrt(uint32_t(num)); 
    } 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end); 
    timespec markcrowntime = timespecdiff(start, end); 
    std::cout << "Done timing Mark Crowne's sqrt variant. Sum of results = " << sum << " (to avoid over-optimization)." << std::endl; 


    // Time inline version: 
    sum = 0; 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start); 
    for(uint64_t num = (widestep - 1); num <= inputlimit; num += widestep) 
    { 
     sum += mcrowne_inline_isqrt(uint32_t(num)); 
    } 
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end); 
    timespec markcrowninlinetime = timespecdiff(start, end); 
    std::cout << "Done timing Mark Crowne's inline sqrt variant. Sum of results = " << sum << " (to avoid over-optimization)." << std::endl; 

    // Results: 
    std::cout << "Mark Crowne sqrt variant time:\t" << markcrowntime.tv_sec << "s, " << markcrowntime.tv_nsec << "ns" << std::endl; 
    std::cout << "Mark Crowne inline sqrt variant time:\t" << markcrowninlinetime.tv_sec << "s, " << markcrowninlinetime.tv_nsec << "ns" << std::endl; 
    std::cout << std::endl; 
} 

---

Actualización 3: Todavía tengo ni idea de cómo comparar con fiabilidad el tiempo de las distintas funciones sin la sincronización en función de la orden de las pruebas. ¡Agradecería mucho cualquier consejo!

Sin embargo, si alguien más leer este está interesado en implementaciones sqrt rápido, debo mencionar: las pruebas de código de Mark Crowne más rápido que cualquier otra versión pura C/C++ He tratado por un margen decente (a pesar de los problemas de fiabilidad con pruebas) , pero el siguiente código SSE parece que podría ser aún un poco más rápido para un entero sqlar de 32 bits escalar. Sin embargo, no se puede generalizar para entradas enteras sin signo de 64 bits sin perder precisión (y la primera conversión firmada también tendría que ser reemplazada por una carga intrínseca para manejar valores> = 2^63):

uint32_t sse_sqrt(uint64_t num) 
{ 
    // Uses 64-bit input, because SSE conversion functions treat all 
    // integers as signed (so conversion from a 32-bit value >= 2^31 
    // will be interpreted as negative). As it stands, this function 
    // will similarly fail for values >= 2^63. 
    // It can also probably be made faster, since it generates a strange/ 
    // useless movsd %xmm0,%xmm0 instruction before the sqrtsd. It clears 
    // xmm0 first too with xorpd (seems unnecessary, but I could be wrong). 
    __m128d result; 
    __m128d num_as_sse_double = _mm_cvtsi64_sd(result, num); 
    result = _mm_sqrt_sd(num_as_sse_double, num_as_sse_double); 
    return _mm_cvttsd_si32(result); 
} 

Answer 1

Probé tu código con gcc 4.5.3. he modificado su segunda versión de código para que coincida con el primero, por ejemplo:

(1 << ((s) * 2 - 2) 

vs

(1 << ((s << 1) - 1) 

sí, s * 2 == s < < 1, pero "-2" y 1"?

También modifiqué sus tipos reemplazando uint32_t con "unsigned long", porque en mi máquina de 64 bits "long" no es un número de 32 bits.

Y luego ejecutar:

g++ -ggdb -O2 -march=native -c -pipe inline.cpp 
g++ -ggdb -O2 -march=native -c -pipe macros.cpp 
objdump -d inline.o > inline.s 
objdump -d macros.o > macros.s 

que podría utilizar "s" en lugar de "c" al ensamblador, pero me gustaría ver ensamblador sin información adicional.

y ¿sabes qué?
El ensamblador es exactamente el mismo, en la primera y en la segunda versión. Así que creo que las medidas de su tiempo son simplemente incorrectas.