Profiling de Desempenho no PDFlibPas: Índices Hash em Delphi

O PDFlibPas, a biblioteca de PDF da losLab para Delphi e C++Builder, acelera seus caminhos de renderização e geração de conteúdo substituindo quatro padrões de trabalho repetido por amortizados: um índice hash preguiçoso para buscas de chave de dicionário, uma tabela de consulta de gama sRGB pré-computada, agrupamento por primeiro byte para despacho de operador de content stream, e TStringBuilder no lugar de concatenação repetida de string. Nenhuma das quatro veio de uma descoberta dramática única — vieram do mesmo padrão nada glamouroso em um profile: uma função pequena chamada uma vez por operador, uma vez por pixel, ou uma vez por caractere, onde um custo linear dentro da chamada vira quadrático ou quase quadrático ao longo de um documento inteiro. Esse é o fio condutor aqui: quatro correções pequenas, de aparência não relacionada, que atacam a mesma forma de problema, mais os limites honestos de cada uma

Onde um renderizador de content stream de fato gasta seu tempo

O renderizador de content stream do PDFlibPas canaliza quase todo seu custo por token através de quatro pontos estreitos: buscas de dicionário de recurso em /Resources, /ColorSpace, /Font, e /ExtGState; correção de gama em cada pixel decodificado de uma imagem Lab, Indexed, ou marcada com ICC; casamento de nome de operador em cada token de cada content stream; e construção de string onde quer que a biblioteca construa saída — escape de string literal no salvamento, exportação XFDF, expansão de token de carimbo e variável. Cada uma das quatro faz uma pequena quantidade de trabalho por si só, e cada uma roda milhares ou milhões de vezes ao longo de um documento realista, que é exatamente a forma de função onde um detalhe de implementação O(n) ou O(n²) para de ser invisível e vira a entrada principal do profile

Por que buscas de dicionário de recurso ficam lentas em um PDF grande?

TPDFDictionary.FindIndexByKeyName é o que o renderizador chama para resolver toda busca de /Resources, /ColorSpace, /Font, e /ExtGState, e costumava percorrer o array Entries do início a cada chamada — tranquilo para um dicionário Resources de três entradas, caro para um Form XObject ou uma página pesada em ExtGState onde o mesmo dicionário é sondado a cada operador que toca cor ou estado gráfico. O PDFlibPas agora constrói um índice hash preguiçoso assim que um dicionário passa de DICT_HASH_THRESHOLD (16) entradas e deixa dicionários menores na varredura linear, já que a maioria dos dicionários de PDF nunca fica tão grande e uma tabela hash para três chaves custaria mais para construir do que economiza. O índice é uma tabela plana de endereçamento aberto indexada por PLAnsiStringHash, um hash FNV-1a com a base de deslocamento canônica 2166136261 e primo 16777619, escolhido para evitar puxar System.Generics.Collections para algo tão sensível a tamanho

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;

O índice é invalidado, em vez de mantido incrementalmente: toda chamada que muta — AddEntry, DeleteEntryByKeyName, Assign, AddDict — limpa o hash e deixa a próxima busca reconstruí-lo do zero. Isso parece um desperdício até você perceber que uma chave de dicionário é um objeto TPDFName, e TPDFName.SetTo pode renomear uma chave já sentada no array Entries de um dicionário sem passar por nenhum dos métodos próprios do dicionário — um índice incremental não tem como observar essa renomeação, enquanto um preguiçoso apenas reconstrói e permanece correto por construção. O preço dessa segurança é uma reconstrução O(n) na primeira vez que um dicionário grande é consultado depois de uma escrita, mais a memória para a própria tabela hash, aproximadamente um Integer por slot em um fator de carga de dois terços — um erro de arredondamento para o punhado de dicionários superdimensionados em um documento típico, e um custo real que o PDFlibPas evita pagar em cada um pequeno mantendo o limiar onde está

Pré-computando gama sRGB em vez de chamar Power por pixel

TPDFSimpleColorManager.XYZ2RGB aplica a função de transferência sRGB a cada pixel decodificado de uma imagem Lab, Indexed, ou baseada em ICC — 1.055 * Power(x, 1/2.4) - 0.055 acima do limiar de segmento linear — e Power(x, y) para um y fracionário não tem forma fechada barata na RTL Pascal: se decompõe em Ln(x) depois Exp(y * Ln(x)), e esse par de chamadas transcendentais, rodado três vezes por pixel para os canais vermelho, verde e azul, é o custo dominante de decodificar um pixel de imagem Lab ou ICC pixel a pixel. O PDFlibPas substitui as três chamadas Power por pixel por uma busca em GSRGBGammaLUT, um array Double de 4096 entradas construído uma vez via EnsureSRGBGammaLUT e indexado arredondando a entrada limitada para o slot mais próximo

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;

Uma tabela de 4096 slots sobre a faixa de entrada [0, 1] dá aproximadamente dezesseis vezes a resolução de um canal de saída de 8 bits, de modo que a quantização que a LUT introduz fica abaixo do que o byte RGB final consegue representar — a busca em tabela substitui matemática transcendental aqui sem um custo de precisão visível. O mesmo raciocínio aparece ao lado dela em Lab2XYZ, onde Power(LMN[i], 3) virou um simples LMN[i]*LMN[i]*LMN[i]: uma potência inteira não precisa de Ln/Exp para começo de conversa, então essa não é uma compensação de LUT de forma alguma, apenas uma chamada Power redundante removida. O truque da LUT só se paga porque a função de transferência é uma função pura de um único Double — não se estenderia de forma limpa a uma transformação de cor que dependesse de vários valores de pixel ou de mais estado que isso

