Tipo más rápido de longitud fija 6 int array

Respondiendo a otra pregunta de desbordamiento de pila ( esta) me topé con un subproblema interesante. ¿Cuál es la manera más rápida de ordenar una matriz de 6 ints?

Como la pregunta es de muy bajo nivel:

• no podemos asumir que las bibliotecas están disponibles (y la llamada en sí tiene su costo), solo C
• para evitar vaciar la tubería de instrucciones (que tiene un muy alto costo) probablemente deberíamos minimizar las ramas, saltos y cualquier otro tipo de flujo de control romper (como los ocultos detrás de los puntos de secuencia en && o ||).
• el espacio está restringido y minimizar los registros y el uso de memoria es un problema, idealmente en el lugar ordenar es probablemente el mejor.

Realmente esta pregunta es una especie de Golf donde el objetivo no es minimizar la longitud de la fuente sino el tiempo de ejecución. Lo llamo código 'Zening' como se usa en el título del libro Zen of Code optimization por Michael Abrashy sus secuelas.

En cuanto a por qué es interesante, hay varias capas:

• el ejemplo es simple y fácil de entender y medir, no implica mucha habilidad C
• muestra los efectos de elección de un buen algoritmo para el problema, pero también los efectos del compilador y el hardware subyacente.

Aquí está mi implementación de referencia (ingenua, no optimizada) y mi conjunto de pruebas.

#include <stdio.h>

static __inline__ int sort6(int * d){

    char j, i, imin;
    int tmp;
    for (j = 0 ; j < 5 ; j++){
        imin = j;
        for (i = j + 1; i < 6 ; i++){
            if (d[i] < d[imin]){
                imin = i;
            }
        }
        tmp = d[j];
        d[j] = d[imin];
        d[imin] = tmp;
    }
}

static __inline__ unsigned long long rdtsc(void)
{
  unsigned long long int x;
     __asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
     return x;
}

int main(int argc, char ** argv){
    int i;
    int d[6][5] = {
        {1, 2, 3, 4, 5, 6},
        {6, 5, 4, 3, 2, 1},
        {100, 2, 300, 4, 500, 6},
        {100, 2, 3, 4, 500, 6},
        {1, 200, 3, 4, 5, 600},
        {1, 1, 2, 1, 2, 1}
    };

    unsigned long long cycles = rdtsc();
    for (i = 0; i < 6 ; i++){
        sort6(d[i]);
        /*
         * printf("d%d : %d %d %d %d %d %d\n", i,
         *  d[i][0], d[i][6], d[i][7],
         *  d[i][8], d[i][9], d[i][10]);
        */
    }
    cycles = rdtsc() - cycles;
    printf("Time is %d\n", (unsigned)cycles);
}

Resultados brutos

Como el número de variantes se está volviendo grande, las reuní todas en una prueba suite que se puede encontrar aquí. Las pruebas reales utilizadas son un poco menos ingenuas que las mostradas anteriormente, gracias a Kevin Stock. Puede compilarlo y ejecutarlo en su propio entorno. Estoy bastante interesado por el comportamiento en diferentes arquitecturas/compiladores de destino. (OK chicos, ponlo en respuestas, voy a + 1 cada contribuyente de un nuevo resultset).

Le di la respuesta a Daniel Stutzbach (por jugar al golf) hace un año, ya que estaba en la fuente de la solución más rápida en ese momento (clasificación red).

Linux 64 bits, gcc 4.6.1 64 bits, Intel Core 2 Duo E8400, - O2

