LBlogue de Desenvolvimento de Software losLabNotas de engenharia para programadores de PDF, Delphi e software de documentos.

Artigo Técnico

Perfilamento de Desempenho do PDFlibPas: Índices de Hash em Delphi

Delphi PDF Library

O PDFlibPas, a biblioteca de PDF da losLab para Delphi e C++Builder, acelera os seus caminhos de renderização e de geração de conteúdo substituindo quatro padrões de trabalho repetido por outros amortizados: um índice de hash preguiçoso para pesquisas de chaves de dicionário, uma tabela de consulta de gama sRGB pré-calculada, agrupamento pelo primeiro byte para o despacho de operadores de fluxo de conteúdo, e TStringBuilder em vez de concatenação repetida de texto. Nenhum dos quatro veio de uma descoberta dramática isolada — vieram do mesmo padrão pouco glamoroso num perfil: uma pequena função chamada uma vez por operador, uma vez por pixel, ou uma vez por carácter, onde um custo linear dentro da chamada se torna quadrático ou quase quadrático ao longo de um documento inteiro. É esse o fio condutor aqui: quatro correções pequenas, aparentemente sem relação entre si, que atacam a mesma forma de problema, mais os limites honestos de cada uma

Onde é que um renderizador de fluxo de conteúdo efetivamente gasta o seu tempo

O renderizador de fluxo de conteúdo do PDFlibPas canaliza quase todo o seu custo por token através de quatro pontos restritos: pesquisas de dicionário de recursos em /Resources, /ColorSpace, /Font, e /ExtGState; correção de gama em cada pixel descodificado de uma imagem Lab, Indexed, ou com etiqueta ICC; correspondência de nome de operador em cada token de cada fluxo de conteúdo; e construção de texto onde quer que a biblioteca produza saída — escape de cadeias literais na gravação, exportação XFDF, expansão de tokens de carimbo e variáveis. Cada um dos quatro faz uma pequena quantidade de trabalho por si só, e cada um corre milhares ou milhões de vezes ao longo de um documento realista, exatamente a forma de função onde um detalhe de implementação O(n) ou O(n²) deixa de ser invisível e passa a ser a entrada de topo do perfil

Porque é que as pesquisas de dicionário de recursos ficam lentas num PDF grande?

O TPDFDictionary.FindIndexByKeyName é o que o renderizador chama para resolver cada pesquisa de /Resources, /ColorSpace, /Font, e /ExtGState, e costumava percorrer o array Entries desde o início em cada chamada — aceitável para um dicionário Resources de três entradas, dispendioso para um Form XObject ou uma página carregada de ExtGState onde o mesmo dicionário é sondado em cada operador que toque cor ou estado gráfico. O PDFlibPas agora constrói um índice de hash preguiçoso assim que um dicionário ultrapassa DICT_HASH_THRESHOLD (16) entradas e deixa os dicionários mais pequenos no varrimento linear, já que a maioria dos dicionários de PDF nunca chega a esse tamanho e uma tabela de hash para três chaves custaria mais a construir do que pouparia. O índice é uma tabela plana de endereçamento aberto indexada por PLAnsiStringHash, um hash FNV-1a com a base de offset canónica 2166136261 e o primo 16777619, escolhido para evitar trazer System.Generics.Collections para algo tão sensível ao 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: cada chamada que altera o dicionário — AddEntry, DeleteEntryByKeyName, Assign, AddDict — limpa o hash e deixa a próxima pesquisa reconstruí-lo do zero. Isso parece um desperdício até se reparar que uma chave de dicionário é um objeto TPDFName, e o TPDFName.SetTo consegue renomear uma chave já presente 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 forma de observar essa renomeação, enquanto um preguiçoso simplesmente reconstrói e mantém-se 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 de hash, aproximadamente um Integer por posição com um fator de carga de dois terços — um erro de arredondamento para o punhado de dicionários sobredimensionados de um documento típico, e um custo real que o PDFlibPas evita pagar em cada dicionário pequeno mantendo o limiar onde está

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

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

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 posições sobre o intervalo de entrada [0, 1] dá aproximadamente dezasseis vezes a resolução de um canal de saída de 8 bits, pelo que a quantização que a LUT introduz fica abaixo do que o byte RGB final consegue representar — a pesquisa em tabela substitui aqui matemática transcendental sem qualquer custo de precisão visível. O mesmo raciocínio surge logo ao lado em Lab2XYZ, onde Power(LMN[i], 3) se tornou um simples LMN[i]*LMN[i]*LMN[i]: uma potência inteira nem sequer precisa de Ln/Exp à partida, pelo que essa nem é uma troca por LUT, apenas uma chamada Power redundante removida. O truque da LUT só compensa 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 do que isso

Como despachar 73 operadores de fluxo de conteúdo rapidamente?

