Grafo de dependencias HotXLS: índice de salidas de fórmulas

Una hoja con 50,000 fórmulas en la columna A, cada una sumando uno a la celda de arriba, y otras 50,000 en la columna B duplicando a su vecina, es tan plano como puede ser un modelo de hoja de cálculo. Evaluarlo cuesta 100,000 sumas y multiplicaciones. Calcular el orden de evaluación cuesta mucho más si el constructor de aristas se escribe de la manera obvia: buscar cada fórmula desde el tope de la hoja referenciada hasta la fila referenciada, probar cada una por traslape y quedarse con las que pegan. Para esta sola hoja eso da del orden de cinco mil millones de pruebas de rectángulo, y casi todas responden que no

Los cinco mil millones son aritmética, no una lectura de cronómetro. Una referencia a la fila r arrastra unos 2r candidatos a la ventana de búsqueda, uno por columna para cada fila que queda por encima, y sumar eso sobre 100,000 referencias aterriza en los miles de millones. Lo interesante es que la ventana de verdad tiene que arrancar en el tope de la hoja, por una razón que no tiene nada que ver con la flojera

Dónde gasta el tiempo una reconstrucción de dependencias

El motor de recálculo de HotXLS reconstruye su grafo de dependencias de fórmulas cada vez que cambia la topología de fórmulas: el primer Recalculate después de cargar o generar un libro, y el primero después de reescribir fórmulas, agregar o quitar hojas, o clonar un bloque de celdas. Las dos clases de libro, TXLSWorkbook y TXLSXWorkbook, construyen para esto un TXLSDepGraph de la unidad lxDepGraph. Cada celda con fórmula se convierte en un nodo con un ancla (Row, Col) y un rectángulo de salida que llega hasta (OutRow2, OutCol2). Para una fórmula ordinaria el rectángulo es la propia celda ancla

Los nodos se ordenan por una clave de 64 bits empaquetada por XLSDepMakeKey: la columna va en los bits 0–13, la fila en los bits 14–33 y el índice de hoja desde el bit 34 hacia arriba. Ordenar por esa clave da un orden hoja-mayor, fila-mayor, así que encontrar la última fórmula que podría importar para una referencia es una sola búsqueda binaria sobre (Sheet2, Row2, 16383). La primera es el problema. El límite inferior tiene que ser (Sheet1, 0, 0), el mismísimo tope de la hoja referenciada, y todo lo que queda entre los dos límites se vuelve candidato

¿Por qué la búsqueda no puede arrancar en la fila referenciada?

Una fórmula matricial anclada por encima de un rango puede ser dueña de celdas adentro. En un TXLSXWorkbook, un array CSE introducido en A1:A8 es un solo nodo cuyo ancla es A1 y cuya salida llega hasta la fila 8, como describe el artículo sobre recálculo incremental y el grafo de dependencias. Una fórmula en D5 que lee solo A5 todavía necesita una arista desde ese nodo. Arranque la búsqueda binaria en la fila 5 y el ancla de la fila 1 nunca se visita, la arista nunca se registra y D5 puede evaluarse antes que el array del que depende. El síntoma es un valor en caché vencido en el libro guardado, mucho más difícil de notar que un recálculo lento

Así que la consulta real tiene dos lados. Un nodo es candidato cuando su ancla está en o antes de Row2 y su salida alcanza al menos Row1, en una hoja dentro de la referencia y con columnas que se traslapan. Un ordenamiento por ancla responde la primera mitad. Nada en el orden por ancla dice algo sobre la segunda mitad, porque una fórmula en la fila 3 puede producir una celda o mil filas. Las tablas de datos what-if tienen la misma forma: TXLSXWorkbook registra cada tabla de datos como un solo nodo que cubre toda su área de resultados. Las fórmulas dynamic array toman otro camino y se marcan volátiles, así que se recalculan en cada pasada; el artículo sobre fórmulas spill de dynamic array cubre cómo se comportan los rangos derramados

