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

401

Respondendo a outra pergunta do Stack Overflow ( esta ), deparei-me com um sub-problema interessante. Qual é a maneira mais rápida de classificar uma matriz de 6 números inteiros?

Como a pergunta é de nível muito baixo:

  • não podemos assumir que as bibliotecas estão disponíveis (e a chamada em si tem seu custo), apenas C simples
  • para evitar esvaziar o pipeline de instruções (que tem um custo muito alto), provavelmente devemos minimizar desvios, saltos e todos os outros tipos de interrupção do fluxo de controle (como aqueles ocultos atrás dos pontos de sequência em &&ou ||).
  • o espaço é restrito e a minimização de registros e o uso da memória são um problema; a classificação ideal é provavelmente a melhor.

Realmente, essa pergunta é um tipo de golfe em que o objetivo não é minimizar o comprimento 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 sequências .

Por que é interessante, existem várias camadas:

  • o exemplo é simples e fácil de entender e medir, não há muita habilidade em C envolvida
  • mostra efeitos de 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 <stdio.h>

static __inline__ int sort6(int * d){

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

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

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

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

Resultados brutos

À medida que o número de variantes aumenta, reuni todas em uma suíte de testes que pode ser encontrada aqui . Os testes atuais usados ​​são um pouco menos ingênuos do que os mostrados acima, graças a Kevin Stock. Você pode compilá-lo e executá-lo em seu próprio ambiente. Estou bastante interessado no comportamento em diferentes arquiteturas / compiladores de destino. (OK pessoal, coloque isso em respostas, adicionarei +1 a cada colaborador de um novo conjunto de resultados).

Dei a resposta a Daniel Stutzbach (para jogar golfe) há um ano, pois ele estava na fonte da solução mais rápida na época (redes de classificação).

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

  • Chamada direta à função da biblioteca qsort: 689.38
  • Implementação ingênua (tipo de inserção): 285,70
  • Classificação de inserção (Daniel Stutzbach): 142.12
  • Classificação de inserção desenrolada: 125.47
  • Ordem de classificação: 102.26
  • Ordem de classificação com registros: 58.03
  • Redes de classificação (Daniel Stutzbach): 111.68
  • Redes de classificação (Paul R): 66,36
  • Classificação de redes 12 com troca rápida: 58,86
  • Redes de classificação 12 reordenadas Swap: 53.74
  • Redes de classificação 12 reorganizadas Simple Swap: 31.54
  • Rede de classificação reordenada com troca rápida: 31,54
  • Rede de classificação reordenada com troca rápida V2: 33.63
  • Classificação de bolha embutida (Paolo Bonzini): 48,85
  • Classificação 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 à função da biblioteca qsort: 705.93
  • Implementação ingênua (classificação por inserção): 135,60
  • Classificação de inserção (Daniel Stutzbach): 142.11
  • Classificação de inserção desenrolada: 126.75
  • Ordem de classificação: 46.42
  • Ordem de classificação com registros: 43,58
  • Redes de classificação (Daniel Stutzbach): 115.57
  • Redes de classificação (Paul R): 64,44
  • Classificando redes 12 com troca rápida: 61,98
  • Redes de classificação 12 reordenadas Swap: 54.67
  • Redes de classificação 12 reorganizadas Simple Swap: 31.54
  • Rede de classificação reordenada com troca rápida: 31,24
  • Rede de classificação reordenada com troca rápida V2: 33.07
  • Classificação de bolha embutida (Paolo Bonzini): 45,79
  • Classificação de inserção desenrolada (Paolo Bonzini): 80.15

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

Comentários sobre soluções propostas

Classificação de inserção (Daniel Stutzbach)

Como esperado, minimizar ramos é realmente uma boa ideia.

Redes de classificação (Daniel Stutzbach)

Melhor que a classificação por inserção. Eu me perguntava se o efeito principal não era o de evitar o loop externo. Eu tentei por tipo de inserção desenrolado para verificar e, de fato, obtemos aproximadamente as mesmas figuras (o código está aqui ).

Redes de classificação (Paul R)

O melhor até agora. O código real que eu usei para testar é aqui . Ainda não sabemos por que é quase duas vezes mais rápido que a outra implementação de rede de classificação. Passagem de parâmetro? Max rápido?

Classificação de redes 12 SWAP com troca rápida

Conforme sugerido por Daniel Stutzbach, combinei sua rede de classificação de 12 trocas com a troca rápida sem ramificação (o código é aqui ). É realmente mais rápido, o melhor até agora com uma pequena margem (aproximadamente 5%), como seria de esperar usando 1 swap a menos.

Também é interessante notar que a troca sem ramificação parece ser muito (4 vezes) menos eficiente do que a simples usando na arquitetura PPC.

Biblioteca de chamadas qsort

Para dar outro ponto de referência, também tentei, como sugerido, chamar a biblioteca qsort (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 o carregamento 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 por outras pessoas, parece até mais rápido (estou realmente surpreso com essa, pois a biblioteca qsort usa uma API mais complexa).

Ordem de classificação

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 classificação da computação não precisa de ramificação. A desvantagem desse método é que ele leva três vezes a quantidade de memória da matriz (uma cópia da matriz e variáveis ​​para armazenar ordens de classificação). Os resultados do desempenho são muito surpreendentes (e interessantes). Na minha arquitetura de referência com sistema operacional de 32 bits e Intel Core2 Quad E8300, a contagem de ciclos ficou um pouco abaixo de 1000 (como redes de classificação com troca de ramificação). Mas quando compilado e executado na minha caixa de 64 bits (Intel Core2 Duo), teve um desempenho muito melhor: tornou-se o mais rápido até agora. Eu finalmente descobri a verdadeira razão. Minha caixa de 32 bits usa o gcc 4.4.1 e minha caixa de 64 bits gcc 4.4.

update :

Como as figuras publicadas acima mostram esse efeito ainda foi aprimorado pelas versões posteriores do gcc e o Rank Order se tornou consistentemente duas vezes mais rápido do que qualquer outra alternativa.

Classificando redes 12 com Swap reordenado

A incrível eficiência da proposta Rex Kerr com o gcc 4.4.3 me fez pensar: como um programa com uso de memória três vezes maior pode ser mais rápido que as redes de classificação sem ramificação? Minha hipótese era que ele tinha menos dependências do tipo lido após gravação, permitindo um melhor uso do agendador de instruções superescalares do x86. Isso me deu uma idéia: reorganizar trocas para minimizar as dependências de leitura após gravação. Em outras palavras: quando você SWAP(1, 2); SWAP(0, 2);precisa aguardar a conclusão da primeira troca antes de executar a segunda, porque ambos acessam uma célula de memória comum. Quando você faz SWAP(1, 2); SWAP(4, 5);o processador pode executar os dois em paralelo. Eu tentei e funciona como esperado, as redes de classificação estão executando 10% mais rápido.

Classificando redes 12 com troca simples

Um ano após o post original sugerido por Steinar H. Gunderson, 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 uma troca otimizada manualmente usando o código de montagem em linha x86 que ainda pode poupar mais alguns ciclos. O mais surpreendente (diz volumes sobre a psicologia do programador) é que, um ano atrás, nenhum dos usados ​​tentou essa versão do swap. O código que eu costumava testar está aqui . Outros sugeriram outras maneiras de escrever uma troca rápida C, mas produz as mesmas performances que a simples com um compilador decente.

O "melhor" código é agora o seguinte:

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 acreditarmos que nosso conjunto de testes (e, sim, é muito ruim, seu benefício é 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 troca em uma média de 4 ciclos. Eu chamo isso incrivelmente rápido. Quaisquer outras melhorias possíveis?

kriss
fonte
2
Você tem algumas restrições nas entradas? Por exemplo, podemos supor que, para qualquer 2 x, y x-ye x+ynão irá causar underflow ou estouro?
Matthieu M.
3
Você deve tentar combinar minha rede de classificação de 12 trocas com a função de troca sem filial de Paul. Sua solução passa todos os parâmetros como elementos separados na pilha, em vez de um único ponteiro para uma matriz. Isso também pode fazer a diferença.
Daniel Stutzbach
2
Observe que a implementação correta do rdtsc em 64 bits é __asm__ volatile (".byte 0x0f, 0x31; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");porque o rdtsc coloca a resposta no EDX: EAX enquanto o GCC espera isso em um único registro de 64 bits. Você pode ver o bug compilando em -O3. Veja também abaixo meu comentário a Paul R sobre um SWAP mais rápido.
Paolo Bonzini
3
@ Tyler: Como você o implementa no nível da montagem sem uma filial?
Loren Pechtel
4
@ Loren: CMP EAX, EBX; SBB EAX, EAXcolocará 0 ou 0xFFFFFFFF EAXdependendo se EAXé maior ou menor que EBX, respectivamente. SBBé "subtrair com empréstimo", a contrapartida de ADC("adicionar com transporte"); o bit de status a que você se refere é o bit de transporte. Então, lembro-me disso ADCe SBBtinha uma latência e taxa de transferência terríveis no Pentium 4 vs. ADDe SUB, e ainda era duas vezes mais lento nas CPUs Core. Desde o 80386, também existem instruções de SETccarmazenamento CMOVcccondicional e movimentação condicional, mas também são lentas.
Jrandom_hacker

Respostas:

162

Para qualquer otimização, é sempre melhor testar, testar, testar. Eu tentaria pelo menos classificar redes e classificar por inserção. Se eu estivesse apostando, apostaria meu dinheiro na inserção com base em experiências anteriores.

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

O algoritmo que você postou é semelhante a uma classificação por inserção, mas parece que você minimizou o número de trocas ao custo de mais comparações. As comparações são muito mais caras que as trocas, porque as filiais podem causar a paralisação do pipeline de instruções.

Aqui está uma implementação de classificação por 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;
        }
}

Aqui está como eu construiria uma rede de classificação. Primeiro, use este site para gerar um conjunto mínimo de macros SWAP para uma rede do comprimento apropriado. Agrupar isso em uma função 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
}
Daniel Stutzbach
fonte
9
+1: bom, você fez isso com 12 trocas em vez das 13 da minha rede codificada à mão e derivada empiricamente acima. Eu daria outro +1 se eu pudesse pelo link para o site que gera redes para você - agora marcado.
Paul R
9
Essa é uma ideia fantástica para uma função de classificação de uso geral, se você espera que a maioria das solicitações seja de matrizes de tamanho pequeno. Use uma instrução switch para os casos que você deseja otimizar, usando este procedimento; deixe o caso padrão usar uma função de classificação de biblioteca.
Mark Ransom
5
@ Mark Uma boa função de classificação de biblioteca já terá um caminho rápido para pequenas matrizes. Muitas bibliotecas modernas usarão um QuickSort ou MergeSort recursivo que muda para InsertionSort depois de retornar para n < SMALL_CONSTANT.
Daniel Stutzbach
3
@ Mark Bem, uma função de classificação da biblioteca C requer que você especifique a operação de comparação por meio de um carregador de funções. A sobrecarga de chamar uma função para cada comparação é enorme. Normalmente, esse ainda é o caminho mais limpo a seguir, porque esse raramente é um caminho crítico no programa. No entanto, se esse for o caminho crítico, realmente poderemos classificar muito mais rapidamente se soubermos que estamos classificando números inteiros e exatamente 6 deles. :)
Daniel Stutzbach
7
@tgwh: A troca de XOR é quase sempre uma má ideia.
Paul R
63

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

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 mine ramificações muito eficientes maxpara isso, já que é efetivamente o que esse código se resume - uma sequência de minemax operações (13 de cada, no total). Deixo isso como um exercício para o leitor.

