c - rapido - dieta para bajar de peso en una semana

La forma más rápida de averiguar un mínimo de 3 números?

Question

En un programa que escribí, el 20% del tiempo se gasta en encontrar el mínimo de 3 números en un ciclo interno, en esta rutina:

static inline unsigned int
min(unsigned int a, unsigned int b, unsigned int c)
{
    unsigned int m = a;
    if (m > b) m = b;
    if (m > c) m = c;
    return m;
}

Hay alguna manera de acelerar esto? Estoy bien con el código de ensamblaje también para x86 / x86_64.

Editar: En respuesta a algunos de los comentarios:
* El compilador utilizado es gcc 4.3.3
* En lo que respecta al montaje, solo soy un principiante allí. Pedí la asamblea aquí, para aprender cómo hacer esto. :)
* Tengo un Intel Kern de cuatro núcleos en ejecución, por lo que se admiten MMX / SSE, etc.
* Es difícil publicar el ciclo aquí, pero puedo decir que es una implementación muy optimizada del algoritmo de levenshtein.

Esto es lo que el compilador me está dando para la versión no en línea de min:

.globl min
    .type   min, @function
min:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %edx
    movl    12(%ebp), %eax
    movl    16(%ebp), %ecx
    cmpl    %edx, %eax
    jbe .L2
    movl    %edx, %eax
.L2:
    cmpl    %ecx, %eax
    jbe .L3
    movl    %ecx, %eax
.L3:
    popl    %ebp
    ret
    .size   min, .-min
    .ident  "GCC: (Ubuntu 4.3.3-5ubuntu4) 4.3.3"
    .section    .note.GNU-stack,"",@progbits

La versión impresa está dentro del código optimizado para -O2 (incluso mis marcadores mrk = 0xfefefefe, antes y después de la llamada a min ()) están siendo optimizados por gcc, por lo que no pude conseguirlo.

Actualización: Probé los cambios sugeridos por Nils, ephemient, sin embargo, no hay un aumento de rendimiento perceptible que obtengo al usar las versiones de ensamblaje de min (). Sin embargo, obtengo un aumento del 12.5% ​​al ​​compilar el programa con -march = i686, lo que supongo es porque todo el programa está obteniendo los beneficios de las nuevas instrucciones más rápidas que gcc está generando con esta opción. gracias por su ayuda chicos.

PD: utilicé el perfilador de ruby ​​para medir el rendimiento (mi programa C es una biblioteca compartida cargada por un programa ruby), así que podía dedicarle tiempo solo para la función C de nivel superior llamada por el programa ruby, que termina llamando a min () abajo de la pila. Por favor mira esta question .

Answer 1

Asegúrese de estar utilizando una configuración apropiada de -march , primero apagado. GCC se predetermina a no utilizar ninguna instrucción que no era compatible con el i386 original. ¡Permitirle usar conjuntos de instrucciones más nuevos puede hacer una GRAN diferencia a veces! En -march=core2 -O2 obtengo:

min:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %edx
    movl    12(%ebp), %ecx
    movl    16(%ebp), %eax
    cmpl    %edx, %ecx
    leave
    cmovbe  %ecx, %edx
    cmpl    %eax, %edx
    cmovbe  %edx, %eax
    ret

El uso de cmov aquí puede ayudarlo a evitar retrasos en la sucursal, y lo obtiene sin ningún asme en línea simplemente al pasar en -march . Cuando está integrado en una función más grande, es probable que sea incluso más eficiente, posiblemente solo cuatro operaciones de ensamblaje. Si necesita algo más rápido que esto, vea si puede hacer que las operaciones del vector SSE funcionen en el contexto de su algoritmo general.

Answer 2

Estas son todas buenas respuestas. A riesgo de ser acusado de no contestar la pregunta, también miraría el otro 80% del tiempo. Stackshots son mi forma favorita de encontrar un código que valga la pena optimizar, especialmente si se trata de llamadas a función que descubres que no necesitas absolutamente.

Answer 3

Este reemplazo directo cambia en aproximadamente 1.5% más rápido en mi AMD Phenom:

static inline unsigned int
min(unsigned int a, unsigned int b, unsigned int c)
{
    asm("cmp   %1,%0/n"
        "cmova %1,%0/n"
        "cmp   %2,%0/n"
        "cmova %2,%0/n"
        : "+r" (a) : "r" (b), "r" (c));
    return a;
}

Los resultados pueden variar; algunos procesadores x86 no manejan muy bien CMOV.

Answer 4

Las extensiones de instrucción SSE2 contienen una instrucción entera min que puede elegir 8 mínimos a la vez. Ver _mm_mulhi_epu16 en http://www.intel.com/software/products/compilers/clin/docs/ug_cpp/comm1046.htm

