Cómo se representan las listas de aristas

Ya sabemos que cada nodo guarda dos listas de aristas. Queda la pregunta que decide buena parte del rendimiento de un motor: con qué estructura de datos. Las tres respuestas que existen en producción —conjuntos hash, arrays con índices cruzados y listas doblemente enlazadas— tienen el mismo orden asintótico y constantes muy distintas, y cada una gana en un perfil de uso concreto.

Las operaciones que hay que soportar

Antes de comparar, fijemos qué se va a hacer con estas listas, porque el ganador depende enteramente de la mezcla.

Alta: añadir una arista al leer una fuente dentro de una computación. Ocurre una vez por lectura, y las lecturas son la operación más frecuente del sistema con diferencia.

Baja de todas: desatar una computación de todas sus fuentes antes de reejecutarla. Ocurre una vez por reejecución, y toca tantas aristas como dependencias tenga el nodo.

Iteración: recorrer los observadores de una fuente al propagar. Ocurre una vez por escritura.

Consulta de pertenencia: comprobar si una arista ya existe, para no duplicarla cuando un cuerpo lee la misma fuente dos veces.

Opción 1: conjunto hash

La más directa. Un Set en cada dirección.

const nodo = { fuentes: new Set(), observadores: new Set() };

function seguir(fuente) {
  if (!Observador) return;
  Observador.fuentes.add(fuente);
  fuente.observadores.add(Observador);
}
function desatar(nodo) {
  for (const f of nodo.fuentes) f.observadores.delete(nodo);
  nodo.fuentes.clear();
}

Alta en tiempo constante, baja en tiempo constante, deduplicación gratis, iteración en orden de inserción. Es correcta, es la más corta y es la que usaremos en el motor del nivel 12 por legibilidad.

Su problema son las constantes. Cada Set es un objeto con una tabla hash detrás; cada add calcula un hash y puede provocar un redimensionado; la iteración salta por memoria no contigua. Para un motor con cientos de miles de aristas y lecturas en bucles apretados, ese sobrecoste se nota. Y hay un detalle de memoria que sorprende: un Set vacío no es gratis, y una aplicación con cincuenta mil nodos paga cien mil conjuntos aunque la mitad no tenga ninguna arista.

Opción 2: arrays con índices cruzados

La representación de Solid. Dos arrays paralelos por dirección: uno con los nodos y otro con el índice que ocupa esta arista en la lista del otro extremo.

// fuente: observadores[] y observadorSlots[]
// computacion: fuentes[] y fuenteSlots[]

function seguir(fuente) {
  if (!Observador) return;
  const hueco = fuente.observadores ? fuente.observadores.length : 0;
  (Observador.fuentes ??= []).push(fuente);
  (Observador.fuenteSlots ??= []).push(hueco);
  (fuente.observadores ??= []).push(Observador);
  (fuente.observadorSlots ??= []).push(Observador.fuentes.length - 1);
}

La ganancia está en la baja. Sin los índices, borrar una computación de la lista de observadores de una fuente exigiría buscarla, con coste lineal. Con los índices se sabe dónde está, y se aplica un intercambio con el último elemento.

function desatar(nodo) {
  while (nodo.fuentes && nodo.fuentes.length) {
    const fuente = nodo.fuentes.pop();
    const indice = nodo.fuenteSlots.pop();          // donde estaba yo
    const obs = fuente.observadores;
    const ultimo = obs.pop();
    const huecoUltimo = fuente.observadorSlots.pop();
    if (indice < obs.length) {                       // si no era yo el ultimo
      obs[indice] = ultimo;                          // muevo el ultimo a mi hueco
      fuente.observadorSlots[indice] = huecoUltimo;
      ultimo.fuenteSlots[huecoUltimo] = indice;      // y reparo su indice cruzado
    }
  }
}

La última línea es la delicada: al mover el último elemento a otro hueco, su índice cruzado queda obsoleto y hay que repararlo en el acto. Si se olvida, la lista se corrompe y la siguiente baja borra la arista equivocada.

A cambio de esa complejidad se obtienen arrays contiguos, iteración rapidísima, y creación perezosa —los arrays se crean en la primera arista con ??=, así que un nodo sin dependencias no paga nada. Es una decisión clásica de rendimiento: complicar el caso raro para abaratar el frecuente.

La tercera opción y cómo elegir

Opción 3: lista doblemente enlazada con reutilización

La representación de Preact Signals, y la que Vue adoptó al reescribir su reactividad sobre alien-signals. En lugar de listas, cada arista es un objeto nodo enlazado en dos listas a la vez: la de fuentes del observador y la de observadores de la fuente.

// Una arista como objeto propio
const arista = {
  fuente, observador,
  siguienteFuente, anteriorFuente,        // en la lista del observador
  siguienteObservador, anteriorObservador, // en la lista de la fuente
  version,                                 // version de la fuente cuando se leyo
};

El coste de alta y baja es constante y sin trucos, porque desenlazar un nodo doblemente enlazado solo requiere tocar sus dos vecinos. Pero la ventaja de verdad es otra, y es la que motivó el diseño: permite reutilizar las aristas entre ejecuciones.

La observación de partida es que la inmensa mayoría de las reejecuciones leen exactamente las mismas fuentes en el mismo orden. Si en vez de destruir todas las aristas y volver a crearlas se recorre la lista existente comprobando si la fuente coincide, en el caso común no se asigna ni un solo objeto: solo se actualiza el campo de versión. Solo cuando el conjunto de dependencias cambia de verdad —una condicional que toma otra rama— hay que enlazar y desenlazar.

flowchart TB
A[reejecutar computacion] --> B{la fuente leida coincide con la arista existente}
B -->|si| C[reutilizar la arista y actualizar la version]
B -->|no| D[desenlazar la vieja y enlazar una nueva]
C --> E[cero asignaciones en el caso comun]
D --> F[coste solo cuando el grafo cambia de forma]
style A fill:#89b4fa,color:#11111b
style B fill:#f9e2af,color:#11111b
style C fill:#a6e3a1,color:#11111b
style D fill:#fab387,color:#11111b
style E fill:#a6e3a1,color:#11111b
style F fill:#94e2d5,color:#11111b

El precio es un objeto por arista en lugar de dos entradas de array, más punteros, y peor localidad de caché al iterar. Se cambia memoria e iteración por ausencia de asignaciones en el camino caliente.

Cómo elegir

Las tres son constantes en lo asintótico. La elección es enteramente de constantes, y depende del perfil.

Si dominan las reejecuciones con dependencias estables —lo típico en interfaces—, la lista enlazada gana porque elimina asignaciones. Si domina la propagación sobre listas de observadores grandes, los arrays ganan por localidad. Si lo que importa es la legibilidad y el tamaño del código, el conjunto hash gana sin discusión.