Tipo mais rápido de matriz de comprimento fixo 6 int

Respondendo a outra pergunta do Stack Overflow ( este aqui ), eu me deparei com um sub-problema interessante. Qual é o caminho mais rápido para classificar uma matriz de 6 ints?

Como a questão é muito baixa:

  • não podemos presumir que bibliotecas estão disponíveis (e a própria chamada tem seu custo), apenas C simples
  • para evitar o esvaziamento de pipeline de instruções (que tem um custo muito alto), provavelmente deveríamos minimizar ramificações, saltos e todos os outros tipos de controle de quebra de stream (como aqueles escondidos atrás de pontos de sequência em && ou || ).
  • sala é restrita e minimizando registros e uso de memory é um problema, idealmente no lugar classificar é provavelmente melhor.

Realmente esta questão é um tipo de golfe em que o objective não é minimizar o tamanho da fonte, mas o tempo de execução. Eu chamo de código ‘Zening’ como usado no título do livro Zen of Code optimization de Michael Abrash e suas seqüências .

Quanto ao porquê é interessante, existem várias camadas:

  • o exemplo é simples e fácil de entender e medir, não há muita habilidade C envolvida
  • mostra efeitos da escolha de um bom algoritmo para o problema, mas também efeitos do compilador e do hardware subjacente.

Aqui está minha implementação de referência (ingênua, não otimizada) e meu conjunto de testes.

 #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 brutos

Como o número de variantes está se tornando grande, juntei todos eles em uma suíte de testes que pode ser encontrada aqui . Os testes reais usados ​​são um pouco menos ingênuos do que os mostrados acima, graças ao Kevin Stock. Você pode compilar e executar em seu próprio ambiente. Estou bastante interessado por comportamento em diferentes arquiteturas / compiladores de destino. (OK pessoal, coloque-o em respostas, eu vou marcar com +1 cada colaborador de um novo conjunto de resultados).

Eu dei a resposta para Daniel Stutzbach (para jogar golfe) um ano atrás, pois ele estava na origem da solução mais rápida da época (redes de sorting).

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

  • Chamada direta para a function de biblioteca qsort: 689.38
  • Implementação ingênua (inserção de sorting): 285.70
  • Tipo de Inserção (Daniel Stutzbach): 142.12
  • Insertion Sort Unrolled: 125,47
  • Ordem do Rank: 102.26
  • Ordem de sorting com registros: 58.03
  • Redes de Classificação (Daniel Stutzbach): 111,68
  • Redes de Classificação (Paul R): 66,36
  • Redes de Classificação 12 com Troca Rápida: 58.86
  • Redes de Classificação 12 reordenadas Troca: 53,74
  • Ordenando Redes 12 reordenadas Troca Simples: 31.54
  • Rede de Ordenação Reordenada com troca rápida: 31,54
  • Rede de Ordenação Reordenada com troca rápida V2: 33.63
  • Ordenar de Bolha Inline (Paolo Bonzini): 48.85
  • Tipo de Inserção Desenrolada (Paolo Bonzini): 75.30

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

  • Chamada direta para a function de biblioteca qsort: 705.93
  • Implementação ingênua (sorting de inserção): 135.60
  • Tipo de Inserção (Daniel Stutzbach): 142.11
  • Insertion Sort Unrolled: 126.75
  • Classificação: 46.42
  • Ordem de sorting com registros: 43.58
  • Redes de Classificação (Daniel Stutzbach): 115,57
  • Redes de Classificação (Paul R): 64,44
  • Redes de Classificação 12 com Troca Rápida: 61,98
  • Redes de Classificação 12 reordenadas Troca: 54.67
  • Ordenando Redes 12 reordenadas Troca Simples: 31.54
  • Rede de Ordenação Reordenada com troca rápida: 31,24
  • Rede de Ordenação Reordenada com troca rápida V2: 33.07
  • Sortimento de Bolha Inlined (Paolo Bonzini): 45.79
  • Tipo de Inserção Desenrolada (Paolo Bonzini): 80.15