Observe que esta implementação se presta facilmente à vetorização (por exemplo, SIMD - a maioria dos ISAs SIMD tem instruções mínimas / máximas de vetor) e também às implementações de GPU (por exemplo, CUDA - sem ramificação, não há problemas com divergência de urdidura etc.).

Consulte também: Implementação rápida de algoritmo para classificar lista muito pequena

Paul R
fonte
11
Para alguns cortes bit para min / max: graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
Rubys
11
@Paul: no contexto real de uso da CUDA, é certamente a melhor resposta. Vou verificar se também está (e quanto) no contexto de golfe x64 e publicar o resultado.
Kriss
11
Sort3seria mais rápido (na maioria das arquiteturas), se você notasse que esse (a+b+c)-(min+max)é o número central.
Rex Kerr
11
@Rex: Entendo - isso parece bom. Para arquiteturas SIMD como AltiVec e SSE, seria o mesmo número de ciclos de instruções (max e min são instruções de ciclo único como adicionar / subtrair), mas para uma CPU escalar normal, seu método parece melhor.
Paul R
2
Se eu deixar GCC otimizar min com instruções de movimentação condicionais eu recebo um aumento de velocidade de 33%: #define SWAP(x,y) { int dx = d[x], dy = d[y], tmp; tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; }. Aqui não estou usando?: Para d [y] porque apresenta um desempenho um pouco pior, mas está quase no barulho.
Paolo Bonzini
45

Como esses números são inteiros e as comparações são rápidas, por que não calcular diretamente a ordem de classificação de cada um:

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];
}
Rex Kerr
fonte
@Rex: com gcc -O1, fica abaixo de 1000 ciclos, muito rápido, mas mais lento que a rede de classificação. Alguma idéia para melhorar o código? Talvez se pudéssemos evitar cópia variedade ...
Kriss
@kriss: É mais rápido que a rede de classificação para mim com -O2. Existe alguma razão pela qual -O2 não está bem ou é mais lento para você no -O2 também? Talvez seja uma diferença na arquitetura da máquina?
Rex Kerr
11
@Rex: desculpe, eu perdi o padrão> vs> = à primeira vista. Funciona em todos os casos.
kriss
3
@kriss: Aha. Isso não é completamente surpreendente - existem muitas variáveis ​​flutuando e elas precisam ser cuidadosamente ordenadas e armazenadas em cache nos registros e assim por diante.
Rex Kerr #
2
@SSpoke 0+1+2+3+4+5=15Desde um deles está faltando, 15 menos a soma dos rendimentos de descanso faltando um
Glenn Teitelbaum
35

