El sistema de actualización y el grafo de dependencias

Este documento describe cómo JMathAnim decide, en cada frame, qué hay que recalcular y qué hay que volver a dibujar: el contrato de versiones, el grafo de dependencias, la pasada de actualización en orden topológico y la invalidación por empuje que mantiene todo eso barato.

Es la referencia de cómo funciona la maquinaria hoy. El relato histórico de por qué llegó a ser así está en UPDATE_SYSTEM.md.

1. El problema

Una escena es una red de objetos que dependen unos de otros. Un Shape tiene un JMPath; la ruta tiene sus JMPathPoint; cada punto tiene tres Vec; un MODrawProperties tiene dos PaintStyle; una fórmula LaTeX agrupa decenas de glifos; un delimitador se estira entre dos anclas; una etiqueta sigue a lo que anota; un grosor puede estar ligado a un Scalar.

Cada frame hay que resolver dos cosas, y hay que resolverlas barato:

1. Orden de actualización. Si A depende de B, B se recalcula antes que A. Una etiqueta no puede colocarse hasta que la figura a la que sigue tenga su geometría definitiva del frame.
2. Detección de cambios. Un objeto solo debe recalcularse si algo de lo que depende cambió de verdad. En una animación larga, casi todo está quieto casi todo el rato.

El grafo resuelve (1). El sistema de versiones resuelve (2). Están diseñados juntos.

2. El contrato de versiones

Versionable

public interface Versionable {
    void changeVersion();
    long getVersion();
}

• changeVersion() se llama cuando el objeto muta.
• getVersion() devuelve la versión efectiva: el máximo entre la versión propia y las de todo su subárbol de dependencias. Esa es la semántica clave. Preguntar a un objeto "¿has cambiado tú o algo dentro de ti desde la última vez?" es comparar un número.

Dependable

public interface Dependable extends Versionable, GraphNode {
    List<Dependable> getDependencies();
    void addDependency(Versionable dep);

    default String getClassName() { return getClass().getSimpleName(); }

    List<Dependable> EMPTY_DEPENDENCIES = Collections.emptyList();
}

​ getDependencies() devuelve List<Dependable>, no List<Versionable>: solo un Dependable puede ser nodo del grafo. El parámetro de addDependency sigue siendo el más ancho porque es el tipo con el que están declaradas la mayoría de las interfaces de la librería, pero AbstractVersioned rechaza y avisa por el logger si le llega algo que no sea Dependable, en vez de guardarlo:

public void addDependency(Versionable dep) {
    if (dep == null) return;
    if (!(dep instanceof Dependable)) {
        //Guardarlo haría que contase para getVersion() sin ser visible para el orden de
        //actualización, que es lo peor de los dos mundos
        JMathAnimScene.logger.warn("Cannot depend on a " + dep.getClass().getSimpleName()
                + ": only Dependable objects can be nodes of the dependency graph. Ignored.");
        return;
    }
    dependencies.add((Dependable) dep);
    notifyStructuralChange();
}

GraphNode

La contabilidad que el grafo lleva sobre cada nodo vive en su propia interfaz, que Dependable extiende. Está separada a propósito: es fontanería del grafo, no algo que el objeto declare sobre sí mismo.

public interface GraphNode {
    long UNRANKED = Long.MIN_VALUE;

    boolean markDepsCacheDirty();          // devuelve si ya estaba sucio
    void setGraphMembership(DependencyGraph graph, long stamp);
    void clearGraphMembership();
    DependencyGraph getOwningGraph();
    long getGraphStamp();
    long getTopoRank();
    void setTopoRank(long rank);
}

La única implementación es AbstractVersioned, de la que hereda todo nodo de la librería. Tenerlo en la interfaz es lo que permite que DependencyGraph hable con cualquier nodo sin preguntar de qué clase es: antes había ocho instanceof AbstractVersioned repartidos por el grafo.

El reloj global

// JMathAnimScene
public static long globalVersion = 0;

Un único contador monótono para todo el proceso. changeVersion() hace version = ++globalVersion, así que las versiones son globalmente ordenables y "más nuevo" es literalmente "número mayor".

La jerarquía

Versionable
   └── Dependable (+ GraphNode)
          └── AbstractVersioned            versión, caché, pertenencia al grafo
                 ├── Vec, Scalar, PaintStyle, MODrawProperties, JMPathPoint, Rect, Camera...
                 └── AbstractUpdateable    + Updateable (needsUpdate/update)
                        ├── JMPath
                        └── MathObject
                               └── AbstractShape, Constructible, compuestos...

3. AbstractVersioned: el núcleo

Cada nodo lleva su versión propia, la caché del máximo de sus dependencias y la contabilidad del grafo:

