پروفایلینگ کارایی در PDFlibPas: ایندکس‌های هش در Delphi

PDFlibPas، کتابخانه‌ی PDF از losLab برای Delphi و C++Builder، مسیرهای رندر و تولید محتوایش را با جایگزینی چهار الگوی کار-تکراری با الگوهای مستهلک‌شده سرعت می‌بخشد: یک ایندکس هش تنبل برای جستجوی کلید دیکشنری، یک جدول جستجوی گامای sRGB از پیش محاسبه‌شده، سطل‌بندی اولین‌بایت برای dispatch عملگر جریان محتوا، و TStringBuilder به‌جای الحاق رشته‌ی تکراری. هیچ‌کدام از این چهارتا از یک کشف دراماتیک نیامدند — از همان الگوی غیرچشمگیر در یک پروفایل آمدند: یک تابع کوچک که یک‌بار به‌ازای هر عملگر، یک‌بار به‌ازای هر پیکسل، یا یک‌بار به‌ازای هر نویسه فراخوانی می‌شود، جایی که یک هزینه‌ی خطی درون فراخوانی به مربعی یا تقریباً مربعی در سراسر یک سند کامل تبدیل می‌شود. این همان خط اصلی اینجاست: چهار رفع اشکال کوچک و بی‌ربط-به‌نظر که همان شکل از مسئله را هدف می‌گیرند، به‌علاوه محدودیت‌های صادقانه‌ی هرکدام

یک رندرر جریان محتوا واقعاً زمانش را کجا صرف می‌کند

رندرر جریان محتوای PDFlibPas تقریباً کل هزینه‌ی به‌ازای هر توکنش را از چهار نقطه‌ی باریک عبور می‌دهد: جستجوهای دیکشنری منبع روی /Resources، /ColorSpace، /Font، و /ExtGState؛ تصحیح گاما روی هر پیکسل رمزگشایی‌شده‌ی یک تصویر Lab، Indexed، یا برچسب‌خورده‌با-ICC؛ تطبیق نام-عملگر روی هر توکن از هر جریان محتوا؛ و ساخت رشته هرجایی که کتابخانه خروجی می‌سازد — فرارگذاری رشته‌ی لفظی در ذخیره، export XFDF، و گسترش توکن مهر و متغیر. هر یک از این چهارتا مقدار کمی کار به‌تنهایی انجام می‌دهد، و هرکدام هزاران یا میلیون‌ها بار روی یک سند واقع‌بینانه اجرا می‌شود، که دقیقاً همان شکل از تابعی است که یک جزئیات پیاده‌سازی O(n) یا O(n²) از نامرئی‌بودن دست می‌کشد و به ورودی برتر پروفایل تبدیل می‌شود

چرا جستجوهای دیکشنری منبع در یک PDF بزرگ کند می‌شوند؟

TPDFDictionary.FindIndexByKeyName چیزی است که رندرر برای حل هر جستجوی /Resources، /ColorSpace، /Font، و /ExtGState فرا می‌خواند، و سابقاً آرایه‌ی Entries را از جلو در هر فراخوانی می‌پیمود — برای یک دیکشنری Resources سه-ورودی‌ای خوب بود، برای یک Form XObject یا یک صفحه‌ی پر از ExtGState که همان دیکشنری روی هر عملگری که رنگ یا وضعیت گرافیکی را لمس می‌کند بررسی می‌شود، گران بود. PDFlibPas حالا یک ایندکس هش تنبل می‌سازد به‌محض اینکه یک دیکشنری از DICT_HASH_THRESHOLD (۱۶) ورودی عبور کند و دیکشنری‌های کوچک‌تر را روی اسکن خطی رها می‌کند، چون اغلب دیکشنری‌های PDF هرگز آن‌قدر بزرگ نمی‌شوند و یک جدول هش برای سه کلید بیشتر از آنچه صرفه‌جویی می‌کند هزینه‌ی ساختن دارد. ایندکس یک جدول address-باز و تخت است کلیددهی‌شده با PLAnsiStringHash، یک هش FNV-1a با basis افست متعارف 2166136261 و پرایم 16777619، انتخاب‌شده برای اجتناب از کشیدن 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) اولین‌باری که یک دیکشنری بزرگ پس از یک نوشتن پرس‌وجو می‌شود، به‌علاوه حافظه‌ی خودِ جدول هش است، تقریباً یک Integer به‌ازای هر اسلات در یک ضریب بار دوسوم — یک خطای گردکردن برای مشتی دیکشنری بزرگ‌تر از حد در یک سند معمولی، و یک هزینه‌ی واقعی که PDFlibPas از پرداختش روی هر دیکشنری کوچک با نگه‌داشتن آستانه جایی که هست اجتناب می‌کند

