تحليل أداء PDFlibPas: فهارس التجزئة في Delphi

يُسرّع PDFlibPas، مكتبة PDF الخاصة بـlosLab لـDelphi وC++Builder، مسارات رسمه وتوليد محتواه باستبدال أربعة أنماط عمل متكرر بأنماط مطفأة التكلفة (amortized): فهرس تجزئة كسول لبحث مفاتيح القاموس، وجدول بحث محسوب مسبقًا لجاما sRGB، وتصنيف بحسب البايت الأول لتوزيع عوامل تدفق المحتوى، وTStringBuilder بدلًا من ربط سلاسل متكرر. لم يأتِ أي من الأربعة من اكتشاف درامي واحد — أتت من النمط نفسه غير المبهرج في ملف تحليل: دالة صغيرة تُستدعى مرة لكل عامل تشغيل، أو مرة لكل بكسل، أو مرة لكل حرف، حيث تصبح تكلفة خطية داخل الاستدعاء تربيعية أو شبه تربيعية عبر مستند كامل. هذا هو الخيط الجامع هنا: أربعة إصلاحات صغيرة تبدو غير مرتبطة تهاجم شكل المشكلة نفسه، بالإضافة إلى الحدود الصادقة لكل واحد منها

أين يقضي راسم تدفق المحتوى وقته فعليًا

يصبّ راسم تدفق المحتوى في PDFlibPas تقريبًا كل تكلفته لكل رمز عبر أربع نقاط ضيقة: بحث قاموس الموارد على /Resources و/ColorSpace و/Font و/ExtGState؛ وتصحيح جاما على كل بكسل مُفكَّك الترميز لصورة Lab، أو مفهرسة، أو موسومة بـ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، وهي دالة تجزئة FNV-1a بأساس إزاحة قانوني 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) في أول مرة يُستعلَم فيها عن قاموس كبير بعد كتابة، بالإضافة إلى ذاكرة جدول التجزئة نفسه، نحو عدد صحيح واحد لكل فتحة عند معامل تحميل ثلثي — خطأ تقريب لحفنة القواميس الضخمة في مستند نموذجي، وتكلفة حقيقية يتجنب PDFlibPas دفعها على كل قاموس صغير بإبقاء العتبة حيث هي

حساب جاما sRGB مسبقًا بدلًا من استدعاء Power لكل بكسل

تطبّق TPDFSimpleColorManager.XYZ2RGB دالة نقل sRGB على كل بكسل مُفكَّك الترميز لصورة Lab، أو مفهرسة، أو مبنية على 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 من 4096 إدخالًا مبنية مرة واحدة عبر 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;

يمنح جدول من 4096 فتحة على نطاق مدخل [0, 1] نحو ستة عشر ضعف دقة قناة مخرجات 8 بت، بحيث يقع التكميم الذي يقدمه جدول البحث تحت ما يستطيع بايت RGB النهائي تمثيله — يستبدل بحث الجدول الرياضيات المتعالية هنا دون تكلفة دقة مرئية. يظهر المنطق نفسه بجواره في Lab2XYZ، حيث أصبحت Power(LMN[i], 3) ببساطة LMN[i]*LMN[i]*LMN[i]: قوة عدد صحيح لا تحتاج Ln/Exp أصلًا، بحيث ليست تلك مقايضة جدول بحث على الإطلاق، مجرد استدعاء Power زائد عن الحاجة أُزيل. حيلة جدول البحث لا تؤتي ثمارها إلا لأن دالة النقل دالة نقية لـDouble واحدة — لن تمتد بنظافة إلى تحويل لون يعتمد على عدة قيم بكسل أو على حالة أكثر من ذلك

كيف توزّع 73 عامل تشغيل لتدفق محتوى بسرعة؟

تُستدعى ContentOperatorFromName مرة واحدة لكل رمز يقرأه PDFlibPas من تدفق محتوى، مطابقة إياه مقابل المجموعة الكاملة من 73 عامل تشغيل الخاصة بالجدول 51 من ISO 32000-1 — من w وq وحتى عاملي مقاييس حروف Type 3 النادري الظهور d0 وd1 — وكانت تجتاز تلك القائمة خطيًا في كل رمز واحد، بحيث كانت صفحة بها بضعة آلاف من عوامل التشغيل تعني بضعة آلاف من عمليات المسح الخطي على الجدول نفسه المكوّن من 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²) من بناء السلاسل النصية

يعيد نمط Result := Result + Fragment في Pascal تخصيص ونسخ السلسلة المتراكمة بأكملها في كل تكرار، بحيث تكلّف بناء مخرجات من 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('&');
        '<':  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 كبير جدًا بحيث لا يمكن تحميله في الذاكرة كشجرة كائنات على الإطلاق، وهذا ما توجد طبقة الوصول المباشر في PDFlibPas من أجله، المغطاة في مقالة دمج وتقسيم ملفات PDF بحجم غيغابايت

شيفرة القاموس، وإدارة الألوان، وتوزيع تدفق المحتوى، وبناء السلاسل النصية المناقشة هنا تُشحن كجزء من PDFlibPas القياسية، مكتبة PDF الخاصة بـlosLab لـDelphi وC++Builder، دون الحاجة لأي إعداد إضافي للحصول على أي منها