protected final ArrayList<Dependable> dependencies = new ArrayList<>();
protected long version = 0;

private long cachedDepsMaxVersion = -1;   // máximo sobre las dependencias
private boolean depsCacheFilled = false;
private boolean depsCacheDirty = false;   // invalidación por empuje
private long cachedAtGlobalVersion = Long.MIN_VALUE;
private boolean computingVersion = false; // corta la recursión en un ciclo

private long graphStamp = -1;             // sello de la reconstrucción que lo descubrió
private DependencyGraph owningGraph = null;
private long topoRank = UNRANKED;

La versión propia no se cachea nunca: getVersion() la lee fresca, así que subir la versión de uno mismo no invalida su propia caché.

getVersion()

public long getVersion() {
    long global = JMathAnimScene.globalVersion;
    //Un sello por encima del reloj global solo puede venir de antes de un reset, es decir de una
    //ejecución anterior. Ese objeto parecería "modificado en el futuro" y escondería a sus
    //dependientes todos los cambios de esta ejecución
    if (version > global) version = 0;
    if (cachedAtGlobalVersion > global) { /* tira la caché */ }
    if (dependencies.isEmpty()) return version;

    boolean cacheValid = depsCacheFilled && !depsCacheDirty
            && ((updatePassDepth > 0 && graphStamp == activePassGraphStamp)
                || cachedAtGlobalVersion == global);
    if (cacheValid) return Math.max(version, cachedDepsMaxVersion);

    if (computingVersion) return version; //ciclo: corta con la versión propia
    computingVersion = true;
    try {
        long max = 0;
        for (int i = 0, n = dependencies.size(); i < n; i++) {
            long v = dependencies.get(i).getVersion();
            if (v > max) max = v;
        }
        cachedDepsMaxVersion = max;
        depsCacheFilled = true;
        depsCacheDirty = false;
        cachedAtGlobalVersion = global;
        return Math.max(version, max);
    } finally {
        computingVersion = false;
    }
}

Hay dos regímenes de validez de la caché, y la diferencia es todo:

Fuera de la ventana la condición es estricta a propósito: nadie garantiza que la bandera de sucio esté al día, así que se exige que el reloj global no se haya movido desde que se llenó la caché. Como una pasada de actualización mueve el reloj muchas veces, fuera de la ventana casi toda consulta recorre el subárbol entero. De ahí la importancia de la ventana (sección 8).

Un detalle que se lee mal si no se dice: el valor devuelto es el mismo en los dos regímenes. La caché solo se cree cuando la bandera dice que nada de abajo cambió, y el recálculo llega al mismo máximo. La ventana cambia el coste, nunca la respuesta.

changeVersion()

public void changeVersion() {
    version = ++JMathAnimScene.globalVersion;
    if (enqueuedAtDrainGeneration != drainGeneration) {
        enqueuedAtDrainGeneration = drainGeneration;
        changedSinceLastDrain.add(this);
        //Un cambio hecho mientras corre una pasada tiene que llegar a los dependientes que esa
        //misma pasada va a visitar después, así que se empuja ya
        if (updatePassDepth > 0 && activePassGraph != null) {
            activePassGraph.markDirtyUpFrom(this);
        }
    }
}

Dos mecanismos, no uno:

• Encolar en changedSinceLastDrain, una lista estática que el grafo drena al principio de cada pasada. Deduplicado por generación de drenaje, así que un objeto que cambia mil veces entre dos frames aparece una vez.
• Empujar ya si hay una pasada abierta, porque el orden topológico ya puede haber pasado por encima del dependiente.

Cambios estructurales

Añadir o quitar una dependencia no es un cambio de valor, es un cambio de forma del grafo:

private void notifyStructuralChange() {
    dependencyStructureVersion++;
    depsCacheDirty = true;
    DependencyGraph graph = owningGraph;
    if (graph != null && graph.ownsStamp(graphStamp)) {
        graph.onNodeStructureChanged(this);   // el grafo apunta QUÉ nodo se recableó
    }
    changeVersion();
}

Solo reporta al grafo un nodo que el grafo tenga ahora mismo. Las aristas se derivan de lo alcanzable desde las raíces, así que la lista de dependencias de un objeto que el grafo no ha descubierto no puede cambiar ninguna arista suya: para que ese objeto pase a ser alcanzable, algún nodo que sí está en el grafo tendría que apuntarle, y eso es a su vez un cambio estructural sobre un nodo del grafo, que sí se reporta. Esto es lo que impide que una animación que fabrica geometría desechable cada frame obligue a reconstruir un grafo que ni toca.

4. AbstractUpdateable: el ciclo de update

