LlosLab Software Development BlogPDF, Delphi 및 문서 소프트웨어 개발자를 위한 엔지니어링 노트.

기술 문서

PDFlibPas 성능 프로파일링: Delphi의 해시 인덱스

Delphi PDF Library

Delphi와 C++Builder용 losLab의 PDF 라이브러리인 PDFlibPas는 반복되는 작업 패턴 네 가지를 상각된 패턴으로 대체함으로써 렌더링과 콘텐츠 생성 경로를 빠르게 만든다: 딕셔너리 키 조회를 위한 지연 해시 인덱스, 미리 계산된 sRGB 감마 룩업 테이블, 콘텐츠 스트림 오퍼레이터 디스패치를 위한 첫 바이트 버킷화, 그리고 반복적인 문자열 연결 대신 쓰는 TStringBuilder다. 이 네 가지 모두는 하나의 극적인 발견에서 나온 것이 아니다 — 프로파일 안의 같은 화려하지 않은 패턴에서 나왔다: 오퍼레이터당 한 번, 픽셀당 한 번, 문자당 한 번 호출되는 작은 함수가 있고, 그 호출 안의 선형 비용이 문서 전체에 걸쳐 2차 혹은 거의 2차 비용이 되는 것이다. 이것이 여기서 관통하는 흐름이다: 서로 무관해 보이는 네 가지 작은 수정이 같은 형태의 문제를 공략하며, 각각에는 정직한 한계도 있다

콘텐츠 스트림 렌더러는 실제로 어디에 시간을 쓰는가

PDFlibPas의 콘텐츠 스트림 렌더러는 토큰당 비용의 거의 전부를 네 개의 좁은 지점으로 흘려보낸다: /Resources, /ColorSpace, /Font, /ExtGState에 대한 리소스 딕셔너리 조회; Lab, Indexed, ICC 태그가 붙은 이미지의 모든 디코딩된 픽셀에 대한 감마 보정; 모든 콘텐츠 스트림의 모든 토큰에 대한 오퍼레이터 이름 매칭; 그리고 라이브러리가 출력을 만드는 모든 곳 — 저장 시 리터럴 문자열 이스케이핑, XFDF 내보내기, 스탬프와 변수 토큰 확장 — 에서의 문자열 생성이다. 이 넷 각각은 그 자체로는 적은 양의 작업을 하지만, 각각은 실제 문서에 걸쳐 수천 번 혹은 수백만 번 실행되며, 이것이 정확히 O(n)이나 O(n²) 구현 세부사항이 더 이상 보이지 않는 것을 멈추고 프로파일의 최상단 항목이 되기 시작하는 함수의 형태다

대용량 PDF에서 리소스 딕셔너리 조회는 왜 느려지는가?

TPDFDictionary.FindIndexByKeyName은 렌더러가 모든 /Resources, /ColorSpace, /Font, /ExtGState 조회를 해석하기 위해 호출하는 것이며, 이는 예전에는 매 호출마다 Entries 배열을 앞에서부터 순회했다 — 항목 세 개짜리 Resources 딕셔너리에는 괜찮지만, 색이나 그래픽 상태를 건드리는 모든 오퍼레이터에서 같은 딕셔너리가 조회되는 Form XObject나 ExtGState가 많은 페이지에는 비쌌다. PDFlibPas는 이제 딕셔너리가 DICT_HASH_THRESHOLD(16)개 항목을 넘어서면 지연 해시 인덱스를 한 번 만들고, 그보다 작은 딕셔너리는 선형 스캔에 남겨둔다. 대부분의 PDF 딕셔너리는 그렇게 커지지 않고, 세 개의 키를 위한 해시 테이블은 절약하는 것보다 만드는 비용이 더 들 것이기 때문이다. 이 인덱스는 PLAnsiStringHash를 키로 하는 평면 오픈 어드레싱 테이블로, 표준적인 오프셋 기준 2166136261과 소수 16777619를 쓰는 FNV-1a 해시다. 이 크기에 민감한 용도를 위해 System.Generics.Collections를 끌어오는 것을 피하기 위해 이렇게 선택했다

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;

이 인덱스는 점진적으로 유지되는 대신 무효화된다: AddEntry, DeleteEntryByKeyName, Assign, AddDict 같은 모든 변경 호출은 해시를 지우고 다음 조회가 처음부터 다시 만들도록 둔다. 딕셔너리 키가 TPDFName 객체이고, TPDFName.SetTo가 딕셔너리 자신의 어떤 메서드도 거치지 않고 딕셔너리의 Entries 배열 안에 이미 앉아 있는 키의 이름을 바꿀 수 있다는 것을 알아차리기 전까지는 이것이 낭비처럼 보인다 — 점진적 인덱스는 그 이름 변경을 관찰할 방법이 전혀 없는 반면, 지연 인덱스는 그저 다시 만들어져 구조적으로 올바른 상태를 유지한다. 그 안전성의 대가는 쓰기 이후 대용량 딕셔너리가 처음 조회될 때의 O(n) 재구축과, 해시 테이블 자체를 위한 메모리다. 3분의 2 적재율에서 슬롯당 대략 Integer 하나꼴이다 — 일반적인 문서 안의 몇 안 되는 과도하게 큰 딕셔너리에는 반올림 오차 수준이며, PDFlibPas가 임계값을 지금 그대로 유지함으로써 모든 작은 딕셔너리에서는 지불하지 않는 실제 비용이다

