Reemplazando siete algoritmos O(N²) en un sábado

Tu IA puede escribir código que funciona. Hacer que sea código que escala es donde se gana o se pierde un runtime espacial, y es exactamente la disciplina alrededor de la cual está construido RakuAI.

Los agentes son buenos escribiendo código que funciona. A veces son malos escribiendo código que escala. Este es un patrón que he llegado a reconocer y a presupuestar: cuando el enmarcado de la incidencia pide una función que haga X, el agente escribe una función que hace X correctamente en una entrada pequeña y se desmorona en una de tamaño real.

Este sábado salí a buscar esas funciones a propósito. Aparecieron siete. Para el final del sábado, las siete estaban corriendo sus algoritmos de producción reales en lugar de los marcadores de posición de fuerza bruta que los agentes habían aterrizado originalmente.

Esta es la entrada sobre qué era cada uno, por qué importaba, y qué se equivocaron los agentes en cada caso.

El patrón

El patrón aparece así. Se archiva una incidencia. «Implementa detección de colisiones entre los objetos A y B. Debería detectar cuándo los objetos se superponen. Criterio de aceptación: la función bool devuelve true cuando se superponen, false en caso contrario.»

El agente escribe la función. La función funciona. La función es fuerza bruta O(N²). Para dos objetos, está bien. Para doscientos objetos, está bien. Para dos mil objetos, la tasa de fotogramas desaparece.

El prompt del agente no especificó el objetivo de complejidad asintótica. El agente satisfizo el prompt. El prompt no satisfizo al motor.

Este es un problema de disciplina de mi parte, no un problema del agente. La solución es ser específico en el prompt sobre los objetivos de complejidad, especificar la clase de algoritmo explícitamente cuando importa, y auditar este tipo de fallback de fuerza bruta con una cadencia regular. Este sábado fue la cadencia de auditoría.

Siete reemplazos específicos

Quiero ser específico sobre cada uno porque el patrón es idéntico y las lecciones se acumulan.

Uno. Detección de colisiones de fase amplia en física 2D. La implementación original era un bucle doblemente anidado sobre cada par de objetos. O(N²) por fotograma. Reemplazado con sweep-and-prune (Baraff, 1992): ordenar las cajas delimitadoras alineadas a los ejes por su coordenada X mínima, luego escanear una vez. Los pares solo se superponen en el eje X si la X máxima de una caja es mayor que la X mínima de la otra. La ordenación es O(N log N); el escaneo es O(N + K) donde K es el número de pares que realmente se superponen. Para escenas típicas, K es mucho menor que N², que es todo el punto.

Dos. Detección de colisiones espaciales para el subsistema de población de agentes. Mismo patrón, superficie distinta. La implementación original era un bucle doblemente anidado que verificaba cada agente contra cada otro agente. Reemplazado con una cuadrícula de hash espacial. Cada agente se hashea por las coordenadas de su celda delimitadora; las colisiones solo se verifican entre agentes en la misma celda o celdas adyacentes. El tamaño de celda se elige como aproximadamente dos veces el radio promedio de agente. Complejidad esperada O(N), peor caso O(N²) cuando todos están en la misma celda, lo que no ocurre en juego normal. La función hash es hash de coordenadas 3D estilo FNV. La deduplicación de pares es mediante un conjunto ordenado de uint64_t de pares (min(a,b), max(a,b)).

Tres. Optimización de caché de vértices del cargador de modelos. La implementación original cargaba vértices y triángulos en el renderizador en el orden que el autor del activo especificaba. La mayoría de las herramientas de autoría no optimizan para la caché de vértices de la GPU, lo que significa que el renderizador desperdicia muchos ciclos volviendo a buscar vértices que ya tenía. Reemplazado con la optimización de caché de vértices de Tom Forsyth de 2006: modelo de caché LRU con un tamaño de 32, puntuando cada triángulo candidato con una función de decaimiento por posición en caché más una bonificación de valencia (los triángulos que comparten vértices con muchos otros triángulos no procesados puntúan más alto). El resultado es una tasa de fallo de caché amortizada que es casi óptima para topologías de malla típicas. La implementación corre en O(T) donde T es el conteo de triángulos.

Cuatro. Emparejamiento de descriptores de características de visión. El pipeline de visión por computadora del runtime hace detección de características en cada fotograma y empareja características entre fotogramas consecutivos para el seguimiento. La implementación original tenía un marcador de posición que devolvía una fracción fija de los descriptores de entrada como «emparejados». El marcador de posición ni siquiera era fuerza bruta. Era un stub deliberado. El reemplazo es emparejamiento de descriptores por fuerza bruta real con la prueba de razón de Lowe (2004). Para descriptores ORB (binarios), la métrica de distancia es Hamming vía XOR más un conteo de bits de Kernighan. Para SIFT y descriptores de punto flotante, la distancia es L². La prueba de razón rechaza emparejamientos ambiguos donde el mejor candidato y el segundo mejor están demasiado cerca en distancia. El umbral para la prueba de razón es 0.75, que es el predeterminado de la literatura. La complejidad es O(N₁ × N₂ × D) donde D es la dimensión del descriptor, que para ORB es 32 bytes. Esto es fuerza bruta en el sentido literal, pero en las longitudes de descriptor y conteos de características con los que trabajamos, es lo bastante rápido y es contra lo que compara la literatura. Aproximaciones más inteligentes (FLANN, k-means jerárquico) están en la cola para un fin de semana posterior.