TXLSDepGraph es una clase pública, así que el caso es fácil de reproducir sin un libro. Los índices de hoja son 1-based y las filas y columnas son 0-based, igual que las coordenadas del calculador. La sonda de abajo registra la raíz del array y el lector, construye las aristas, y además corre una cadena invertida de referencias a punto por el mismo tipo de grafo para mostrar el contador en el que se apoyan las siguientes secciones

uses
  System.SysUtils, lxDepGraph;

function PointRef(ASheet, ARow, ACol: Integer): TXLSDepRange;
begin
  Result.Sheet1 := ASheet;
  Result.Sheet2 := ASheet;
  Result.Row1 := ARow;
  Result.Row2 := ARow;
  Result.Col1 := ACol;
  Result.Col2 := ACol;
  Result.LookupScan := False;
end;

procedure ProbeOutputIndex;
const
  N = 100000;
var
  G: TXLSDepGraph;
  Deps: TXLSDepRangeList;
  Reader, Row: Integer;
begin
  Deps := TXLSDepRangeList.Create;
  G := TXLSDepGraph.Create;
  try
    // array CSE: ancla A1 (fila 0, col 0), salida hasta A8 (fila 7)
    G.AddNode(1, 0, 0, 7, 0, False, nil);
    // D5 (fila 4, col 3) lee solo A5
    Deps.Add(PointRef(1, 4, 0));
    Reader := G.AddNode(1, 4, 3, 4, 3, False, Deps);
    G.BuildEdges;
    Writeln('D5 precedents: ', G.Nodes[Reader].PrecedentCount);  // 1, la raíz A1
    Writeln('rectangles tested: ', G.EdgeCandidateChecks);       // 2: la raíz A1 y el propio D5
  finally
    G.Free;
  end;

  // Cadena A1..A100000, cada celda lee la de arriba, insertada de abajo hacia arriba
  G := TXLSDepGraph.Create;
  try
    for Row := N - 1 downto 0 do
    begin
      Deps.Clear;
      if Row > 0 then
        Deps.Add(PointRef(1, Row - 1, 0));
      G.AddNode(1, Row, 0, Row, 0, False, Deps);
    end;
    G.BuildEdges;
    Writeln('chain checks: ', G.EdgeCandidateChecks);  // N - 1 = 99999
  finally
    G.Free;
    Deps.Free;
  end;
end;

Poda de subárboles por su fila de salida mayor

TXLSDepGraph.BuildEdges conserva el ordenamiento por ancla para el límite superior y responde el límite inferior con un segment tree aumentado con el máximo, tendido sobre el orden ya ordenado. Cada entrada del árbol guarda el mayor OutRow2 de todos los nodos que tiene debajo. La consulta desciende solo dentro de la ventana de claves y descarta cualquier subárbol cuyo máximo almacenado quede por encima de Row1, porque ninguna fórmula de ese subárbol puede alcanzar las filas referenciadas. Los nodos que sobreviven igual pasan por la prueba completa de rectángulo, así que el tramo de hojas y las columnas se verifican exactamente como antes

La técnica es lo bastante pequeña para mostrarla completa. El boceto de abajo es una versión mínima escrita para este artículo, con nombres propios; ninguno es API de HotXLS, y los arreglos los llena quien lee a partir de una lista de filas de salida ya ordenada por clave de ancla

uses
  System.Math, System.Generics.Collections;

// Solo un boceto: un segment tree aumentado con el máximo sobre nodos ordenados por clave de ancla.
// OutRow2[i] es la última fila de salida del i-ésimo nodo en el orden ordenado.
type
  TOutputIndex = record
    OutRow2: TArray<Integer>;
    MaxRow: TArray<Integer>;   // SetLength(MaxRow, 4 * Length(OutRow2))
  end;

procedure BuildMax(var Ix: TOutputIndex; Node, L, R: Integer);
var
  M: Integer;
begin
  if L = R then
  begin
    Ix.MaxRow[Node] := Ix.OutRow2[L];
    Exit;
  end;
  M := (L + R) shr 1;
  BuildMax(Ix, Node * 2, L, M);
  BuildMax(Ix, Node * 2 + 1, M + 1, R);
  Ix.MaxRow[Node] := Max(Ix.MaxRow[Node * 2], Ix.MaxRow[Node * 2 + 1]);