O ContentOperatorFromName é chamado uma vez para cada token que o PDFlibPas lê de um fluxo de conteúdo, comparando-o com o conjunto completo de 73 operadores da Tabela 51 da ISO 32000-1 — de w e q até aos raramente vistos operadores de métricas de glifo Type 3 d0 e d1 — e costumava percorrer essa lista linearmente em cada token, pelo que uma página com alguns milhares de operadores significava alguns milhares de varrimentos lineares sobre a mesma tabela de 73 entradas. O PDFlibPas agora agrupa a tabela pelo primeiro byte do operador no arranque, num array fixo indexado por AnsiChar, pelo que uma pesquisa se torna um índice de array mais um varrimento apenas do punhado de operadores que partilham esse primeiro 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;

Os operadores de PDF são sensíveis a maiúsculas/minúsculas — w e W, f e F, sc e SC são todos operadores diferentes — pelo que GOpBuckets indexa pelo byte em bruto e a comparação residual dentro de um agrupamento é uma simples igualdade de AnsiString sensível a maiúsculas/minúsculas. O array tem 16 posições por letra, o que cobre confortavelmente a tabela atual — o agrupamento mais ocupado, T, contém treze operadores, já que quase todos os operadores de estado de texto e de posicionamento de texto começam por essa letra — mas o EnsureOpBuckets para silenciosamente de acrescentar a um agrupamento assim que a sua contagem atinja 16, pelo que um agrupamento que alguma vez precisasse de uma décima quarta entrada falharia silenciosamente em vez de ruidosamente: o operador resolver-se-ia para coUnknown sem qualquer exceção a apontar a razão. Esse é o custo de manutenção de trocar uma estrutura de dados que degrada com elegância por uma que não o faz — despacha mais depressa porque nunca precisa de um crescimento com verificação de limites, e precisa de um humano a vigiar o único agrupamento perto do seu teto

Eliminar O(n²) da construção de texto

O padrão Result := Result + Fragment do Pascal realoca e copia toda a cadeia de texto acumulada em cada iteração, pelo que construir uma saída de N caracteres um fragmento de cada vez custa O(n²) em vez de O(n) — fácil de passar despercebido numa revisão, já que cada linha parece um acréscimo barato, e dispendioso na prática porque PLDirectEscapeLiteralString corre em cada cadeia literal de PDF escrita durante a gravação e XFDFXMLEscape corre em cada valor de campo exportado para XFDF. O PDFlibPas corrige os dois com técnicas diferentes, escolhidas em função do que cada função consegue prever antecipadamente. O PLDirectEscapeLiteralString conhece o comprimento da sua saída antes de escrever um único byte — uma passagem classifica cada carácter como simples ou com escape e soma o total, o SetLength aloca uma vez, e uma segunda passagem preenche o buffer por índice. O XFDFXMLEscape não consegue prever barato o comprimento da sua saída, já que o texto de campo Unicode varia demasiado para se pré-calcular, pelo que acrescenta antes a um TStringBuilder pré-dimensionado aproximadamente para o comprimento da 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;

A escolha entre as duas é, na realidade, sobre o que se sabe antes de o ciclo começar. Contar-depois-preencher é a mais rápida das duas quando o tamanho da saída é barato de calcular, já que não faz qualquer realocação e nenhuma contabilidade além de um contador Integer, mas significa escrever a lógica de classificação duas vezes — uma para contar, outra para produzir — o que é, por si só, um risco de manutenção se as duas cópias divergirem. O TStringBuilder abdica de algum desse desempenho de pico em troca de escrever a lógica uma única vez e obter acréscimos O(1) amortizados a partir do crescimento geométrico do buffer, a opção mais segura por predefinição sempre que o tamanho da saída não é fácil de conhecer antecipadamente

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

As quatro correções acima são instâncias de uma única ideia: encontrar a chamada que corre uma vez por unidade de entrada — por chave de dicionário, por pixel, por token de operador, por carácter — e substituir o seu custo linear ou imprevisível por uma tabela pré-calculada, um índice de hash, ou um buffer pré-dimensionado. Nada disto é específico do PDF; um serviço em Delphi que resolva a mesma chave de pesquisa milhares de vezes por pedido, converta valores num ciclo apertado, despache sobre um vocabulário fixo de tokens, ou construa longas cadeias de texto um carácter de cada vez, esbarra nas mesmas formas de falha e leva às mesmas correções. O que nenhuma destas quatro alterações toca é a concorrência ou a pegada de memória: uma pesquisa de dicionário mais rápida numa única thread não faz nada por duas threads em corrida sobre a mesma instância de TPDFlib, um problema estrutural abordado separadamente em o artigo sobre segurança de threads na renderização paralela de páginas, e não faz nada por um PDF demasiado grande para carregar como uma árvore de objetos em memória de todo, para o qual serve a camada de Acesso Direto no PDFlibPas, abordada em o artigo sobre fundir e dividir PDFs de gigabytes

O código de dicionário, de gestão de cor, de despacho de fluxo de conteúdo, e de construção de texto aqui discutido faz parte do PDFlibPas padrão, a biblioteca de PDF da losLab para Delphi e C++Builder, sem qualquer configuração extra necessária para o obter