• Llamada directa a la función de biblioteca qsort: 689.38
• Implementación ingenua (ordenación de inserción): 285.70
• Clasificación por inserción (Daniel Stutzbach): 142.12
• Ordenación de inserción Desenrollada: 125.47
• Orden de clasificación: 102.26
• Orden de rango con registros : 58.03
• Redes de clasificación (Daniel Stutzbach): 111.68
• Redes de clasificación (Pablo R) : 66.36
• Ordenación de redes 12 con Intercambio rápido: 58.86
• Ordenación de redes 12 Intercambio reordenado: 53.74
• Ordenación de redes 12 Intercambio simple reordenado: 31.54
• Red de clasificación reordenada con intercambio rápido: 31.54
• Red de clasificación reordenada con intercambio rápido V2: 33.63
• Tipo de burbuja en línea (Paolo Bonzini) : 48.85
• Ordenación de inserción desenrollada (Paolo Bonzini) : 75.30

Linux 64 bits, gcc 4.6.1 64 bits, Intel Core 2 Duo E8400, - O1

• Llamada directa a la función de biblioteca qsort: 705.93
• Implementación ingenua (ordenación de inserción): 135.60
• Clasificación por inserción (Daniel Stutzbach): 142.11
• Ordenación de inserción Desenrollada: 126.75
• Orden de rango : 46.42
• Orden de rango con registros: 43.58
• Redes de clasificación (Daniel Stutzbach) : 115.57
• Redes de clasificación (Pablo R) : 64.44
• Ordenación de redes 12 con Intercambio rápido: 61.98
• Ordenación de redes 12 Intercambio reordenado: 54.67
• Ordenación de redes 12 Intercambio simple reordenado: 31.54
• Red de clasificación reordenada con intercambio rápido: 31.24
• Red de clasificación reordenada con intercambio rápido V2: 33.07
• Tipo de burbuja en línea (Paolo Bonzini): 45.79
• Ordenación de inserción desenrollada (Paolo Bonzini): 80.15

Incluí los resultados-O1 y-O2 porque sorprendentemente para varios programas O2 es menos eficiente que O1. Me pregunto qué optimización específica tiene este efecto .

Observaciones sobre las soluciones propuestas

Tipo de inserción (Daniel Stutzbach)

Como se espera minimizar las ramas es de hecho un buena idea.

Redes de clasificación (Daniel Stutzbach)

Mejor que la ordenación por inserción. Me preguntaba si el efecto principal no era conseguir de evitar el bucle externo. Le di una oportunidad por tipo de inserción desenrollada para comprobar y de hecho obtenemos aproximadamente las mismas cifras (código es aquí).

Redes de clasificación (Paul R)

El mejor hasta ahora. El código real que usé para probar es aquí . Aún no sé por qué es casi dos veces más rápido que el otro ordenación de la implementación de la red. ¿Paso de parámetros ? Rápido max ?

Redes de clasificación 12 SWAP con Fast Swap

Como sugirió Daniel Stutzbach, combiné su red de ordenación de 12 swap con el intercambio rápido sin ramas (el código es aquí). De hecho, es más rápido, el mejor hasta ahora con un pequeño margen (aproximadamente el 5%), como podría esperarse con 1 swap menos.

También es interesante notar que el intercambio sin ramas parece ser mucho (4 veces) menos eficiente que el simple usando if en arquitectura PPC.

Llamando a la biblioteca qsort

Para dar otro punto de referencia también intenté como se sugirió llamar a la biblioteca qsort (el código es aquí). Como era de esperar, es mucho más lento: de 10 a 30 veces más lento... como se hizo obvio con el nuevo conjunto de pruebas, el principal problema parece ser la carga inicial de la biblioteca después de la primera llamada, y no se compara tan mal con otra versión. Es solo entre 3 y 20 veces más lento en mi Linux. En algunas arquitecturas usadas para pruebas por otros parece incluso ser más rápido (estoy realmente sorprendido por eso, ya que la biblioteca qsort utiliza una API más compleja).

Orden de Rango