Eu incluí os resultados -O1 e -O2 porque, surpreendentemente, para vários programas, o O2 é menos eficiente que o O1. Gostaria de saber qual otimização específica tem esse efeito?

Comentários sobre soluções propostas

Tipo de Inserção (Daniel Stutzbach)

Como esperado, minimizar as ramificações é realmente uma boa ideia.

Redes de Classificação (Daniel Stutzbach)

Melhor que o tipo de inserção. Eu me perguntei se o efeito principal não era evitar o loop externo. Eu tentei por ordenação de inserção desenrolada para verificar e na verdade nós temos mais ou menos os mesmos números (o código está aqui ).

Redes de Classificação (Paul R)

O melhor até agora. O código real que usei para testar está aqui . Ainda não sei porque é quase duas vezes mais rápido que a implementação da rede de sorting. Parâmetro passando? Rápido max?

Redes de Classificação 12 SWAP com Swap Rápido

Como sugerido por Daniel Stutzbach, combinei sua rede de sorting de 12 swap com o swap rápido sem agência (o código está aqui ). É de fato mais rápido, o melhor até agora com uma pequena margem (aproximadamente 5%), como seria de se esperar usando 1 troca a menos.

Também é interessante notar que a troca sem filial parece ser muito (4 vezes) menos eficiente que a simples usando if na arquitetura PPC.

Chamando Biblioteca qsort

Para dar outro ponto de referência, eu também tentei, como sugerido, apenas chamar o qsort da biblioteca (o código está aqui ). Como esperado, é muito mais lento: 10 a 30 vezes mais lento … como ficou óbvio com o novo conjunto de testes, o principal problema parece ser a carga inicial da biblioteca após a primeira chamada, e não se compara tão mal com outros versão. É apenas entre 3 e 20 vezes mais lento no meu Linux. Em algumas arquiteturas usadas para testes de outros, parece até ser mais rápido (estou realmente surpreso com isso, já que o qsort da biblioteca usa uma API mais complexa).

Ordem de sorting

Rex Kerr propôs outro método completamente diferente: para cada item da matriz calcule diretamente sua posição final. Isso é eficiente porque a ordem de sorting de computação não precisa de ramificação. A desvantagem desse método é que ele leva três vezes a quantidade de memory da matriz (uma cópia da matriz e variables ​​para armazenar ordens de sorting). Os resultados de desempenho são muito surpreendentes (e interessantes). Na minha arquitetura de referência com 32 bits OS e Intel Core2 Quad E8300, a contagem de ciclos estava um pouco abaixo de 1000 (como classificar redes com swap de ramificação). Mas quando compilado e executado na minha checkbox de 64 bits (Intel Core2 Duo) ele teve um desempenho muito melhor: ele se tornou o mais rápido até agora. Eu finalmente descobri o verdadeiro motivo. Minha checkbox de 32bits usa gcc 4.4.1 e meu 64bits box gcc 4.4.3 e o último parece muito melhor em otimizar este código em particular (houve pouca diferença para outras propostas).

atualização :

Conforme os números publicados acima, esse efeito ainda foi aprimorado pelas versões posteriores do gcc e o Rank Order tornou-se consistentemente duas vezes mais rápido que qualquer outra alternativa.

Redes de Classificação 12 com Swap reordenado

A incrível eficiência da proposta do Rex Kerr com o gcc 4.4.3 me fez pensar: como um programa com 3 vezes mais uso de memory pode ser mais rápido do que redes de sorting sem ramificação? Minha hipótese era que ele tinha menos dependencies do tipo read after write, permitindo um melhor uso do escalonador de instruções superescalares do x86. Isso me deu uma ideia: reorganizar os swaps para minimizar a leitura após as dependencies de gravação. Mais simplesmente, quando você faz SWAP(1, 2); SWAP(0, 2); SWAP(1, 2); SWAP(0, 2); você tem que esperar que a primeira troca seja concluída antes de executar a segunda porque ambos acessam uma célula de memory comum. Quando você faz SWAP(1, 2); SWAP(4, 5); SWAP(1, 2); SWAP(4, 5); o processador pode executar ambos em paralelo. Eu tentei e funciona como esperado, as redes de sorting estão funcionando cerca de 10% mais rápido.