public boolean needsUpdate() {
    //Comprobación por tirón: getVersion() es la versión efectiva (propia más dependencias),
    //así que detecta tanto mutaciones directas como cambios en cualquier punto del subárbol
    return getVersion() != lastProcessedVersion;
}

public boolean update() {
    if (updating) return false;           // reentrada
    updating = true;
    boolean flag = applyUpdaters(true);   // updaters "antes"
    if (needsUpdate()) {
        performMathObjectUpdateActions();
        flag = true;
    }
    flag |= applyUpdaters(false);         // updaters "después"
    ...
}

update() se llama en todos los nodos actualizables del orden, cambien o no, porque hay updaters que dependen de estado externo (tiempo, cámara, entrada de la GUI) y no de versiones. Lo que la versión decide es si se rehace el trabajo caro de dentro.

5. El grafo: estructura

La tabla de nodos

Todo lo que el grafo sabe de un nodo vive en un único registro, y las aristas apuntan a registros, no a objetos:

private static final class Node {
    final Dependable owner;      // el objeto que representa
    List<Node> deps;             // aristas salientes, null si no hay
    List<Node> dependents;       // aristas inversas, null si no hay
    boolean present;             // si el grafo lo tiene, o es solo un hueco reservado
}

private final Map<Dependable, Node> nodeInfo = new IdentityHashMap<>();

Node no redefine equals ni hashCode a propósito: la identidad es lo que define un nodo del grafo, así que un HashSet<Node> ya es un conjunto por referencia.

Los nodos se identifican por referencia, nunca por equals. Algunos objetos versionados tienen igualdad por valor (JMColor, Rect), y una tabla con hash de valor fundiría dos dependencias distintas pero iguales en un solo nodo y, peor, perdería la pista de una en cuanto su valor (y por tanto su hash) cambiase, tirando silenciosamente la invalidación que debía haber empujado. Por eso IdentityHashMap.

present distingue un nodo que el grafo tiene de un hueco creado porque otro declaró una arista hacia él y todavía no se ha visitado. Un nodo que una reparación descarta sale de la tabla y queda marcado como ausente, para que la copia que aún esté en nodeOrder se reconozca como muerta.

Raíces frente a descubiertos

private final Map<Dependable, Integer> rootSlots = new IdentityHashMap<>();
private final List<Dependable> rootOrder = new ArrayList<>();  // con null en los huecos
private int rootOrderDead;

• Raíces: lo que la escena añadió explícitamente con addNode (desde JMathAnimScene.add). Son lo único que sobrevive entre reconstrucciones.
• Descubiertos: todo lo demás, redescubierto transitivamente desde las raíces en cada reconstrucción.

Mantenerlos separados es lo que hace que removeNode encoja el grafo de verdad: una vez fuera la raíz, sus descendientes exclusivos dejan de ser alcanzables y desaparecen solos.

rootSlots guarda en qué hueco está cada raíz, así que quitar una es una búsqueda y una escritura, no un barrido más un desplazamiento. Los huecos se cierran de forma amortizada cuando pasan de la mitad. Un desmontaje de diapositiva que quita cientos de raíces una a una era cuadrático.

Los cuatro órdenes

private final List<Node> nodeOrder;           // orden de descubrimiento (semillas del DFS)
private final List<Node> topoOrder;           // orden topológico completo
private final List<Updateable> updateableOrder;   // el subconjunto que updateAll recorre
private final List<Updateable> intermediateOrder; // lo que updateIntermediate recorre
private final Set<Dependable> samplers;           // los IntermediateUpdateable que hay ahora

updateableOrder es el que se recorre por frame. Las cachés de versión se recalculan solas al consultarlas, así que la pasada no necesita visitar el grafo entero, solo los nodos actualizables.

samplers no es un orden, es el índice que hace barato reconstruir intermediateOrder (7.1). Está ahí porque encontrar los samplers barriendo la tabla de nodos costaba O(escena) para localizar el uno que suele haber, y ese coste era la mitad de la razón por la que ese orden solo se podía recalcular en una reconstrucción completa.

La única función que crea aristas

private Node linkTo(Node from, Dependable dep) {
    Node target = entryOf(dep);
    //Los llamantes dimensionan la lista antes (una ruta declara una arista por punto, y crecer
    //desde la capacidad por defecto copiaría el array una docena de veces)
    if (from.deps == null) from.deps = new ArrayList<>(4);
    from.deps.add(target);
    if (target.dependents == null) target.dependents = new ArrayList<>(2);
    target.dependents.add(from);
    return target;
}

Los tres recorridos que descubren nodos (rebuildEdges, discoverBelow, appendNewSubtree) pasan todos por aquí y solo se diferencian en qué hacen luego con el destino.

Rangos