از پیش محاسبه‌کردن گامای sRGB به‌جای فراخوانی Power به‌ازای هر پیکسل

TPDFSimpleColorManager.XYZ2RGB تابع انتقال sRGB را روی هر پیکسل رمزگشایی‌شده‌ی یک تصویر Lab، Indexed، یا مبتنی‌بر-ICC اعمال می‌کند — 1.055 * Power(x, 1/2.4) - 0.055 بالای آستانه‌ی بخش-خطی — و Power(x, y) برای یک y کسری هیچ فرم بسته‌ی ارزانی در RTL از Pascal ندارد: به Ln(x) سپس Exp(y * Ln(x)) تجزیه می‌شود، و آن جفت فراخوانی متعالی، اجراشده سه‌بار به‌ازای هر پیکسل برای کانال‌های قرمز، سبز، و آبی، هزینه‌ی مسلط رمزگشایی یک پیکسل تصویر Lab یا ICC پیکسل‌به‌پیکسل است. PDFlibPas سه فراخوانی Power به‌ازای هر پیکسل را با یک جستجو درون GSRGBGammaLUT جایگزین می‌کند، یک آرایه‌ی Double ۴۰۹۶ورودی‌ای که یک‌بار از طریق EnsureSRGBGammaLUT ساخته شده و با گردکردن ورودی گیره‌شده به نزدیک‌ترین اسلات ایندکس‌گذاری می‌شود

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;

یک جدول ۴۰۹۶اسلاتی در سراسر بازه‌ی ورودی [۰, ۱] تقریباً شانزده برابر رزولوشن یک کانال خروجی ۸بیتی می‌دهد، پس quantizationای که LUT معرفی می‌کند زیر چیزی می‌نشیند که بایت نهایی RGB می‌تواند نمایش دهد — جستجوی جدول جبر ریاضی متعالی را اینجا بدون هزینه‌ی دقت قابل‌مشاهده‌ای جایگزین می‌کند. همان استدلال کنارش در Lab2XYZ نمایان می‌شود، جایی که Power(LMN[i], 3) به یک LMN[i]*LMN[i]*LMN[i] ساده تبدیل شد: یک توان صحیح در وهله‌ی اول به Ln/Exp نیاز ندارد، پس آن یکی اصلاً یک معامله‌ی LUT نیست، صرفاً یک فراخوانی زائد Power حذف‌شده. ترفند LUT فقط چون تابع انتقال یک تابع خالص از یک Double تکی است سود می‌دهد — به یک تبدیل رنگ که به چند مقدار پیکسل یا به وضعیتی بیش از آن بستگی داشت تمیز گسترش نمی‌یافت

چطور ۷۳ عملگر جریان محتوا را سریع dispatch کنیم؟

