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

Respondiendo a otra pregunta de desbordamiento de stack ( esta ) tropecé con un sub-problema interesante. ¿Cuál es la forma más rápida de ordenar una matriz de 6 ints?

Como la pregunta es de muy bajo nivel:

  • no podemos suponer que las bibliotecas están disponibles (y la llamada en sí tiene su costo), solo la C simple
  • para evitar el vaciado de la línea de instrucciones (que tiene un costo muy alto) probablemente deberíamos minimizar las twigs, los saltos y cualquier otro tipo de flujo de control (como los ocultos detrás de los puntos de secuencia en && o || ).
  • la sala está restringida y minimizar los registros y el uso de la memoria es un problema; lo ideal es que el tipo de clasificación sea probablemente el mejor.

Realmente esta pregunta es un tipo de golf donde el objective 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 de Michael Abrash y sus secuelas .

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

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

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

 #include  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 sin procesar

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

Le di la respuesta a Daniel Stutzbach (para el golf) hace un año porque él estaba en la fuente de la solución más rápida en ese momento (clasificación de redes).

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

  • Llamada directa a la función de la biblioteca qsort: 689.38
  • Implementación ingenua (ordenación por inserción): 285.70
  • Clasificación de inserción (Daniel Stutzbach): 142.12
  • Insertion Sort Unrolled: 125.47
  • Orden de rango: 102.26
  • Orden de rango con registros: 58.03
  • Ordenando Redes (Daniel Stutzbach): 111.68
  • Ordenando Redes (Paul R): 66.36
  • Clasificación de redes 12 con intercambio rápido: 58.86
  • Redes de ordenamiento 12 intercambio reordenado: 53.74
  • Redes de ordenamiento 12 reordenado Simple Swap: 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
  • Clasificación de burbuja en línea (Paolo Bonzini): 48.85
  • Tipo de inserción desenrollado (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 la biblioteca qsort: 705.93
  • Implementación ingenua (ordenación por inserción): 135.60
  • Clasificación de inserción (Daniel Stutzbach): 142.11
  • Insertion Sort Unrolled: 126.75
  • Orden de rango: 46.42
  • Orden de rango con registros: 43.58
  • Ordenando Redes (Daniel Stutzbach): 115.57
  • Ordenando Redes (Paul R): 64.44
  • Clasificación de redes 12 con cambio rápido: 61.98
  • Redes de ordenamiento 12 intercambio reordenado: 54.67
  • Redes de ordenamiento 12 reordenado Simple Swap: 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
  • Clasificación de burbuja en línea (Paolo Bonzini): 45.79
  • Tipo de inserción desenrollado (Paolo Bonzini): 80.15

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

Comentarios sobre soluciones propuestas

Clasificación de inserción (Daniel Stutzbach)

Como se esperaba, minimizar las sucursales es una buena idea.

Ordenando Redes (Daniel Stutzbach)

Mejor que el tipo de inserción. Me preguntaba si el principal efecto no sería evitar el bucle externo. Lo probé por tipo de inserción desenrollada para verificar y, de hecho, tenemos más o menos las mismas cifras (el código está aquí ).

Ordenando Redes (Paul R)

Lo mejor por mucho. El código real que usé para probar está aquí . Aún no sé por qué es casi dos veces más rápido que la otra implementación de red de clasificación. ¿Pasa el parámetro? Fast Max?

Clasificación de redes 12 SWAP con Fast Swap

Como sugirió Daniel Stutzbach, combiné su red de clasificación de 12 intercambios con intercambio rápido sin sucursales (el código está aquí ). De hecho, es más rápido, el mejor hasta el momento con un pequeño margen (aproximadamente el 5%) que podría esperarse utilizando 1 menos de intercambio.

También es interesante notar que el swap sin sucursales parece ser mucho (4 veces) menos eficiente que el simple usando if en la architecture PPC.

Llamando a la biblioteca qsort

Para dar otro punto de referencia también intenté, como se sugirió, simplemente llamar a la biblioteca qsort (el código está 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 otras versión. Es entre 3 y 20 veces más lento en mi Linux. En algunas architectures usadas para pruebas por otros parece incluso ser más rápido (estoy realmente sorprendido por eso, ya que la biblioteca qsort usa una API más compleja).

Orden de rango

Rex Kerr propuso otro método completamente diferente: para cada elemento de la matriz, calcule directamente su posición final. Esto es eficiente porque el orden de rango computacional no necesita una bifurcación. El inconveniente de este método es que requiere tres veces la cantidad de memoria de la matriz (una copia de la matriz y las variables para almacenar órdenes de rango). Los resultados de rendimiento son muy sorprendentes (e interesantes). En mi architecture de referencia con 32 bits OS e Intel Core2 Quad E8300, el recuento de ciclos fue ligeramente inferior a 1000 (como las redes de clasificación con intercambio de twigs). 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 el momento. 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 para optimizar este código en particular (había muy poca diferencia para otras propuestas).

actualización :

Como se muestra en las figuras anteriores, este efecto aún se vio reforzado por las versiones posteriores de gcc y el orden de clasificación se volvió consistentemente el doble de rápido que cualquier otra alternativa.

Clasificación de redes 12 con intercambio reordenado

La asombrosa eficiencia de la propuesta de Rex Kerr con gcc 4.4.3 me hizo preguntarme: ¿cómo podría un progtwig con 3 veces más uso de memoria ser más rápido que las redes de clasificación sin sucursales? Mi hipótesis era que tenía menos dependencias del tipo lectura después de escritura, lo que permite un mejor uso del progtwigdor de instrucciones superescalar del x86. Eso me dio una idea: reordenar swaps para minimizar las dependencias de lectura tras escritura. Más simple: cuando haces SWAP(1, 2); SWAP(0, 2); SWAP(1, 2); SWAP(0, 2); debe esperar a que finalice el primer intercambio antes de realizar el segundo, ya que ambos acceden a una celda de memoria común. Cuando haces SWAP(1, 2); SWAP(4, 5); SWAP(1, 2); SWAP(4, 5); el procesador puede ejecutar ambos en paralelo. Lo intenté y funciona como se esperaba, las redes de clasificación funcionan aproximadamente un 10% más rápido.

Clasificación de redes 12 con intercambio simple

Un año después de la publicación original, Steinar H. Gunderson sugirió que no intentáramos ser más listos que el comstackdor y mantener el código de intercambio simple. De hecho, es una buena idea ya que el código resultante es aproximadamente un 40% más rápido. También propuso un intercambio optimizado a mano utilizando el código de ensamblaje en línea x86 que aún puede ahorrar algunos ciclos más. Lo más sorprendente (dice volúmenes sobre la psicología del progtwigdor) es que hace un año ninguno de los que usaban intentó esa versión del intercambio. El código que solía probar está aquí . Otros sugirieron otras formas de escribir un intercambio C rápido, pero produce los mismos resultados que el simple con un comstackdor decente.

El “mejor” código ahora es 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, el mero beneficio es ser breve, simple y fácil de entender lo que estamos midiendo), el número promedio de ciclos del código resultante para un tipo es inferior a 40 ciclos ( 6 pruebas son ejecutadas). Eso pone cada intercambio en un promedio de 4 ciclos. Lo llamo increíblemente rápido. Cualquier otra mejora posible?

Para cualquier optimización, siempre es mejor probar, probar y probar. Intentaría, al menos, clasificar redes y ordenar por inserción. Si estuviera apostando, pondría mi dinero en el tipo de inserción basado en la experiencia pasada.

¿Sabes algo sobre los datos de entrada? Algunos algoritmos funcionarán mejor con ciertos tipos de datos. Por ejemplo, la ordenación de inserción tiene mejor rendimiento en dato ordenado o casi ordenado, por lo que será la mejor opción si hay una posibilidad superior a la media de datos casi ordenados.

El algoritmo que publicó es similar a un ordenamiento de inserción, pero parece que ha minimizado el número de intercambios a costa de más comparaciones. Sin embargo, las comparaciones son mucho más costosas que los intercambios, porque las sucursales pueden hacer que la tubería de instrucciones se estanque.

Aquí hay una implementación de ordenación de inserción:

 static __inline__ int sort6(int *d){ int i, j; for (i = 1; i < 6; i++) { int tmp = d[i]; for (j = i; j >= 1 && tmp < d[j-1]; j--) d[j] = d[j-1]; d[j] = tmp; } } 

Así es como construiría una red de clasificación. Primero, use este sitio para generar un conjunto mínimo de macros SWAP para una red de la longitud adecuada. Envolver eso en una función me da:

 static __inline__ int sort6(int * d){ #define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; } SWAP(1, 2); SWAP(0, 2); SWAP(0, 1); SWAP(4, 5); SWAP(3, 5); SWAP(3, 4); SWAP(0, 3); SWAP(1, 4); SWAP(2, 5); SWAP(2, 4); SWAP(1, 3); SWAP(2, 3); #undef SWAP } 

Aquí hay una implementación usando redes de clasificación :

 inline void Sort2(int *p0, int *p1) { const int temp = min(*p0, *p1); *p1 = max(*p0, *p1); *p0 = temp; } inline void Sort3(int *p0, int *p1, int *p2) { Sort2(p0, p1); Sort2(p1, p2); Sort2(p0, p1); } inline void Sort4(int *p0, int *p1, int *p2, int *p3) { Sort2(p0, p1); Sort2(p2, p3); Sort2(p0, p2); Sort2(p1, p3); Sort2(p1, p2); } inline void Sort6(int *p0, int *p1, int *p2, int *p3, int *p4, int *p5) { Sort3(p0, p1, p2); Sort3(p3, p4, p5); Sort2(p0, p3); Sort2(p2, p5); Sort4(p1, p2, p3, p4); } 

Realmente necesita implementaciones mínimas y max sin sucursales muy eficientes para esto, ya que es a lo que se reduce realmente este código: una secuencia de operaciones max y max (13 de cada una, en total). Dejo esto como un ejercicio para el lector.

Tenga en cuenta que esta implementación se presta fácilmente a la vectorización (por ejemplo, SIMD, la mayoría de SIMD ISA tienen instrucciones vectoriales mínimas / máximas) y también a implementaciones de GPU (por ejemplo, CUDA, al ser sin sucursales no hay problemas con la distorsión warp, etc.).

Ver también: Implementación rápida de algoritmos para ordenar listas muy pequeñas

Dado que estos son enteros y las comparaciones son rápidas, ¿por qué no calcular el orden jerárquico de cada uno directamente?

 inline void sort6(int *d) { int e[6]; memcpy(e,d,6*sizeof(int)); int o0 = (d[0]>d[1])+(d[0]>d[2])+(d[0]>d[3])+(d[0]>d[4])+(d[0]>d[5]); int o1 = (d[1]>=d[0])+(d[1]>d[2])+(d[1]>d[3])+(d[1]>d[4])+(d[1]>d[5]); int o2 = (d[2]>=d[0])+(d[2]>=d[1])+(d[2]>d[3])+(d[2]>d[4])+(d[2]>d[5]); int o3 = (d[3]>=d[0])+(d[3]>=d[1])+(d[3]>=d[2])+(d[3]>d[4])+(d[3]>d[5]); int o4 = (d[4]>=d[0])+(d[4]>=d[1])+(d[4]>=d[2])+(d[4]>=d[3])+(d[4]>d[5]); int o5 = 15-(o0+o1+o2+o3+o4); d[o0]=e[0]; d[o1]=e[1]; d[o2]=e[2]; d[o3]=e[3]; d[o4]=e[4]; d[o5]=e[5]; } 

Parece que llegué a la fiesta un año tarde, pero aquí vamos …

Al observar el ensamblaje generado por gcc 4.5.2 observé que se realizan cargas y almacenes para cada intercambio, lo que realmente no es necesario. Sería mejor cargar los 6 valores en los registros, ordenarlos y almacenarlos nuevamente en la memoria. Ordené que las cargas en las tiendas estuvieran lo más cerca posible de allí, los registros se necesitaban por primera vez y se usaban por última vez. También utilicé la macro SWAP de Steinar H. Gunderson. Actualización: Cambié a la macro SWAP de Paolo Bonzini, que gcc se convierte en algo similar a la de Gunderson, pero gcc puede ordenar mejor las instrucciones, ya que no se proporcionan como ensamblaje explícito.

Usé el mismo orden de intercambio que la red de intercambio reordenada como el de mejor rendimiento, aunque puede haber un mejor orden. Si encuentro más tiempo, generaré y probaré un montón de permutaciones.

Cambié el código de prueba para considerar más de 4000 arrays y mostrar el número promedio de ciclos necesarios para ordenar cada uno. En un i5-650 obtengo ~ 34.1 ciclos / clasificación (utilizando -O3), en comparación con la red de ordenación reordenada original obteniendo ~ 65.3 ciclos / clasificación (utilizando -O1, tiempos -O2 y -O3).

 #include  static inline void sort6_fast(int * d) { #define SWAP(x,y) { int dx = x, dy = y, tmp; tmp = x = dx < dy ? dx : dy; y ^= dx ^ tmp; } register int x0,x1,x2,x3,x4,x5; x1 = d[1]; x2 = d[2]; SWAP(x1, x2); x4 = d[4]; x5 = d[5]; SWAP(x4, x5); x0 = d[0]; SWAP(x0, x2); x3 = d[3]; SWAP(x3, x5); SWAP(x0, x1); SWAP(x3, x4); SWAP(x1, x4); SWAP(x0, x3); d[0] = x0; SWAP(x2, x5); d[5] = x5; SWAP(x1, x3); d[1] = x1; SWAP(x2, x4); d[4] = x4; SWAP(x2, x3); d[2] = x2; d[3] = x3; #undef SWAP #undef min #undef max } static __inline__ unsigned long long rdtsc(void) { unsigned long long int x; __asm__ volatile ("rdtsc; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx"); return x; } void ran_fill(int n, int *a) { static int seed = 76521; while (n--) *a++ = (seed = seed *1812433253 + 12345); } #define NTESTS 4096 int main() { int i; int d[6*NTESTS]; ran_fill(6*NTESTS, d); unsigned long long cycles = rdtsc(); for (i = 0; i < 6*NTESTS ; i+=6) { sort6_fast(d+i); } cycles = rdtsc() - cycles; printf("Time is %.2lf\n", (double)cycles/(double)NTESTS); for (i = 0; i < 6*NTESTS ; i+=6) { if (d[i+0] > d[i+1] || d[i+1] > d[i+2] || d[i+2] > d[i+3] || d[i+3] > d[i+4] || d[i+4] > d[i+5]) printf("d%d : %d %d %d %d %d %d\n", i, d[i+0], d[i+1], d[i+2], d[i+3], d[i+4], d[i+5]); } return 0; } 

Modifiqué el conjunto de pruebas modificado para informar también relojes por clasificación y ejecutar más pruebas (la función cmp también se actualizó para manejar el desbordamiento de enteros), aquí están los resultados en algunas architectures diferentes. Intenté probar en una CPU AMD pero rdtsc no es confiable en el X6 1100T que tengo disponible.

 Clarkdale (i5-650) ================== Direct call to qsort library function 635.14 575.65 581.61 577.76 521.12 Naive implementation (insertion sort) 538.30 135.36 134.89 240.62 101.23 Insertion Sort (Daniel Stutzbach) 424.48 159.85 160.76 152.01 151.92 Insertion Sort Unrolled 339.16 125.16 125.81 129.93 123.16 Rank Order 184.34 106.58 54.74 93.24 94.09 Rank Order with registers 127.45 104.65 53.79 98.05 97.95 Sorting Networks (Daniel Stutzbach) 269.77 130.56 128.15 126.70 127.30 Sorting Networks (Paul R) 551.64 103.20 64.57 73.68 73.51 Sorting Networks 12 with Fast Swap 321.74 61.61 63.90 67.92 67.76 Sorting Networks 12 reordered Swap 318.75 60.69 65.90 70.25 70.06 Reordered Sorting Network w/ fast swap 145.91 34.17 32.66 32.22 32.18 Kentsfield (Core 2 Quad) ======================== Direct call to qsort library function 870.01 736.39 723.39 725.48 721.85 Naive implementation (insertion sort) 503.67 174.09 182.13 284.41 191.10 Insertion Sort (Daniel Stutzbach) 345.32 152.84 157.67 151.23 150.96 Insertion Sort Unrolled 316.20 133.03 129.86 118.96 105.06 Rank Order 164.37 138.32 46.29 99.87 99.81 Rank Order with registers 115.44 116.02 44.04 116.04 116.03 Sorting Networks (Daniel Stutzbach) 230.35 114.31 119.15 110.51 111.45 Sorting Networks (Paul R) 498.94 77.24 63.98 62.17 65.67 Sorting Networks 12 with Fast Swap 315.98 59.41 58.36 60.29 55.15 Sorting Networks 12 reordered Swap 307.67 55.78 51.48 51.67 50.74 Reordered Sorting Network w/ fast swap 149.68 31.46 30.91 31.54 31.58 Sandy Bridge (i7-2600k) ======================= Direct call to qsort library function 559.97 451.88 464.84 491.35 458.11 Naive implementation (insertion sort) 341.15 160.26 160.45 154.40 106.54 Insertion Sort (Daniel Stutzbach) 284.17 136.74 132.69 123.85 121.77 Insertion Sort Unrolled 239.40 110.49 114.81 110.79 117.30 Rank Order 114.24 76.42 45.31 36.96 36.73 Rank Order with registers 105.09 32.31 48.54 32.51 33.29 Sorting Networks (Daniel Stutzbach) 210.56 115.68 116.69 107.05 124.08 Sorting Networks (Paul R) 364.03 66.02 61.64 45.70 44.19 Sorting Networks 12 with Fast Swap 246.97 41.36 59.03 41.66 38.98 Sorting Networks 12 reordered Swap 235.39 38.84 47.36 38.61 37.29 Reordered Sorting Network w/ fast swap 115.58 27.23 27.75 27.25 26.54 Nehalem (Xeon E5640) ==================== Direct call to qsort library function 911.62 890.88 681.80 876.03 872.89 Naive implementation (insertion sort) 457.69 236.87 127.68 388.74 175.28 Insertion Sort (Daniel Stutzbach) 317.89 279.74 147.78 247.97 245.09 Insertion Sort Unrolled 259.63 220.60 116.55 221.66 212.93 Rank Order 140.62 197.04 52.10 163.66 153.63 Rank Order with registers 84.83 96.78 50.93 109.96 54.73 Sorting Networks (Daniel Stutzbach) 214.59 220.94 118.68 120.60 116.09 Sorting Networks (Paul R) 459.17 163.76 56.40 61.83 58.69 Sorting Networks 12 with Fast Swap 284.58 95.01 50.66 53.19 55.47 Sorting Networks 12 reordered Swap 281.20 96.72 44.15 56.38 54.57 Reordered Sorting Network w/ fast swap 128.34 50.87 26.87 27.91 28.02 

El código de prueba es bastante malo; desborda la matriz inicial (¿no leen las personas aquí las advertencias del comstackdor?), printf está imprimiendo los elementos incorrectos, utiliza .byte para rdtsc sin una buena razón, solo hay una ejecución (!), no hay nada que compruebe que el los resultados finales son realmente correctos (por lo que es muy fácil “optimizar” algo sutilmente incorrecto), las pruebas incluidas son muy rudimentarias (¿no hay números negativos?) y no hay nada que impida que el comstackdor descarte toda la función como código muerto.

Dicho esto, también es bastante fácil mejorar la solución de red bitónica; simplemente cambie las cosas min / max / SWAP a

 #define SWAP(x,y) { int tmp; asm("mov %0, %2 ; cmp %1, %0 ; cmovg %1, %0 ; cmovg %2, %1" : "=r" (d[x]), "=r" (d[y]), "=r" (tmp) : "0" (d[x]), "1" (d[y]) : "cc"); } 

y me sale un 65% más rápido (Debian gcc 4.4.5 con -O2, amd64, Core i7).

Me encontré con esta pregunta de Google hace unos días porque también tuve la necesidad de ordenar rápidamente una matriz de longitud fija de 6 enteros. En mi caso, sin embargo, mis enteros son solo 8 bits (en lugar de 32) y no tengo un requisito estricto de usar solo C. Pensé que compartiría mis hallazgos de todos modos, en caso de que pudieran ser útiles para alguien …

Implementé una variante de una ordenación de red en ensamblaje que usa SSE para vectorizar las operaciones de comparación e intercambio, en la medida de lo posible. Se necesitan seis “pases” para ordenar completamente la matriz. Utilicé un mecanismo novedoso para convertir directamente los resultados de PCMPGTB (comparación vectorizada) a los parámetros aleatorios para PSHUFB (intercambio vectorizado), usando solo un PADDB (complemento vectorizado) y en algunos casos también una instrucción PAND (AND a nivel de bit).

Este enfoque también tuvo el efecto secundario de producir una función verdaderamente sin sucursales. No hay instrucciones de salto en absoluto.

Parece que esta implementación es aproximadamente un 38% más rápida que la implementación que actualmente está marcada como la opción más rápida en la pregunta (“Clasificación de redes 12 con intercambio simple”). Modifiqué esa implementación para usar elementos de arreglo de caracteres durante mi prueba, para que la comparación sea justa.

Debo señalar que este enfoque se puede aplicar a cualquier tamaño de matriz de hasta 16 elementos. Espero que la ventaja de velocidad relativa sobre las alternativas crezca para las matrices más grandes.

El código está escrito en MASM para procesadores x86_64 con SSSE3. La función usa la “nueva” convención de llamadas de Windows x64. Aquí está…

 PUBLIC simd_sort_6 .DATA ALIGN 16 pass1_shuffle OWORD 0F0E0D0C0B0A09080706040503010200h pass1_add OWORD 0F0E0D0C0B0A09080706050503020200h pass2_shuffle OWORD 0F0E0D0C0B0A09080706030405000102h pass2_and OWORD 00000000000000000000FE00FEFE00FEh pass2_add OWORD 0F0E0D0C0B0A09080706050405020102h pass3_shuffle OWORD 0F0E0D0C0B0A09080706020304050001h pass3_and OWORD 00000000000000000000FDFFFFFDFFFFh pass3_add OWORD 0F0E0D0C0B0A09080706050404050101h pass4_shuffle OWORD 0F0E0D0C0B0A09080706050100020403h pass4_and OWORD 0000000000000000000000FDFD00FDFDh pass4_add OWORD 0F0E0D0C0B0A09080706050403020403h pass5_shuffle OWORD 0F0E0D0C0B0A09080706050201040300h pass5_and OWORD 0000000000000000000000FEFEFEFE00h pass5_add OWORD 0F0E0D0C0B0A09080706050403040300h pass6_shuffle OWORD 0F0E0D0C0B0A09080706050402030100h pass6_add OWORD 0F0E0D0C0B0A09080706050403030100h .CODE simd_sort_6 PROC FRAME .endprolog ; pxor xmm4, xmm4 ; pinsrd xmm4, dword ptr [rcx], 0 ; pinsrb xmm4, byte ptr [rcx + 4], 4 ; pinsrb xmm4, byte ptr [rcx + 5], 5 ; The benchmarked 38% faster mentioned in the text was with the above slower sequence that tied up the shuffle port longer. Same on extract ; avoiding pins/extrb also means we don't need SSE 4.1, but SSSE3 CPUs without SSE4.1 (eg Conroe/Merom) have slow pshufb. movd xmm4, dword ptr [rcx] pinsrw xmm4, word ptr [rcx + 4], 2 ; word 2 = bytes 4 and 5 movdqa xmm5, xmm4 pshufb xmm5, oword ptr [pass1_shuffle] pcmpgtb xmm5, xmm4 paddb xmm5, oword ptr [pass1_add] pshufb xmm4, xmm5 movdqa xmm5, xmm4 pshufb xmm5, oword ptr [pass2_shuffle] pcmpgtb xmm5, xmm4 pand xmm5, oword ptr [pass2_and] paddb xmm5, oword ptr [pass2_add] pshufb xmm4, xmm5 movdqa xmm5, xmm4 pshufb xmm5, oword ptr [pass3_shuffle] pcmpgtb xmm5, xmm4 pand xmm5, oword ptr [pass3_and] paddb xmm5, oword ptr [pass3_add] pshufb xmm4, xmm5 movdqa xmm5, xmm4 pshufb xmm5, oword ptr [pass4_shuffle] pcmpgtb xmm5, xmm4 pand xmm5, oword ptr [pass4_and] paddb xmm5, oword ptr [pass4_add] pshufb xmm4, xmm5 movdqa xmm5, xmm4 pshufb xmm5, oword ptr [pass5_shuffle] pcmpgtb xmm5, xmm4 pand xmm5, oword ptr [pass5_and] paddb xmm5, oword ptr [pass5_add] pshufb xmm4, xmm5 movdqa xmm5, xmm4 pshufb xmm5, oword ptr [pass6_shuffle] pcmpgtb xmm5, xmm4 paddb xmm5, oword ptr [pass6_add] pshufb xmm4, xmm5 ;pextrd dword ptr [rcx], xmm4, 0 ; benchmarked with this ;pextrb byte ptr [rcx + 4], xmm4, 4 ; slower version ;pextrb byte ptr [rcx + 5], xmm4, 5 movd dword ptr [rcx], xmm4 pextrw word ptr [rcx + 4], xmm4, 2 ; x86 is little-endian, so this is the right order ret simd_sort_6 ENDP END 

Puede comstackr esto en un objeto ejecutable y vincularlo a su proyecto C. Para obtener instrucciones sobre cómo hacer esto en Visual Studio, puede leer este artículo . Puede usar el siguiente prototipo C para llamar a la función desde su código C:

 void simd_sort_6(char *values); 

Aunque me gusta mucho el macro swap proporcionado:

 #define min(x, y) (y ^ ((x ^ y) & -(x < y))) #define max(x, y) (x ^ ((x ^ y) & -(x < y))) #define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; } 

Veo una mejora (que un buen comstackdor podría hacer):

 #define SWAP(x,y) { int tmp = ((x ^ y) & -(y < x)); y ^= tmp; x ^= tmp; } 

Tomamos nota de cómo min y max funcionan y extraemos la sub-expresión común explícitamente. This eliminates the min and max macros completely.

Never optimize min/max without benchmarking and looking at actual compiler generated assembly. If I let GCC optimize min with conditional move instructions I get a 33% speedup:

 #define SWAP(x,y) { int dx = d[x], dy = d[y], tmp; tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; } 

(280 vs. 420 cycles in the test code). Doing max with ?: is more or less the same, almost lost in the noise, but the above is a little bit faster. This SWAP is faster with both GCC and Clang.

Compilers are also doing an exceptional job at register allocation and alias analysis, effectively moving d[x] into local variables upfront, and only copying back to memory at the end. In fact, they do so even better than if you worked entirely with local variables (like d0 = d[0], d1 = d[1], d2 = d[2], d3 = d[3], d4 = d[4], d5 = d[5] ). I'm writing this because you are assuming strong optimization and yet trying to outsmart the compiler on min/max. 🙂

By the way, I tried Clang and GCC. They do the same optimization, but due to scheduling differences the two have some variation in the results, can't say really which is faster or slower. GCC is faster on the sorting networks, Clang on the quadratic sorts.

Just for completeness, unrolled bubble sort and insertion sorts are possible too. Here is the bubble sort:

 SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4); SWAP(4,5); SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4); SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(0,1); SWAP(1,2); SWAP(0,1); 

