Hoy compartimos código de código abierto que puede ordenar matrices de números aproximadamente diez veces más rápido que std::sort de C++, y supera a los algoritmos específicos de arquitectura más avanzados, siendo portátil en todas las arquitecturas de CPU modernas. A continuación analizamos cómo lo logramos.

Primero, un poco de contexto. Existe una tendencia reciente hacia bases de datos columnares que almacenan consecutivamente todos los valores de una columna particular, en lugar de almacenar todos los campos de un registro o "fila" antes que los del siguiente registro. Esto puede ser más rápido de filtrar u ordenar, que son bloques de construcción clave para consultas SQL; por lo tanto, nos centramos en este diseño de datos.

Dado que la ordenación ha sido muy estudiada, ¿cómo podemos encontrar una aceleración de 10x? La respuesta está en las instrucciones SIMD/vectoriales. Estas llevan a cabo operaciones sobre múltiples elementos independientes en una sola instrucción—por ejemplo, operar sobre 16 float32 a la vez cuando se usa el conjunto de instrucciones AVX-512, o cuatro en Arm NEON.

Si ya está familiarizado con SIMD, es posible que haya oído que se utiliza en supercomputadoras, álgebra lineal para aplicaciones de aprendizaje automático, procesamiento de video o códecs de imágenes como JPEG XL. Pero si las operaciones SIMD solo involucran elementos independientes, ¿cómo podemos ordenarlos, lo que implica reorganizar elementos adyacentes del arreglo? Imagine que tenemos alguna forma especial de ordenar, por ejemplo, arreglos de 256 elementos. Entonces, el algoritmo Quicksort para ordenar un arreglo más grande consiste en particionarlo en dos subarreglos: aquellos menores que un valor "pivote" (idealmente la mediana), y todos los demás; luego recursar hasta que un subarreglo sea de a lo sumo 256 elementos, y usar nuestro método especial para ordenarlos. La partición representa la mayor parte del tiempo de CPU, así que si podemos acelerarla usando SIMD, tenemos una ordenación rápida.

Afortunadamente, los conjuntos de instrucciones modernos (Arm SVE, RISC-V V, x86 AVX-512) incluyen una instrucción especial adecuada para la partición. Dada una entrada separada de valores sí/no (si un elemento es menor que el pivote), esta instrucción de "almacenamiento comprimido" almacena en memoria consecutiva solo los elementos cuyo valor de entrada correspondiente es "sí". Luego podemos negar lógicamente los valores sí/no y aplicar la instrucción nuevamente para escribir los elementos en la otra partición. Esta estrategia se ha utilizado en un Quicksort específico para AVX-512. Pero ¿qué pasa con otros conjuntos de instrucciones como AVX2 que no tienen almacenamiento comprimido? Trabajos anteriores han mostrado cómo emular esta instrucción usando instrucciones de permutación. Nos basamos en estas técnicas para lograr el primer Quicksort vectorizado que es portátil a seis conjuntos de instrucciones en tres arquitecturas, y de hecho supera a las ordenaciones específicas de arquitectura anteriores.

Nuestra implementación utiliza las funciones SIMD portátiles de Highway, por lo que no tenemos que reimplementar aproximadamente 3,000 líneas de C++ para cada plataforma. Highway utiliza almacenamiento comprimido cuando está disponible y, de lo contrario, las instrucciones de permutación equivalentes. En contraste con el estado del arte anterior—que también era específico para enteros de 32 bits—admitimos una gama completa de entradas de 16-128 bits. A pesar de nuestra única implementación portátil, alcanzamos velocidades récord tanto en AVX2, AVX-512 (Intel Skylake) como en Arm NEON (Apple M1). Para un millón de números de 32/64/128 bits, nuestro código ejecutándose en Apple M1 puede producir salida ordenada a tasas de 499/471/466 MB/s. En un Skylake de 3 GHz con AVX-512, las velocidades son 1123/1119/1120 MB/s. Curiosamente, AVX-512 es 1.4-1.6 veces más rápido que AVX2—una aceleración que vale la pena por cero esfuerzo adicional (Highway verifica qué instrucciones están disponibles en la CPU y utiliza las mejores disponibles). Cuando se ejecuta en AVX2, medimos 798 MB/s, mientras que el estado del arte anterior optimizado para AVX2 solo alcanza 699 MB/s. En comparación, la biblioteca estándar alcanza 58/128/117 MB/s en la misma CPU, por lo que hemos logrado una aceleración de 9-19x dependiendo del tipo de números.

Anteriormente, la ordenación se consideraba costosa. Nos interesa ver qué nuevas aplicaciones y capacidades se desbloquearán al poder ordenar a 1 GB/s en un solo núcleo de CPU. La fuente con licencia Apache2 ...