Parece que cheguei à festa um ano atrasado, mas aqui vamos nós ...

Observando a montagem gerada pelo gcc 4.5.2, observei que cargas e lojas estão sendo feitas para cada troca, o que realmente não é necessário. Seria melhor carregar os 6 valores nos registradores, classificá-los e armazená-los novamente na memória. Ordenei que as cargas nas lojas estivessem o mais próximo possível dos registros necessários e usados ​​pela última vez. Também usei a macro SWAP de Steinar H. Gunderson. Atualização: mudei para a macro SWAP de Paolo Bonzini, que o gcc se converte em algo semelhante ao de Gunderson, mas o gcc é capaz de ordenar melhor as instruções, pois elas não são fornecidas como montagem explícita.

Usei a mesma ordem de troca que a rede de troca reordenada, que apresentou o melhor desempenho, embora possa haver uma melhor ordem. Se eu encontrar mais tempo, gerarei e testarei várias permutações.

Alterei o código de teste para considerar mais de 4000 matrizes e mostrar o número médio de ciclos necessários para classificar cada um. Em um i5-650, estou recebendo ~ 34,1 ciclos / classificação (usando -O3), em comparação com a rede de classificação reordenada original obtendo ~ 65,3 ciclos / classificação (usando -O1, supera -O2 e -O3).

#include <stdio.h>

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

Mudei modificado o conjunto de testes para também relatam relógios por tipo e executar mais testes (a função cmp foi atualizado para estouro punho inteiro também), aqui estão os resultados em algumas arquiteturas diferentes. Tentei testar em uma CPU AMD, mas o rdtsc não é confiável no X6 1100T que 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
Kevin Stock
fonte
Sua idéia de variáveis ​​de registro deve ser aplicada à solução "Rank Order" de Rex Kerr. Isso deve ser mais rápido e, talvez, a -O3otimização não seja contraproducente.
precisa saber é o seguinte
11
@ cdunn2001 Acabei de testar, não estou vendo melhorias (exceto alguns ciclos em -O0 e -Os). Olhando para o asm, parece que o gcc já conseguiu usar registros e eliminar a chamada para memcpy.
Kevin da
Você gostaria de adicionar a versão de troca simples ao seu conjunto de testes? Acho que poderia ser interessante compará-la com a troca rápida de montagem otimizada manualmente.
kriss
11
Seu código ainda usa a troca de Gunderson, a minha seria #define SWAP(x,y) { int oldx = x; x = x < y ? x : y; y ^= oldx ^ x; }.
Paolo Bonzini
@ Paolo Bonzini: Sim, pretendo adicionar um caso de teste ao seu, mas ainda não tive tempo. Mas evitarei a montagem em linha.
kriss
15

Eu me deparei com essa pergunta do Google há alguns dias atrás, porque eu também precisava classificar rapidamente uma matriz de comprimento fixo de 6 números inteiros. No entanto, no meu caso, meus números inteiros são apenas 8 bits (em vez de 32) e não tenho um requisito estrito de usar apenas C. Eu pensei em compartilhar minhas descobertas de qualquer maneira, caso possam ser úteis para alguém ...

Eu implementei uma variante de uma classificação de rede no assembly que usa o 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 a matriz. Usei um novo mecanismo para converter diretamente os resultados do PCMPGTB (comparação vetorizada) em parâmetros aleatórios para PSHUFB (troca vetorizada), usando apenas um PADDB (adição vetorizada) e, em alguns casos, também uma instrução PAND (AND bit a bit).

Essa abordagem também teve o efeito colateral de produzir um função verdadeiramente sem ramo. 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 pergunta ("Classificando redes 12 com troca simples"). Modifiquei essa implementação para usar charelementos de matriz durante meus testes, para tornar a comparação justa.

Devo observar que essa abordagem pode ser aplicada a qualquer tamanho de matriz com até 16 elementos. Espero que a vantagem da velocidade relativa sobre as alternativas cresça mais para as matrizes maiores.

O código está escrito no MASM para processadores x86_64 com SSSE3. A função 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 (e.g. 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 em um objeto 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 função do seu código C:

void simd_sort_6(char *values);
Joe Crivello
fonte
Seria interessante comparar o seu com outras propostas em nível de montagem. Os desempenhos comparados da implementação não os incluem. O uso do SSE parece bom de qualquer maneira.
kriss
Outra área de pesquisas futuras seria a aplicação das novas instruções do Intel AVX para esse problema. Os vetores maiores de 256 bits são grandes o suficiente para acomodar 8 DWORDs.
Joe Crivello
11
Em vez de pxor / pinsrd xmm4, mem, 0, basta usar movd!
Peter Cordes
14

O código de teste é muito ruim; transborda a matriz inicial (as pessoas aqui não leem avisos do compilador?), o printf está imprimindo os elementos errados, usa .byte para rdtsc sem nenhuma boa razão, 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 subtilmente errado), os testes incluídos são muito rudimentares (sem números negativos?) e não há nada para impedir o compilador de descartar toda a função como código morto.

Dito isto, também é muito fácil melhorar a solução de rede bitônica; basta alterar o material mínimo / máximo / 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 sai 65% mais rápido para mim (Debian gcc 4.4.5 com -O2, amd64, Core i7).

Steinar H. Gunderson
fonte
OK, o código de teste está ruim. Sinta-se livre para melhorá-lo. E sim, você pode usar o código de montagem. Por que não percorrer todo o caminho e codificá-lo totalmente usando o x86 assembler? Pode ser um pouco menos portátil, mas por que se preocupar?
kriss
Obrigado por perceber o estouro da matriz, eu o corrigi. Outras pessoas podem não ter percebido isso porque clicaram no link para copiar / colar código, onde não há excesso.
kriss
4
Você nem precisa de assembler, na verdade; se você soltar todos os truques inteligentes, o GCC reconhecerá a sequência e inserirá os movimentos condicionais para você: #define min (a, b) ((a <b)? a: b) #define max (a, b) ( (a <b) b: a) # define SWAP (x, y) {int a = min (d [x], d [y]); int b = max (d [x], d [y]); d [x] = a; d [y] = b; } Ele sai talvez um pouco mais lento que a variante asm inline, mas é difícil dizer, devido à falta de benchmarking adequado.
Steinar H. Gunderson
3
... e, finalmente, se seus números são flutuantes e você não precisa se preocupar com NaN, etc., o GCC pode converter isso em instruções SSSS minss / maxss, que são ainda ~ 25% mais rápidas. Moral: Solte os truques inteligentes de quebra-cabeças e deixe o compilador fazer seu trabalho. :-)
Steinar H. Gunderson
13

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

Vejo uma melhoria (que um bom compilador pode fazer):

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

Tomamos nota de como min e max funcionam e extraímos explicitamente a subexpressão comum. Isso elimina completamente as macros min e max.