Answer 5

Mi opinión sobre una implementación de ensamblador x86, sintaxis GCC. Debe ser trivial para traducir a otra sintaxis de ensamblador en línea:

int inline least (int a, int b, int c)
{
  int result;
  __asm__ ("mov     %1, %0/n/t"
           "cmp     %0, %2/n/t" 
           "cmovle  %2, %0/n/t"
           "cmp     %0, %3/n/t"
           "cmovle  %3, %0/n/t" 
          : "=r"(result) : 
            "r"(a), "r"(b), "r"(c)
          );
  return result;
}

Nueva versión mejorada:

int inline least (int a, int b, int c)
{
  __asm__ (
           "cmp     %0, %1/n/t" 
           "cmovle  %1, %0/n/t"
           "cmp     %0, %2/n/t"
           "cmovle  %2, %0/n/t" 
          : "+r"(a) : 
            "%r"(b), "r"(c)
          );
  return a;
}

NOTA: Puede o no ser más rápido que el código C.

Esto depende de muchos factores. Por lo general, cmov gana si las ramas no son predecibles (en algunas arquitecturas x86). El ensamblador en línea OTOH siempre es un problema para el optimizador, por lo que la penalización de optimización para el código circundante puede superar todas las ganancias.

Por cierto, Sudhanshu, sería interesante escuchar cómo funciona este código con sus datos de prueba.

Answer 6

Podría intentar algo como esto para ahorrar en declaraciones y comparaciones innecesarias:

static inline unsigned int
min(unsigned int a, unsigned int b, unsigned int c)
{ 
    if (a < b)
    {
        if (a < c) 
             return a; 
        else 
             return c;
    }

    if (b < c)
        return b;
    else return c;
}

Answer 7

Primero, mira el desmontaje. Eso te dirá mucho. Por ejemplo, tal como está escrito, hay 2 sentencias if (lo que significa que hay 2 posibles errores de predicción de bifurcaciones), pero mi suposición es que un compilador de C moderno decente tendrá alguna optimización inteligente que pueda hacerlo sin ramificarse. Me gustaría saberlo.

En segundo lugar, si su libc tiene funciones min / max incorporadas especiales, úselos. GNU libc tiene fmin / fmax para coma flotante, por ejemplo, y afirman que "en algunos procesadores estas funciones pueden usar instrucciones especiales de máquina para realizar estas operaciones más rápido que el código C equivalente". Tal vez hay algo similar para uints.

Finalmente, si haces esto en un grupo de números en paralelo, probablemente haya instrucciones vectoriales para hacer esto, lo que podría proporcionar una aceleración significativa. Pero incluso he visto que el código no vectorial es más rápido cuando se usan unidades de vectores. Algo así como "cargue una uint en un registro de vectores, llame a la función de min de vectores, obtenga resultados" parece tonto, pero en realidad podría ser más rápido.

Answer 8

Sí, post ensamblaje, pero mi optimización ingenua es:

static inline unsigned int
min(unsigned int a, unsigned int b, unsigned int c)
{
    unsigned int m = a;
    if (m > b) m = b;
    if (m > c) return c;
    return m;
}

Answer 9

Si solo está haciendo una comparación, es posible que desee desenrollar el ciclo manualmente.

Primero, vea si puede hacer que el compilador desenrolle el ciclo, y si no puede, hágalo usted mismo. Esto al menos reducirá la sobrecarga del control de bucle ...

Answer 10

Suponiendo que su compilador no está listo para el almuerzo, esto debería compilar hasta dos comparaciones y dos movimientos condicionales. No es posible hacer mucho mejor que eso.

Si publica el ensamblado que su compilador está realmente generando, podemos ver si hay algo innecesario que lo esté ralentizando.

Lo primero que hay que verificar es que la rutina se está en línea. El compilador no está obligado a hacerlo, y si está generando una llamada de función, será muy costoso para una operación tan simple.

Si la llamada realmente se está introduciendo, el desenrollado del bucle puede ser beneficioso, como dijo DigitalRoss, o la vectorización puede ser posible.

Editar: si quiere vectorizar el código y está usando un procesador x86 reciente, querrá usar la instrucción pminud SSE4.1 (intrínseca: _mm_min_epu32 ), que toma dos vectores de cuatro entradas sin signo cada uno, y produce un vector de cuatro entradas sin firmar. Cada elemento del resultado es el mínimo de los elementos correspondientes en las dos entradas.

También observo que su compilador usó ramas en lugar de movimientos condicionales; Probablemente deberías probar una versión que usa movimientos condicionales primero y ver si eso te permite acelerar antes de ir a las carreras en una implementación de vector.