end;

// Reúne, de izquierda a derecha, cada nodo en [Lo, Hi) cuya salida alcanza Row1
procedure Query(const Ix: TOutputIndex; Node, L, R, Lo, Hi, Row1: Integer;
  Hits: TList<Integer>);
var
  M: Integer;
begin
  if (R < Lo) or (L >= Hi) or (Ix.MaxRow[Node] < Row1) then
    Exit;                        // fuera de la ventana, o nada alcanza Row1
  if L = R then
  begin
    Hits.Add(L);                 // quien llama igual corre la prueba completa de rectángulo
    Exit;
  end;
  M := (L + R) shr 1;
  Query(Ix, Node * 2, L, M, Lo, Hi, Row1, Hits);           // primero el izquierdo
  Query(Ix, Node * 2 + 1, M + 1, R, Lo, Hi, Row1, Hits);   // conserva el orden de escaneo
end;

// Construya una vez con BuildMax(Ix, 1, 0, Count - 1),
// luego, por referencia, llame Query(Ix, 1, 0, Count - 1, Lo, Hi, Row1, Hits)

Por referencia, el trabajo baja del tamaño de la ventana a O((k + 1) log n), donde k es el número de nodos cuya salida realmente alcanza las filas referenciadas. De vuelta en el modelo inicial, una referencia de Br a Ar ahora prueba dos rectángulos, Ar y el propio Br, y una referencia de Ar a la celda de arriba prueba los dos nodos de esa fila. A mano eso da unas 200,000 pruebas para la construcción completa en lugar de cinco mil millones

Las mismas aristas, en el mismo orden

La recursión izquierdo-antes-que-derecho importa más de lo que parece. Los nodos sobrevivientes se visitan exactamente en el orden en que un bucle plano sobre la ventana los visitaría, así que los arreglos Dependents y Precedents de cada nodo se llenan en la misma secuencia, y el orden topológico construido a partir de ellos sale igual en cada corrida. Ese orden no es solo contabilidad interna: cuando el grafo está al día, el escritor XLSX emite xl/calcChain.xml en el orden que devuelve FullTopoOrder, así que un orden de visita no determinista aparecería como diffs ruidosos entre dos guardados de un libro sin cambios

Los tipos de arista también conservan sus reglas. Las referencias que caen en el argumento de lookup-array de VLOOKUP, MATCH, XLOOKUP y funciones similares producen aristas de lookup-scan, que propagan la suciedad pero se mantienen fuera de la detección de ciclos. Cuando un nodo tiene a la vez una referencia dura y una de lookup hacia el mismo precedente, una arista dura registrada primero suprime la arista de escaneo posterior, y una arista de escaneo registrada primero conserva su lugar mientras la dura igual se agrega. Ese ordenamiento es lo que evita que los rangos de lookup produzcan referencias circulares falsas, y solo se sostiene si la caminata podada visita los candidatos en orden de escaneo

La propiedad EdgeCandidateChecks hace observable la poda. Cuenta los rectángulos de salida que la llamada más reciente a BuildEdges probó de verdad y se reinicia al comienzo de cada construcción. En la sonda de arriba, la cadena invertida reporta 99,999, una prueba por referencia, aunque los nodos se insertaron de abajo hacia arriba y el ordenamiento tuvo que reacomodarlos todos. AddNode marca como vencidos tanto el ordenamiento como las aristas, así que el próximo BuildEdges o NodeIndexOf reconstruye el índice en lugar de parcharlo

Dónde queda el costo restante

El árbol poda solo por filas, y esa decisión moldea lo que un modelo grande todavía paga