and here is the insertion sort:

 //#define ITER(x) { if (t < d[x]) { d[x+1] = d[x]; d[x] = t; } } //Faster on x86, probably slower on ARM or similar: #define ITER(x) { d[x+1] ^= t < d[x] ? d[x] ^ d[x+1] : 0; d[x] = t < d[x] ? t : d[x]; } static inline void sort6_insertion_sort_unrolled_v2(int * d){ int t; t = d[1]; ITER(0); t = d[2]; ITER(1); ITER(0); t = d[3]; ITER(2); ITER(1); ITER(0); t = d[4]; ITER(3); ITER(2); ITER(1); ITER(0); t = d[5]; ITER(4); ITER(3); ITER(2); ITER(1); ITER(0); 

This insertion sort is faster than Daniel Stutzbach's, and is especially good on a GPU or a computer with predication because ITER can be done with only 3 instructions (vs. 4 for SWAP). For example, here is the t = d[2]; ITER(1); ITER(0); line in ARM assembly:

  MOV r6, r2 CMP r6, r1 MOVLT r2, r1 MOVLT r1, r6 CMP r6, r0 MOVLT r1, r0 MOVLT r0, r6 

For six elements the insertion sort is competitive with the sorting network (12 swaps vs. 15 iterations balances 4 instructions/swap vs. 3 instructions/iteration); bubble sort of course is slower. But it's not going to be true when the size grows, since insertion sort is O(n^2) while sorting networks are O(n log n).

