Arreglo de Judy

En informática , un arreglo Judy es una implementación optimizada manualmente por Hewlett-Packard a principios de la década de 2000 de un árbol radix de 256 niveles que utiliza muchos tipos de nodos situacionales para reducir la latencia de los llenados de la línea de caché de la CPU . ^{[ 1 ] [ 2 ]} Como un árbol radix comprimido, un arreglo Judy puede almacenar datos indexados por enteros o cadenas potencialmente dispersos con un uso de memoria comparativamente bajo y una baja latencia de lectura, sin depender de hash o balanceo de árboles, y sin sacrificar el recorrido en orden. ^{[ 3 ]} La latencia por operación escala como${\displaystyle O(\log n)}$—como se espera de un árbol— y el factor constante principal es lo suficientemente pequeño como para que los arreglos de Judy sean adecuados incluso para el rango de petaelementos. ^{[ 4 ]} Cuando son aplicables, pueden ser más rápidos que las implementaciones de árboles AVL , árboles B , tablas hash o listas de salto del mismo período de tiempo. ^{[ 3 ]}

El conjunto Judy fue inventado por Douglas Baskins a lo largo de los años previos a 2002 y recibió su nombre en honor a su hermana. ^{[ 5 ]}

En términos generales, los nodos de árbol en los arreglos de Judy se dividen en tres categorías, aunque la implementación utiliza variaciones situacionales dentro de cada categoría: ^{[ 2 ]}

• Un nodo lineal es una lista de asociación corta, de capacidad fija y basada en matrices, diseñada para caber en una línea de caché. Es decir, dicho nodo tiene una matriz de bytes de clave y una matriz paralela de valores o punteros. La búsqueda se realiza mediante una búsqueda lineal sobre la matriz de claves y, posteriormente, mediante acceso aleatorio al índice correspondiente en la matriz de valores/punteros.
• Un nodo de mapa de bits es un vector de bits de tamaño 256 que registra qué valores/elementos secundarios están presentes y, a continuación, una lista ordenada de los valores o punteros correspondientes. La búsqueda se realiza mediante el conteo de bits hasta el índice de destino y, posteriormente, mediante acceso aleatorio a la entrada correspondiente en la matriz de valores/punteros. El mapa de bits cabe en una línea de caché típica de la CPU, y el acceso aleatorio solo carga una línea de caché de la lista ordenada, por lo que para leer estos nodos se requieren como máximo dos líneas de caché.
• Un nodo sin comprimir es un nodo trie convencional , representado como una matriz de valores/punteros. La búsqueda se realiza mediante acceso aleatorio utilizando el byte clave como índice, lo que a nivel de CPU requiere acceder a una línea de caché.

Los nodos lineales se utilizan para ramificaciones bajas, los nodos de mapa de bits para ramificaciones intermedias y los nodos sin comprimir para ramificaciones altas. ^{[ 2 ]}

Gracias a las optimizaciones de caché , los arreglos Judy son rápidos, especialmente para conjuntos de datos muy grandes. En ciertas tareas que involucran datos secuenciales o casi secuenciales, los arreglos Judy pueden incluso superar a las tablas hash, ya que, a diferencia de estas, la estructura de árbol interna de los arreglos Judy mantiene el orden de las claves. ^{[ 6 ]}

Por otro lado, los arreglos Judy no son adecuados para todos los tipos de clave, dependen en gran medida de la división de casos en tiempo de compilación (lo que aumenta tanto el tamaño del código compilado como el trabajo que implica el reajuste para una nueva arquitectura ^{[ 6 ]} ), hacen algunas concesiones a arquitecturas antiguas que pueden no ser relevantes para las máquinas modernas y no explotan SIMD . ^{[ 2 ]} Están optimizados para el rendimiento de lectura sobre el rendimiento de escritura. ^{[ 2 ]}

• Árbol de raíz
• Trie bit a bit con mapa de bits
• Trie mapeado a matriz hash

• Sitio principal de Judy Arrays
• Cómo funcionan los arreglos Judy y por qué son tan rápidos.
• Descripción técnica completa de los arreglos Judy.
• Una comparación de rendimiento independiente de Judy con tablas hash.
• Una implementación compacta de arreglos Judy en 1250 líneas de código C.