Cada nodo lleva su posición en el orden topológico como un rango, no como un índice:

private static final long RANK_GAP = 1024;

Una ordenación completa reparte rangos separados por RANK_GAP, de modo que un nodo descubierto después puede colocarse entre dos existentes sin renumerar nada. Es lo que hace posible la reparación incremental.

6. sort(): reparar primero, reconstruir si no se puede

Lo que se apunta

No se apunta "algo cambió", se apunta qué cambió:

private final Set<Dependable> pendingStructural;      // nodos recableados
private final List<Dependable> pendingStructuralOrder;
private final List<Dependable> pendingAddedRoots;
private final List<Dependable> pendingRemovedRoots;

Un contador no puede decir qué nodo se recableó, y por tanto no deja más salida que redescubrirlo todo. Esta es la diferencia entre O(escena) y O(lo que se movió) por frame.

El punto de entrada

public void sort() {
    if (!needsSorting()) return;
    boolean patched = false;
    if (!fullRebuildNeeded && lastSeenForeignClaim == foreignClaimVersion) {
        patched = tryIncrementalPatch();
        if (!patched) incrementalFallbackCount++;
    }
    if (!patched) {
        fullRebuildAndSort();
    }
    clearPendingWork();
    if (VALIDATE_PATCHES && patched) validateAgainstFullRebuild();
}

Abandonar una reparación a medias es siempre seguro y solo cuesta la reconstrucción que viene detrás: una reparación nunca toca rootSlots ni rootOrder, que es todo lo que lee una reconstrucción.

La reconstrucción completa

rebuildEdges() vacía la tabla, se pone un sello nuevo y hace un BFS desde las raíces:

nodeInfo.clear();
nodeOrder.clear();
myStamp = ++stampCounter;
ArrayDeque<Node> pending = ...;                 // sembrado con las raíces vivas
while (!pending.isEmpty()) {
    Node info = pending.poll();
    if (info.present) continue;
    markPresent(info);
    Dependable node = info.owner;
    if (node instanceof IntermediateUpdateable) samplers.add(node);

    DependencyGraph previousOwner = node.getOwningGraph();
    boolean wasMine = (previousOwner == this) && (node.getGraphStamp() == previousStamp);
    if (!wasMine) {
        //Nuevo en este grafo: mientras estuvo fuera nadie le empujaba invalidaciones, así que lo
        //que tenga cacheado no es de fiar desde aquí
        node.markDepsCacheDirty();
        ...
    }
    node.setGraphMembership(this, myStamp);
    List<Dependable> declared = node.getDependencies();
    sizeDepsFor(info, declared.size());
    for (int i = 0; i < declared.size(); i++) {
        Node target = linkTo(info, declared.get(i));
        if (!target.present) pending.add(target);
    }
}

El registro se vacía al principio y se rellena aquí, así que queda exacto: se ha visitado todo lo alcanzable, y un sampler que ha salido de la escena deja de estar en él.

Después fullRebuildAndSort() ordena con postOrderDfs, reparte rangos y rellena updateableOrder.

El DFS post-orden es iterativo, con el camino en campos reutilizados. La recursión que sustituye bajaba tanto como la profundidad del DAG, y una cadena larga de constructibles podía desbordar la pila de Java en mitad de un frame. Las aristas de vuelta (ciclos) se ignoran con un aviso, para que una dependencia cíclica accidental degrade el orden en vez de abortar el frame.

La reparación incremental

La regla en la que se apoya todo: el orden topológico sigue siendo válido mientras toda arista nueva apunte a un nodo que ya venga antes. Un nodo descubierto por la reparación viene antes por construcción (nada más lo alcanza todavía), y un nodo añadido como raíz nueva se pone al final, donde nada puede depender de él. Lo que no encaje en esas dos formas hace que la reparación se rinda.

private boolean tryIncrementalPatch() {
    if (nodeInfo.isEmpty()) return false;   // primera vez: reconstrucción

    // 1. raíces quitadas primero: un nodo que deja de ser alcanzable tiene que estar fuera antes
    //    de mirar otra vez las aristas de quien le apuntaba
    for (...) updateableDropped |= dropUnreachableFrom(info);

    // 2. nodos recableados
    for (...) {
        int dropped = patchNodeEdges(info);
        if (dropped == PATCH_FAILED) return false;
        ...
    }

    // 3. raíces nuevas, al final del orden
    for (...) if (!appendNewSubtree(root)) return false;

    if (updateableDropped) updateableOrder.removeIf(u -> !isInGraph((Dependable) u));
    // una reparación puede mover la clausura de un sampler, y rehacer ese orden es barato, así
    // que se rehace en vez de razonar sobre si hacía falta (ver 7.1)
    if (!samplers.isEmpty()) rebuildIntermediateOrder();
    compactNodeOrderIfNeeded();
    incrementalPatchCount++;
    return true;
}