Ordenando Redes 12 com Troca Simples

Um ano após o post original, Steinar H. Gunderson sugeriu que não devemos tentar enganar o compilador e manter o código de troca simples. É realmente uma boa ideia, pois o código resultante é cerca de 40% mais rápido! Ele também propôs um swap otimizado manualmente usando o código de assembly in-line x86 que ainda pode poupar mais alguns ciclos. O mais surpreendente (diz volumes sobre a psicologia do programador) é que há um ano nenhum usou essa versão de swap. O código que usei para testar está aqui . Outros sugeriram outras maneiras de escrever uma troca rápida C, mas ela produz os mesmos desempenhos que a simples com um compilador decente.

O “melhor” código é agora como segue:

 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 } 

Se acreditamos em nosso teste (e, sim, é muito ruim, é mero benefício ser curto, simples e fácil de entender o que estamos medindo), o número médio de ciclos do código resultante para um tipo é inferior a 40 ciclos ( 6 testes são executados). Isso coloca cada swap em uma média de 4 ciclos. Eu chamo isso incrivelmente rápido. Quaisquer outras melhorias possíveis?

Para qualquer otimização, é sempre melhor testar, testar e testar. Eu tentaria, pelo menos, classificar redes e tipo de inserção. Se eu estivesse apostando, colocaria meu dinheiro no tipo de inserção com base na experiência passada.

Você sabe alguma coisa sobre os dados de input? Alguns algoritmos terão melhor desempenho com determinados tipos de dados. Por exemplo, a sorting por inserção apresenta um desempenho melhor em dados classificados ou quase classificados, portanto, será a melhor opção se houver uma chance acima da média de dados quase ordenados.

O algoritmo que você postou é semelhante a uma sorting de inserção, mas parece que você minimizou o número de swaps ao custo de mais comparações. No entanto, as comparações são muito mais caras do que os swaps, porque as agências podem fazer com que o pipeline de instruções pare.

Aqui está uma implementação de sorting de inserção:

 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; } } 

Veja como eu criaria uma rede de sorting. Primeiro, use este site para gerar um conjunto mínimo de macros SWAP para uma rede do tamanho apropriado. Embrulhar isso em uma function me dá:

 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 } 

Aqui está uma implementação usando redes de sorting :

 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); } 

Você realmente precisa de implementações min e max sem ramificações muito eficientes para isso, já que é efetivamente o que esse código resume – uma sequência de operações min e max (13 de cada, no total). Deixo isso como um exercício para o leitor.

Observe que essa implementação se presta facilmente à vetorização (por exemplo, SIMD – a maioria das ISAs do SIMD tem instruções de min / max de vetor) e também às implementações da GPU (por exemplo, CUDA – sem ramificação não há problemas com divergência de deformação, etc.).

Veja também: Implementação rápida de algoritmos para classificar listas muito pequenas

Como estes são números inteiros e comparativos são rápidos, porque não calcular a ordem de sorting de cada um diretamente:

 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 cheguei à festa um ano atrasado, mas aqui vamos nós …

Olhando para a assembly gerada pelo gcc 4.5.2, observei que cargas e armazenamentos estão sendo feitos para cada troca, o que realmente não é necessário. Seria melhor carregar os 6 valores em registradores, classificá-los e armazená-los de volta na memory. Eu ordenei que as cargas nas lojas fossem o mais próximo possível de lá. Os registros são primeiro necessários e usados ​​pela última vez. Eu também usei a macro SWAP de Steinar H. Gunderson. Atualização: Mudei para a macro SWAP de Paolo Bonzini, que o gcc converte em algo semelhante ao Gunderson, mas o gcc é capaz de ordenar melhor as instruções, uma vez que elas não são dadas como uma assembly explícita.