픽셀당 Power를 호출하는 대신 sRGB 감마 미리 계산하기

TPDFSimpleColorManager.XYZ2RGB는 Lab, Indexed, ICC 기반 이미지의 모든 디코딩된 픽셀에 sRGB 전송 함수를 적용한다 — 선형 구간 임계값 위에서는 1.055 * Power(x, 1/2.4) - 0.055 — 그리고 분수 지수 y에 대한 Power(x, y)는 Pascal RTL에 저렴한 닫힌 형식이 없다: 이는 Ln(x)를 거쳐 Exp(y * Ln(x))로 분해되며, 픽셀당 빨강, 초록, 파랑 채널에 대해 세 번씩 실행되는 그 초월함수 호출 쌍이 Lab이나 ICC 이미지를 픽셀 단위로 디코딩하는 지배적인 비용이다. PDFlibPas는 픽셀당 세 번의 Power 호출을 GSRGBGammaLUT에 대한 한 번의 조회로 대체하는데, 이는 EnsureSRGBGammaLUT를 통해 한 번 만들어지고 클램프된 입력을 가장 가까운 슬롯으로 반올림해 인덱싱되는 4096개 항목짜리 Double 배열이다

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;

[0, 1] 입력 범위에 걸친 4096슬롯 테이블은 8비트 출력 채널의 대략 16배 해상도를 제공하므로, 이 룩업 테이블이 도입하는 양자화는 최종 RGB 바이트가 표현할 수 있는 것보다 아래에 자리한다 — 여기서는 테이블 조회가 눈에 띄는 정밀도 비용 없이 초월함수 연산을 대체한다. 같은 논리가 그 옆의 Lab2XYZ에서도 나타나는데, 여기서는 Power(LMN[i], 3)가 순수한 LMN[i]*LMN[i]*LMN[i]가 되었다: 정수 거듭제곱은 애초에 Ln/Exp가 전혀 필요 없으므로, 이는 룩업 테이블 절충이 전혀 아니고 그저 불필요한 Power 호출을 제거한 것일 뿐이다. 룩업 테이블 트릭이 이득이 되는 것은 오직 전송 함수가 단일 Double의 순수 함수이기 때문이다 — 여러 픽셀 값이나 더 많은 상태에 의존하는 색상 변환으로는 깔끔하게 확장되지 않을 것이다

73개의 콘텐츠 스트림 오퍼레이터를 어떻게 빠르게 디스패치하는가?

ContentOperatorFromName은 PDFlibPas가 콘텐츠 스트림에서 읽어들이는 모든 토큰마다 한 번 호출되어, 이를 ISO 32000-1 Table 51의 전체 73개 오퍼레이터 집합 — w와 q부터 좀처럼 보이지 않는 d0과 d1 Type 3 글리프 메트릭 오퍼레이터까지 — 에 대해 매칭한다. 이는 예전에는 모든 단일 토큰마다 그 목록을 선형으로 순회했으므로, 몇천 개의 오퍼레이터를 가진 페이지는 같은 73개 항목짜리 테이블에 대한 몇천 번의 선형 스캔을 뜻했다. PDFlibPas는 이제 시작 시점에 오퍼레이터의 첫 바이트로 그 테이블을 버킷화해, 고정된 AnsiChar 인덱스 배열의 슬롯으로 만든다. 그래서 조회는 배열 인덱스 하나에 더해 같은 첫 문자를 공유하는 몇 안 되는 오퍼레이터만의 스캔이 된다

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;

PDF 오퍼레이터는 대소문자를 구분한다 — w와 W, f와 F, sc와 SC는 모두 서로 다른 오퍼레이터다 — 그래서 GOpBuckets는 원시 바이트를 키로 삼고, 버킷 안의 나머지 비교는 순수한 대소문자 구분 AnsiString 동등 비교다. 이 배열은 글자당 16슬롯 크기로 잡혀 있으며, 오늘날의 테이블을 여유 있게 커버한다 — 가장 붐비는 버킷인 T는 열세 개의 오퍼레이터를 담는데, 거의 모든 텍스트 상태와 텍스트 위치 지정 오퍼레이터가 그것으로 시작하기 때문이다 — 하지만 EnsureOpBuckets는 버킷의 개수가 16에 도달하면 조용히 추가를 멈추므로, 열네 번째 항목이 필요했던 버킷은 요란하게가 아니라 조용히 실패할 것이다: 그 오퍼레이터는 이유를 가리키는 예외 없이 coUnknown으로 해석될 것이다. 이것이 우아하게 저하되지 않는 자료구조를 우아하게 저하되지 않는 것과 맞바꾼 유지보수 비용이다 — 이는 경계 검사가 있는 성장이 전혀 필요 없기 때문에 더 빠르게 디스패치하며, 그 상한에 가까워진 버킷 하나를 지켜보는 사람이 필요하다

