LlosLab Software Development BlogNotas técnicas sobre PDF, Delphi y software documental para desarrolladores

Artículo técnico

Perfilado de rendimiento en PDFlibPas: índices hash en Delphi

Delphi PDF Library

PDFlibPas, la biblioteca PDF de losLab para Delphi y C++Builder, acelera sus vías de renderizado y generación de contenido sustituyendo cuatro patrones de trabajo repetido por otros amortizados: un índice hash perezoso para las búsquedas de clave de diccionario, una tabla de búsqueda de gamma sRGB precalculada, una agrupación por primer byte para el despacho de operadores de flujo de contenido, y TStringBuilder en lugar de concatenación de cadenas repetida. Ninguna de las cuatro surgió de un único descubrimiento dramático, todas surgieron del mismo patrón poco glamuroso en un perfil: una función pequeña llamada una vez por operador, una vez por píxel, o una vez por carácter, donde un coste lineal dentro de la llamada se convierte en cuadrático o casi cuadrático a lo largo de todo un documento. Ese es el hilo conductor aquí: cuatro soluciones pequeñas y de aspecto no relacionado que atacan la misma forma de problema, más los límites honestos de cada una

Dónde emplea realmente su tiempo un renderizador de flujo de contenido

El renderizador de flujo de contenido de PDFlibPas canaliza casi todo su coste por token a través de cuatro puntos estrechos: búsquedas de diccionario de recursos en /Resources, /ColorSpace, /Font y /ExtGState; corrección de gamma en cada píxel decodificado de una imagen Lab, Indexed o etiquetada con ICC; comparación de nombre de operador en cada token de cada flujo de contenido; y construcción de cadenas en cualquier lugar donde la biblioteca genera salida, escape de cadenas literales al guardar, exportación XFDF, expansión de tokens de sello y variable. Cada uno de los cuatro hace una pequeña cantidad de trabajo por sí solo, y cada uno se ejecuta miles o millones de veces en un documento realista, que es exactamente la forma de función donde un detalle de implementación O(n) u O(n²) deja de ser invisible y empieza a ser la entrada principal del perfil

¿Por qué se vuelven lentas las búsquedas de diccionario de recursos en un PDF grande?

TPDFDictionary.FindIndexByKeyName es lo que llama el renderizador para resolver cada búsqueda de /Resources, /ColorSpace, /Font y /ExtGState, y solía recorrer el array Entries desde el principio en cada llamada, algo correcto para un diccionario Resources de tres entradas, costoso para un Form XObject o una página cargada de ExtGState donde se sondea el mismo diccionario en cada operador que toca color o estado gráfico. PDFlibPas ahora construye un índice hash perezoso en cuanto un diccionario supera DICT_HASH_THRESHOLD (16) entradas y deja los diccionarios más pequeños en el escaneo lineal, ya que la mayoría de los diccionarios PDF nunca llegan a ser tan grandes y una tabla hash para tres claves costaría más construirla de lo que ahorra. El índice es una tabla plana de direccionamiento abierto indexada por PLAnsiStringHash, un hash FNV-1a con la base de desplazamiento canónica 2166136261 y el primo 16777619, elegido para evitar traer System.Generics.Collections para algo tan sensible al tamaño

Const
  DICT_HASH_THRESHOLD = 16;

Function TPDFDictionary.LookupKeyIndex(Const Key: AnsiString): Integer;
Var
  H, Probe: Integer;
Begin
  Result:= -1;
  If FKeyHashMask= 0 Then
  Begin
    // Not built yet; small dictionaries stay linear since the
    // build cost would not amortize over a handful of entries.
    If Length(Entries)> DICT_HASH_THRESHOLD Then
      BuildKeyHash
    Else
      Exit;
  End;
  H:= PLAnsiStringHash(Key) And FKeyHashMask;
  Probe:= 1;
  While FKeyHash[H]<> -1 Do
  Begin
    If Entries[FKeyHash[H]].Key.Name= Key Then
    Begin
      Result:= FKeyHash[H];
      Exit;
    End;
    H:= (H+ Probe) And FKeyHashMask;
    Inc(Probe);
  End;
End;

El índice se invalida en lugar de mantenerse incrementalmente: cada llamada que muta, AddEntry, DeleteEntryByKeyName, Assign, AddDict, limpia el hash y deja que la siguiente búsqueda lo reconstruya desde cero. Eso parece derrochador hasta que notáis que una clave de diccionario es un objeto TPDFName, y TPDFName.SetTo puede renombrar una clave ya alojada en el array Entries de un diccionario sin pasar por ninguno de los propios métodos del diccionario, un índice incremental no tiene forma de observar ese renombrado, mientras que uno perezoso simplemente se reconstruye y permanece correcto por construcción. El precio de esa seguridad es una reconstrucción O(n) la primera vez que se consulta un diccionario grande tras una escritura, más la memoria para la propia tabla hash, aproximadamente un Integer por ranura a un factor de carga de dos tercios, un error de redondeo para el puñado de diccionarios sobredimensionados en un documento típico, y un coste real que PDFlibPas evita pagar en cada diccionario pequeño manteniendo el umbral donde está

