c++ - una - return arduino ejemplo

¿Por qué una función en línea tiene menor eficiencia que una función incorporada?

Question

Estaba intentando una pregunta sobre matrices en InterviewBit . En esta pregunta hice una función en línea que devuelve el valor absoluto de un entero. Pero me dijeron que mi algoritmo no era eficiente al enviarlo. Pero cuando cambié a usar abs() de la biblioteca C ++, dio un veredicto de respuesta correcta .

Aquí está mi función que tiene un veredicto ineficiente -

inline int abs(int x){return x>0 ? x : -x;}

int Solution::coverPoints(vector<int> &X, vector<int> &Y) {
    int l = X.size();
    int i = 0;
    int ans = 0;
    while (i<l-1){
        ans = ans + max(abs(X[i]-X[i+1]), abs(Y[i]-Y[i+1]));
        i++;
    }
    return ans;
}

Aquí está el que tiene la respuesta correcta :

int Solution::coverPoints(vector<int> &X, vector<int> &Y) {
    int l = X.size();
    int i = 0;
    int ans = 0;
    while (i<l-1){
        ans = ans + max(abs(X[i]-X[i+1]), abs(Y[i]-Y[i+1]));
        i++;
    }
    return ans;
}

¿Por qué sucedió esto, ya que pensé que las funciones en línea son más rápidas ya que no se realiza ninguna llamada? ¿O es que el sitio tiene un error? Y si el sitio es correcto, ¿qué utiliza C ++ abs() que sea más rápido que inline abs() ?

Answer 1

No estoy de acuerdo con su veredicto. Ellos están claramente equivocados .

En los compiladores de optimización actuales, ambas soluciones producen el mismo resultado exacto . E incluso, si no produjeran exactamente lo mismo , producirían un código tan eficiente como el de la biblioteca (podría ser un poco sorprendente que todo coincida: el algoritmo, los registros utilizados. Tal vez porque la implementación real de la biblioteca es la misma como uno de OP?).

Ningún compilador de optimización sano creará una rama en su código abs() (si se puede hacer sin una rama), como sugiere otra respuesta. Si el compilador no está optimizando, entonces puede que no esté en la biblioteca abs() , por lo que tampoco será rápido.

La optimización de abs() es una de las cosas más fáciles de hacer para un compilador (solo agregue una entrada para él en el optimizador de mirilla, y listo).

Además, he visto implementaciones de bibliotecas en el pasado, donde abs() se implementaron como una función de biblioteca no en línea (aunque fue hace mucho tiempo).

Prueba de que ambas implementaciones son las mismas:

GCC:

myabs:
    mov     edx, edi    ; argument passed in EDI by System V AMD64 calling convention
    mov     eax, edi
    sar     edx, 31
    xor     eax, edx
    sub     eax, edx
    ret

libabs:
    mov     edx, edi    ; argument passed in EDI by System V AMD64 calling convention
    mov     eax, edi
    sar     edx, 31
    xor     eax, edx
    sub     eax, edx
    ret

Sonido metálico:

myabs:
    mov     eax, edi    ; argument passed in EDI by System V AMD64 calling convention
    neg     eax
    cmovl   eax, edi
    ret

libabs:
    mov     eax, edi    ; argument passed in EDI by System V AMD64 calling convention
    neg     eax
    cmovl   eax, edi
    ret

Visual Studio (MSVC):

libabs:
    mov      eax, ecx    ; argument passed in ECX by Windows 64-bit calling convention 
    cdq
    xor      eax, edx
    sub      eax, edx
    ret      0

myabs:
    mov      eax, ecx    ; argument passed in ECX by Windows 64-bit calling convention 
    cdq
    xor      eax, edx
    sub      eax, edx
    ret      0

ICC:

myabs:
    mov       eax, edi    ; argument passed in EDI by System V AMD64 calling convention 
    cdq
    xor       edi, edx
    sub       edi, edx
    mov       eax, edi
    ret      