문자열 만들기에서 O(n²)를 잘라내기

Pascal의 Result := Result + Fragment 패턴은 매 반복마다 누적된 전체 문자열을 재할당하고 복사하므로, N개 문자 출력을 한 조각씩 만드는 것은 O(n) 대신 O(n²) 비용이 든다 — 각 줄이 저렴한 추가 하나처럼 보이므로 리뷰에서 놓치기 쉽고, PLDirectEscapeLiteralString이 저장 시 작성되는 모든 리터럴 PDF 문자열에서 실행되고 XFDFXMLEscape가 XFDF로 내보내지는 모든 필드 값에서 실행되므로 실무에서는 비싸다. PDFlibPas는 각 함수가 미리 무엇을 예측할 수 있는지에 따라 다른 기법으로 이 둘을 고친다. PLDirectEscapeLiteralString은 단 한 바이트도 쓰기 전에 출력 길이를 안다 — 한 번의 패스가 각 문자를 평범한 것인지 이스케이프될 것인지 분류하고 전체 합을 구하며, SetLength가 한 번 할당하고, 두 번째 패스가 인덱스로 버퍼를 채운다. XFDFXMLEscape는 저렴하게 출력 길이를 예측할 수 없는데, 유니코드 필드 텍스트가 미리 계산하기에는 너무 다양하기 때문이다. 그래서 대신 대략 입력 길이만큼 미리 크기를 잡은 TStringBuilder에 추가한다

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;

이 둘 사이의 선택은 실제로 루프가 시작되기 전에 무엇을 아는지의 문제다. 출력 크기를 계산하는 것이 저렴할 때는 세고-채우기 방식이 둘 중 더 빠른데, 재할당이 전혀 없고 Integer 카운터를 넘어서는 회계도 없기 때문이다. 하지만 이는 분류 로직을 두 번 작성해야 한다는 뜻이다 — 한 번은 세기 위해, 한 번은 내보내기 위해 — 그리고 이 두 사본이 서로 어긋나면 그 자체로 유지보수 위험이 된다. TStringBuilder는 그 최대 처리량의 일부를 포기하는 대신 로직을 한 번만 작성하고 기하급수적인 버퍼 성장으로부터 상각된 O(1) 추가를 얻는데, 이는 출력 크기를 미리 알기 쉽지 않을 때마다 더 안전한 기본값이다

이 패턴이 적용되는 곳, 그리고 적용되지 않는 곳

위의 네 가지 수정 모두 하나의 발상의 사례다: 입력 단위당 한 번 실행되는 호출 — 딕셔너리 키당, 픽셀당, 오퍼레이터 토큰당, 문자당 — 을 찾아, 그 선형적이거나 예측 불가능한 비용을 미리 계산된 테이블, 해시 인덱스, 또는 미리 크기가 잡힌 버퍼로 대체하는 것이다. 이 중 어느 것도 PDF에 특화된 것이 아니다; 요청당 같은 조회 키를 수천 번 해석하거나, 촘촘한 루프 안에서 값을 변환하거나, 고정된 토큰 어휘로 디스패치하거나, 긴 문자열을 한 문자씩 만드는 Delphi 서비스는 같은 실패 형태에 부딪히고 같은 수정을 적용받는다. 이 네 가지 변경 중 어느 것도 건드리지 않는 것은 동시성이나 메모리 사용량이다: 더 빠른 단일 스레드 딕셔너리 조회는 같은 TPDFlib 인스턴스에서 경쟁하는 두 스레드에는 아무 도움이 되지 않는데, 이는 병렬 페이지 렌더링의 스레드 안전성에 관한 글에서 별도로 다루는 구조적 문제다. 그리고 이는 애초에 객체 트리로 메모리에 로드하기에는 너무 큰 PDF에도 아무 도움이 되지 않는데, 이것이 기가바이트 단위 PDF 병합·분할에 관한 글에서 다루는 PDFlibPas의 Direct Access 계층이 존재하는 이유다

여기서 다룬 딕셔너리, 색상 관리, 콘텐츠 스트림 디스패치, 문자열 생성 코드는 별도 설정 없이 그대로 얻을 수 있는, Delphi와 C++Builder용 losLab의 PDF 라이브러리인 표준 PDFlibPas의 일부로 제공된다