phkahler
fonte
Isso os leva para trás, observe que d [y] obtém o máximo, que é x ^ (subexpressão comum).
Kevin da
Eu notei a mesma coisa; Eu acho que a sua implementação está correta, você deseja, em d[x]vez dex (o mesmo para y), e d[y] < d[x]a desigualdade aqui (sim, diferente do código min / max).
Tyler
Eu tentei com o seu swap, mas a otimização local tem efeitos negativos em um nível maior (acho que isso introduz dependências). E o resultado é mais lento que o outro swap. Mas como você pode ver com a nova solução proposta, havia realmente muito desempenho para obter a otimização da troca.
kriss
12

Nunca otimize o mínimo / o máximo sem fazer comparações e observar o conjunto gerado pelo compilador. Se eu permitir que o GCC otimize o mínimo com instruções de movimentação condicional, recebo uma aceleração de 33%:

#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 ciclos no código de teste). Fazer max com?: É mais ou menos o mesmo, quase perdido no barulho, mas o acima é um pouco mais rápido. Esse SWAP é mais rápido com o GCC e o Clang.

Os compiladores também estão fazendo um trabalho excepcional na alocação de registros e na análise de alias, movendo efetivamente d [x] para variáveis ​​locais antecipadamente e apenas copiando de volta para a memória no final. De fato, eles o fazem ainda melhor do que se você trabalhasse inteiramente com variáveis ​​locais (como d0 = d[0], d1 = d[1], d2 = d[2], d3 = d[3], d4 = d[4], d5 = d[5]). Estou escrevendo isso porque você está assumindo uma otimização forte e ainda tentando enganar o compilador em mín / máx. :)

A propósito, tentei Clang e GCC. Eles fazem a mesma otimização, mas devido às diferenças de agendamento, os dois têm alguma variação nos resultados, não podem dizer realmente qual é mais rápido ou mais lento. O GCC é mais rápido nas redes de classificação, Clang nos tipos quadráticos.

Apenas para completar, também é possível a classificação desenrolada de bolhas e tipos de inserção. Aqui está o tipo de bolha:

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

e aqui está o tipo de inserção:

//#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);

Esse tipo de inserção é mais rápido que o de Daniel Stutzbach e é especialmente bom em uma GPU ou em um computador com predicação porque o ITER pode ser feito com apenas 3 instruções (vs. 4 para SWAP). Por exemplo, aqui está a t = d[2]; ITER(1); ITER(0);linha na montagem do ARM:

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

Para seis elementos, a classificação por inserção é competitiva com a rede de classificação (12 swaps vs. 15 iterações equilibram 4 instruções / swap vs. 3 instruções / iteração); o tipo de bolha, é claro, é mais lento. Mas não será verdade quando o tamanho aumentar, pois a classificação de inserção é O (n ^ 2) enquanto as redes de classificação são O (n log n).

Paolo Bonzini
fonte
11
Mais ou menos relacionado: enviei um relatório ao GCC para que ele pudesse implementar a otimização diretamente no compilador. Não tenho certeza de que isso será feito, mas pelo menos você pode acompanhar como evolui.
Morwenn 28/10/2015
11

Portei o conjunto de testes para uma máquina de arquitetura PPC que não consigo identificar (não precisava tocar no código, apenas aumente as iterações do teste, use 8 casos de teste para evitar poluir os resultados com os mods e substitua o rdtsc específico do x86):

Chamada direta para a função da biblioteca qsort : 101

Implementação ingênua (classificação por inserção) : 299

Classificação de inserção (Daniel Stutzbach) : 108

Classificação de inserção desenrolada : 51

Redes de classificação (Daniel Stutzbach) : 26

Redes de classificação (Paul R) : 85

Classificando redes 12 com troca rápida : 117

Redes de classificação 12 troca reordenada : 116

Ordem de classificação : 56

jheriko
fonte
11
Muito interessante. Parece que a troca sem filial é uma má ideia para o PPC. Também pode ser um efeito relacionado ao compilador. Qual foi usado?
kriss
É uma ramificação do compilador gcc - a lógica min, max provavelmente não é sem ramificação - vou inspecionar a desmontagem e informar você, mas, a menos que o compilador seja inteligente o suficiente, incluindo algo como x <y sem um se ainda se tornar um ramo - em x86 / x64 a instrução CMOV pode evitar isso, mas não existe tal instrução para valores de pontos fixos no PPC, apenas flutua. Eu posso brincar com isso amanhã e informar: lembro que havia um mínimo / máximo sem ramificação muito mais simples na fonte Winamp AVS, mas era apenas para carros alegóricos - mas pode ser um bom começo para uma abordagem verdadeiramente sem ramificações.
precisa saber é o seguinte
4
Aqui é um min branchless / max para PPC com entradas sem sinal: subfc r5,r4,r3; subfe r6,r6,r6; andc r6,r5,r6; add r4,r6,r4; subf r3,r6,r3. r3 / r4 são entradas, r5 / r6 são registros de arranhões, na saída r3 obtém o mínimo e r4 obtém o máximo. Ele deve ser decentemente agendado manualmente. Encontrei-o com o superoptimizador GNU, iniciando com sequências mín e máx de 4 instruções e procurando manualmente duas que poderiam ser combinadas. Para entradas assinadas, é claro que você pode adicionar 0x80000000 a todos os elementos no início e subtraí-lo novamente no final e trabalhar como se não tivessem assinado.
Paolo Bonzini
7

Uma troca XOR pode ser útil em suas funções de troca.

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

O if pode causar muita divergência no seu código, mas se você tiver uma garantia de que todos os seus ints são únicos, isso pode ser útil.

naj
fonte
11
xor troca funciona para valores iguais, bem ... x ^ = y sets x 0, y ^ = x folhas y como y (== x), x ^ = y conjuntos de X para Y
jheriko
11
Quando não funciona é quando xe yaponte para o mesmo local.
hobbs
De qualquer forma, quando usado com redes de classificação, nunca ligamos com xey apontando para o mesmo local. Ainda há uma maneira de evitar testes, que é maior para obter o mesmo efeito que a troca sem ramificação. Eu tenho uma ideia para conseguir isso.
kriss
5

Ansioso para tentar fazer isso e aprender com esses exemplos, mas primeiro alguns tempos do meu PowerBook G4 de 1,5 GHz e PPC Power4 G / 1 GB de RAM DDR. (Emprestei um temporizador semelhante ao rdtsc para PPC em http://www.mcs.anl.gov/~kazutomo/rdtsc.html para os cronogramas.) o programa algumas vezes e os resultados absolutos variaram, mas os resultados consistentes O teste mais rápido foi "Insertion Sort (Daniel Stutzbach)", com "Insertion Sort Unrolled" um segundo próximo.

Aqui está o último conjunto de horários:

**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
Nico
fonte
4

Aqui está minha contribuição para este segmento: um shellsort otimizado de 1, 4 hiatos para um vetor int de 6 membros (valp) contendo valores exclusivos.

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<a) break;

      *cp=a;
      *(cp+1)=c;
      cp-=1;
      c=*cp;
    } while (cp>=valp);
    ip+=1;
    cp=ip;
  } while (ip<ep);
}

