LlosLab Software Development BlogNotas de ingeniería para desarrolladores de software de PDF, Delphi y documentos.

Artículo técnico

Perfilado de rendimiento de PDFlibPas: índices hash en Delphi

Delphi PDF Library

PDFlibPas, la biblioteca PDF de losLab para Delphi y C++Builder, acelera sus rutas de renderizado y generación de contenido reemplazando cuatro patrones de trabajo repetido por otros amortizados: un índice hash perezoso para búsquedas de clave de diccionario, una tabla de búsqueda de gamma sRGB precalculada, agrupamiento por primer byte para el despacho de operador de flujo de contenido, y TStringBuilder en lugar de concatenación de cadenas repetida. Ninguno de los cuatro vino de un descubrimiento dramático único —vinieron del mismo patrón poco glamoroso 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 costo lineal dentro de la llamada se vuelve cuadrático o casi cuadrático a través de todo un documento. Ese es el hilo conductor aquí: cuatro correcciones pequeñas, de apariencia no relacionada, que atacan la misma forma de problema, más los límites honestos de cada una

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

El renderizador de flujo de contenido de PDFlibPas canaliza casi todo su costo 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 dondequiera que la biblioteca construya salida —escapado de cadena literal al guardar, exportación XFDF, expansión de token 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 sobre 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 superior 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 arreglo Entries desde el frente en cada llamada —bien para un diccionario Resources de tres entradas, costoso para un Form XObject o una página con mucho 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 se ve derrochador hasta que se nota que una clave de diccionario es un objeto TPDFName, y TPDFName.SetTo puede renombrar una clave ya sentada en el arreglo 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 después de 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 costo real que PDFlibPas evita pagar en cada diccionario pequeño manteniendo el umbral donde está

Precalcular 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 de segmento lineal— y Power(x, y) para un y fraccionario no tiene una forma cerrada barata en el 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 costo dominante de decodificar un píxel de imagen Lab o ICC uno por uno. PDFlibPas reemplaza las tres llamadas Power por píxel con una búsqueda en GSRGBGammaLUT, un arreglo 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 reemplaza aquí la matemática trascendental sin un costo 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 tipo LUT, solo una llamada Power redundante eliminada. El truco de la LUT solo rinde porque la función de transferencia es una función pura de un único Double —no se extendería limpiamente 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 raramente vistos operadores de métrica de glifo Tipo 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 inicio, en un arreglo fijo indexado por AnsiChar de ranuras, así que una búsqueda se convierte en un índice de arreglo 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 crudo y la comparación residual dentro de un bucket es una simple igualdad de AnsiString que distingue mayúsculas de minúsculas. El arreglo está dimensionado en 16 ranuras por letra, que cubre cómodamente la tabla actual —el bucket más ocupado, T, contiene trece operadores, ya que casi cada operador de estado de texto y posicionamiento de texto empieza con ella— pero EnsureOpBuckets deja silenciosamente de agregar a un bucket en cuanto su conteo llega a 16, así que un bucket que alguna vez necesitara una decimocuarta entrada fallaría silenciosamente en lugar de ruidosamente: el operador se resolvería a coUnknown sin ninguna excepción que apunte a por qué. Ese es el costo de mantenimiento de cambiar una estructura de datos que se degrada con gracia 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 un humano vigilando el único bucket cerca de su techo

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

El patrón Result := Result + Fragment de Pascal reasigna y copia toda la cadena acumulada en cada iteración, así que construir una salida de N caracteres un fragmento a la vez cuesta O(n²) en lugar de O(n) —fácil de pasar por alto en revisión, ya que cada línea parece un anexado barato, y costoso en la práctica porque PLDirectEscapeLiteralString se ejecuta en cada cadena literal de PDF escrita durante el guardado y XFDFXMLEscape se ejecuta en cada valor de campo exportado a XFDF. PDFlibPas corrige los dos con técnicas distintas, elegidas según lo que cada función puede predecir de antemano. PLDirectEscapeLiteralString conoce su longitud de salida antes de escribir un solo byte —una pasada clasifica cada carácter como plano o escapado y suma el total, SetLength asigna una vez, y una segunda pasada llena el búfer por índice. XFDFXMLEscape no puede predecir barato su longitud de salida, ya que el texto de campo Unicode varía demasiado como para precalcularse, así que en su lugar anexa 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 los dos en realidad es sobre qué se sabe antes de que empiece el bucle. Contar-y-luego-llenar es el más rápido de los dos cuando el tamaño de salida es barato de calcular, ya que hace cero reasignaciones y ninguna contabilidad más allá de un contador Integer, pero significa escribir la lógica de clasificación dos veces —una para contar, una 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 vez y obtener anexados O(1) amortizados por el crecimiento geométrico del búfer, que es el valor predeterminado más seguro cada vez que el tamaño de salida no es fácil de conocer de antemano

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

Las cuatro correcciones 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 reemplazar su costo 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 cerrado, despacha sobre un vocabulario fijo de tokens, o construye cadenas largas un carácter a la vez se topa con las mismas formas de fallo y toma las mismas correcciones. Lo que ninguno de estos cuatro cambios toca es la concurrencia o la huella de memoria: una búsqueda de diccionario de un solo hilo más rápida no hace nada por dos hilos compitiendo en la misma instancia de TPDFlib, que es un problema estructural cubierto por separado en el artículo sobre seguridad de hilos en el renderizado paralelo de páginas, 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 Acceso Directo 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 discutido aquí se incluye como 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