libabs:
    mov       eax, edi    ; argument passed in EDI by System V AMD64 calling convention 
    cdq
    xor       edi, edx
    sub       edi, edx
    mov       eax, edi
    ret      

Compruébelo usted mismo en Godbolt Compiler Explorer, donde puede inspeccionar el código de máquina generado por varios compiladores. (Enlace proporcionado amablemente por Peter Cordes.)

Answer 2

Su solución podría ser "más limpia" por el libro de texto si usó la versión estándar de la biblioteca, pero creo que la evaluación es incorrecta. No existe una razón realmente buena y justificable para que su código sea rechazado.

Este es uno de esos casos en los que alguien es formalmente correcto (según el libro de texto), pero insiste en saber la única solución correcta de una manera totalmente estúpida en lugar de aceptar una solución alternativa y decir "... pero esta sería la mejor práctica. usted sabe " .

Técnicamente, es un enfoque correcto y práctico para decir "usar la biblioteca estándar, para eso es, y es probable que se optimice lo más posible" . A pesar de que la parte "optimizada tanto como puede ser" puede, en algunas situaciones, muy bien estar equivocada debido a algunas restricciones que la norma impone a ciertos alogoritmos y / o contenedores.

Ahora, opiniones, mejores prácticas, y religión a un lado. De hecho, si comparas los dos enfoques ...