No meu laptop HP dv7-3010so, com um Athlon M300 a 2 Ghz de dois núcleos (memória DDR2), ele é executado em 165 ciclos de clock. Esta é uma média calculada a partir do tempo de cada sequência única (6! / 720 no total). Compilado no Win32 usando o OpenWatcom 1.8. O loop é essencialmente uma classificação de inserção e tem 16 instruções / 37 bytes de comprimento.

Não tenho um ambiente de 64 bits para compilar.

Olof Forshell
fonte
agradável. Vou adicioná-lo ao teste mais longo
kriss 23/03
3

Se o tipo de inserção for razoavelmente competitivo aqui, eu recomendaria tentar um shellsort. Receio que 6 elementos sejam provavelmente muito pouco para estar entre os melhores, mas pode valer a pena tentar.

Código de exemplo, não testado, sem erros, etc. Você deseja ajustar a sequência inc = 4 e inc - = 3 para encontrar o ideal (tente inc = 2, inc - = 1 por exemplo).

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

Eu não acho que isso vai ganhar, mas se alguém postar uma pergunta sobre a classificação de 10 elementos, quem sabe ...

Segundo a Wikipedia, isso pode até ser combinado com redes de classificação: Pratt, V (1979). Shellsort e redes de triagem (excelentes dissertações em ciências da computação). Festão. ISBN 0-824-04406-1

gcp
fonte
fique à vontade para propor alguma implementação :-)
kriss
Proposta adicionada. Aproveite os insetos.
gcp
3

Sei que estou super atrasado, mas estava interessado em experimentar algumas soluções diferentes. Primeiro, limpei a pasta, compilei e coloquei em um repositório. Eu mantive algumas soluções indesejáveis ​​como becos sem saída para que outros não tentassem. Entre isso, estava minha primeira solução, que tentou garantir que x1> x2 fosse calculado uma vez. Após a otimização, não é mais rápido que as outras versões simples.

Eu adicionei uma versão em loop da classificação por ordem de classificação, já que minha própria aplicação deste estudo é para classificar de 2 a 8 itens; portanto, como há um número variável de argumentos, é necessário um loop. É também por isso que ignorei as soluções de rede de classificação.

O código de teste não testou se as duplicatas foram tratadas corretamente, portanto, enquanto as soluções existentes estavam todas corretas, adicionei um caso especial ao código de teste para garantir que as duplicatas fossem manipuladas corretamente.

Em seguida, escrevi uma classificação de inserção inteiramente nos registros do AVX. Na minha máquina, é 25% mais rápido que os outros tipos de inserção, mas 100% mais lento que a ordem de classificação. Fiz isso puramente para o experimento e não esperava que isso fosse melhor devido à ramificação no tipo de inserção.

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
}

Em seguida, escrevi uma ordem de classificação usando o AVX. Isso corresponde à velocidade das outras soluções de ordem de classificação, mas não é mais rápido. O problema aqui é que eu só posso calcular os índices com o AVX e, em seguida, tenho que fazer uma tabela de índices. Isso ocorre porque o cálculo é baseado no destino e não na origem. Consulte Convertendo de índices baseados na fonte para índices baseados no destino

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

O repo pode ser encontrado aqui: https://github.com/eyepatchParrot/sort6/

tapa-olho
fonte
11
Você pode usar vmovmskpsem vetores inteiros (com uma conversão para manter os intrínsecos felizes), evitando a necessidade de deslocar o ffsresultado bitscan ( ) à direita .
9788 Peter Cordes
11
Você pode adicionar condicionalmente 1 com base em um cmpgtresultado, subtraindo -o, em vez de mascará-lo set1(1). por exemplo, index = _mm256_sub_epi32(index, gt)fazindex -= -1 or 0;
Peter Cordes
11
eq = _mm256_insert_epi32(eq, 0, I)não é uma maneira eficiente de zerar um elemento se ele compilar como gravado (especialmente para elementos fora do ponto baixo 4, porque vpinsrdsó está disponível com um destino XMM; índices maiores que 3 precisam ser emulados). Em vez disso, _mm256_blend_epi32( vpblendd) com um vetor zerado. vpblenddé uma instrução de operação única executada em qualquer porta, em comparação com uma reprodução aleatória que precisa da porta 5 nas CPUs Intel. ( agner.org/optimize ).
Peter Cordes
11
Além disso, considere gerar os rotvetores com diferentes shuffles da mesma fonte ou, pelo menos, executar 2 cadeias dep em paralelo que você usa alternadamente, em vez de uma única cadeia dep através de uma shuffle de cruzamento de faixa (latência de 3 ciclos). Isso aumentará o ILP em uma única classificação. 2 dep chains limitam o número de constantes do vetor a um número razoável, apenas 2: 1 para uma rotação e uma para 2 etapas de rotação combinadas.
Peter Cordes
2

Essa questão está se tornando bastante antiga, mas na verdade eu tive que resolver o mesmo problema hoje em dia: agoritmos rápidos para classificar pequenas matrizes. Eu pensei que seria uma boa idéia compartilhar meu conhecimento. Enquanto eu comecei a usar redes de classificação, finalmente consegui encontrar outros algoritmos para os quais o número total de comparações realizadas para classificar cada permutação de 6 valores era menor que nas redes de classificação e menor que na classificação por inserção. Não contei o número de swaps; Eu esperaria que fosse aproximadamente equivalente (talvez um pouco maior às vezes).

O algoritmo sort6usa o algoritmo sort4que usa o algoritmosort3 . Aqui está a implementação em alguma forma C ++ leve (o original é pesado para modelos, para que possa trabalhar com qualquer iterador de acesso aleatório e qualquer função de comparação adequada).

Classificando 3 valores

O algoritmo a seguir é uma classificação de inserção desenrolada. Quando dois swaps (6 atribuições) precisam ser executados, ele usa 4 atribuições:

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

Parece um pouco complexo porque a classificação possui mais ou menos um ramo para cada permutação possível da matriz, usando 2 a 3 comparações e no máximo 4 atribuições para classificar os três valores.

Classificando 4 valores

Essa chamada sort3então executa uma classificação de inserção desenrolada com o último elemento da matriz:

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

Esse algoritmo realiza 3 a 6 comparações e, no máximo, 5 swaps. É fácil desenrolar uma classificação de inserção, mas usaremos outro algoritmo para a última classificação ...

Classificando 6 valores

Este usa uma versão desenrolada do que chamei de classificação de inserção dupla . O nome não é tão bom, mas é bastante descritivo, eis como ele funciona:

  • Classifique tudo, exceto o primeiro e o último elemento da matriz.
  • Troque o primeiro e os elementos da matriz se o primeiro for maior que o último.
  • Insira o primeiro elemento na sequência classificada da frente e o último elemento da parte de trás.

Após a troca, o primeiro elemento é sempre menor que o último, o que significa que, ao inseri-los na sequência classificada, não haverá mais de N comparações para inserir os dois elementos no pior caso: por exemplo, se o primeiro elemento foi inserido na 3ª posição e, em seguida, o último não pode ser inserido abaixo da 4ª posição.

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

