Conteo de profundidad, versiones y épocas

Entre el marcado en dos fases y la ordenación topológica explícita hay un espacio de técnicas intermedias que los motores reales usan de verdad: contadores de versión para saber si algo cambió sin comparar valores, marcas de época para no verificar dos veces en el mismo ciclo, y conteo de dependencias pendientes para saber cuándo un nodo está listo. Esta lección las cierra las tres y las sitúa en los motores donde aparecen.

Contadores de versión

La idea: en vez de comparar valores para saber si una fuente cambió, dale a cada fuente un número que se incrementa en cada escritura efectiva. Un nodo guarda la versión que vio de cada fuente; si coincide, no ha cambiado.

let RelojGlobal = 0;

function escribir(fuente, valor) {
  if (fuente.iguales(fuente.valor, valor)) return;
  fuente.valor = valor;
  fuente.version = ++RelojGlobal;
}

function algunaFuenteCambio(nodo) {
  for (let i = 0; i < nodo.fuentes.length; i++) {
    if (nodo.fuentes[i].version !== nodo.versionesVistas[i]) return true;
  }
  return false;
}

La ventaja sobre comparar valores es doble. Primero, comparar dos enteros es más barato que comparar dos valores arbitrarios, sobre todo si la igualdad es estructural. Segundo, y más importante, no hay que conservar el valor anterior para compararlo: basta el número. En nodos que producen objetos grandes eso ahorra memoria de verdad.

La versión también permite algo que la comparación de valores no: distinguir no ha cambiado de ha cambiado y ha vuelto al mismo valor. Con versiones, a que pasa de 1 a 2 y vuelve a 1 genera dos versiones nuevas y el sistema lo nota. Con comparación de valores, el nodo que lo lea al final no verá diferencia. Cuál de las dos semánticas quieres depende del caso, y merece la pena saber que hay elección.

Angular usa este mecanismo de forma central: sus nodos reactivos llevan versión de productor y una comprobación que actualiza el valor solo si alguna versión de sus dependencias avanzó. Preact Signals guarda una versión en cada arista, precisamente para detectar la divergencia sin comparar.

Marcas de época

Segunda técnica. Un contador global que se incrementa una vez por ciclo de propagación, y un campo por nodo que registra en qué época se verificó por última vez.

let Epoca = 0;

function vaciarCola(cola) {
  Epoca++;                                  // empieza un ciclo nuevo
  for (const efecto of cola) actualizar(efecto);
}

function actualizar(nodo) {
  if (nodo.verificadoEn === Epoca) return;  // ya resuelto en este ciclo
  nodo.verificadoEn = Epoca;
  // ... resolucion normal
}

El problema que resuelve es el del rombo desde el otro lado: en un grafo con muchos caminos convergentes, el mismo nodo intermedio puede ser consultado muchas veces durante la resolución de un solo ciclo. Sin la marca, cada consulta recorrería su subárbol de fuentes. Con la marca, la primera consulta lo resuelve y las demás salen inmediatamente.

En un grafo con k rombos anidados, la diferencia es entre 2 elevado a k visitas y k visitas. No es una optimización menor: es la diferencia entre exponencial y lineal.

Conteo de dependencias pendientes

La tercera técnica es la más cercana a la ordenación topológica sin serlo. En vez de calcular la altura de cada nodo, se cuenta cuántas de sus fuentes están pendientes de resolver, y un nodo solo se procesa cuando ese contador llega a cero.

// Fase 1: marcar y contar
function marcarConConteo(fuente) {
  for (const obs of fuente.observadores) {
    obs.pendientes = (obs.pendientes ?? 0) + 1;
    if (obs.pendientes === 1) marcarConConteo(obs);   // primera vez, propaga
  }
}

// Fase 2: procesar solo los que ya no esperan a nadie
function resolver(nodo) {
  const cambio = ejecutarSiHaceFalta(nodo);
  for (const obs of nodo.observadores) {
    obs.pendientes--;
    if (obs.pendientes === 0) resolver(obs);          // ya estan todas sus fuentes
  }
}

Esto es un ordenamiento topológico de Kahn, hecho al vuelo y sin calcular alturas. La garantía es la misma que la de la cola de prioridad —ningún nodo se procesa antes que sus dependencias— y no requiere mantener ninguna propiedad global entre propagaciones, porque el conteo se construye y se consume dentro de un solo ciclo.

El precio es que la fase 1 tiene que recorrer el subgrafo entero para contar, incluso las ramas que luego no cambiarán nada. Es decir: se pierde parte de la pereza. A cambio, se gana un orden estricto y explícito sin el coste de mantener alturas entre propagaciones.

flowchart TB
T[tecnicas de consistencia] --> V[versiones]
T --> E[epocas]
T --> C[conteo de pendientes]
V --> V1[detectar cambio sin comparar valores]
E --> E1[no verificar dos veces por ciclo]
C --> C1[orden estricto sin mantener alturas]
style T fill:#cba6f7,color:#11111b
style V fill:#89b4fa,color:#11111b
style E fill:#94e2d5,color:#11111b
style C fill:#fab387,color:#11111b
style V1 fill:#a6e3a1,color:#11111b
style E1 fill:#a6e3a1,color:#11111b
style C1 fill:#a6e3a1,color:#11111b

Cómo se combinan, y cierre del nivel

Cómo se combinan en la práctica

Ningún motor real usa una sola técnica. La combinación típica es esta.

Marcado en dos fases como esqueleto, porque no exige mantener nada entre propagaciones y tolera grafos dinámicos.

Versiones para decidir si una fuente cambió, porque es más barato que comparar valores y evita guardar el anterior.

Épocas para no repetir verificaciones dentro de un ciclo, porque es lo que hace que los rombos anidados no exploten.

Y una cola explícita de efectos, ordenada por un criterio predecible —orden de creación o profundidad en el árbol de componentes— porque el orden entre efectos es observable por el programador y conviene que no dependa del azar.

Cierre del nivel

Un motor es glitch-free si garantiza que ningún nodo se evalúa antes que sus dependencias transitivas. Hay dos formas de garantizarlo: descubrir el orden al recorrer, con marcado en dos fases, o calcularlo por adelantado, con alturas o con conteo de pendientes. Los motores de interfaz eligen la primera porque su grafo es dinámico, y refuerzan la eficiencia con versiones y épocas.

Lo que viene ahora es el otro gran mecanismo de ahorro: el nodo que decide no propagar porque su valor no ha cambiado. Es el nivel 6.