• Los fallos de columna se pagan en las hojas: las 2,626 fórmulas que llenan A100:Z200 alcanzan todas la fila 100, así que una referencia a AA100:AA200 prueba cada una antes de rechazarla por columnas
• Las referencias de columna completa y otras referencias anchas genuinamente tienen muchos precedentes; el índice elimina las pruebas desperdiciadas, y construir las aristas reales sigue siendo proporcional a cuántas hay
• Una referencia que abarca varias hojas abre una ventana que cubre toda la primera hoja, así que las fórmulas de ahí con salidas profundas llegan a la prueba de hoja; las aristas salen iguales y solo la poda es más débil
• El árbol toma cuatro enteros por nodo, unos 1.6 MB para 100,000 fórmulas, y cualquier cambio de topología paga un reordenamiento O(n log n) completo más una construcción O(n) del árbol en la próxima construcción de aristas

Las filas son la dimensión única correcta para indexar. Los reportes generados, los libros contables y los modelos financieros crecen hacia abajo, así que la distancia en filas es de donde sale casi todo el desperdicio de candidatos, mientras que un fallo de columna lo rechaza la prueba de rectángulo en un puñado de comparaciones de enteros. Una segunda dimensión en el árbol complicaría cada consulta para ahorrar pruebas que ya son baratas

Del lado de quien llama, el paso caro es la reconstrucción, y las ediciones de valores no la disparan. Recalculate construye el grafo en su primera llamada; las siguientes reevalúan solo las fórmulas aguas abajo de los valores cambiados, más las volátiles. Escribir todas las fórmulas primero y recalcular una sola vez es el patrón al que hay que apuntar. El banco de pruebas de abajo cronometra los dos tipos de pasada en el motor clásico, donde Recalculate devuelve el número de celdas con fórmula que no pudo evaluar; córralo en el hardware que va a hospedar el trabajo por lotes, porque los tiempos absolutos dependen muchísimo de la máquina

uses
  System.SysUtils, System.Diagnostics, lxHandle;

procedure TimeCascadeRecalc;
var
  Wb: TXLSWorkbook;
  Sh: TXLSWorksheet;
  I, Failed: Integer;
  Watch: TStopwatch;
begin
  Wb := TXLSWorkbook.Create;
  try
    Sh := Wb.Sheets.Add;
    Sh.Cells[1, 1].Value := 1;
    for I := 2 to 50000 do                     // cadena de 49,999 eslabones en la columna A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50,000 dependientes en la columna B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // construye el grafo, evalúa todo
    Writeln(Format('first pass: %d not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));

    Sh.Cells[1, 1].Value := 10;                // edición de valor: el grafo se reutiliza
    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // solo el subgrafo sucio
    Writeln(Format('value pass: %d not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

En este modelo la pasada de valores todavía reevalúa las 99,999 fórmulas, porque toda la columna A cuelga de A1; lo que se salta es la construcción del grafo. Sobrescribir una celda con fórmula con un valor plano es otro asunto, porque eso cambia la topología y el próximo Recalculate reconstruye el grafo desde cero

La misma forma cuadrática en nombres definidos clonados

Las bandas de reporte esconden el mismo patrón en otro lugar. TXLSXWorksheet.CloneRangeTo copia los nombres definidos que apuntan directamente a un rango dentro del bloque clonado, y cada copia necesita un nombre único en su scope: Total_2, Total_3, y así sucesivamente. Una búsqueda que reinicia en _2 para cada copia prueba un candidato más cada vez, así que una hoja construida a partir de cientos de bandas clonadas gasta un número cuadrático de búsquedas de nombres solo en nombrar

TXLSXDefinedNames lo evita con una pista de sufijo guardada en su índice de nombres, una por nombre base y scope. La siguiente búsqueda arranca desde el sufijo devuelto la última vez y lo reverifica primero, porque quien llama es libre de no agregar ese nombre. Eliminar un nombre, renombrarlo vía Name, moverlo con SheetIndex o limpiar la colección tira el índice junto con todas las pistas, así que el próximo clon vuelve al primer sufijo libre y rellena cualquier hueco que el cambio haya abierto

Para aplicaciones Delphi y C++Builder que generan o recalculan hojas de cálculo grandes, el componente Excel HotXLS para Delphi y C++Builder usa este grafo de dependencias indexado en el motor de recálculo de sus dos clases de libro, la clásica y la XLSX