Static Search Trees: 40 veces más rápido que la búsqueda binaria

• Implementa un árbol de búsqueda estático llamado "árbol S+" para realizar búsquedas de alta velocidad sobre datos ordenados
• Parte del código propuesto en una publicación de Algorithmica, lo optimiza e implementa en código ideas adicionales y mejoras sugeridas
• Tras analizar el código ensamblador, optimiza todas las instrucciones posibles para maximizar el rendimiento
• Introduce batching para procesar múltiples consultas en paralelo y mejorar el throughput
• El objetivo es ejecutar consultas de forma eficiente sobre datos ordenados con un alto throughput mediante el árbol S+

1. Introducción y motivación

• Definición del problema:

  • Entrada: lista ordenada de enteros sin signo de 32 bits vals: Vec<u32>
  • Salida: una estructura de datos de tamaño mínimo que devuelva el valor mayor o igual que una consulta específica (q)
  • Métrica: número de consultas independientes que pueden procesarse por segundo

• Objetivo:

  • Construir estructuras de datos eficientes en bioinformática, en particular para acelerar la búsqueda en suffix arrays para indexación de secuencias de ADN
  • Maximizar el rendimiento aprovechando el desempeño del CPU y las instrucciones SIMD

• Material recomendado:

  • Estudio sobre búsqueda binaria y disposición de arreglos (“Array Layouts for Comparison-Based Searching”)
  • Material introductorio sobre árboles S+ y árboles B estáticos

2. Árboles S+ y optimización

2.1 Búsqueda binaria y layout Eytzinger

• La búsqueda binaria de la biblioteca estándar de Rust tiene poca eficiencia de caché y su rendimiento cae a medida que crece el tamaño de los datos
• Layout Eytzinger:
  • Almacena un árbol de búsqueda binaria en forma de arreglo para maximizar el uso de caché
  • Rendimiento: hasta 4 veces más rápido que la búsqueda binaria para datos que exceden la caché L3

2.2 Concepto de árbol S+

• Árbol S:
  • Estructura de árbol hexadecimal con 15 valores ordenados por nodo
  • Más eficiente que un árbol B y más compactable que el layout Eytzinger
• Árbol S+:
  • Almacena todos los datos en nodos hoja y los duplica en los nodos superiores
  • Ofrece una búsqueda simple y una estructura eficiente

2.3 Optimización de la función find

• Búsqueda lineal básica:
  • Recorre los datos y devuelve el valor que cumple la condición (ineficiente)
• Vectorización automática:
  • Se transforma en código sin ramas, con mejora de rendimiento de 2 veces gracias al uso de instrucciones SIMD
• Implementación SIMD manual:
  • Optimización manual con instrucciones SIMD para exprimir el rendimiento al máximo con 5 instrucciones

3. Batching y prefetching

3.1 Batching

• Procesa múltiples consultas en paralelo para compensar la latencia de memoria
• El throughput mejora al aumentar el tamaño del lote, hasta saturarse en un tamaño máximo de lote de 16

3.2 Prefetching

• Trae por adelantado el siguiente nodo a memoria y mejora el rendimiento en datos que exceden la caché L3
• Combinado con batching, reduce el tiempo de procesamiento de 45ns/query a 30ns/query

4. Optimización del layout y de la estructura de datos

4.1 Cambio del tamaño de nodo

• Reduce a 15 la cantidad de valores por nodo para simplificar multiplicaciones y mejorar la eficiencia de caché
• Logra una ligera mejora de rendimiento para datos dentro de la caché L3

4.2 Cambio del layout de memoria

• Experimenta con layouts almacenados en orden inverso o con configuraciones que minimizan el padding
• Ni el orden inverso ni la reducción de padding tienen un impacto importante en el rendimiento

5. Particionamiento de datos

5.1 Particionamiento basado en prefijos

• Separa las particiones según los bits más altos de los datos
• Mejora el rendimiento con datos pequeños, pero introduce sobrecarga de memoria

5.2 Subárboles comprimidos

• Empaqueta cada subárbol para aumentar la eficiencia espacial
• Requiere rastrear el tamaño de las particiones y la velocidad de consulta disminuye ligeramente

6. Comparación multihilo

• Con 6 hilos, el tiempo por consulta se reduce de 27ns a 7ns
• El límite de ancho de banda de la RAM se convierte en el cuello de botella

7. Conclusión e investigación futura

• Más de 40 veces de mejora frente a la búsqueda binaria (1150ns/query → 27ns/query)
• Trabajo futuro:
  • Optimización del balanceo de datos y reducción de accesos a RAM
  • Manejo de consultas por rango y consultas ordenadas
  • Integración con búsqueda en suffix arrays

[beenzinozino]

Vaya... si se aplica a las bibliotecas integradas de varios lenguajes, parece que el impacto podría ser considerable.

[GN⁺]

Comentarios de Hacker News

• Se observa que Rust se usa cada vez más en contenido de bajo nivel relacionado con algoritmos. Antes, predominaba el contenido escrito en C(++) o en pseudocódigo científico.

  • Aunque no conoce bien Rust, pudo entender el contenido escrito en Rust. Es similar a cómo un programador de Rust puede entender ejemplos de algoritmos escritos en C.
  • Prefiere que Rust se estandarice, y cree que también sería bueno usar Zig

• No se exploró el método de dividir las consultas en lotes. El costo principal es hacer búsquedas en tablas fuera de caché

  • Si hay suficientes consultas, se pueden resolver varias capas del árbol al mismo tiempo
  • Puede surgir el problema de tener que ordenar los resultados en el orden correcto de salida

• La cantidad de valores int32 no es tan grande, y el bitset completo ocupa 512MB. Para una estructura de datos general, recomienda Roaring Bitmaps

  • Si solo se necesitan consultas simples, vale la pena considerar una función hash perfecta mínima

• Le sorprenden las formas de mejorar la eficiencia de bajo nivel en Rust. Le gustaría compararlo con una implementación en C++

• La ventaja del árbol Eytzinger es que existe una fórmula para convertir índices de nodos a posiciones en recorrido inorden

  • Es útil cuando el almacenamiento base de claves es un conjunto de claves ordenadas
  • Con Eytzinger, se pueden predecir de antemano varias iteraciones del bucle

• Le sorprende que buscar u32 en 4GB de memoria tenga una sobrecarga de ~27ns

  • Tiene curiosidad por cómo avanza la optimización con tamaño de lote 8
  • Los resultados con multihilo también son interesantes. Al pasar de 1 a 6 hilos, la sobrecarga mejora 4 veces

• Hay mucha discusión sobre Rust y C++, pero piensa en cómo implementarlo en Common Lisp manteniendo SIMD

• Cada vez que lee un artículo sobre optimización de bajo nivel, agradece que el autor haya invertido tiempo en ahorrarle nanosegundos

  • Se pregunta cuánto tiempo ha ahorrado la humanidad gracias a la acumulación de estas optimizaciones

• Cree que hay un error en la figura 3 de la sección 1.7. Sugiere que la etiqueta del eje y en la figura 1 de la sección 1.3 debería ser "throughput inverso"

• Si de vez en cuando hay que soportar escrituras, se puede usar un gran árbol de búsqueda estático y un árbol pequeño con escritura habilitada

  • Cuando haya suficientes cambios, se pueden transferir al nuevo versión del árbol estático