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

HotXLS 2.383.1, la librería nativa de Excel para Delphi y C++Builder, construye las aristas de dependencia de fórmulas mediante un índice de intervalos de salida: los nodos de fórmula quedan ordenados por celda ancla, y un segment tree que guarda la fila de salida mayor (OutRow2) de cada subárbol permite a TXLSDepGraph.BuildEdges saltarse bloques enteros de fórmulas que no pueden alcanzar un rango referenciado. En un libro Win32 con unas 100,000 fórmulas, el recálculo forzado cayó de 18.488 segundos a 102–109 milisegundos

Nadie hace profiling del grafo de dependencias hasta que un trabajo por lotes que antes tardaba un segundo empieza a tardar veinte. El grafo se reconstruye cada vez que cambia la topología de fórmulas — el primer Recalculate tras cargar o generar un libro, o cualquier pasada después de que el grafo fue invalidado — y en el trace previo al fix, esa primera pasada sola tomó 16,074 ms. La evaluación nunca fue el problema; decidir quién depende de quién sí lo era

¿Por qué recalcular 100,000 fórmulas tomaba 18 segundos?

El viejo constructor de aristas era cuadrático respecto del número de fórmulas de una hoja. Para cada rango de dependencia, BuildEdges hacía una búsqueda binaria de una ventana de nodos candidatos y luego probaba cada uno con RangeIntersectsOutput, y esa ventana arrancaba en lo más alto de la hoja referenciada. Las claves de nodo salen de XLSDepMakeKey, que empaqueta el índice de hoja desde el bit 34 hacia arriba, la fila en los bits 14–33 y la columna en los bits 0–13, así que el límite inferior (Sheet1, 0, 0) significaba «toda fórmula desde la fila 1 hasta el final del rango referenciado»

