Grafo de dependencias en HotXLS: indexar salidas array

HotXLS 2.383.1, la biblioteca Excel nativa 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 siguen ordenados por celda ancla, y un segment tree que guarda la mayor fila de salida (OutRow2) de cada subárbol permite a TXLSDepGraph.BuildEdges saltarse bloques enteros de fórmulas que no pueden alcanzar un rango referenciado. En un workbook Win32 con unas 100.000 fórmulas, el recálculo forzado bajó de 18,488 segundos a 102–109 milisegundos

Nadie hace profiling del grafo de dependencias hasta que un trabajo por lotes que 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 workbook, o cualquier pasada después de que el grafo se haya invalidado — y en la traza anterior al fix, solo esa primera pasada se llevaba 16.074 ms. Evaluar nunca fue el problema; decidir quién depende de quién sí lo fue

¿Por qué recalcular 100.000 fórmulas tardaba 18 segundos?

El constructor de aristas antiguo era cuadrático respecto al número de fórmulas de una hoja. Para cada rango de dependencia, BuildEdges buscaba por bisección una ventana de nodos candidatos y luego probaba cada uno con RangeIntersectsOutput, y esa ventana empezaba 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 fondo 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);   // lo más alto 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, deduplicada mediante EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

El fixture de rendimiento que destapó esto es un modelo en cascada de los de siempre: A2:A50000 suma cada uno uno a la celda de arriba, y B1:B50000 duplica cada uno al vecino de la columna A. Una referencia a la fila r arrastraba por tanto unos 2r candidatos por el test del rectángulo, de modo que una sola construcción del grafo hacía del orden de cinco mil millones de comprobaciones de intersección — una estimación a bote pronto, pero cuadra con los 18,5 segundos del reloj. Todas las comprobaciones decían «no» salvo una o dos

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

Porque una fórmula array anclada por encima de un rango puede poseer celdas dentro de él. Cada TXLSDepNode describe un rectángulo de salida desde su ancla (Row, Col) hasta (OutRow2, OutCol2), y una fórmula array 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 tiene que recibir igualmente una arista de una fórmula que solo lee A5; empieza la búsqueda binaria en la fila 5 y esa arista desaparece en silencio, lo que significa un valor cacheado obsoleto en un informe enviado en lugar de uno lento. La consulta es en realidad de dos caras — ancla en o antes de Row2, salida que alcanza al menos Row1 — y un único orden de ordenación no puede responder a las dos mitades. Los resultados multicelda también aparecen en workbooks modernos, y el artículo sobre fórmulas spill de dynamic array cubre cómo se comportan los rangos spilled en HotXLS

Un segment tree de filas de salida máximas

HotXLS conserva el orden por ancla para el límite superior y añade un segment tree aumentado para el límite inferior. BuildNodeIndex ordena FNodeOrder por clave de nodo como antes, y después BuildMaxOutRowTree llena FNodeMaxOutRow2 (reservado a cuatro entradas por nodo) con el mayor OutRow2 encontrado bajo cada subárbol. QueryNodeTree solo desciende 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 pasan igualmente por el test completo de RangeIntersectsOutput, así que los tramos de hoja y las columnas se comprueban exactamente como antes

// TXLSDepGraph.BuildNodeIndex / BuildEdges desde 2.383.1 (condensado sin grandes cambios)
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 antiguo
end;

La recursión izquierda-antes-que-derecha no es una elección de estilo. Las hojas supervivientes se visitan exactamente en el orden en que las visitaba el viejo bucle while, así que los arrays Dependents y Precedents se rellenan en la misma secuencia y el orden topológico sigue siendo determinista. Lo mismo vale para las dos clases de aristas: una arista dura registrada primero sigue suprimiendo una posterior arista LookupScan del mismo par, mientras que una arista de escaneo registrada antes que una dura conserva su puesto — la distinción que evita que los rangos de lookup produzcan referencias circulares falsas. Por referencia, el coste baja del tamaño de la ventana a O((k + 1) log n), donde k es el número de fórmulas cuya salida alcanza de verdad las filas referenciadas

¿Qué garantiza el índice de salidas 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 última construcción, así que la afirmación es medible y no retórica. El test de regresión EdgeBuildDeepChainsCheckOneCandidatePerDependency construye cadenas de referencias puntuales de 1.024 y 100.000 nodos, insertadas en orden inverso para forzar la ordenación espacial, y aserta exactamente N − 1 comprobaciones — 99.999 para la cadena larga — más el orden de precedente, dependiente y topológico esperado para cada nodo. Tests acompañantes cubren raíces array insertadas desordenadas a través de tramos de hojas, referencias duras y de lookup-scan duplicadas (10 comprobaciones, con las reglas de supresión de arriba), y una reconstrucción tras AddNode, que limpia el flag de ordenación de modo que el siguiente 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

La traza Win32 anterior al fix, conservada 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 ejecuciones focalizadas en serie 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ó ninguna línea base Win64 anterior al fix, así que no se reclama aceleración en Win64. Las mismas ejecuciones pasaron la puerta 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 de su carga, así que reproduce la carga de trabajo en tu 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 salidas?

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

• Los fallos por columna se siguen pagando en las hojas: las 2.626 fórmulas que llenan A100:Z200 llegan todas a la fila 100, así que una referencia a AA100:AA200 las prueba una a una antes de rechazarlas
• Las referencias anchas, como los rangos de columna entera, tienen de verdad muchos precedentes; el índice elimina comprobaciones 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 al test 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 una reordenación O(n log n) completa más una construcción de árbol O(n) en la siguiente construcción de aristas

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

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 informe crecían de forma cuadrática en búsquedas de nombres. El índice de nombres con ámbito guarda ahora una pista de sufijo por nombre base y por ámbito, y recompueba el último candidato devuelto, porque quien llama puede no llegar a añadirlo; borrar, renombrar o cambiar de ámbito 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 búsquedas de candidatos y cuatro nombres base alternantes necesitan 5.039, mientras que los mínimos del benchmark de informes bajaron de unos 240 ms a 18–20 ms. La propia puerta de tiempos de bandas de informe sigue sin ser estable — tres de seis ejecuciones superaron su ratio de 1,05 en el primer intento tras el fix — y el historial de rendimiento mantiene esos fallos registrados en lugar de retocar el umbral hasta que pase

Si tu aplicación Delphi o C++Builder genera o recalcula workbooks de Excel grandes, el componente Excel HotXLS para Delphi y C++Builder incluye este grafo de dependencias indexado en su motor de recálculo para sus dos clases de workbook, la clásica y la XLSX