Rex Kerr propuso otro método completamente diferente : para cada elemento de la matriz calcular directamente su posición final. Esto es eficiente porque el orden de rango de computación no necesita rama. El inconveniente de este método es que toma tres veces la cantidad de memoria de la matriz (una copia de la matriz y variables para almacenar órdenes de rango). Los resultados de rendimiento son muy sorprendentes (e interesantes). En mi arquitectura de referencia con sistema operativo de 32 bits e Intel Core2 Quad E8300, el recuento de ciclos estaba ligeramente por debajo de 1000 (como las redes de clasificación con swap de ramificación). Pero cuando se compiló y ejecutó en mi caja de 64 bits (Intel Core2 Duo) funcionó mucho mejor : se convirtió en el más rápido hasta ahora. Finalmente descubrí la verdadera razón. Mi caja de 32 bits usa gcc 4.4.1 y mi caja de 64 bits gcc 4.4.3 y la última parece mucho mejor en la optimización de este código en particular (había muy poca diferencia para otras propuestas).

actualización:

Como muestran las cifras publicadas anteriormente, este efecto aún se vio mejorado por las versiones posteriores de gcc y el Orden de rango se volvió consistentemente dos veces más rápido que cualquier otra alternativa.

Ordenación de redes 12 con Swap reordenado

La increíble eficiencia de la propuesta de Rex Kerr con gcc 4.4.3 me hizo preguntarme: ¿cómo podría un programa con 3 veces más ¿el uso de memoria es más rápido que las redes de clasificación sin ramas? Mi hipótesis era que tenía menos dependencias del tipo lectura tras escritura, permitiendo un mejor uso del planificador de instrucciones superescalar del x86. Eso me dio una idea: reordenar los swaps para minimizar las dependencias de lectura después de escritura. En pocas palabras: cuando haces SWAP(1, 2); SWAP(0, 2); tienes que esperar a que termine el primer intercambio antes de realizar el segundo porque ambos acceden a una celda de memoria común. Cuando lo hace SWAP(1, 2); SWAP(4, 5);el procesador puede ejecutar ambos en paralelo. Lo probé y funciona como se esperaba, las redes de clasificación se ejecutan aproximadamente un 10% más rápido.

Ordenación de redes 12 con Intercambio Simple

Un año después del post original Steinar H. Gunderson sugirió, que no deberíamos tratar de ser más astutos que el compilador y mantener el código de intercambio simple. De hecho, es una buena idea ya que el código resultante es aproximadamente 40% más rápido! También propuso un intercambio optimizado a mano usando código de ensamblaje en línea x86 que aún puede ahorrar algo más ciclo. Lo más sorprendente (dice volúmenes sobre psicología del programador) es que hace un año ninguno de los usados probó esa versión de swap. El código que usé para probar es aquí . Otros sugirieron otras formas de escribir un intercambio rápido en C, pero produce el mismo rendimiento que el simple con un compilador decente.

El código" mejor " es ahora el siguiente:

static inline void sort6_sorting_network_simple_swap(int * d){
#define min(x, y) (x<y?x:y)
#define max(x, y) (x<y?y:x) 
#define SWAP(x,y) { const int a = min(d[x], d[y]); \
                    const int b = max(d[x], d[y]); \
                    d[x] = a; d[y] = b; }
    SWAP(1, 2);
    SWAP(4, 5);
    SWAP(0, 2);
    SWAP(3, 5);
    SWAP(0, 1);
    SWAP(3, 4);
    SWAP(1, 4);
    SWAP(0, 3);
    SWAP(2, 5);
    SWAP(1, 3);
    SWAP(2, 4);
    SWAP(2, 3);
#undef SWAP
#undef min
#undef max
}

Si creemos que nuestro conjunto de pruebas (y, sí, es bastante pobre, su mero beneficio es ser corto, simple y fácil de entender lo que somos medición), el número medio de ciclos del código resultante para un tipo es inferior a 40 ciclos (se ejecutan 6 pruebas). Eso pone cada intercambio en un promedio de 4 ciclos. Yo llamo a eso increíblemente rápido. ¿Alguna otra mejora posible ?