"5 centavos" para falar sobre as sortes

Na continuação do tópico , quero compartilhar meu código, que ultrapassa std::sort() das versões atuais da Biblioteca GNU C ++ e (aproximadamente, não há dados exatos) repete o resultado de "Sort Alexandrescu" com o CppCon 2019 .

Condições da tarefa

No código (não C++ ), foi necessário um esforço razoável para que a classificação não fosse pior que std::sort() para se livrar da sobrecarga de usar a biblioteca qsort() . Incluindo, portanto, use macros em vez de modelos.
Por sua vez, se você classifica "ratos" em vez de "elefantes", o custo de qsort() bastante alto: aritmética de endereço extra e uma chamada indireta para a função comparadora.

Resultado

De acordo com as informações disponíveis, essa combinação de algoritmos e recursos de implementação é mais rápida do que muitas outras opções, no sentido prático:

• pelo número de comparações e movimentos (medido substituindo a classe C++ pela contagem de comparações e atribuições).
• pelo volume do código da máquina (ocupa pouco espaço no cache).
• pelo volume do código fonte e sua transparência.
• em seqüências aleatórias longas, o ganho tende a 3-5%, dependendo de SORT_THRESHOLD .
• até 1,5-2-3 vezes mais rápido com dados pedidos ou predominantemente pedidos.
• uma pequena perda apenas em seqüências muito curtas na ordem inversa.

É muito provável que esta opção seja um pouco mais rápida e / ou um pouco mais lenta do que a grande maioria das sortes, mas descobrir isso é literalmente um trabalho titânico que eu não posso pagar.

É interessante que alguém compare essa opção com as opções atuais do Tarantool, PostgreSQL, SQLite e MySQL. Espero que o Kaamos não consiga passar com o seu SysBench .

Como está Alexandrescu?

No primeiro comentário do RPG18, havia um link para uma apresentação recente de Andrei Alexandrescu “A velocidade é encontrada nas mentes das pessoas” , onde ele leva a uma idéia bastante semelhante, mas vai para heap_sort mais perto da final.

O desempenho me pareceu um pouco prolongado (se o olegbunin tivesse dado 90 minutos pelo menos uma vez ...), mas os números não são suficientes. Em particular, quero ver o comportamento de classificação com o aumento de N , pois um aumento no limite de conclusão do QuickSort leva à aceleração em tamanhos grandes e à desaceleração em tamanhos pequenos, etc.

No entanto, a julgar pelos números que Alexandrescu cita, a opção descrita repentinamente dá uma aceleração semelhante. No entanto, até encontrar o código mostrado para Alexandrescu em sua forma finalizada, "pegar e comparar", e não há tempo para codificar por vídeo (escreva se você o encontrar ou fizer).

Lado ideológico

O lado teórico e ideológico do "algoritmo" é bastante simples:

1. Para sequências não curtas, usamos o QuickSort com todas as otimizações aceitáveis:
   
   • Não recursivamente usando a pilha interna de posições nos ponteiros.
   • Como elemento de suporte, usamos a mediana do primeiro, do meio e do último elementos.
   • Nós não classificamos pequenas porções, deixamos para o ShellSort.
   • Após a divisão, sempre colocamos a maior parte da pilha; como resultado, a pilha não pode ser mais profunda que Log2(N) .
2. Adicionar dados de classificação usando o ShellSort:
   
   • número mínimo de passes.
   • a etapa na primeira passagem está correlacionada com o tamanho máximo do segmento não classificado.
   • total apenas duas passagens com as etapas 8 e (inevitavelmente) 1.
3. O uso do ShellSort permite aumentar de maneira relativamente segura o limite de saída do QuckSort. Como resultado, temos uma combinação de uma das melhores opções do QuickSort com economia devido a uma saída anterior e pré-classificação um pouco mais rápida.

Deve-se observar que, dependendo da arquitetura do processador e das condições do aplicativo, você pode aumentar o ganho em seqüências longas de 10 a 15% escolhendo SORT_THRESHOLD entre 128-256. No entanto, isso atrasa o processamento de seqüências com a ordem inversa e próxima a ela.
No entanto, esse é um bom bônus se você entender que a ordem inversa é improvável em seus dados ou se puder detectar esses casos de maneira barata e executar uma ramificação com um pequeno SORT_THRESHOLD .

PS
A opção de classificação descrita foi "refeita" para o meu projeto libmdbx (banco de dados de valores-chave rapidamente incorporado com ACID), no qual outro dia a descrição do README e da API foi atualizada (na verdade, reescrita). Portanto, serei grato por corrigir erros de digitação e por conselhos e sugestões. Ele próprio, por via de regra, não é visível falta de algumas informações.