Eu usei a mesma ordem de troca que a rede de troca reordenada, dada como a de melhor desempenho, embora possa haver uma ordenação melhor. Se eu encontrar mais algum tempo, gerarei e testarei um monte de permutações.

Eu mudei o código de teste para considerar mais de 4000 arrays e mostrar o número médio de ciclos necessários para classificar cada um deles. Em um i5-650 estou recebendo ~ 34,1 ciclos / tipo (usando -O3), em comparação com a rede de sorting reordenada original recebendo ~ 65,3 ciclos / tipo (usando -O1, beats -O2 e -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; } 

Eu mudei modifiquei o conjunto de testes para também relatar clocks por sorting e executar mais testes (a function cmp também foi atualizada para tratar o estouro de inteiro), aqui estão os resultados em algumas arquiteturas diferentes. Eu tentei testar em um cpu AMD, mas rdtsc não é confiável no X6 1100T eu tenho disponível.

 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 

O código de teste é muito ruim; ele sobrecarrega o array inicial (as pessoas não leem os avisos do compilador?), o printf está imprimindo os elementos errados, ele usa .byte para o rdtsc sem um bom motivo, há apenas uma execução (!), não há nada verificando se o Os resultados finais estão realmente corretos (por isso é muito fácil “otimizar” algo sutilmente errado), os testes incluídos são muito rudimentares (não há números negativos?) e não há nada que impeça o compilador de descartar a function inteira como código morto.

Dito isto, também é muito fácil melhorar a solução de rede bitônica; basta alterar o material min / max / SWAP para

 #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"); } 

e é 65% mais rápido para mim (Debian gcc 4.4.5 com -O2, amd64, Core i7).

Eu tropecei nesta pergunta do Google há alguns dias atrás, porque eu também tive a necessidade de classificar rapidamente uma matriz de comprimento fixo de 6 inteiros. No meu caso, no entanto, meus números inteiros são apenas 8 bits (em vez de 32) e eu não tenho uma exigência estrita de usar apenas C. Eu pensei que eu iria compartilhar minhas descobertas de qualquer maneira, no caso eles podem ser úteis para alguém …

Implementei uma variante de uma sorting de rede em assembly que usa SSE para vetorizar as operações de comparação e troca, na medida do possível. São necessários seis “passes” para classificar completamente o array. Eu usei um novo mecanismo para converter diretamente os resultados de PCMPGTB (comparação vetorizada) para misturar parâmetros para PSHUFB (troca vetorizada), usando apenas uma instrução PADDB (adição vetorizada) e em alguns casos também uma instrução PAND (bitwise AND).

Essa abordagem também teve o efeito colateral de produzir uma function verdadeiramente sem agência. Não há instruções de salto.

Parece que esta implementação é cerca de 38% mais rápida que a implementação atualmente marcada como a opção mais rápida na questão (“Classificando redes 12 com troca simples”). Eu modifiquei essa implementação para usar elementos de matriz de char durante meus testes, para tornar a comparação justa.

Devo observar que essa abordagem pode ser aplicada a qualquer tamanho de matriz de até 16 elementos. Espero que a vantagem de velocidade relativa sobre as alternativas aumente para os arrays maiores.

O código está escrito em MASM para processadores x86_64 com SSSE3. A function usa a “nova” convenção de chamada do Windows x64. Aqui 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 

Você pode compilar isso para um object executável e vinculá-lo ao seu projeto C. Para obter instruções sobre como fazer isso no Visual Studio, você pode ler este artigo . Você pode usar o seguinte protótipo C para chamar a function do seu código C:

 void simd_sort_6(char *values); 

Embora eu realmente goste da macro de troca fornecida:

 #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; } 

I see an improvement (which a good compiler might make):

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

We take note of how min and max work and pull the common sub-expression explicitly. 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). Garland. 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 } 

Ou

 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

código js

 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: repaired 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 //repaired 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 classs 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.