patchNodeEdges rehace las aristas salientes de un nodo:

List<Dependable> declared = node.getDependencies();
if (sameEdges(info.deps, declared)) return PATCH_OK;   // reportó, pero nada se movió

// desengancha las inversas viejas antes de enganchar las nuevas, para que una dependencia que
// esté en las dos acabe con exactamente una entrada de vuelta
List<Node> previous = info.deps;
for (...) detachDependent(previous.get(i), info);
info.deps = null;
sizeDepsFor(info, declared.size());
discoverGroup.clear();

for (int i = 0; i < declared.size(); i++) {
    Node target = linkTo(info, declared.get(i));
    if (target.present) {
        long depRank = declared.get(i).getTopoRank();
        if (depRank == GraphNode.UNRANKED || depRank >= rank) return PATCH_FAILED;
    } else if (!discoverBelow(target, rank)) {
        return PATCH_FAILED;
    }
}
// lo que ya no se declara y nada más alcanza, fuera
for (...) if (old.present) updateableDropped |= dropUnreachableFrom(old);

sameEdges compara lo registrado contra lo declarado antes de construir nada, que es lo que deja sin asignación el caso más frecuente de todos: un nodo que reporta un cambio y resulta que sus aristas son las mismas.

discoverBelow coloca lo recién alcanzable un rango por debajo de su dependiente:

long rank = dependentRank - 1;
if (rank % RANK_GAP == 0) {
    //La banda bajo el dependiente está gastada y este rango chocaría con uno que repartió una
    //ordenación completa. Una reconstrucción renumera con huecos frescos, así que nos rendimos
    rankExhaustedCount++;
    return false;
}
...
    if (node instanceof Updateable) return false;   // ver abajo
...
    if (target.present) {
        long depRank = target.owner.getTopoRank();
        if (depRank == GraphNode.UNRANKED || depRank > rank) return false;
        //La misma regla que patchNodeEdges: una dependencia tiene que venir estrictamente antes.
        //La única excepción es un nodo del grupo que se está colocando ahora mismo, que comparte
        //este rango y cuyo orden interno resuelven las propias aristas
        if (depRank == rank && !inDiscoverGroup(target)) return false;
    }

Solo entra material con forma de hoja. Un Updateable habría que insertarlo en updateableOrder en la posición correcta, que es lo único que una reparación no sabe hacer, así que su llegada es lo que la hace rendirse. En la animación para la que existe esto, lo que llega son puntos de ruta y sus vectores, y ninguno es actualizable.

El grupo de descubrimiento abarca toda la llamada a patchNodeEdges, no una llamada a discoverBelow: dos dependencias nuevas del mismo nodo se descubren por separado pero aterrizan en el mismo rango, así que son legítimamente el mismo grupo.

dropUnreachableFrom tira un nodo que ya nada alcanza, y lo que quede inalcanzable con él. Un nodo que siga siendo raíz, o del que algo siga dependiendo, se queda.

Por qué existe todo esto

El caso extremo es showCreation. Su estrategia pide getSubShape(0, lt) cada frame, y la ruta resultante tiene un punto más que la del frame anterior. Antes de que JMPath.copyStateFrom redimensionase en sitio, eso destruía y recreaba todos los puntos de la ruta, y cada punto son cuatro nodos del grafo (el JMPathPoint más sus tres Vec). Con cientos de animaciones de glifo vivas a la vez, el grafo tenía que redescubrir decenas de miles de nodos por frame para añadir uno.

Medido con GraphRebuildBenchmark sobre 12 líneas de LaTeX:

antes   nodes=56169 patches=40 fallbacks=1 patchVisits=1411124 patchVisitsPerFrame=23518.7
ahora   nodes=56169 patches=40 fallbacks=1 patchVisits= 289212 patchVisitsPerFrame= 4820.2

Comprobar la reparación contra la reconstrucción

Con -Djmathanim.graph.validate=true, cada reparación se contrasta con una reconstrucción completa del mismo grafo: conjuntos de nodos, aristas de cada nodo (por referencia, no con equals) y updateableOrder posición a posición. Es demasiado lento para un render de verdad; está para que una tanda de tests demuestre que el camino rápido y el lento coinciden.

7. La pasada de actualización

public void updateAll() {
    sort();
    markDirtyUpwards(AbstractVersioned.drainChangedObjects());
    AbstractVersioned.beginUpdatePass(this, myStamp);
    try {
        //Indexado y no for-each: un updater puede añadir o quitar objetos de la escena, lo que
        //hoy solo apunta trabajo pendiente, pero un iterador convertiría cualquier desliz futuro
        //en una ConcurrentModificationException en mitad de un frame
        for (int i = 0; i < updateableOrder.size(); i++) {
            updateableOrder.get(i).update();
        }
    } finally {
        AbstractVersioned.endUpdatePass();
    }
}

