- Para visualizar el proceso de compilación de JavaScript y WebAssembly del motor SpiderMonkey, se renovó por completo la herramienta interna y se implementó una función para generar gráficas interactivas
- El iongraph basado en Graphviz existente tenía un layout inestable y una estructura poco intuitiva, lo que reducía la eficiencia de depuración; para reemplazarlo, se diseñó directamente un nuevo algoritmo de layout
- El nuevo algoritmo simplifica el método Sugiyama para representar con claridad la estructura de los bucles, e implementa un layout estable y rápido en menos de 1000 líneas de código JavaScript
- La gráfica usa aristas rectas estilo diagrama ferroviario para mejorar la legibilidad y logra una velocidad de renderizado miles de veces superior a Graphviz
- La herramienta está integrada en el Firefox Profiler y existe el plan de ampliarla en el futuro con funciones como búsqueda y visualización de registros
Renovación de la herramienta de visualización de SpiderMonkey
- Se reconstruyó la herramienta para visualizar las gráficas internas que genera el compilador de optimización Ion de SpiderMonkey
- El usuario puede ingresar código JavaScript en una página web y explorar en tiempo real, mediante gráficas, el proceso de optimización de funciones
- La gráfica permite revisar los cambios por etapas con arrastre, zoom y controles deslizantes
- El iongraph basado en Graphviz anterior generaba salida en PDF, pero no coincidía con la estructura del código fuente y sufría una grave inestabilidad en la salida
- Incluso pequeños cambios en el código alteraban mucho la posición de los nodos, lo que dificultaba comparar entre pases
- La estructura de bucles y condicionales se distorsionaba visualmente, por lo que resultaba difícil entender el flujo de control
Límites de Graphviz y un nuevo enfoque
- El algoritmo Sugiyama de Graphviz es adecuado para la optimización de gráficas generales, pero no refleja las características de un grafo de flujo de control (CFG)
- Los bucles de JavaScript y WebAssembly tienen un único punto de entrada y presentan un flujo de control reducible
- El equipo de SpiderMonkey aprovechó esas restricciones para diseñar un algoritmo especializado simplificado
- Eliminación de ciclos: se ignoran las backedges de los bucles
- Nivelación (Leveling): los bloques posteriores al bucle se colocan más abajo para reflejar el flujo del código
- Se omite la minimización de cruces: se fija el orden de las ramas true/false para priorizar la estabilidad
- Preservación de la estructura en árbol de bucles: los bucles anidados se expresan con claridad visual
- Como resultado, se logró un layout conciso, rápido y estable; la implementación inicial consta de unas 1000 líneas de JavaScript
Etapas del algoritmo de layout de iongraph
- Paso 1: Layering
- Los bloques se ordenan por niveles y se refleja la relación entre interior y exterior de los bucles
- Tras el final del bucle, los bloques se colocan hacia abajo según toda la altura del bucle
- Paso 2: creación de nodos dummy
- Se agregan nodos dummy a las aristas que atraviesan varios niveles para evitar conflictos visuales
- Las aristas que apuntan al mismo destino se fusionan para reducir el ruido visual
- Paso 3: alineación de aristas (Straighten)
- Se alinean nodos padre e hijo para mantener la forma de líneas verticales y se aplica sangría a los bucles
- Los nodos dummy también participan en la alineación para evitar superposiciones y preservar la estructura
- Paso 4: tracking de aristas horizontales
- Las aristas horizontales se ordenan por tracks para que no se superpongan
- Se separan hacia arriba y abajo según la dirección de la arista, y las aristas que pueden fusionarse se agrupan en una sola
- Paso 5: distribución vertical (Verticalize)
- Se asignan coordenadas Y a cada nivel para lograr una distribución de altura uniforme y mejorar la legibilidad
- Paso 6: renderizado (Render)
- Se usan aristas rectas de estilo diagrama ferroviario
- Las aristas solo se cruzan en vertical y horizontal, con dirección y estructura claras
Efectos de un algoritmo simple
- En lugar de optimizaciones complejas, se asegura legibilidad y estabilidad con una distribución predecible basada en reglas
- Al fijar el orden de los nodos y simplificar las aristas, se mantiene la consistencia entre pases
- Al excluir un constraint solver, se logra una estructura más fácil de entender para las personas
- Esto permite un diseño centrado en el significado, como la distribución dentro de los bucles o la colocación descendente de los bloques posteriores
- Mejora de rendimiento: una gráfica de funciones de zlib que en Graphviz tardaba 10 minutos se renderiza en 20 milisegundos
- Se obtiene una velocidad miles de veces mayor y mejor capacidad de exploración
Planes a futuro
- La integración de iongraph en el Firefox Profiler ya está completa, por lo que se pueden revisar las gráficas durante el análisis de rendimiento
- Por ahora solo puede usarse en builds del shell de SpiderMonkey; no está incluido en builds del navegador
- Propuestas de funciones futuras
- Funciones avanzadas de navegación, búsqueda, visualización de asignación de registros, entre otras
- No hay una hoja de ruta clara, y se agradecen las contribuciones open source
- Para hacer pruebas locales, configura
IONFLAGS=logs para generar /tmp/ion.json y luego
cárgalo en la distribución independiente
- El código fuente está publicado en GitHub y es posible comunicarse directamente con los desarrolladores a través de una sala de chat de Matrix
1 comentarios
Comentarios en Hacker News
Para hacer una comparación precisa, no sería con Graphviz completo sino con dot(1)
Graphviz es un framework de visualización que incluye varios motores de layout (dot, neato, fdp, sfdp, circo, twopi, etc.)
Estaría genial que el nuevo algoritmo terminara aportándose a Graphviz
La documentación relevante está en la descripción del lenguaje de Graphviz y en la documentación del motor de layout dot
Quizá funcione bien en grafos de flujo de control (CFG) con reducible control flow, pero parece que habría muchas excepciones complejas
Además, iongraph está basado en JavaScript, así que para integrarlo en Graphviz habría que convertirlo a C con una herramienta como Claude
La capacidad de revisar directamente la implementación original del algoritmo realmente parece un superpoder
Como alguien que ha hecho visualizaciones complejas con Graphviz, al principio me sorprendió que alguien lo reimplementara por su cuenta
Pero al ver la estructura del algoritmo, me di cuenta de que quizá sea más simple de lo que parece
Aun así, sigue siendo cierto que hasta terminar una implementación real es difícil conocer la complejidad oculta
Si especializas un algoritmo general para un dominio de problema específico, puedes obtener resultados mucho mejores
Pero en la mayoría de los casos usamos algoritmos de propósito general por comodidad
Diseñar sistemas adaptados a una aplicación específica trae grandes mejoras en rendimiento, escalabilidad y tolerancia a fallos
Pero cuando apuntas a una mejora de 1000x, 1 o 2 años se van rapidísimo
Los sistemas generales de layout de grafos tienen que manejar una variedad mucho mayor de casos, así que inevitablemente se vuelven más complejos
Por eso me parece un buen compromiso analizar la entrada y usar un algoritmo rápido para los casos especiales, y en los demás un algoritmo general garantizado
Fue un buen artículo. Como referencia, el dot de Graphviz no es una implementación pura del algoritmo de Sugiyama
La implementación real está explicada en detalle en los papers del sitio
Si ves las imágenes que comparan dot e iongraph en grafos grandes, dot está optimizado para minimizar el área, e iongraph no
Las visualizaciones de grafos grandes se ven impresionantes, pero en la práctica rara vez resultan útiles
La visualización solo sirve hasta unas cuantas decenas de nodos, y más allá de eso la complejidad de las aristas hace muy difícil entenderla
Al final solo funcionan bien en ejemplos simples, y en entornos complejos más bien estorban
La mayoría de los problemas se pueden reducir a unidades pequeñas
Eso sí, Graphviz se ve poco estético incluso en grafos pequeños, mientras que iongraph tiene mucha mejor legibilidad de líneas
A largo plazo creo que hacen falta elementos interactivos como búsqueda y funciones de resaltar/ocultar
Me frustra la limitación de que los diagramas no puedan exportar ni recibir enlaces
Mermaid permite enlaces de texto, pero los enlaces dentro del diagrama son limitados
También vale la pena ver la discusión relacionada en StackOverflow
Hace falta una herramienta donde este tipo de funciones se consideren de primera clase desde la etapa de diseño
La verdadera fortaleza de Graphviz es el lenguaje dot
Los grafos definidos en dot tienen muy buena compatibilidad entre distintas herramientas, y la sintaxis es simple y fácil de leer
Han aparecido alternativas como Mermaid, pero parece que dot seguirá siendo un formato estándar por mucho tiempo
De verdad fue un artículo muy bueno
Me pregunto si técnicas como estas también se usaron en el motor de layout TALA de D2
Ver ejemplos de TALA
Si te interesa el graph drawing, recomiendo las clases de Will Evans (enlace)
Hace tiempo contribuí con un bugfix al lexer de Dot de Open Graph Drawing Framework (OGDF),
y OGDF implementa algoritmos más rápidos y con menos cruces que Graphviz
En mi experiencia, los resultados de OGDF eran mucho más limpios
Para el historial del PR, ver este enlace de GitHub
Interesante. Me gustaría saber cómo se ejecutan los ejemplos
Lo bueno de este proyecto es que soporta exploración interactiva pensando en un entorno de cliente web
Como es un layout especializado para grafos de flujo de control (CFG), permite una visualización adaptada al dominio
Graphviz también tiene funciones de polylines y control del orden de aristas, pero están poco documentadas
Sería bueno integrar el algoritmo de enrutamiento de aristas de Brandes y Kopf
Graphviz es un proyecto de casi 40 años, y hoy lo mantienen apenas unas cuantas personas voluntarias de segunda generación
Hacer herramientas siempre ha sido un mercado difícil, y sus usuarios suelen ser gente muy capaz pero en departamentos con poco presupuesto
Es una pena la lentitud con la que avanzan las herramientas declarativas de diagramas 2D
Siempre apoyo con un +1 a la gente que trabaja en este tipo de áreas
Yo también he usado mermaid y graphviz, pero al final siempre vuelvo a FigJam: tiene mejor legibilidad y acabado visual
graphviz depende de un binario enorme, y mermaid depende del renderizado SVG del navegador, así que se vuelve incómodo
Hace falta una herramienta para crear diagramas fácilmente solo con texto
Me parece que el enfoque del autor es un buen intento de controlar ese trade-off
Quedé satisfecho salvo por el hecho de que no manejaba loops
La salida en SVG/HTML facilita modificar estilos y copiar contenido
Si quieres una herramienta de diagramas basada en texto, recomiendo TikZ
Ver la wiki de TikZ
Eso sí, no tiene la retroalimentación visual inmediata de algo como FigJam
No me gustó la excesiva cantidad de dependencias ni la falta de consistencia en el código de mermaid
En cambio, nomnoml (enlace) tiene un código limpio y también existe graphre, una versión portada a Typescript (enlace)
Para usar mermaid junto con resvg-js, hace falta refactorizar lo relacionado con la medición del ancho del texto en SVG