I ported the test suite to a PPC architecture machine I can not identify (didn’t have to touch code, just increase the iterations of the test, use 8 test cases to avoid polluting results with mods and replace the x86 specific rdtsc):

Direct call to qsort library function : 101

Naive implementation (insertion sort) : 299

Insertion Sort (Daniel Stutzbach) : 108

Insertion Sort Unrolled : 51

Sorting Networks (Daniel Stutzbach) : 26

Sorting Networks (Paul R) : 85

Sorting Networks 12 with Fast Swap : 117

Sorting Networks 12 reordered Swap : 116

Rank Order : 56

An XOR swap may be useful in your swapping functions.

 void xorSwap (int *x, int *y) { if (*x != *y) { *x ^= *y; *y ^= *x; *x ^= *y; } } 

The if may cause too much divergence in your code, but if you have a guarantee that all your ints are unique this could be handy.

Looking forward to trying my hand at this and learning from these examples, but first some timings from my 1.5 GHz PPC Powerbook G4 w/ 1 GB DDR RAM. (I borrowed a similar rdtsc-like timer for PPC from http://www.mcs.anl.gov/~kazutomo/rdtsc.html for the timings.) I ran the program a few times and the absolute results varied but the consistently fastest test was “Insertion Sort (Daniel Stutzbach)”, with “Insertion Sort Unrolled” a close second.

Here’s the last set of times:

 **Direct call to qsort library function** : 164 **Naive implementation (insertion sort)** : 138 **Insertion Sort (Daniel Stutzbach)** : 85 **Insertion Sort Unrolled** : 97 **Sorting Networks (Daniel Stutzbach)** : 457 **Sorting Networks (Paul R)** : 179 **Sorting Networks 12 with Fast Swap** : 238 **Sorting Networks 12 reordered Swap** : 236 **Rank Order** : 116 

Here is my contribution to this thread: an optimized 1, 4 gap shellsort for a 6-member int vector (valp) containing unique values.

 void shellsort (int *valp) { int c,a,*cp,*ip=valp,*ep=valp+5; c=*valp; a=*(valp+4);if (c>a) {*valp= a;*(valp+4)=c;} c=*(valp+1);a=*(valp+5);if (c>a) {*(valp+1)=a;*(valp+5)=c;} cp=ip; do { c=*cp; a=*(cp+1); do { if (c=valp); ip+=1; cp=ip; } while (ip 

On my HP dv7-3010so laptop with a dual-core Athlon M300 @ 2 Ghz (DDR2 memory) it executes in 165 clock cycles. This is an average calculated from timing every unique sequence (6!/720 in all). Compiled to Win32 using OpenWatcom 1.8. The loop is essentially an insertion sort and is 16 instructions/37 bytes long.

I do not have a 64-bit environment to compile on.

If insertion sort is reasonably competitive here, I would recommend trying a shellsort. I’m afraid 6 elements is probably just too little for it to be among the best, but it might be worth a try.

Example code, untested, undebugged, etc. You want to tune the inc = 4 and inc -= 3 sequence to find the optimum (try inc = 2, inc -= 1 for example).

 static __inline__ int sort6(int * d) { char j, i; int tmp; for (inc = 4; inc > 0; inc -= 3) { for (i = inc; i < 5; i++) { tmp = a[i]; j = i; while (j >= inc && a[j - inc] > tmp) { a[j] = a[j - inc]; j -= inc; } a[j] = tmp; } } } 

I don’t think this will win, but if someone posts a question about sorting 10 elements, who knows…

According to Wikipedia this can even be combined with sorting networks: Pratt, V (1979). Shellsort and sorting networks (Outstanding dissertations in the computer sciences). Guirnalda. ISBN 0-824-04406-1

This question is becoming quite old, but I actually had to solve the same problem these days: fast agorithms to sort small arrays. I thought it would be a good idea to share my knowledge. While I first started by using sorting networks, I finally managed to find other algorithms for which the total number of comparisons performed to sort every permutation of 6 values was smaller than with sorting networks, and smaller than with insertion sort. I didn’t count the number of swaps; I would expect it to be roughly equivalent (maybe a bit higher sometimes).

The algorithm sort6 uses the algorithm sort4 which uses the algorithm sort3 . Here is the implementation in some light C++ form (the original is template-heavy so that it can work with any random-access iterator and any suitable comparison function).

Sorting 3 values

The following algorithm is an unrolled insertion sort. When two swaps (6 assignments) have to be performed, it uses 4 assignments instead:

 void sort3(int* array) { if (array[1] < array[0]) { if (array[2] < array[0]) { if (array[2] < array[1]) { std::swap(array[0], array[2]); } else { int tmp = array[0]; array[0] = array[1]; array[1] = array[2]; array[2] = tmp; } } else { std::swap(array[0], array[1]); } } else { if (array[2] < array[1]) { if (array[2] < array[0]) { int tmp = array[2]; array[2] = array[1]; array[1] = array[0]; array[0] = tmp; } else { std::swap(array[1], array[2]); } } } } 

It looks a bit complex because the sort has more or less one branch for every possible permutation of the array, using 2~3 comparisons and at most 4 assignments to sort the three values.

Sorting 4 values

This one calls sort3 then performs an unrolled insertion sort with the last element of the array:

 void sort4(int* array) { // Sort the first 3 elements sort3(array); // Insert the 4th element with insertion sort if (array[3] < array[2]) { std::swap(array[2], array[3]); if (array[2] < array[1]) { std::swap(array[1], array[2]); if (array[1] < array[0]) { std::swap(array[0], array[1]); } } } } 

This algorithm performs 3 to 6 comparisons and at most 5 swaps. It is easy to unroll an insertion sort, but we will be using another algorithm for the last sort...

Sorting 6 values

This one uses an unrolled version of what I called a double insertion sort . The name isn't that great, but it's quite descriptive, here is how it works:

  • Sort everything but the first and the last elements of the array.
  • Swap the first and the elements of the array if the first is greater than the last.
  • Insert the first element into the sorted sequence from the front then the last element from the back.

After the swap, the first element is always smaller than the last, which means that, when inserting them into the sorted sequence, there won't be more than N comparisons to insert the two elements in the worst case: for example, if the first element has been insert in the 3rd position, then the last one can't be inserted lower than the 4th position.

 void sort6(int* array) { // Sort everything but first and last elements sort4(array+1); // Switch first and last elements if needed if (array[5] < array[0]) { std::swap(array[0], array[5]); } // Insert first element from the front if (array[1] < array[0]) { std::swap(array[0], array[1]); if (array[2] < array[1]) { std::swap(array[1], array[2]); if (array[3] < array[2]) { std::swap(array[2], array[3]); if (array[4] < array[3]) { std::swap(array[3], array[4]); } } } } // Insert last element from the back if (array[5] < array[4]) { std::swap(array[4], array[5]); if (array[4] < array[3]) { std::swap(array[3], array[4]); if (array[3] < array[2]) { std::swap(array[2], array[3]); if (array[2] < array[1]) { std::swap(array[1], array[2]); } } } } } 

My tests on every permutation of 6 values ever show that this algorithms always performs between 6 and 13 comparisons. I didn't compute the number of swaps performed, but I don't expect it to be higher than 11 in the worst case.

I hope that this helps, even if this question may not represent an actual problem anymore 🙂

EDIT: after putting it in the provided benchmark, it is cleary slower than most of the interesting alternatives. It tends to perform a bit better than the unrolled insertion sort, but that's pretty much it. Basically, it isn't the best sort for integers but could be interesting for types with an expensive comparison operation.

I know I’m super-late, but I was interested in experimenting with some different solutions. First, I cleaned up that paste, made it compile, and put it into a repository. I kept some undesirable solutions as dead-ends so that others wouldn’t try it. Among this was my first solution, which attempted to ensure that x1>x2 was calculated once. After optimization, it is no faster than the other, simple versions.

I added a looping version of rank order sort, since my own application of this study is for sorting 2-8 items, so since there are a variable number of arguments, a loop is necessary. This is also why I ignored the sorting network solutions.

The test code didn’t test that duplicates were handled correctly, so while the existing solutions were all correct, I added a special case to the test code to ensure that duplicates were handled correctly.

Then, I wrote an insertion sort that is entirely in AVX registers. On my machine it is 25% faster than the other insertion sorts, but 100% slower than rank order. I did this purely for experiment and had no expectation of this being better due to the branching in insertion sort.

 static inline void sort6_insertion_sort_avx(int* d) { __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], 0, 0); __m256i index = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7); __m256i shlpermute = _mm256_setr_epi32(7, 0, 1, 2, 3, 4, 5, 6); __m256i sorted = _mm256_setr_epi32(d[0], INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX); __m256i val, gt, permute; unsigned j; // 8 / 32 = 2^-2 #define ITER(I) \ val = _mm256_permutevar8x32_epi32(src, _mm256_set1_epi32(I));\ gt = _mm256_cmpgt_epi32(sorted, val);\ permute = _mm256_blendv_epi8(index, shlpermute, gt);\ j = ffs( _mm256_movemask_epi8(gt)) >> 2;\ sorted = _mm256_blendv_epi8(_mm256_permutevar8x32_epi32(sorted, permute),\ val, _mm256_cmpeq_epi32(index, _mm256_set1_epi32(j))) ITER(1); ITER(2); ITER(3); ITER(4); ITER(5); int x[8]; _mm256_storeu_si256((__m256i*)x, sorted); d[0] = x[0]; d[1] = x[1]; d[2] = x[2]; d[3] = x[3]; d[4] = x[4]; d[5] = x[5]; #undef ITER } 

Then, I wrote a rank order sort using AVX. This matches the speed of the other rank-order solutions, but is no faster. The issue here is that I can only calculate the indices with AVX, and then I have to make a table of indices. This is because the calculation is destination-based rather than source-based. See Converting from Source-based Indices to Destination-based Indices

 static inline void sort6_rank_order_avx(int* d) { __m256i ror = _mm256_setr_epi32(5, 0, 1, 2, 3, 4, 6, 7); __m256i one = _mm256_set1_epi32(1); __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], INT_MAX, INT_MAX); __m256i rot = src; __m256i index = _mm256_setzero_si256(); __m256i gt, permute; __m256i shl = _mm256_setr_epi32(1, 2, 3, 4, 5, 6, 6, 6); __m256i dstIx = _mm256_setr_epi32(0,1,2,3,4,5,6,7); __m256i srcIx = dstIx; __m256i eq = one; __m256i rotIx = _mm256_setzero_si256(); #define INC(I)\ rot = _mm256_permutevar8x32_epi32(rot, ror);\ gt = _mm256_cmpgt_epi32(src, rot);\ index = _mm256_add_epi32(index, _mm256_and_si256(gt, one));\ index = _mm256_add_epi32(index, _mm256_and_si256(eq,\ _mm256_cmpeq_epi32(src, rot)));\ eq = _mm256_insert_epi32(eq, 0, I) INC(0); INC(1); INC(2); INC(3); INC(4); int e[6]; e[0] = d[0]; e[1] = d[1]; e[2] = d[2]; e[3] = d[3]; e[4] = d[4]; e[5] = d[5]; int i[8]; _mm256_storeu_si256((__m256i*)i, index); d[i[0]] = e[0]; d[i[1]] = e[1]; d[i[2]] = e[2]; d[i[3]] = e[3]; d[i[4]] = e[4]; d[i[5]] = e[5]; } 

The repo can be found here: https://github.com/eyepatchParrot/sort6/

I believe there are two parts to your question.

  • The first is to determine the optimal algorithm. This is done – at least in this case – by looping through every possible ordering (there aren’t that many) which allows you to compute exact min, max, average and standard deviation of compares and swaps. Have a runner-up or two handy as well.
  • The second is to optimize the algorithm. A lot can be done to convert textbook code examples to mean and lean real-life algorithms. If you realize that an algorithm can’t be optimized to the extent required, try a runner-up.

I wouldn’t worry too much about emptying pipelines (assuming current x86): branch prediction has come a long way. What I would worry about is making sure that the code and data fit in one cache line each (maybe two for the code). Once there fetch latencies are refreshingly low which will compensate for any stall. It also means that your inner loop will be maybe ten instructions or so which is right where it should be (there are two different inner loops in my sorting algorithm, they are 10 instructions/22 bytes and 9/22 long respectively). Assuming the code doesn’t contain any divs you can be sure it will be blindingly fast.

I found that at least on my system, the functions sort6_iterator() and sort6_iterator_local() defined below both ran at least as fast, and frequently noticeably faster, than the above current record holder:

 #define MIN(x, y) (x inline void sort6_iterator(IterType it) { #define SWAP(x,y) { const auto a = MIN(*(it + x), *(it + y)); \ const auto b = MAX(*(it + x), *(it + y)); \ *(it + x) = a; *(it + 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 } 

I passed this function a std::vector ‘s iterator in my timing code. I suspect that using iterators gives g++ certain assurances about what can and can’t happen to the memory that the iterator refers to, which it otherwise wouldn’t have and it is these assurances that allow g++ to better optimize the sorting code (which if I remember correctly, is also part of the reason why so many std algorithms, such as std::sort() , generally have such obscenely good performance). However, while timing I noticed that the context (ie surrounding code) in which the call to the sorting function was made had a significant impact on performance, which is likely due to the function being inlined and then optimized. For instance, if the program was sufficiently simple then there usually wasn’t much of a difference in performance between passing the sorting function a pointer versus passing it an iterator; otherwise using iterators usually resulted in noticeably better performance and never (in my experience so far at least) any noticeably worse performance. I suspect that this may be because g++ can globally optimize sufficiently simple code.

Moreover, sort6_iterator() is some times (again, depending on the context in which the function is called) consistently outperformed by the following sorting function:

 template inline void sort6_iterator_local(IterType it) { #define SWAP(x,y) { const auto a = MIN(data##x, data##y); \ const auto b = MAX(data##x, data##y); \ data##x = a; data##y = b; } //DD = Define Data #define DD1(a) auto data##a = *(it + a); #define DD2(a,b) auto data##a = *(it + a), data##b = *(it + b); //CB = Copy Back #define CB(a) *(it + a) = data##a; DD2(1,2) SWAP(1, 2) DD2(4,5) SWAP(4, 5) DD1(0) SWAP(0, 2) DD1(3) SWAP(3, 5) SWAP(0, 1) SWAP(3, 4) SWAP(1, 4) SWAP(0, 3) CB(0) SWAP(2, 5) CB(5) SWAP(1, 3) CB(1) SWAP(2, 4) CB(4) SWAP(2, 3) CB(2) CB(3) #undef CB #undef DD2 #undef DD1 #undef SWAP } 

Note that defining SWAP() as follows some times results in slightly better performance although most of the time it results in slightly worse performance or a negligible difference in performance.

 #define SWAP(x,y) { const auto a = MIN(data##x, data##y); \ data##y = MAX(data##x, data##y); \ data##x = a; } 

If you just want a sorting algorithm that gcc -O3 is consistently good at optimizing then, depending on how you pass the input, try one of the following two algorithms:

 template inline void sort6(T it) { #define SORT2(x,y) {if(data##x>data##y){auto a=std::move(data##y);data##y=std::move(data##x);data##x=std::move(a);}} #define DD1(a) register auto data##a=*(it+a); #define DD2(a,b) register auto data##a=*(it+a);register auto data##b=*(it+b); #define CB1(a) *(it+a)=data##a; #define CB2(a,b) *(it+a)=data##a;*(it+b)=data##b; DD2(1,2) SORT2(1,2) DD2(4,5) SORT2(4,5) DD1(0) SORT2(0,2) DD1(3) SORT2(3,5) SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5) SORT2(1,4) SORT2(0,3) CB1(0) SORT2(2,4) CB1(4) SORT2(1,3) CB1(1) SORT2(2,3) CB2(2,3) #undef CB1 #undef CB2 #undef DD1 #undef DD2 #undef SORT2 } 

O

 template inline void sort6(T& e0, T& e1, T& e2, T& e3, T& e4, T& e5) { #define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);} #define DD1(a) register auto data##a=e##a; #define DD2(a,b) register auto data##a=e##a;register auto data##b=e##b; #define CB1(a) e##a=data##a; #define CB2(a,b) e##a=data##a;e##b=data##b; DD2(1,2) SORT2(1,2) DD2(4,5) SORT2(4,5) DD1(0) SORT2(0,2) DD1(3) SORT2(3,5) SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5) SORT2(1,4) SORT2(0,3) CB1(0) SORT2(2,4) CB1(4) SORT2(1,3) CB1(1) SORT2(2,3) CB2(2,3) #undef CB1 #undef CB2 #undef DD1 #undef DD2 #undef SORT2 } 

The reason for using the register keyword is because this is one of the few times that you know that you want these values in registers. Without register , the compiler will figure this out most of the time but sometimes it doesn’t. Using the register keyword helps solve this issue. Normally, however, don’t use the register keyword since it’s more likely to slow your code than speed it up.

Also, note the use of templates. This is done on purpose since, even with the inline keyword, template functions are generally much more aggressively optimized by gcc than vanilla C functions (this has to do with gcc needing to deal with function pointers for vanilla C functions but not with template functions).

I know this is an old question.

But I just wrote a different kind of solution I want to share.
Using nothing but nested MIN MAX,

It’s not fast as it uses 114 of each,
could reduce it to 75 pretty simply like so -> pastebin

But then it’s not purely min max anymore.

What might work is doing min/max on multiple integers at once with AVX

PMINSW reference

 #include  static __inline__ int MIN(int a, int b){ int result =a; __asm__ ("pminsw %1, %0" : "+x" (result) : "x" (b)); return result; } static __inline__ int MAX(int a, int b){ int result = a; __asm__ ("pmaxsw %1, %0" : "+x" (result) : "x" (b)); return result; } static __inline__ unsigned long long rdtsc(void){ unsigned long long int x; __asm__ volatile (".byte 0x0f, 0x31" : "=A" (x)); return x; } #define MIN3(a, b, c) (MIN(MIN(a,b),c)) #define MIN4(a, b, c, d) (MIN(MIN(a,b),MIN(c,d))) static __inline__ void sort6(int * in) { const int A=in[0], B=in[1], C=in[2], D=in[3], E=in[4], F=in[5]; in[0] = MIN( MIN4(A,B,C,D),MIN(E,F) ); const int AB = MAX(A, B), AC = MAX(A, C), AD = MAX(A, D), AE = MAX(A, E), AF = MAX(A, F), BC = MAX(B, C), BD = MAX(B, D), BE = MAX(B, E), BF = MAX(B, F), CD = MAX(C, D), CE = MAX(C, E), CF = MAX(C, F), DE = MAX(D, E), DF = MAX(D, F), EF = MAX(E, F); in[1] = MIN4 ( MIN4( AB, AC, AD, AE ), MIN4( AF, BC, BD, BE ), MIN4( BF, CD, CE, CF ), MIN3( DE, DF, EF) ); const int ABC = MAX(AB,C), ABD = MAX(AB,D), ABE = MAX(AB,E), ABF = MAX(AB,F), ACD = MAX(AC,D), ACE = MAX(AC,E), ACF = MAX(AC,F), ADE = MAX(AD,E), ADF = MAX(AD,F), AEF = MAX(AE,F), BCD = MAX(BC,D), BCE = MAX(BC,E), BCF = MAX(BC,F), BDE = MAX(BD,E), BDF = MAX(BD,F), BEF = MAX(BE,F), CDE = MAX(CD,E), CDF = MAX(CD,F), CEF = MAX(CE,F), DEF = MAX(DE,F); in[2] = MIN( MIN4 ( MIN4( ABC, ABD, ABE, ABF ), MIN4( ACD, ACE, ACF, ADE ), MIN4( ADF, AEF, BCD, BCE ), MIN4( BCF, BDE, BDF, BEF )), MIN4( CDE, CDF, CEF, DEF ) ); const int ABCD = MAX(ABC,D), ABCE = MAX(ABC,E), ABCF = MAX(ABC,F), ABDE = MAX(ABD,E), ABDF = MAX(ABD,F), ABEF = MAX(ABE,F), ACDE = MAX(ACD,E), ACDF = MAX(ACD,F), ACEF = MAX(ACE,F), ADEF = MAX(ADE,F), BCDE = MAX(BCD,E), BCDF = MAX(BCD,F), BCEF = MAX(BCE,F), BDEF = MAX(BDE,F), CDEF = MAX(CDE,F); in[3] = MIN4 ( MIN4( ABCD, ABCE, ABCF, ABDE ), MIN4( ABDF, ABEF, ACDE, ACDF ), MIN4( ACEF, ADEF, BCDE, BCDF ), MIN3( BCEF, BDEF, CDEF ) ); const int ABCDE= MAX(ABCD,E), ABCDF= MAX(ABCD,F), ABCEF= MAX(ABCE,F), ABDEF= MAX(ABDE,F), ACDEF= MAX(ACDE,F), BCDEF= MAX(BCDE,F); in[4]= MIN ( MIN4( ABCDE, ABCDF, ABCEF, ABDEF ), MIN ( ACDEF, BCDEF ) ); in[5] = MAX(ABCDE,F); } int main(int argc, char ** argv) { int d[6][6] = { {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 (int i = 0; i < 6; i++) { sort6(d[i]); } cycles = rdtsc() - cycles; printf("Time is %d\n", (unsigned)cycles); for (int i = 0; i < 6; i++) { printf("d%d : %d %d %d %d %d %d\n", i, d[i][0], d[i][1], d[i][2], d[i][3], d[i][4], d[i][5]); } } 

EDITAR:
Rank order solution inspired by Rex Kerr's, Much faster than the mess above

 static void sort6(int *o) { const int A=o[0],B=o[1],C=o[2],D=o[3],E=o[4],F=o[5]; const unsigned char AB = A>B, AC = A>C, AD = A>D, AE = A>E, BC = B>C, BD = B>D, BE = B>E, CD = C>D, CE = C>E, DE = D>E, a = AB + AC + AD + AE + (A>F), b = 1 - AB + BC + BD + BE + (B>F), c = 2 - AC - BC + CD + CE + (C>F), d = 3 - AD - BD - CD + DE + (D>F), e = 4 - AE - BE - CE - DE + (E>F); o[a]=A; o[b]=B; o[c]=C; o[d]=D; o[e]=E; o[15-abcde]=F; } 

Maybe I am late to the party, but at least my contribution is a new approach.

  • The code really should be inlined
  • even if inlined, there are too many branches
  • the analysing part is basically O(N(N-1)) which seems OK for N=6
  • the code could be more effective if the cost of swap would be higher (irt the cost of compare )
  • I trust on static functions being inlined.
  • The method is related to rank-sort
    • instead of ranks, the relative ranks (offsets) are used.
    • the sum of the ranks is zero for every cycle in any permutation group.
    • instead of SWAP() ing two elements, the cycles are chased, needing only one temp, and one (register->register) swap (new <- old).

Update: changed the code a bit, some people use C++ compilers to compile C code …

 #include  #if WANT_CHAR typedef signed char Dif; #else typedef signed int Dif; #endif static int walksort (int *arr, int cnt); static void countdifs (int *arr, Dif *dif, int cnt); static void calcranks(int *arr, Dif *dif); int wsort6(int *arr); void do_print_a(char *msg, int *arr, unsigned cnt) { fprintf(stderr,"%s:", msg); for (; cnt--; arr++) { fprintf(stderr, " %3d", *arr); } fprintf(stderr,"\n"); } void do_print_d(char *msg, Dif *arr, unsigned cnt) { fprintf(stderr,"%s:", msg); for (; cnt--; arr++) { fprintf(stderr, " %3d", (int) *arr); } fprintf(stderr,"\n"); } static void inline countdifs (int *arr, Dif *dif, int cnt) { int top, bot; for (top = 0; top < cnt; top++ ) { for (bot = 0; bot < top; bot++ ) { if (arr[top] < arr[bot]) { dif[top]--; dif[bot]++; } } } return ; } /* Copied from RexKerr ... */ static void inline calcranks(int *arr, Dif *dif){ dif[0] = (arr[0]>arr[1])+(arr[0]>arr[2])+(arr[0]>arr[3])+(arr[0]>arr[4])+(arr[0]>arr[5]); dif[1] = -1+ (arr[1]>=arr[0])+(arr[1]>arr[2])+(arr[1]>arr[3])+(arr[1]>arr[4])+(arr[1]>arr[5]); dif[2] = -2+ (arr[2]>=arr[0])+(arr[2]>=arr[1])+(arr[2]>arr[3])+(arr[2]>arr[4])+(arr[2]>arr[5]); dif[3] = -3+ (arr[3]>=arr[0])+(arr[3]>=arr[1])+(arr[3]>=arr[2])+(arr[3]>arr[4])+(arr[3]>arr[5]); dif[4] = -4+ (arr[4]>=arr[0])+(arr[4]>=arr[1])+(arr[4]>=arr[2])+(arr[4]>=arr[3])+(arr[4]>arr[5]); dif[5] = -(dif[0]+dif[1]+dif[2]+dif[3]+dif[4]); } static int walksort (int *arr, int cnt) { int idx, src,dst, nswap; Dif difs[cnt]; #if WANT_REXK calcranks(arr, difs); #else for (idx=0; idx < cnt; idx++) difs[idx] =0; countdifs(arr, difs, cnt); #endif calcranks(arr, difs); #define DUMP_IT 0 #if DUMP_IT do_print_d("ISteps ", difs, cnt); #endif nswap = 0; for (idx=0; idx < cnt; idx++) { int newval; int step,cyc; if ( !difs[idx] ) continue; newval = arr[idx]; cyc = 0; src = idx; do { int oldval; step = difs[src]; difs[src] =0; dst = src + step; cyc += step ; if(dst == idx+1)idx=dst; oldval = arr[dst]; #if (DUMP_IT&1) fprintf(stderr, "[Nswap=%d] Cyc=%d Step=%2d Idx=%d Old=%2d New=%2d #### Src=%d Dst=%d[%2d]->%2d <-- %d\n##\n" , nswap, cyc, step, idx, oldval, newval , src, dst, difs[dst], arr[dst] , newval ); do_print_a("Array ", arr, cnt); do_print_d("Steps ", difs, cnt); #endif arr[dst] = newval; newval = oldval; nswap++; src = dst; } while( cyc); } return nswap; } /*************/ int wsort6(int *arr) { return walksort(arr, 6); } 

Well, if it’s only 6 elements and you can leverage parallelism, want to minimize conditional branching, etc. Why you don’t generate all the combinations and test for order? I would venture that in some architectures, it can be pretty fast (as long as you have the memory preallocated)

Try ‘merging sorted list’ sort. 🙂 Use two array. Fastest for small and big array.
If you concating, you only check where insert. Other bigger values you not need compare (cmp = ab>0).
For 4 numbers, you can use system 4-5 cmp (~4.6) or 3-6 cmp (~4.9). Bubble sort use 6 cmp (6). Lots of cmp for big numbers slower code.
This code use 5 cmp (not MSL sort):
if (cmp(arr[n][i+0],arr[n][i+1])>0) {swap(n,i+0,i+1);} if (cmp(arr[n][i+2],arr[n][i+3])>0) {swap(n,i+2,i+3);} if (cmp(arr[n][i+0],arr[n][i+2])>0) {swap(n,i+0,i+2);} if (cmp(arr[n][i+1],arr[n][i+3])>0) {swap(n,i+1,i+3);} if (cmp(arr[n][i+1],arr[n][i+2])>0) {swap(n,i+1,i+2);}

Principial MSL 9 8 7 6 5 4 3 2 1 0 89 67 45 23 01 ... concat two sorted lists, list length = 1 6789 2345 01 ... concat two sorted lists, list length = 2 23456789 01 ... concat two sorted lists, list length = 4 0123456789 ... concat two sorted lists, list length = 8

js code

 function sortListMerge_2a(cmp) { var step, stepmax, tmp, a,b,c, i,j,k, m,n, cycles; var start = 0; var end = arr_count; //var str = ''; cycles = 0; if (end>3) { stepmax = ((end - start + 1) >> 1) << 1; m = 1; n = 2; for (step=1;step0) {arr[n][k] = arr[m][j]; j++; k++;} else {arr[n][k] = arr[m][i]; i++; k++;} } while (i 

Sort 4 items with usage cmp==0. Numbers of cmp is ~4.34 (FF native have ~4.52), but take 3x time than merging lists. But better less cmp operations, if you have big numbers or big text. Edit: repaird bug

Online test http://mlich.zam.slu.cz/js-sort/x-sort-x2.htm

 function sort4DG(cmp,start,end,n) // sort 4 { var n = typeof(n) !=='undefined' ? n : 1; var cmp = typeof(cmp) !=='undefined' ? cmp : sortCompare2; var start = typeof(start)!=='undefined' ? start : 0; var end = typeof(end) !=='undefined' ? end : arr[n].length; var count = end - start; var pos = -1; var i = start; var cc = []; // stabilni? cc[01] = cmp(arr[n][i+0],arr[n][i+1]); cc[23] = cmp(arr[n][i+2],arr[n][i+3]); if (cc[01]>0) {swap(n,i+0,i+1);} if (cc[23]>0) {swap(n,i+2,i+3);} cc[12] = cmp(arr[n][i+1],arr[n][i+2]); if (!(cc[12]>0)) {return n;} cc[02] = cc[01]==0 ? cc[12] : cmp(arr[n][i+0],arr[n][i+2]); if (cc[02]>0) { swap(n,i+1,i+2); swap(n,i+0,i+1); // bubble last to top cc[13] = cc[23]==0 ? cc[12] : cmp(arr[n][i+1],arr[n][i+3]); if (cc[13]>0) { swap(n,i+2,i+3); swap(n,i+1,i+2); // bubble return n; } else { cc[23] = cc[23]==0 ? cc[12] : (cc[01]==0 ? cc[30] : cmp(arr[n][i+2],arr[n][i+3])); // new cc23 | c03 //repaird if (cc[23]>0) { swap(n,i+2,i+3); return n; } return n; } } else { if (cc[12]>0) { swap(n,i+1,i+2); cc[23] = cc[23]==0 ? cc[12] : cmp(arr[n][i+2],arr[n][i+3]); // new cc23 if (cc[23]>0) { swap(n,i+2,i+3); return n; } return n; } else { return n; } } return n; } 

Here are three typical sorting methods that represent three different classes of Sorting Algorithms:

 Insertion Sort: Θ(n^2) Heap Sort: Θ(n log n) Count Sort: Θ(3n) 

But check out Stefan Nelsson discussion on the fastest sorting algorithm? where he discuss a solution that goes down to O(n log log n) .. check out its implementation in C

This Semi-Linear Sorting algorithm was presented by a paper in 1995:

A. Andersson, T. Hagerup, S. Nilsson, and R. Raman. Sorting in linear time? In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing, pages 427-436, 1995.