Meus testes em cada permutação de 6 valores sempre mostram que esse algoritmo sempre executa entre 6 e 13 comparações. Não calculei o número de swaps realizados, mas não espero que seja maior que 11 no pior caso.

Espero que isso ajude, mesmo que essa pergunta possa não representar mais um problema real :)

EDIT: depois de colocá-lo no benchmark fornecido, é claramente mais lento que a maioria das alternativas interessantes. Ele tende a ter um desempenho um pouco melhor do que o tipo de inserção desenrolada, mas é praticamente isso. Basicamente, não é o melhor tipo para números inteiros, mas pode ser interessante para tipos com uma operação de comparação cara.

Morwenn
fonte
Isso é legal. Como o problema resolvido tem muitas décadas, provavelmente uma programação em C, a questão agora tem quase 5 anos não parece tão relevante.
quer
Você deve dar uma olhada na maneira como as outras respostas são cronometradas. O ponto é que, com esses conjuntos de dados pequenos, a comparação de contagens ou mesmo comparações e trocas não diz realmente o quão rápido é um algoritmo (basicamente classificar 6 polegadas é sempre O (1) porque O (6 * 6) é O (1)). O mais rápido atual das soluções propostas anteriormente é encontrar imediatamente a posição de cada valor usando uma grande comparação (da RexKerr).
kriss
@kriss É o mais rápido agora? Da minha leitura dos resultados, a abordagem das redes de classificação foi a mais rápida, a minha ruim. Também é verdade que minha solução vem da minha biblioteca genérica e nem sempre estou comparando números inteiros, nem sempre estou usando operator<para a comparação. Além da contagem objetiva de comparações e swaps, também cronometrei corretamente meus algoritmos; essa solução foi a mais rápida genérica, mas eu realmente senti falta da @ RexKerr. Vou tentar :)
Morwenn
A solução da RexKerr (Order Rank) tornou-se a mais rápida na arquitetura X86 desde o compilador gcc 4.2.3 (e a partir do gcc 4.9 tornou-se quase duas vezes mais rápida que a segunda melhor). Mas depende muito das otimizações do compilador e pode não ser verdade em outras arquiteturas.
quer
@kriss Isso é interessante saber. E eu poderia de fato mais diferenças novamente com -O3. Acho que vou adotar outra estratégia para minha biblioteca de classificação: fornecer três tipos de algoritmos para ter um baixo número de comparações, um baixo número de trocas ou potencialmente o melhor desempenho. Pelo menos, o que acontece será transparente para o leitor. Obrigado por suas idéias :)
Morwenn
1

Eu acredito que há duas partes em sua pergunta.

  • O primeiro é determinar o algoritmo ideal. Isso é feito - pelo menos nesse caso - percorrendo todos os pedidos possíveis (não são muitos), o que permite calcular exatamente o mínimo, o máximo, o desvio médio e o padrão de comparação e troca. Tenha um vice-campeão ou dois à mão também.
  • O segundo é otimizar o algoritmo. Muito pode ser feito para converter exemplos de códigos de livros didáticos em algoritmos da vida real e ruins. Se você perceber que um algoritmo não pode ser otimizado na extensão necessária, tente um segundo colocado.

Eu não me preocuparia muito em esvaziar pipelines (assumindo o x86 atual): a previsão de ramificação já percorreu um longo caminho. O que me preocuparia é garantir que o código e os dados se encaixem em uma linha de cache cada (talvez duas para o código). Uma vez lá, as latências de busca são refrescantemente baixas, o que compensará qualquer interrupção. Isso também significa que seu loop interno terá talvez dez instruções, aproximadamente o que deveria estar (existem dois loops internos diferentes no meu algoritmo de classificação, são 10 instruções / 22 bytes e 9/22 de comprimento, respectivamente). Supondo que o código não contenha divs, você pode ter certeza de que será incrivelmente rápido.

Olof Forshell
fonte
Não sei como entender sua resposta. Primeiro, não entendo de que algoritmo você está propondo? E como seria ideal se você tivesse que percorrer 720 pedidos possíveis (as respostas existentes levam muito menos que 720 ciclos). Se você tem entrada aleatória, não consigo imaginar (mesmo no nível teórico) como a previsão de ramificação poderia ter um desempenho melhor que 50-50, exceto se ela não se importar com todos os dados de entrada. Além disso, a maioria das boas soluções já propostas provavelmente já funcionará com dados e código totalmente em cache. Mas talvez eu tenha entendido completamente sua resposta. Mente mostrando algum código?
kriss
O que eu quis dizer foi que existem apenas 720 (6!) Combinações diferentes de 6 números inteiros e, executando todas elas pelos algoritmos candidatos, você pode determinar muitas coisas como mencionei - essa é a parte teórica. A parte prática é ajustar o algoritmo para rodar no menor número possível de ciclos de clock. Meu ponto de partida para classificar 6 números inteiros é um shellsort de 1, 4 hiatos. O intervalo 4 abre o caminho para uma boa previsão de ramificação no intervalo 1.
Olof Forshell
O 1, 4 gap shellsort para 6! combinações exclusivas (começando com 012345 e terminando com 543210) terão o melhor caso de 7 comparações e 0 trocas e o pior de 14 comparações e 10 trocas. O caso médio é de 11,14 comparações e 6 trocas.
precisa saber é o seguinte
11
Não recebo a "distribuição aleatória regular" - o que estou fazendo é testar todas as combinações possíveis e determinar as estatísticas mín / média / máx. O Shellsort é uma série de tipos de inserção de incrementos decrescentes, de modo que o incremento final - 1 - faz muito menos trabalho do que se for executado sozinho, como em um tipo de inserção puro. Quanto à contagem de clock, meu algoritmo requer, em média, 406 ciclos de clock e isso inclui a coleta de estatísticas e a realização de duas chamadas para a rotina de classificação - uma para cada intervalo. Este é um compilador móvel Athlon M300 OpenWatcom.
Olof Forshell 14/03/12
11
"distribuição aleatória regular" significa que todas as combinações de dados reais classificadas podem não ter a mesma probabilidade. Se todas as combinações não tiverem a mesma probabilidade, suas estatísticas serão quebradas porque a média precisa levar em consideração quantas vezes uma distribuição provavelmente ocorrerá. Para a contagem do relógio, se você tentar qualquer outra implementação desse tipo (links fornecidos acima) e executá-la em seu sistema de teste, teremos uma base de comparação e veremos o desempenho do escolhido.
kriss
1

Eu sei que esta é uma pergunta antiga.

Mas acabei de escrever um tipo diferente de solução que quero compartilhar.
Usando nada além de MIN MAX aninhado,

Não é rápido como ele usa 114 de cada um,
poderia reduzi-la a 75 muito simplesmente como assim -> pastebin

Mas então não é mais puramente min max.

O que pode funcionar é fazer min / max em vários números inteiros de uma só vez com o AVX

Referência PMINSW

#include <stdio.h>

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