Como você despacha 73 operadores de content stream rápido?

ContentOperatorFromName é chamado uma vez para cada token que o PDFlibPas lê de um content stream, casando-o contra o conjunto completo de 73 operadores da Tabela 51 da ISO 32000-1 — de w e q até os raramente vistos operadores de métrica de glifo Tipo 3 d0 e d1 — e costumava percorrer essa lista linearmente em cada token único, de modo que uma página com alguns milhares de operadores significava alguns milhares de varreduras lineares sobre a mesma tabela de 73 entradas. O PDFlibPas agora agrupa a tabela pelo primeiro byte do operador na inicialização, em um array fixo indexado por AnsiChar de slots, de modo que uma busca vira um índice de array mais uma varredura apenas do punhado de operadores que compartilham aquele primeiro caractere

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;

Operadores de PDF diferenciam maiúsculas de minúsculas — w e W, f e F, sc e SC são todos operadores diferentes — de modo que GOpBuckets usa o byte bruto como chave e a comparação residual dentro de um bucket é uma simples igualdade de AnsiString sensível a maiúsculas/minúsculas. O array é dimensionado em 16 slots por letra, o que cobre confortavelmente a tabela de hoje — o bucket mais ocupado, T, contém treze operadores, já que quase todo operador de estado de texto e posicionamento de texto começa com ele — mas EnsureOpBuckets silenciosamente para de adicionar a um bucket assim que sua contagem atinge 16, de modo que um bucket que algum dia precisasse de uma décima quarta entrada falharia silenciosamente, em vez de ruidosamente: o operador se resolveria para coUnknown sem nenhuma exceção apontando por quê. Esse é o custo de manutenção de trocar uma estrutura de dados que degrada graciosamente por uma que não: ela despacha mais rápido porque nunca precisa de um crescimento com verificação de limite, e precisa de um humano observando o único bucket próximo de seu teto

Cortando O(n²) da construção de string

O padrão Result := Result + Fragment do Pascal realoca e copia toda a string acumulada a cada iteração, de modo que construir uma saída de N caracteres um fragmento por vez custa O(n²) em vez de O(n) — fácil de perder na revisão, já que cada linha parece um append barato, e caro na prática porque PLDirectEscapeLiteralString roda em toda string literal de PDF escrita durante o salvamento e XFDFXMLEscape roda em todo valor de campo exportado para XFDF. O PDFlibPas corrige os dois com técnicas diferentes, escolhidas pelo que cada função consegue prever de antemão. PLDirectEscapeLiteralString sabe o comprimento de sua saída antes de escrever um único byte — uma passada classifica cada caractere como simples ou escapado e soma o total, SetLength aloca uma vez, e uma segunda passada preenche o buffer por índice. XFDFXMLEscape não consegue prever facilmente o comprimento de sua saída, já que texto de campo Unicode varia demais para pré-computar, de modo que faz append em um TStringBuilder pré-dimensionado para aproximadamente o comprimento da entrada, em vez disso

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('&');
        '<':  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;

A escolha entre as duas é realmente sobre o que você sabe antes de o loop começar. Contar-depois-preencher é a mais rápida das duas quando o tamanho da saída é barato de calcular, já que faz zero realocações e nenhuma contabilidade além de um contador Integer, mas significa escrever a lógica de classificação duas vezes — uma vez para contar, uma vez para emitir — que é seu próprio risco de manutenção se as duas cópias divergirem. TStringBuilder abre mão de um pouco desse pico de throughput em troca de escrever a lógica uma vez e obter appends amortizados de O(1) a partir de crescimento geométrico de buffer, que é o padrão mais seguro sempre que o tamanho da saída não é fácil de saber de antemão

Onde esse padrão se aplica, e onde não

Todas as quatro correções acima são instâncias de uma única ideia: encontre a chamada que roda uma vez por unidade de entrada — por chave de dicionário, por pixel, por token de operador, por caractere — e substitua seu custo linear ou imprevisível por uma tabela pré-computada, um índice hash, ou um buffer pré-dimensionado. Nada disso é específico de PDF; um serviço Delphi que resolve a mesma chave de busca milhares de vezes por requisição, converte valores em um loop apertado, despacha em um vocabulário fixo de tokens, ou constrói strings longas um caractere de cada vez atinge as mesmas formas de falha e recebe as mesmas correções. O que nenhuma dessas quatro mudanças toca é concorrência ou pegada de memória: uma busca de dicionário single-thread mais rápida não faz nada por duas threads competindo pela mesma instância de TPDFlib, que é um problema estrutural coberto separadamente em o artigo sobre segurança de thread em renderização paralela de página, e não faz nada por um PDF grande demais para carregar em memória como uma árvore de objetos de forma alguma, que é para o que a camada Direct Access no PDFlibPas serve, coberta em o artigo sobre mesclar e dividir PDFs de gigabytes

O código de dicionário, gerenciamento de cor, despacho de content stream, e construção de string discutido aqui vem como parte do PDFlibPas padrão, a biblioteca de PDF da losLab para Delphi e C++Builder, sem nenhuma configuração extra necessária para obter qualquer uma dessas