Hoje estamos compartilhando código de código aberto que pode classificar arrays de números cerca de dez vezes mais rápido que o std::sort do C++, e supera algoritmos específicos de arquitetura de última geração, sendo portátil em todas as arquiteturas modernas de CPU. Abaixo discutimos como conseguimos isso.

Primeiro, um pouco de contexto. Há uma tendência recente em direção a bancos de dados colunares que armazenam consecutivamente todos os valores de uma coluna específica, em vez de armazenar todos os campos de um registro ou "linha" antes dos do próximo registro. Isso pode ser mais rápido para filtrar ou classificar, que são blocos de construção essenciais para consultas SQL; portanto, focamos nesse layout de dados.

Dado que a classificação tem sido intensamente estudada, como podemos encontrar um ganho de velocidade de 10x? A resposta está nas instruções SIMD/vetoriais. Elas realizam operações em múltiplos elementos independentes em uma única instrução—por exemplo, operar em 16 float32 de uma vez ao usar o conjunto de instruções AVX-512, ou quatro no Arm NEON.

Se você já está familiarizado com SIMD, pode ter ouvido falar que ele é usado em supercomputadores, álgebra linear para aplicações de aprendizado de máquina, processamento de vídeo ou codecs de imagem como JPEG XL. Mas se as operações SIMD envolvem apenas elementos independentes, como podemos classificá-los, o que envolve reorganizar elementos adjacentes do array? Imagine que temos alguma maneira especial de classificar, por exemplo, arrays de 256 elementos. Então, o algoritmo Quicksort para classificar um array maior consiste em particioná-lo em dois subarrays: aqueles menores que um valor "pivô" (idealmente a mediana), e todos os outros; depois recursar até que um subarray tenha no máximo 256 elementos, e usar nosso método especial para classificá-los. O particionamento é responsável pela maior parte do tempo de CPU, então se pudermos acelerá-lo usando SIMD, temos uma classificação rápida.

Felizmente, os conjuntos de instruções modernos (Arm SVE, RISC-V V, x86 AVX-512) incluem uma instrução especial adequada para particionamento. Dada uma entrada separada de valores sim/não (se um elemento é menor que o pivô), esta instrução "compress-store" armazena em memória consecutiva apenas os elementos cuja entrada correspondente é "sim". Podemos então negar logicamente os valores sim/não e aplicar a instrução novamente para escrever os elementos na outra partição. Essa estratégia foi usada em um Quicksort específico para AVX-512. Mas e quanto a outros conjuntos de instruções como AVX2 que não têm compress-store? Trabalhos anteriores mostraram como emular essa instrução usando instruções de permutação. Construímos sobre essas técnicas para alcançar o primeiro Quicksort vetorizado que é portátil para seis conjuntos de instruções em três arquiteturas, e de fato supera classificações específicas de arquitetura anteriores.

Nossa implementação usa as funções SIMD portáteis do Highway, então não precisamos reimplementar cerca de 3.000 linhas de C++ para cada plataforma. O Highway usa compress-store quando disponível e, caso contrário, as instruções de permutação equivalentes. Em contraste com o estado da arte anterior—que também era específico para inteiros de 32 bits—suportamos uma gama completa de entradas de 16 a 128 bits. Apesar de nossa única implementação portátil, alcançamos velocidades recordes tanto em AVX2, AVX-512 (Intel Skylake) quanto em Arm NEON (Apple M1). Para um milhão de números de 32/64/128 bits, nosso código rodando no Apple M1 pode produzir saída classificada a taxas de 499/471/466 MB/s. Em um Skylake de 3 GHz com AVX-512, as velocidades são 1123/1119/1120 MB/s. Curiosamente, o AVX-512 é 1,4-1,6 vezes mais rápido que o AVX2—um ganho de velocidade que vale a pena por zero esforço adicional (o Highway verifica quais instruções estão disponíveis na CPU e usa as melhores disponíveis). Ao rodar em AVX2, medimos 798 MB/s, enquanto o estado da arte anterior otimizado para AVX2 consegue apenas 699 MB/s. Em comparação, a biblioteca padrão alcança 58/128/117 MB/s na mesma CPU, então conseguimos um ganho de velocidade de 9-19x dependendo do tipo de números.

Anteriormente, a classificação era considerada cara. Estamos interessados em ver quais novos aplicativos e capacidades serão desbloqueados ao poder classificar a 1 GB/s em um único núcleo de CPU. A fonte licenciada sob Apache2 ...