Precalcular la gamma sRGB en lugar de llamar a Power por píxel

TPDFSimpleColorManager.XYZ2RGB aplica la función de transferencia sRGB a cada píxel decodificado de una imagen Lab, Indexed o basada en ICC, 1.055 * Power(x, 1/2.4) - 0.055 por encima del umbral del segmento lineal, y Power(x, y) para un y fraccionario no tiene una forma cerrada barata en la RTL de Pascal: se descompone en Ln(x) y luego Exp(y * Ln(x)), y ese par de llamadas trascendentales, ejecutado tres veces por píxel para los canales rojo, verde y azul, es el coste dominante de decodificar una imagen Lab o ICC píxel a píxel. PDFlibPas sustituye las tres llamadas Power por píxel por una única búsqueda en GSRGBGammaLUT, un array Double de 4096 entradas construido una vez mediante EnsureSRGBGammaLUT e indexado redondeando la entrada acotada a la ranura más cercana

Const
  SRGB_GAMMA_LUT_SIZE = 4096;
Var
  GSRGBGammaLUT: Array [0..SRGB_GAMMA_LUT_SIZE- 1] Of Double;
  GSRGBGammaLUTReady: Boolean= False;

Procedure EnsureSRGBGammaLUT;
Var
  I: Integer;
  X: Double;
Begin
  If GSRGBGammaLUTReady Then
    Exit;
  For I:= 0 To SRGB_GAMMA_LUT_SIZE- 1 Do
  Begin
    X:= I/ SRGB_GAMMA_LUT_SIZE;
    If X> 0.0031308 Then
      GSRGBGammaLUT[I]:= 1.055* Power(X, 1/ 2.4)- 0.055
    Else
      GSRGBGammaLUT[I]:= 12.92* X;
  End;
  GSRGBGammaLUTReady:= True;
End;

Function SRGBGamma(X: Double): Double;
Var
  Idx: Integer;
Begin
  If X<= 0 Then
    Result:= 0
  Else If X>= 1 Then
    Result:= 1
  Else
  Begin
    Idx:= Round(X* SRGB_GAMMA_LUT_SIZE);
    If Idx> SRGB_GAMMA_LUT_SIZE- 1 Then
      Idx:= SRGB_GAMMA_LUT_SIZE- 1;
    Result:= GSRGBGammaLUT[Idx];
  End;
End;

Una tabla de 4096 ranuras sobre el rango de entrada [0, 1] da aproximadamente dieciséis veces la resolución de un canal de salida de 8 bits, así que la cuantización que introduce la LUT se sitúa por debajo de lo que puede representar el byte RGB final, la búsqueda en tabla sustituye aquí a la aritmética trascendental sin un coste de precisión visible. El mismo razonamiento aparece justo al lado en Lab2XYZ, donde Power(LMN[i], 3) se convirtió en un simple LMN[i]*LMN[i]*LMN[i]: una potencia entera de entrada no necesita Ln/Exp en primer lugar, así que esa no es en absoluto una compensación de LUT, solo una llamada Power redundante eliminada. El truco de la LUT solo compensa porque la función de transferencia es una función pura de un único Double, no se extendería con limpieza a una transformación de color que dependiera de varios valores de píxel o de más estado que ese

¿Cómo se despachan rápido 73 operadores de flujo de contenido?

ContentOperatorFromName se llama una vez por cada token que lee PDFlibPas de un flujo de contenido, comparándolo contra el conjunto completo de 73 operadores de la Tabla 51 de ISO 32000-1, desde w y q hasta los rara vez vistos operadores de métricas de glifo Type 3 d0 y d1, y solía recorrer esa lista linealmente en cada token individual, así que una página con unos pocos miles de operadores significaba unos pocos miles de escaneos lineales sobre la misma tabla de 73 entradas. PDFlibPas ahora agrupa la tabla por el primer byte del operador al arrancar, en un array fijo de ranuras indexado por AnsiChar, así que una búsqueda se convierte en un índice de array más un escaneo de solo el puñado de operadores que comparten ese primer carácter

Type
  TOpSlot= Record
    Count: Integer;
    Ops: Array [0..15] Of TPDFContentOperator;
  End;

Var
  GOpBuckets: Array [AnsiChar] Of TOpSlot;
  GBucketsReady: Boolean= False;

Function ContentOperatorFromName(Const Name: AnsiString): TPDFContentOperator;
Var
  Ch: AnsiChar;
  Slot: ^TOpSlot;
  I: Integer;
  Op: TPDFContentOperator;
Begin
  Result:= coUnknown;
  If (Name= '') Then
    Exit;
  EnsureOpBuckets;
  Ch:= Name[1];
  Slot:= @GOpBuckets[Ch];
  If Slot^.Count= 0 Then
    Exit;
  For I:= 0 To Slot^.Count- 1 Do
  Begin
    Op:= Slot^.Ops[I];
    If (PDFContentOpInfo[Op].Name= Name) Then
    Begin
      Result:= Op;
      Exit;
    End;
  End;
End;