Los dos ascensos

La invalidación sube por las aristas inversas. Hay dos puntos de entrada sobre una única implementación:

private void climbMarkingDirty(boolean stopAtDirtyParent) {
    //Invariante del bucle, así que la rama de abajo no cuesta nada: null es el ascenso dentro de
    //la pasada, que no necesita contabilidad propia porque un padre ya sucio es la propia parada
    Set<Node> visited = stopAtDirtyParent ? null : drainVisited;
    if (visited != null) visited.clear();
    while (!climbStack.isEmpty()) {
        List<Node> back = climbStack.pop().dependents;
        if (back == null) continue;
        for (int i = 0; i < back.size(); i++) {
            Node parent = back.get(i);
            if (visited == null) {
                if (parent.owner.markDepsCacheDirty()) continue;
            } else {
                if (!visited.add(parent)) continue;
                parent.owner.markDepsCacheDirty();
            }
            climbStack.push(parent);
        }
    }
}

• markDirtyUpwards(drenaje), al principio de la pasada. Marca todos los ancestros, sin el atajo del otro: un nodo ensuciado por una reconstrucción, o por la reparación de ejecución previa de getVersion(), quedó marcado sin que nadie subiera por encima, así que en el drenaje un padre sucio no prueba nada. Las semillas se apilan sin marcarlas visitadas a propósito: un objeto cambiado que además es dependiente de otro objeto cambiado tiene que marcarse cuando se le alcance como padre, porque lo que se le quedó viejo ahí es su caché de sus dependencias, y de eso su propia subida de versión no dice nada.

• markDirtyUpFrom(nodo), desde changeVersion() mientras la pasada corre. Para en los padres que ya estén sucios: dentro de la pasada, quien los marcó subió también por encima, así que sus ancestros ya están marcados. Eso mantiene lineal, y no cuadrática, una cascada a lo largo de una cadena de dependencias.

La pila (climbStack) es un campo reutilizado. Los ascensos no anidan: el drenaje corre antes de abrir la pasada, y el de dentro de la pasada solo llama a markDepsCacheDirty, que no llama a nada. Reutilizarla es lo que deja sin asignación un camino que se recorre una vez por objeto mutado.

Modelo de coste

Los cambios se propagan por empuje. Lo mutado desde la pasada anterior marca sucias las cachés de sus dependientes transitivos por las aristas inversas; lo que cambian las propias actualizaciones se empuja al momento. Las cachés se recalculan de forma perezosa al consultarlas, así que un frame en el que se movieron cuatro objetos cuesta O(subgrafo cambiado) y no O(escena), y un frame totalmente estático es casi gratis.

7.1 La pasada intermedia

public void updateIntermediate() {
    if (samplers.isEmpty()) return;
    sort();
    if (intermediateOrder.isEmpty()) return;
    ...
}

Existe para los IntermediateUpdateable: objetos cuyo estado depende de la historia de sus dependencias y no solo de su estado actual. El único hoy es Trail, que va registrando por dónde pasa un punto. JoinAnimation la llama en el relevo entre dos animaciones hijas, para que quien registra dónde han estado las cosas vea la posición que tienen justo en ese instante en vez de saltársela.

Una escena sin ninguno, que es casi cualquiera, contesta con ese isEmpty() y no ordena ni recorre nada. Importa porque el gancho se llama una vez por relevo cruzado, y los relevos no son raros: crear una fórmula reproduce una animación hija por glifo, o sea unos ocho relevos por frame.

El orden intermedio

intermediateOrder son los samplers más los nodos actualizables de los que dependen, en orden topológico: lo que hay que actualizar antes de que el sampler lea las posiciones. Se recalcula desde samplers, sin escanear nada:

private void rebuildIntermediateOrder() {
    intermediateOrder.clear();
    if (samplers.isEmpty()) return;
    // BFS bajando por las aristas desde cada sampler
    ...
    intermediateOrder.sort(Comparator.comparingLong(u -> ((Dependable) u).getTopoRank()));
}

Las dos decisiones de esas líneas son las que permiten que una reparación mantenga este orden, y antes ninguna de las dos se cumplía:

• Las semillas salen del registro, no de un barrido. Buscar los samplers recorriendo nodeOrder costaba O(escena) para encontrar el uno o dos que suele haber.
• Se ordena por rango, no filtrando topoOrder. Una reparación deja topoOrder obsoleto a propósito, así que depender de él ataba este orden a la reconstrucción completa. Ordenar por rango es exacto porque todo Updateable tiene un rango único: discoverBelow, lo único que reparte rangos compartidos, rechaza de plano los Updateable.