Cinco. Solucionador de restricciones de física de tela. La implementación original iteraba las restricciones en un orden fijo con un conteo bajo de iteraciones, lo que producía tela tambaleante que no convergía. Reemplazado con un solucionador de dinámica basada en posición con barajado adecuado de restricciones entre iteraciones. El barajado importa porque los solucionadores de restricciones que siempre procesan las restricciones en el mismo orden se sesgan: la tela termina estirándose predeciblemente en una dirección. Barajar cada iteración elimina el sesgo. El conteo de iteraciones se elevó de 4 a 12 para calidad de producción, con una ruta rápida de 4 iteraciones para dispositivos de gama baja.

Seis. Planificación de rutas de agentes de IA para el subsistema de multitudes. La implementación original era un marcador de posición que elegía un vecino válido al azar en cada paso. Los agentes deambulaban en direcciones aleatorias y ocasionalmente llegaban a sus destinos por suerte. Reemplazado con planificación de rutas A* adecuada sobre la malla de navegación, con la heurística siendo distancia euclidiana y la función de costo ponderada por la pendiente del terreno y el tipo de superficie. La implementación usa un montículo binario para el conjunto abierto y un conjunto de hash para el conjunto cerrado, lo que hace que el costo por paso sea O(log N) en el montículo y O(1) en el conjunto de hash.

Siete. Mezcla de animación entre múltiples clips. La implementación original era un marcador de posición que simplemente reproducía el clip solicitado más recientemente e ignoraba los demás. Reemplazado con un árbol de mezcla ponderado adecuado: cada fotograma de salida es una suma ponderada de las transformaciones por hueso de los clips contribuyentes, con los pesos impulsados por una topología de árbol de mezcla que el autor de la animación especifica. El cálculo de la mezcla respeta el orden de la jerarquía de huesos para que los huesos hijos hereden correctamente las transformaciones mezcladas del padre.

Qué aprendí

Tres cosas, ninguna sorprendente en retrospectiva.

Especifica el algoritmo en la incidencia. Para cualquier función que opere sobre un tamaño de entrada no trivial, el enmarcado de la incidencia tiene que especificar la complejidad esperada. «Detecta colisiones entre N objetos» no es suficiente. «Detecta colisiones entre N objetos en el peor caso O(N log N) usando sweep-and-prune (Baraff 1992) o equivalente» es suficiente. La cita es la disciplina. Sin ella, el agente escribe lo correcto más fácil, que es fuerza bruta.

La pasada de auditoría es esencial. No habría atrapado estas leyendo las PRs a medida que aterrizaban. Cada PR individual era una función que funcionaba, con pruebas que aprobaban. La pasada de auditoría que dice «encuentra cada función en el runtime que sea O(N²) o peor y evalúa si debería serlo» es lo que las hace salir a la superficie. Agrega la auditoría a la cadencia.

La literatura es el código de trampa. Cada uno de estos reemplazos es un algoritmo publicado con un artículo de décadas de antigüedad detrás. Baraff 1992. Forsyth 2006. Lowe 2004. Dinámica basada en posición. A*. Estos no son novedosos. Los agentes escribirán la versión equivalente a la literatura de cualquiera de ellos si les dices qué artículo leer.

Lo que socios y constructores deberían llevarse de esto

Si estás evaluando un motor para una asociación y el equipo no ha hecho una auditoría algorítmica de su base de código, pídeles que hagan una. La auditoría hará salir cosas a la superficie. La respuesta del equipo a lo que sale a la superficie dice más que cualquier lista de funciones.

Si estás corriendo un flujo de trabajo impulsado por agentes en una base de código sensible al rendimiento, la pasada de auditoría no es opcional. Los agentes aterrizarán código que funciona. El código que funciona a veces será la versión de fuerza bruta. La auditoría es cómo averiguas cuál.

Si eres un laboratorio de IA construyendo un agente de codificación para trabajo sensible al rendimiento, la métrica que optimizaría es «¿el agente pregunta sobre la complejidad asintótica cuando está implementando una función cuyo nombre implica una preocupación de escalamiento?». La mayoría de los agentes no lo hacen. Los que sí lo hacen producen mejor código.

Tarde de sábado. Siete algoritmos de fuerza bruta reemplazados por sus versiones de producción reales. El motor se volvió más rápido. La base de código se volvió más honesta.

De vuelta a construir.