Google crea el primer Quicksort vectorizado: 10x más rápido

Google libera un Quicksort vectorizado y portátil: 10x más rápido que `std::sort`

Google publicó bajo licencia Apache 2 el código de un Quicksort vectorizado capaz de ordenar arreglos numéricos cerca de 10 veces más rápido que la implementación std::sort de C++, superando además a algoritmos específicos por arquitectura. El trabajo, firmado por Jan Wassenberg del equipo de Brain Computer Architecture Research, se apoya en la librería Highway y en instrucciones SIMD/vectoriales presentes en CPUs modernas (Arm SVE, RISC-V V y x86 AVX-512/AVX2).

El dato concreto para un founder que trabaja con datos a escala: en un Apple M1, el código ordena un millón de números de 32/64/128 bits a 499/471/466 MB/s; en un Intel Skylake a 3 GHz con AVX-512, alcanza 1123/1119/1120 MB/s, es decir, más de 1 GB/s por núcleo en una sola CPU de uso general.

Por qué importa en bases de datos columnares y pipelines de IA

La pieza angular del avance es el data layout columnar: en lugar de guardar filas completas de un registro, las bases de datos modernas (Snowflake, BigQuery, ClickHouse, DuckDB, DuckDB, Apache Arrow) almacenan columnas contiguas en memoria porque filtrar, agrupar y ordenar por una sola columna es mucho más eficiente. Ordenar es el bloque constructivo del ORDER BY, de joins y de agregaciones; si ordenar se vuelve 10x más rápido, consultas enteras se vuelven 10x más rápidas sin tocar el resto del stack.

👥 ¿Quieres ir más allá de la noticia?

En nuestra comunidad discutimos las tendencias, compartimos oportunidades y nos ayudamos entre emprendedores. Sin humo, solo acción.

👥 Unirme a la comunidad

El segundo punto clave es la portabilidad. Hasta ahora, las implementaciones SIMD de ordenamiento eran específicas para una arquitectura (AVX-512 o NEON). Highway detecta automáticamente las instrucciones disponibles y usa las mejores: en Skylake, AVX-512 resulta 1.4–1.6 veces más rápido que AVX2 sin esfuerzo adicional del desarrollador. Esto permite escribir el código una sola vez y desplegarlo en servidores Intel, chips Apple Silicon, GPUs ARM en la nube (AWS Graviton) o aceleradores RISC-V sin mantener variantes.

Cómo logra Google una aceleración de un dígito

La idea central combina tres técnicas:

SIMD sobre instrucciones compress-store. Las arquitecturas modernas (Arm SVE, RISC-V V, x86 AVX-512) incluyen una instrucción compress-store que recibe un vector de números y otro vector de bits sí/no, y almacena solo los elementos marcados como "sí". Aplicada dos veces —una para los menores al pivote y otra para los mayores— resuelve la partición del Quicksort en pocas instrucciones. Para arquitecturas sin compress-store como AVX2, Highway emula el comportamiento con instrucciones permute equivalentes.
Quicksort con caso base vectorizado. El algoritmo particiona arreglos grandes de forma SIMD y, al llegar a sub-arreglos de hasta 256 elementos, aplica una rutina de ordenamiento vectorial específica para ese tamaño. La mayor parte del tiempo de CPU se consume en la partición, así que vectorizarla es lo que mueve la aguja.
Comparación contra el estado del arte. En AVX2, la implementación previa optimizada para esa arquitectura alcanzaba 699 MB/s; el código de Google llega a 798 MB/s en la misma CPU. En el mismo hardware, std::sort solo alcanza 58/128/117 MB/s para 32/64/128 bits, lo que explica la mejora de 9–19x reportada por Wassenberg.

Qué cambia para una startup que procesa datos

El trabajo no es una librería de producción out-of-the-box —es una implementación de referencia publicada en GitHub bajo Apache 2—, pero abre tres líneas de optimización realistas para equipos técnicos:

Acelerar pipelines analíticos sin cambiar de base de datos. Equipos que ya usan DuckDB, ClickHouse o Arrow como motor analítico embebido pueden ver mejoras sustanciales simplemente al actualizar a versiones que integren rutinas SIMD como estas. Revisar las notas de cada release para confirmar el soporte.
Ordenar a 1 GB/s por núcleo en CPU. Si tu workload actual está ligado a std::sort, pandas.DataFrame.sort_values o implementaciones de NumPy menos vectorizadas, el techo de CPU se mueve un orden de magnitud arriba. Antes de saltar a un clúster más grande, vale la pena auditar si el cuello de botella está en ordenamiento puro.
Diseñar para datos columnares desde el inicio. Formatos como Apache Arrow, Parquet o DuckDB ya aprovechan layouts columnares. Si tu arquitectura los soporta nativamente, cualquier rutina de ordenamiento que adoptes rendirá mejor que sobre representaciones orientadas a filas.

Limitaciones a tener en cuenta

El benchmark se ejecutó sobre arreglos de números (enteros y flotantes de 16 a 128 bits), no sobre registros complejos con claves múltiples. Para cargas de datos en producción, el cuello de botella rara vez es solo la comparación de números: entran en juego la localidad de memoria, la latencia de RAM y disco, y la serialización. Aún así, acelerar el núcleo del algoritmo siempre es ganancia neta, porque reduce el tiempo de CPU cobrado en instancias cloud (especialmente en Graviton o instancias reservadas que se facturan por hora, no por uso).

Otra arista: Highway requiere compiladores modernos (Clang, GCC) y CPUs con SIMD. Para hardware legacy sin AVX2 como mínimo, el código cae a un camino no vectorizado. Conviene auditar el parque de servidores y los targets mínimos antes de depender de estas rutinas en producción.

El contexto abierto: Highway, RISC-V V y la nueva era del SIMD portable

Highway es la librería base que Google mantiene desde hace años para abstraer las diferencias entre sets de instrucciones SIMD sin tener que reescribir ~3000 líneas de C++ por plataforma. El anuncio es relevante porque es el primer Quicksort vectorizado y portable simultáneamente a seis sets de instrucciones y tres arquitecturas, según el equipo de Wassenberg. Hasta ahora, ese tipo de código existía solo para AVX-512 de forma específica.

La tendencia de fondo es que el SIMD dejó de ser dominio exclusivo de supercomputadoras, álgebra lineal para ML, codecs de video o JPEG XL y empieza a permatar software de uso general. Ordenar a 1 GB/s por núcleo en una sola CPU es un umbral nuevo: lo que ayer requería GPU o cómputo distribuido empieza a caber en un portátil.

Para founders y CTOs, la lectura estratégica es clara: invertir tiempo en auditar qué tan SIMD-friendly es tu stack analítico (lenguaje, librerías, formatos de archivo) paga dividendos desproporcionados frente a subir el tamaño de la instancia o añadir más nodos al clúster.