ContentOperatorFromName یک‌بار به‌ازای هر توکنی که PDFlibPas از یک جریان محتوا می‌خواند فراخوانی می‌شود، آن را در برابر مجموعه‌ی کامل ۷۳ عملگر جدول ۵۱ از ISO 32000-1 تطبیق می‌دهد — از w و q تا عملگرهای متریک-گلیف نوع ۳ به‌ندرت-دیده‌شده‌ی d0 و d1 — و سابقاً آن فهرست را در هر توکن تکی به‌طور خطی می‌پیمود، پس یک صفحه با چند هزار عملگر یعنی چند هزار اسکن خطی روی همان جدول ۷۳ورودی‌ای. 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 است. آرایه به اندازه‌ی ۱۶ اسلات به‌ازای هر حرف اندازه‌گذاری شده، که به‌راحتی جدول امروز را پوشش می‌دهد — شلوغ‌ترین سطل، T، سیزده عملگر نگه می‌دارد، چون تقریباً هر عملگر وضعیت-متن و موقعیت‌دهی-متن با آن شروع می‌شود — اما EnsureOpBuckets بی‌سروصدا از افزودن به یک سطل به‌محض اینکه شمارشش به ۱۶ برسد دست می‌کشد، پس سطلی که هرگز به یک ورودی چهاردهم نیاز پیدا کند بی‌سروصدا شکست می‌خورد نه بلند: عملگر به coUnknown حل می‌شود بدون هیچ استثنایی که به دلیلش اشاره کند. آن هزینه‌ی نگه‌داری معامله‌ی یک ساختار داده که با ظرافت افت می‌کند در برابر یکی که چنین نمی‌کند است — سریع‌تر dispatch می‌کند چون هرگز به یک رشد بازه-بررسی‌شده نیاز ندارد، و به یک انسان که آن یک سطل نزدیک به سقفش را می‌پاید نیاز دارد

حذف O(n²) از ساخت رشته

الگوی Result := Result + Fragment در Pascal کل رشته‌ی انباشته‌شده را در هر تکرار دوباره تخصیص و کپی می‌کند، پس ساخت یک خروجی N-نویسه‌ای یک قطعه در یک زمان به‌جای O(n) هزینه‌ی O(n²) دارد — آسان برای از قلم‌افتادن در بازبینی، چون هر خط شبیه یک الحاق ارزان به‌نظر می‌رسد، و گران در عمل چون PLDirectEscapeLiteralString روی هر رشته‌ی لفظی PDF نوشته‌شده در طول ذخیره اجرا می‌شود و XFDFXMLEscape روی هر مقدار فیلد export‌شده به 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('&');
        '<':  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 که همان کلید جستجو را هزاران بار به‌ازای هر درخواست حل می‌کند، مقادیر را در یک حلقه‌ی تنگ تبدیل می‌کند، روی یک واژگان ثابت از توکن‌ها dispatch می‌کند، یا رشته‌های بلند را یک نویسه در یک زمان می‌سازد، به همان شکل‌های شکست برخورد می‌کند و همان رفع اشکال‌ها را می‌گیرد. آنچه هیچ‌کدام از این چهار تغییر لمس نمی‌کند همزمانی یا رد پای حافظه است: یک جستجوی دیکشنری تک‌رشته‌ای سریع‌تر هیچ کاری برای دو رشته که روی همان نمونه‌ی TPDFlib مسابقه می‌دهند انجام نمی‌دهد، که یک مسئله‌ی ساختاری است جداگانه پوشش‌داده‌شده در مقاله‌ی امنیت رشته در رندر موازی صفحه، و هیچ کاری برای یک PDF که برای بارگذاری اصلاً به‌عنوان یک درخت شیء در حافظه بیش‌ازحد بزرگ است انجام نمی‌دهد، که همان چیزی است که لایه‌ی Direct Access در PDFlibPas برایش وجود دارد، پوشش‌داده‌شده در مقاله‌ی ادغام و تقسیم PDFهای گیگابایتی

کد دیکشنری، مدیریت رنگ، dispatch جریان محتوا، و ساخت رشته که در اینجا بحث شد، به‌عنوان بخشی از PDFlibPas استاندارد، کتابخانه‌ی PDF از losLab برای Delphi و C++Builder، عرضه می‌شود، بدون هیچ پیکربندی اضافی لازم برای گرفتن هرکدام