// Antes de 2.383.1 - TXLSDepGraph.BuildEdges, para el rango de dependencia r del nodo d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // tope de la hoja
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...dos búsquedas binarias sobre FNodeOrder producen la ventana [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // arista dura o arista LookupScan, deduplicadas vía EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

El fixture de rendimiento que lo expuso es un modelo en cascada común: A2:A50000 suma uno a la celda de arriba, y B1:B50000 duplica al vecino de la columna A. Una referencia a la fila r arrastraba entonces unos 2r candidatos por la prueba de rectángulo, así que una sola construcción del grafo hacía del orden de cinco mil millones de verificaciones de intersección — una estimación a mano alzada, pero cuadra con los 18.5 segundos del reloj. Cada verificación decía «no» salvo una o dos

¿Por qué el constructor de aristas no puede arrancar la búsqueda en la fila referenciada?

Porque una fórmula matricial anclada por encima de un rango puede ser dueña de celdas adentro. Cada TXLSDepNode describe un rectángulo de salida desde su ancla (Row, Col) hasta (OutRow2, OutCol2), y una fórmula matricial CSE recibe un nodo para su rectángulo entero, como explica el artículo sobre recálculo incremental y el grafo de dependencias. Una raíz anclada en A1 que llena A1:A10 aún debe recibir una arista de una fórmula que lee solo A5; arranque la búsqueda binaria en la fila 5 y esa arista desaparece en silencio, lo que significa un valor en caché vencido en un reporte entregado en lugar de uno lento. La consulta en realidad es de dos lados — ancla en o antes de Row2, salida que alcance al menos Row1 — y un solo orden de ordenamiento no puede responder ambas mitades. Los resultados multicelda también aparecen en libros modernos, y el artículo sobre fórmulas spill de dynamic array cubre cómo se comportan los rangos derramados en HotXLS

Un segment tree de filas de salida máximas

HotXLS conserva el ordenamiento por ancla para el límite superior y agrega un segment tree aumentado para el límite inferior. BuildNodeIndex ordena FNodeOrder por clave de nodo como antes, y luego BuildMaxOutRowTree llena FNodeMaxOutRow2 (asignado a cuatro entradas por nodo) con el mayor OutRow2 encontrado bajo cada subárbol. QueryNodeTree desciende solo dentro de la ventana de claves y abandona cualquier subárbol cuya fila de salida máxima quede por encima de FRanges[r].Row1, porque ninguna fórmula dentro puede alcanzar las filas referenciadas. Las hojas que sobreviven igual pasan por la prueba completa de RangeIntersectsOutput, así que los tramos de hoja y las columnas se verifican exactamente igual que antes

// TXLSDepGraph.BuildNodeIndex / BuildEdges desde 2.383.1 (condensado sin mucha ceremonia)
procedure BuildMaxOutRowTree(ATreeIndex, ALeft, ARight: Integer);
var
  Mid: Integer;
begin
  if ALeft = ARight then
  begin
    FNodeMaxOutRow2[ATreeIndex] := FNodes[FNodeOrder[ALeft]].OutRow2;
    Exit;
  end;
  Mid := (ALeft + ARight) shr 1;
  BuildMaxOutRowTree(ATreeIndex * 2, ALeft, Mid);
  BuildMaxOutRowTree(ATreeIndex * 2 + 1, Mid + 1, ARight);
  FNodeMaxOutRow2[ATreeIndex] := Max(FNodeMaxOutRow2[ATreeIndex * 2],
    FNodeMaxOutRow2[ATreeIndex * 2 + 1]);
end;

procedure QueryNodeTree(ATreeIndex, ALeft, ARight, ALower, AUpper: Integer);
var
  Split: Integer;
begin
  // fuera de la ventana de claves, o ninguna salida de este subárbol alcanza Row1
  if (ARight < ALower) or (ALeft >= AUpper) or
     (FNodeMaxOutRow2[ATreeIndex] < FRanges[r].Row1) then
    Exit;
  if ALeft = ARight then
  begin
    Inc(FEdgeCandidateChecks);
    if RangeIntersectsOutput(FRanges[r], FNodes[FNodeOrder[ALeft]]) then
    begin
      // sin cambios: supresión EdgeStamp / ScanStamp, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // primero el subárbol izquierdo
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // conserva el orden viejo
end;

La recursión izquierdo-antes-que-derecho no es una elección estilística. Las hojas sobrevivientes se visitan en exactamente el orden en que el viejo loop while las visitaba, así que los arreglos Dependents y Precedents se llenan en la misma secuencia y el orden topológico sigue siendo determinista. Lo mismo vale para los dos tipos de arista: una arista dura registrada primero sigue suprimiendo una arista LookupScan posterior del mismo par, mientras que una arista de escaneo registrada antes que una dura conserva su lugar — la distinción que evita que los rangos de lookup produzcan referencias circulares falsas. Por referencia, el costo baja del tamaño de la ventana a O((k + 1) log n), donde k es el número de fórmulas cuya salida realmente alcanza las filas referenciadas

¿Qué garantiza el índice de salida y cómo se verifica?

TXLSDepGraph produce las mismas aristas en el mismo orden que antes, y la nueva propiedad EdgeCandidateChecks cuenta cuántos rectángulos de salida probó realmente la construcción más reciente, así que la afirmación es medible y no retórica. La prueba de regresión EdgeBuildDeepChainsCheckOneCandidatePerDependency construye cadenas de referencias a punto de 1,024 y 100,000 nodos, insertadas en orden inverso para forzar el ordenamiento espacial, y afirma exactamente N − 1 verificaciones — 99,999 para la cadena larga — más el precedente, el dependiente y el orden topológico esperados para cada nodo. Pruebas acompañantes cubren raíces de array insertadas fuera de orden a través de tramos de hojas, referencias duras y de lookup-scan duplicadas (10 verificaciones, con las reglas de supresión de arriba), y una reconstrucción tras AddNode, que limpia la bandera de ordenamiento de modo que el próximo BuildEdges o NodeIndexOf reconstruye el árbol y resetea el contador en lugar de acumularlo

Resultados medidos: de 18.5 segundos a unos 0.1 segundos

El trace Win32 previo al fix, conservado en la línea base de rendimiento del proyecto para la versión 2.383.0, registró dos recálculos forzados de 18,488 ms y 19,578 ms. Tras la indexación, tres corridas seriales enfocadas por arquitectura midieron 102.332–109.429 ms en Win32 y 116.990–133.995 ms en Win64, unas 170 a 180 veces más rápido en Win32; no se registró línea base Win64 previa al fix, así que no se afirma aceleración alguna en Win64. Las mismas corridas pasaron el gate existente que mantiene una auditoría de recálculo de solo lectura dentro de 1.35 veces un recálculo forzado. Los números absolutos dependen de la máquina y su carga, así que reproduzca la carga de trabajo en su propio hardware antes de citarlos

uses
  System.SysUtils, System.Diagnostics, lxHandle;

procedure TimeChainRecalc;
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;                  // la primera llamada construye el grafo
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

¿Dónde deja de ayudar el índice de salida?

El árbol poda solo por filas, y eso deja unos cuantos límites honestos que vale conocer antes de diseñar un modelo muy grande alrededor suyo

• Los fallos de columna igual se pagan en las hojas: las 2,626 fórmulas que llenan A100:Z200 todas alcanzan la fila 100, así que una referencia a AA100:AA200 las prueba una por una antes de rechazarlas
• Las referencias anchas, como los rangos de columna completa, genuinamente tienen muchos precedentes; el índice elimina verificaciones desperdiciadas, no aristas reales, y construir esas aristas sigue siendo proporcional a su número
• Para referencias que abarcan varias hojas, el máximo almacenado ignora la hoja, así que las fórmulas de hojas intermedias con salidas profundas llegan a la prueba de hoja; los resultados siguen siendo correctos, solo la poda es más débil
• El árbol cuesta cuatro enteros por nodo de fórmula, unos 1.6 MB para 100,000 nodos, y cualquier AddNode lo invalida, así que los cambios de topología pagan un re-ordenamiento O(n log n) completo más una construcción O(n) del árbol en la próxima construcción de aristas

La misma forma cuadrática en la clonación de nombres de bandas de reporte

La versión 2.383.2 arregló un problema hermano en TXLSXDefinedNames.UniqueCloneName: cada nombre definido copiado reiniciaba su búsqueda de sufijo en _2, así que las copias repetidas de bandas de reporte crecían de forma cuadrática en lookups de nombres. El índice de nombres con scope ahora guarda una pista de sufijo por nombre base y por scope, y reverifica el último candidato devuelto, porque quien llama puede que no lo agregue de verdad; eliminar, renombrar o cambiar el scope de un nombre invalida el índice, lo que restaura el nombrado del primer disponible. En la suite de regresión, 1,024 clones secuenciales necesitan 5,088 lookups de candidatos y cuatro nombres base alternantes necesitan 5,039, mientras que los mínimos del benchmark de reportes bajaron de unos 240 ms a 18–20 ms. El propio gate de tiempos de bandas de reporte sigue sin ser estable — tres de seis corridas excedieron su ratio de 1.05 en el primer intento tras el fix — y la historia de rendimiento mantiene esos fallos en el registro en lugar de afinar el umbral hasta que pase

Si su aplicación Delphi o C++Builder genera o recalcula libros de Excel grandes, el componente Excel HotXLS para Delphi y C++Builder trae este grafo de dependencias indexado en su motor de recálculo, tanto para su clase de libro clásica como para la XLSX