EDIT:
Solução de ordem de classificação inspirada em Rex Kerr, muito mais rápida que a bagunça acima

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-a-b-c-d-e]=F;
}
PrincePolka
fonte
11
sempre bom ver novas soluções. Parece que é possível uma otimização fácil. No final, pode não ser tão diferente de redes de classificação.
kriss
Sim, o número de MIN e MAX pode ser reduzido, por exemplo, MIN (AB, CD) se repete algumas vezes, mas reduzi-los muito será difícil, eu acho. Eu adicionei seus casos de teste.
PrincePolka 28/09
pmin / maxsw opera em números inteiros assinados de 16 bits ( int16_t). Mas sua função C afirma que classifica uma matriz de int(que é de 32 bits em todas as implementações em C que suportam essa asmsintaxe). Você o testou apenas com números inteiros positivos pequenos que têm apenas 0 na metade superior? Isso vai funcionar ... Para intvocê precisar do SSE4.1 pmin/maxsd(d = dword). felixcloutier.com/x86/pminsd:pminsq ou pminusdpara uint32_t.
Peter Cordes
1

Descobri que, pelo menos no meu sistema, as funções sort6_iterator()e as sort6_iterator_local()definidas a seguir executavam pelo menos com a mesma rapidez e com frequência notavelmente mais rápidas do que o atual detentor de registro acima:

#define MIN(x, y) (x<y?x:y)
#define MAX(x, y) (x<y?y:x)

template<class IterType> 
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
}

Passei std::vectoro iterador dessa função a no meu código de temporização.

Eu suspeito (de comentários como este e em outros lugares) que o uso de iteradores fornece ao g ++ certas garantias sobre o que pode e o que não pode acontecer com a memória à qual o iterador se refere, o que de outra forma não teria e são essas garantias que permitem ao g ++ otimizar melhor o código de classificação (por exemplo, com ponteiros, o compilador não pode ter certeza de que todos os ponteiros estão apontando para diferentes locais de memória). Se bem me lembro, isso também faz parte do motivo pelo qual muitos algoritmos STL, comostd::sort() , geralmente têm um desempenho tão obscenamente bom.

Além disso, sort6_iterator()é algumas vezes (mais uma vez, dependendo do contexto em que a função é chamada) consistentemente superado pela função de classificação seguinte, que copia os dados em locais variáveis antes separá-los. 1 Observe que, como existem apenas 6 variáveis ​​locais definidas, se essas variáveis ​​locais são primitivas, elas provavelmente nunca serão realmente armazenadas na RAM e, em vez disso, serão armazenadas nos registros da CPU até o final da chamada de função, o que ajuda a fazer essa classificação função rápida. (Também ajuda que o compilador saiba que variáveis ​​locais distintas têm locais distintos na memória).

template<class IterType> 
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
}

Observe que a definição a SWAP()seguir algumas vezes resulta em desempenho ligeiramente melhor, embora na maioria das vezes resulte em desempenho ligeiramente pior ou em uma diferença insignificante de desempenho.

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

Se você deseja apenas um algoritmo de classificação que, nos tipos de dados primitivos, o gcc -O3 seja sempre bom em otimizar, independentemente do contexto em que a chamada para a função de classificação apareça em 1 , dependendo de como você passa a entrada, tente um dos seguintes dois algoritmos:

template<class T> 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, se você deseja passar as variáveis ​​por referência, use-as (a função abaixo difere das anteriores nas 5 primeiras linhas):

template<class T> 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
}

O motivo para usar a registerpalavra-chave é que essa é uma das poucas vezes em que você sabe que deseja esses valores nos registros. Sem register, o compilador descobrirá isso na maioria das vezes, mas às vezes não. O uso da registerpalavra - chave ajuda a resolver esse problema. Normalmente, no entanto, não use a registerpalavra-chave, pois é mais provável que seu código fique mais lento do que acelerá-lo.

Observe também o uso de modelos. Isso é feito de propósito, já que, mesmo com a inlinepalavra - chave, as funções de modelo geralmente são otimizadas de maneira muito mais agressiva pelo gcc do que as funções vanilla C (isso tem a ver com o gcc que precisa lidar com ponteiros de função para funções vanilla C, mas não com funções de modelo).

  1. Enquanto cronometrava várias funções de classificação, notei que o contexto (código circundante) no qual a chamada para a função de classificação foi feita teve um impacto significativo no desempenho, o que provavelmente se deve ao fato de a função ser incorporada e otimizada. Por exemplo, se o programa era suficientemente simples, geralmente não havia muita diferença no desempenho entre passar a função de classificação um ponteiro e passar um iterador; caso contrário, o uso de iteradores geralmente resultaria em um desempenho notavelmente melhor e nunca (na minha experiência até agora, pelo menos) em um desempenho notavelmente pior. Suspeito que isso ocorra porque o g ++ pode otimizar globalmente o código suficientemente simples.
Matthew K.
fonte
0

Tente 'mesclar lista classificada'. :) Use duas matrizes. O mais rápido para pequenas e grandes séries.
Se você concordar, verifique apenas onde inserir. Outros valores maiores que você não precisa comparar (cmp = ab> 0).
Para 4 números, você pode usar o sistema 4-5 cmp (~ 4.6) ou 3-6 cmp (~ 4.9). A classificação por bolha usa 6 cmp (6). Muitos cmp para grandes números de código mais lento.
Este código usa 5 cmp (não classificação MSL):
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;step<stepmax;step<<=1)	//bounds 1-1, 2-2, 4-4, 8-8...
		{
		a = start;
		while (a<end)
			{
			b = a + step;
			c = a + step + step;
			b = b<end ? b : end;
			c = c<end ? c : end;
			i = a;
			j = b;
			k = i;
			while (i<b && j<c)
				{
				if (cmp(arr[m][i],arr[m][j])>0)
					{arr[n][k] = arr[m][j]; j++; k++;}
				else	{arr[n][k] = arr[m][i]; i++; k++;}
				}
			while (i<b)
				{arr[n][k] = arr[m][i]; i++; k++;
}
			while (j<c)
				{arr[n][k] = arr[m][j]; j++; k++;
}
			a = c;
			}
		tmp = m; m = n; n = tmp;
		}
	return m;
	}
else
	{
	// sort 3 items
	sort10(cmp);
	return m;
	}
}

Pedro
fonte
0

Classifique 4 itens com o uso cmp == 0. O número de cmp é ~ 4,34 (o nativo do FF tem ~ 4,52), mas leva 3x o tempo que as listas mescladas. Mas melhor, menos operações de cmp, se você tiver grandes números ou grandes textos. Edit: bug reparado

Teste online 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;
}
peter
fonte
11
O caso de uso é um pouco diferente do contexto inicial da pergunta. Com tipos de tamanho fixo, os detalhes são importantes e a contagem de cmp de swaps não é suficiente. Eu nem ficaria surpreso se não fosse o tipo real que consumisse tempo, mas algo completamente diferente chamando typeof () no init. Não sei como realizar a medição do tempo real usando o Javascript. Talvez com nó?
kriss
0