int main(int argc, char**)
{
  40f360:       53                      push   %rbx
  40f361:       48 83 ec 20             sub    $0x20,%rsp
  40f365:       89 cb                   mov    %ecx,%ebx
  40f367:       e8 a4 be ff ff          callq  40b210 <__main>
return std::abs(argc);
  40f36c:       89 da                   mov    %ebx,%edx
  40f36e:       89 d8                   mov    %ebx,%eax
  40f370:       c1 fa 1f                sar    $0x1f,%edx
  40f373:       31 d0                   xor    %edx,%eax
  40f375:       29 d0                   sub    %edx,%eax
//}

int main(int argc, char**)
{
  40f360:       53                      push   %rbx
  40f361:       48 83 ec 20             sub    $0x20,%rsp
  40f365:       89 cb                   mov    %ecx,%ebx
  40f367:       e8 a4 be ff ff          callq  40b210 <__main>
return (argc > 0) ? argc : -argc;
  40f36c:       89 da                   mov    %ebx,%edx
  40f36e:       89 d8                   mov    %ebx,%eax
  40f370:       c1 fa 1f                sar    $0x1f,%edx
  40f373:       31 d0                   xor    %edx,%eax
  40f375:       29 d0                   sub    %edx,%eax
//}

... dan como resultado exactamente las mismas instrucciones idénticas.

Pero incluso si el compilador usó una comparación seguida de un movimiento condicional (que puede hacer en "asignaciones de bifurcación" más complicadas y que hará, por ejemplo, en el caso de min / max ), eso es quizás un ciclo de CPU o un poco más lento que los bits hacks, así que a menos que lo hagas varios millones de veces, la afirmación "no eficiente" es algo dudosa de todos modos.
Un error de caché, y tiene cien veces la penalización de un movimiento condicional.

Hay argumentos válidos a favor y en contra de cualquiera de los dos enfoques, que no discutiré en detalle. Lo que quiero decir es que rechazar la solución de la OP como "totalmente errónea" debido a un detalle tan insignificante y sin importancia es bastante estrecho.

EDITAR:

(Trivialidades divertidas)

Acabo de intentarlo, por diversión y sin fines de lucro, en mi caja de Linux Mint que usa una versión algo más antigua de GCC (5.4 en comparación con la versión 7.1 anterior).

Debido a que <cmath> sin pensar mucho (hey, una función como abs pertenece claramente a las matemáticas, ¿no?) En lugar de <cstdlib> que alberga la sobrecarga de enteros, el resultado fue, bueno ... sorprendente Llamar a la función de la biblioteca era muy inferior a la envoltura de expresión única.

Ahora, en defensa de la biblioteca estándar, si incluye <cstdlib> , entonces, nuevamente, la salida producida es exactamente idéntica en ambos casos.

Para referencia, el código de prueba parecía:

#ifdef DRY
  #include <cmath>
  int main(int argc, char**)
  {
     return std::abs(argc);
  }
#else
  int abs(int v) noexcept { return (v >= 0) ? v : -v; }
  int main(int argc, char**)
  {
     return abs(argc);
  }
#endif

...Resultando en

4004f0: 89 fa                   mov    %edi,%edx
4004f2: 89 f8                   mov    %edi,%eax
4004f4: c1 fa 1f                sar    $0x1f,%edx
4004f7: 31 d0                   xor    %edx,%eax
4004f9: 29 d0                   sub    %edx,%eax
4004fb: c3                      retq 

Ahora, aparentemente es bastante fácil caer en la trampa de usar, sin saberlo, la función de biblioteca estándar incorrecta (¡demostré lo fácil que soy yo!). Y todo eso sin la menor advertencia del compilador, como "hey, sabes, estás usando una sobrecarga double en un valor entero (bueno, obviamente no hay ninguna advertencia, es una conversión válida).

Con eso en mente, puede haber otra "justificación" por la que el OP que proporcionó su propia línea de un solo personaje no fue tan terriblemente malo e incorrecto. Después de todo, podría haber cometido el mismo error.

Answer 3

Sus abs realizan ramificaciones basadas en una condición. Mientras que la variante incorporada simplemente elimina el bit de signo del entero, lo más probable es que use solo un par de instrucciones. Posible ejemplo de montaje (tomado de here ):

cdq
xor eax, edx
sub eax, edx

El cdq copia el signo del registro eax para registrar edx. Por ejemplo, si es un número positivo, edx será cero, de lo contrario, edx será 0xFFFFFF, que denota -1. La operación xor con el número de origen no cambiará nada si es un número positivo (cualquier número xor 0 no cambiará). Sin embargo, cuando eax es negativo, eax xor 0xFFFFFF produce (no eax). El paso final es restar edx de eax. Nuevamente, si eax es positivo, edx es cero, y el valor final sigue siendo el mismo. Para valores negativos, (~ eax) - (-1) = –eax, que es el valor deseado.

Como puede ver, este enfoque utiliza solo tres instrucciones aritméticas simples y ninguna ramificación condicional en absoluto.

Edit : Después de algunas investigaciones, resultó que muchas implementaciones integradas de abs utilizan el mismo enfoque, return __x >= 0 ? __x : -__x; return __x >= 0 ? __x : -__x; , y tal patrón es un objetivo obvio para la optimización del compilador para evitar ramificaciones innecesarias.

Sin embargo, eso no justifica el uso de la implementación de abs personalizada, ya que viola el principio DRY y nadie puede garantizar que su implementación será igual de buena para escenarios más sofisticados y / o plataformas inusuales. Normalmente, se debe pensar en reescribir algunas de las funciones de la biblioteca solo cuando hay un problema de rendimiento definido o algún otro defecto detectado en la implementación existente.

Edit2 : el simple cambio de int a float muestra una considerable degradación del rendimiento:

float libfoo(float x)
{
    return ::std::fabs(x);
}

andps   xmm0, xmmword ptr [rip + .LCPI0_0]

Y una versión personalizada:

inline float my_fabs(float x)
{
    return x>0.0f?x:-x;
}

float myfoo(float x)
{
    return my_fabs(x);
}

movaps  xmm1, xmmword ptr [rip + .LCPI1_0] # xmm1 = [-0.000000e+00,-0.000000e+00,-0.000000e+00,-0.000000e+00]
xorps   xmm1, xmm0
xorps   xmm2, xmm2
cmpltss xmm2, xmm0
andps   xmm0, xmm2
andnps  xmm2, xmm1
orps    xmm0, xmm2

compilador en línea