Con las dos fuera, tryIncrementalPatch ya no tiene motivo para rendirse ante un sampler y simplemente rehace este orden al final. Se rehace entero en vez de mirar si la reparación tocó la clausura: cuesta O(clausura del sampler), que son catorce nodos en una escena con un Trail y nunca puede ser peor que la reconstrucción que sustituye.

Lo que había antes era una línea, if (anySamplerSeen) return false, y salía carísima: con un solo Trail en escena toda ordenación pasaba a ser una reconstrucción completa, y como updateIntermediate() llama a sort() en cada relevo, eran ocho reconstrucciones de la escena entera por frame. Medido sobre doce líneas de LaTeX, crear la fórmula pasó de 24,3 s a 3,3 s al quitarla, y las visitas a nodos del grafo de 25,6 millones a 356 mil.

8. La ventana de consulta

public void beginQueryWindow() { AbstractVersioned.beginUpdatePass(this, myStamp); }
public void endQueryWindow()   { AbstractVersioned.endUpdatePass(); }

Abre el régimen barato de getVersion() fuera de updateAll(). Mientras está abierta, los nodos sellados por este grafo contestan desde sus cachés invalidadas por empuje, y cualquier changeVersion() se propaga a los dependientes al momento.

La escena la abre después de doUpdates() y la cierra después de guardar el frame:

private void doDraws(boolean saveFrame) {
    objectsAlreadydrawn.clear();
    doLinks();
    doUpdates();                       // graph.updateAll()
    dependencyGraph.beginQueryWindow();
    try {
        camera.update();
        fixedCamera.update();
        if (!animationIsDisabled) { /* ordenar por capa y dibujar */ }
        if (saveFrame) {
            frameCount++;
            saveMPFrame();
        }
    } finally {
        dependencyGraph.endQueryWindow();
    }
    // ahora sí, quitar de la escena lo marcado para quitar
}

Los dos detalles de esas dos líneas son deliberados y cuestan caro si se cambian:

• Se abre después de doUpdates(), no antes. Una reconstrucción dentro de la pasada cambia el sello del grafo, y una ventana abierta con el sello viejo se autodesactivaría para el resto del frame, porque beginUpdatePass limpia activePassGraph cuando el sello no coincide.

• El frame se guarda desde dentro, no en advanceFrame después. El renderer pregunta getVersion() de cada objeto del que tiene un nodo para decidir qué reconstruir (computeIsDirty y updateRendererCommandNode), y fuera de la ventana cada una de esas preguntas recorre un árbol de dependencias entero. Perfilando un showCreation con JFR, eso era en torno a una quinta parte del hilo de JavaFX. Que el cuerpo de getRenderedImage corra en el hilo de JavaFX no es problema: el par Platform.runLater más FutureTask.get establece el happens-before necesario.

9. La vida de un frame

advanceFrame()
├── renderer.clearAndPrepareCanvasForAnotherFrame()
└── doDraws(saveFrame)
    ├── doLinks()                              aplica los links de valor
    ├── doUpdates() -> graph.updateAll()
    │   ├── sort()
    │   │   ├── needsSorting()                 ¿hay trabajo apuntado?
    │   │   ├── tryIncrementalPatch()          repara las aristas de lo que cambió
    │   │   └── fullRebuildAndSort()           solo si la reparación no puede
    │   ├── markDirtyUpwards(drenaje)          sube las banderas por las aristas inversas
    │   ├── beginUpdatePass()
    │   ├── for cada updateable en orden topológico: update()
    │   │      └── update() puede changeVersion() -> markDirtyUpFrom() empuja al momento
    │   └── endUpdatePass()
    ├── beginQueryWindow()
    │   ├── camera.update() / fixedCamera.update()
    │   ├── dibujar cada objeto visible        el renderer construye render commands
    │   └── saveMPFrame()
    │       └── renderer.saveFrame()
    │           ├── computeIsDirty()           getVersion() por objeto, O(1) aquí dentro
    │           └── getRenderedImage()         en el hilo de JavaFX
    └── endQueryWindow()

Y la estructura de datos que sostiene ese flujo:

graph LR
    subgraph escena
        S["JMathAnimScene<br/>sceneObjects"]
    end
    subgraph grafo["DependencyGraph"]
        R["rootSlots + rootOrder<br/>(raíces)"]
        T["nodeInfo<br/>IdentityHashMap&lt;Dependable, Node&gt;"]
        O["updateableOrder<br/>(orden topológico)"]
    end
    subgraph objetos
        A["AbstractVersioned<br/>version, depsCacheDirty,<br/>graphStamp, topoRank"]
    end
    S -->|"add / remove"| R
    R -->|"BFS: rebuildEdges"| T
    T -->|"postOrderDfs + rangos"| O
    T -->|"Node.owner"| A
    A -->|"getDependencies()"| T
    A -->|"notifyStructuralChange()"| R
    O -->|"update()"| A
    T -->|"aristas inversas: climbMarkingDirty"| A

10. Contadores

public String getStatsSummary() {
    return String.format("nodes=%d rebuilds=%d rebuildVisits=%d patches=%d patchVisits=%d"
            + " fallbacks=%d rankExhausted=%d interVisits=%d", ...);
}

Todos se incrementan dentro de una reconstrucción o de una reparación, nunca por nodo y por frame, así que no cuestan nada en el camino por frame. resetStats() los pone a cero para medir una fase aislada.

GraphRebuildBenchmark los imprime por fase y es la forma estándar de comprobar que un cambio no ha roto la reparación incremental. Las fases van emparejadas —showCreation, shift, wait y las mismas tres con un Trail en escena— para que la diferencia dentro de cada par sea el sampler y nada más. Los tiempos absolutos no son comparables entre ejecuciones en máquinas distintas; los contadores sí, y son deterministas.

11. Invariantes y trampas

Cosas que parecen inocentes y no lo son:

• No pongas estado de recorrido en Node. Darle una marca de visitado al ascenso dentro de la pasada (un sello por generación en el registro del nodo) hizo la suite entera un 10% más lenta. La gracia de ese camino es que solo lee los registros; marcar visitado escribe en ellos y ensucia una segunda línea de caché por nodo en el camino más caliente del sistema. No lo necesita: un padre ya sucio es la propia parada.

• Un sampler no debe depender de media escena. rebuildIntermediateOrder() corre al final de cada reparación, y cuesta lo que alcanza el sampler. Un Trail que sigue un punto alcanza una docena de nodos; uno que siguiera el centro de una fórmula entera arrastraría su clausura en cada parche, y son varios por frame. interVisits es el contador que lo delata.

• No registres dependencias sobre objetos desechables. addDependency / removeDependency disparan notifyStructuralChange, y un nodo que se recablea cada frame arrastra al grafo con él.

• getVersion() cuesta O(1) o O(subárbol) según dónde se llame. Dentro de la ventana, O(1). Fuera, casi siempre lo segundo. Si añades una consulta de versión en un camino por frame, comprueba de qué lado está.

• La ventana no puede abrirse antes de doUpdates() (sección 8).

• copyStateFrom no debe subir la versión si nada cambió. restoreStates corre una vez por frame para cada objeto animado, y una restauración que devuelve los valores que ya estaban ahí no puede decirle al renderer que la geometría se movió.

• removeDependency y removeDependencies siguen usando equals. Rect y JMColor comparan por valor, así que un MODrawProperties cuyo color de trazo sea igual al de relleno quita el que no es. MathObject.dependsOnByReference es el helper que existe para eso. Pendiente.

• isRigid está declarado en MathObject y no se pone a true en ningún sitio. AbstractShape.copiesPathState() es el gancho que sí se usa: Line y Ray lo devuelven false porque su ruta son dos puntos de borde que rebuildShape() recalcula, y en el caso de Ray el primero comparte su Vec con p1, así que copiarle una ruta ajena reescribiría la definición del rayo.

12. Mapa de ficheros

13. Glosario

• Versión efectiva: max(versión propia, versiones del subárbol). Lo que devuelve getVersion().
• Reloj global: JMathAnimScene.globalVersion, monótono para todo el proceso.
• Drenaje: vaciar changedSinceLastDrain al principio de una pasada.
• Empuje / invalidación por empuje: subir la bandera de caché sucia por las aristas inversas, en vez de que cada nodo deduzca su propia obsolescencia.
• Sello (graphStamp): identifica la reconstrucción del grafo que descubrió un nodo. Que coincida con el del grafo es lo que hace que su pertenencia esté viva.
• Rango (topoRank): posición en el orden topológico, con huecos para poder insertar sin renumerar.
• Reparación / parche: rehacer las aristas de los pocos nodos que reportaron cambios, dejando el resto del grafo y su orden en paz.
• Ventana de consulta: intervalo en el que las consultas de versión se contestan desde las cachés en vez de recorriendo el árbol.
• Clausura de un sampler: el sampler y todo aquello de lo que depende, transitivamente. Es lo que cuesta rehacer intermediateOrder, y lo que acota ese coste lejos del tamaño de la escena.
• Sampler: un IntermediateUpdateable, hoy solo Trail.