Talvez eu esteja atrasado para a festa, mas pelo menos minha contribuição é uma nova abordagem.

  • O código realmente deve estar embutido
  • mesmo se embutido, há muitos ramos
  • a parte analisada é basicamente O (N (N-1)), o que parece bom para N = 6
  • o código poderia ser mais eficaz se o custo deswap fosse maior (em relação ao custo de compare)
  • Confio nas funções estáticas sendo incorporadas.
  • O método está relacionado à classificação por classificação
    • em vez de classificações, as classificações relativas (compensações) são usadas.
    • a soma das classificações é zero para cada ciclo em qualquer grupo de permutação.
    • em vez de SWAP()dois elementos, os ciclos são perseguidos, necessitando apenas de uma temp e uma troca (register-> register) (new <- old).

Atualização: mudou um pouco o código, algumas pessoas usam compiladores C ++ para compilar o código C ...

#include <stdio.h>

#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);
}
wildplasser
fonte
parece uma espécie de bolha. Potencialmente um bom candidato para a implementação mais lenta, mas ainda pode ser interessante saber se trabalhar no código faz muita diferença. Coloque seu código no mesmo formato que outros, para que possamos executar a referência nele.
kriss
@kriss en.wikipedia.org/wiki/Permutation_group Certamente não é um tipo de bolha: o código detecta ciclos na permutação especificada e percorre esses ciclos, colocando cada elemento em seu lugar final. A wsort6()função final tem a interface correta.
joop
@ joop: meu mau, nenhum tipo de bolha de fato. Dito isto no contexto, ainda estou esperando que o código seja muito pior do que qualquer outra implementação atual. A propósito, a solução de ordem de classificação é ótima em relação ao número de swaps, pois encontra diretamente a posição final de todos os itens. Também não está claro se o walkort funciona mesmo quando removemos a hipótese de que todos os números classificados são diferentes, como aqui. Para comparar o código, devemos usar o código de rastreamento. Além disso, como geralmente estou compilando em um compilador C ++, o código não funcionará porque o OP chamou uma variável "new" (e isso quebra o destaque da sintaxe).
kriss
O método está muito próximo da ordem de classificação, apenas as atribuições finais são feitas no local . Além das fileiras o1..o5, não há necessidade da segunda e[6]matriz temporária . E: compilar o código C em um compilador C ++ e culpar o código?
joop
@greybeard: obrigado, eu adicionei um espaço antes #include. Corrigido
wildplasser
0
//Bruteforce compute unrolled count dumbsort(min to 0-index)
void bcudc_sort6(int* a)
{
    int t[6] = {0};
    int r1,r2;

    r1=0;
    r1 += (a[0] > a[1]);
    r1 += (a[0] > a[2]);
    r1 += (a[0] > a[3]);
    r1 += (a[0] > a[4]);
    r1 += (a[0] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[0];

    r2=0;
    r2 += (a[1] > a[0]);
    r2 += (a[1] > a[2]);
    r2 += (a[1] > a[3]);
    r2 += (a[1] > a[4]);
    r2 += (a[1] > a[5]);
    while(t[r2]){r2++;} 
    t[r2] = a[1];

    r1=0;
    r1 += (a[2] > a[0]);
    r1 += (a[2] > a[1]);
    r1 += (a[2] > a[3]);
    r1 += (a[2] > a[4]);
    r1 += (a[2] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[2];

    r2=0;
    r2 += (a[3] > a[0]);
    r2 += (a[3] > a[1]);
    r2 += (a[3] > a[2]);
    r2 += (a[3] > a[4]);
    r2 += (a[3] > a[5]);
    while(t[r2]){r2++;} 
    t[r2] = a[3];

    r1=0;
    r1 += (a[4] > a[0]);
    r1 += (a[4] > a[1]);
    r1 += (a[4] > a[2]);
    r1 += (a[4] > a[3]);
    r1 += (a[4] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[4];

    r2=0;
    r2 += (a[5] > a[0]);
    r2 += (a[5] > a[1]);
    r2 += (a[5] > a[2]);
    r2 += (a[5] > a[3]);
    r2 += (a[5] > a[4]);
    while(t[r2]){r2++;} 
    t[r2] = a[5];

    a[0]=t[0];
    a[1]=t[1];
    a[2]=t[2];
    a[3]=t[3];
    a[4]=t[4];
    a[5]=t[5];
}

static __inline__ void sort6(int* a)
{
    #define wire(x,y); t = a[x] ^ a[y] ^ ( (a[x] ^ a[y]) & -(a[x] < a[y]) ); a[x] = a[x] ^ t; a[y] = a[y] ^ t;
    register int t;

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

    #undef wire
}
FrantzelasG
fonte
Independentemente da velocidade, você tem certeza de que funciona? Na força bruta, seus loops são duvidosos. Parece-me que eles não funcionarão se tivermos zero em valores classificados.
kriss
11
A matriz t [6] é inicializada em 0x0. Portanto, não importa onde e se uma chave com valor 0x0 será gravada.
FranG
-1

Bem, se são apenas 6 elementos e você pode alavancar o paralelismo, deseja minimizar a ramificação condicional etc. Por que você não gera todas as combinações e testa a ordem? Eu arriscaria que, em algumas arquiteturas, pode ser bem rápido (desde que você tenha a memória pré-alocada)

GClaramunt
fonte
9
Existem 720 pedidos, e as versões rápidas estão bem abaixo de 100 ciclos. Mesmo que um paralelismo maciço pudesse ser alavancado, em uma escala de tempo tão pequena, o custo de criação e sincronização dos encadeamentos provavelmente excederia o custo de apenas classificar as matrizes em um núcleo.
Kevin da
-3

Aqui estão três métodos típicos de classificação que representam três classes diferentes de algoritmos de classificação:

Insertion Sort: Θ(n^2)

Heap Sort: Θ(n log n)

Count Sort: Θ(3n)

Mas confira a discussão de Stefan Nelsson sobre o algoritmo de classificação mais rápido? onde ele discute uma solução que desce para O(n log log n).. confira sua implementação em C

Este algoritmo de classificação semi-linear foi apresentado por um artigo em 1995:

A. Andersson, T. Hagerup, S. Nilsson e R. Raman. Classificando em tempo linear? Em Anais do 27º Simpósio Anual da ACM sobre a Teoria da Computação, páginas 427-436, 1995.

Khaled A Khunaifer
fonte
8
Isso é interessante, mas não vem ao caso. Big-Θ visa ocultar fatores constantes e mostrar a tendência quando o tamanho do problema (n) aumenta. O problema aqui é totalmente sobre um tamanho de problema fixo (n = 6) e leva em consideração fatores constantes.
kriss
@kriss você está certo, minha comparação é assintótica, então a comparação prática vai mostrar se é rápido ou não para esse caso
Khaled.K
4
Você não pode concluir, porque cada algoritmo diferente oculta uma constante multiplicativa K diferente (e também uma constante aditiva C). ou seja: k0, c0 para classificação de inserção, k1, c1 para classificação de heap e assim por diante. Todas essas constantes sendo realmente diferentes (você poderia dizer em termas físicos que cada algoritmo possui seu próprio "coeficiente de atrito"), não é possível concluir que um algoritmo seja realmente mais rápido nesse caso (ou em qualquer caso n fixo).
kriss