Los operadores PDF distinguen mayúsculas de minúsculas, w y W, f y F, sc y SC son todos operadores distintos, así que GOpBuckets indexa por el byte en bruto y la comparación residual dentro de un bucket es una simple igualdad de AnsiString que distingue mayúsculas. El array tiene un tamaño de 16 ranuras por letra, lo que cubre cómodamente la tabla actual, el bucket más ocupado, T, contiene trece operadores, ya que casi todos los operadores de estado de texto y posicionamiento de texto empiezan por ella, pero EnsureOpBuckets deja silenciosamente de añadir a un bucket en cuanto su recuento llega a 16, así que un bucket que alguna vez necesitara una decimocuarta entrada fallaría en silencio en lugar de ruidosamente: el operador se resolvería a coUnknown sin ninguna excepción que señalara por qué. Ese es el coste de mantenimiento de cambiar una estructura de datos que se degrada con elegancia por una que no lo hace, despacha más rápido porque nunca necesita un crecimiento con comprobación de límites, y necesita a una persona vigilando el único bucket cercano a su techo

Eliminar el O(n²) de la construcción de cadenas

El patrón Result := Result + Fragment de Pascal reserva y copia toda la cadena acumulada en cada iteración, así que construir una salida de N caracteres un fragmento cada vez cuesta O(n²) en lugar de O(n), fácil de pasar por alto en una revisión, ya que cada línea parece un añadido barato, y costoso en la práctica porque PLDirectEscapeLiteralString se ejecuta en cada cadena literal PDF escrita durante el guardado y XFDFXMLEscape se ejecuta en cada valor de campo exportado a XFDF. PDFlibPas arregla los dos con técnicas distintas, elegidas según lo que cada función puede predecir por adelantado. PLDirectEscapeLiteralString conoce la longitud de su salida antes de escribir un solo byte, una pasada clasifica cada carácter como plano o escapado y suma el total, SetLength reserva una vez, y una segunda pasada rellena el búfer por índice. XFDFXMLEscape no puede predecir barato la longitud de su salida, ya que el texto de campo Unicode varía demasiado como para precalcularlo, así que en su lugar añade a un TStringBuilder predimensionado aproximadamente a la longitud de entrada

Function XFDFXMLEscape(Const W: WideString): WideString;
Var
  I: Integer;
  Builder: TStringBuilder;
Begin
  // TStringBuilder avoids the O(n^2) WideString concatenation that
  // XFDF export used to hit on every field value
  Builder:= TStringBuilder.Create(Length(W)+ 16);
  Try
    For I:= 1 To Length(W) Do
    Begin
      Case W[I] Of
        '&':  Builder.Append('&amp;');
        '<':  Builder.Append('&lt;');
        '>':  Builder.Append('&gt;');
        // ...'"', tab, CR and LF cases follow the same shape
      Else
        Builder.Append(W[I]);
      End;
    End;
    Result:= Builder.ToString;
  Finally
    Builder.Free;
  End;
End;

La elección entre las dos en realidad depende de qué sepáis antes de que empiece el bucle. Contar-y-luego-rellenar es la más rápida de las dos cuando el tamaño de salida es barato de calcular, ya que no hace ninguna reserva adicional y ninguna contabilidad más allá de un contador Integer, pero significa escribir la lógica de clasificación dos veces, una para contar, otra para emitir, que es su propio riesgo de mantenimiento si las dos copias se desvían entre sí. TStringBuilder renuncia a un poco de ese rendimiento máximo a cambio de escribir la lógica una sola vez y obtener añadidos amortizados O(1) mediante crecimiento geométrico del búfer, que es la opción por defecto más segura siempre que el tamaño de salida no sea fácil de conocer de antemano

Dónde se aplica este patrón, y dónde no

Las cuatro soluciones de arriba son instancias de una idea: encontrar la llamada que se ejecuta una vez por unidad de entrada, por clave de diccionario, por píxel, por token de operador, por carácter, y sustituir su coste lineal o impredecible por una tabla precalculada, un índice hash o un búfer predimensionado. Nada de esto es específico de PDF; un servicio Delphi que resuelve la misma clave de búsqueda miles de veces por solicitud, convierte valores en un bucle ajustado, despacha sobre un vocabulario fijo de tokens, o construye cadenas largas un carácter cada vez se topa con las mismas formas de fallo y admite las mismas soluciones. Lo que ninguno de estos cuatro cambios toca es la concurrencia ni la huella de memoria: una búsqueda de diccionario de un solo hilo más rápida no hace nada por dos hilos compitiendo sobre la misma instancia TPDFlib, que es un problema estructural cubierto por separado en el artículo sobre seguridad de hilos en el renderizado de páginas en paralelo, y no hace nada por un PDF demasiado grande para cargarlo en memoria como un árbol de objetos en absoluto, que es para lo que sirve la capa de Direct Access en PDFlibPas, cubierta en el artículo sobre fusionar y dividir PDF de varios gigabytes

El código de diccionario, gestión de color, despacho de flujo de contenido y construcción de cadenas tratado aquí forma parte del PDFlibPas estándar, la biblioteca PDF de losLab para Delphi y C++Builder, sin necesidad de configuración adicional para obtener nada de esto