PDFlibPas, losLab PDF biblioteka, skirta Delphi ir C++Builder, paspartina atvaizdavimo ir turinio generavimo kelius, pakeisdama keturis pasikartojančio darbo modelius amortizuotais: tingų maišos indeksą žodyno raktų paieškai, iš anksto apskaičiuotą sRGB gama paieškos lentelę, turinio srauto operatorių parinkimą pagal pirmą baitą ir TStringBuilder vietoj pasikartojančio eilučių sujungimo. Nė vienas iš šių sprendimų neatsirado dėl vieno dramatiško atradimo — juos atskleidė tas pats neįspūdingas profilio modelis: maža funkcija iškviečiama kartą kiekvienam operatoriui, pikseliui arba simboliui, o linijinė operacijos kaina visame dokumente tampa kvadratinė arba beveik kvadratinė. Tai pagrindinė šio straipsnio mintis: keturi maži, iš pirmo žvilgsnio nesusiję pataisymai, sprendžiantys tos pačios formos problemą, ir sąžiningai nurodytos kiekvieno jų ribos
Kur turinio srauto atvaizdavimo priemonė iš tikrųjų praleidžia laiką
PDFlibPas turinio srauto atvaizdavimo priemonė beveik visas vieno žetono sąnaudas sutelkia keturiuose siauruose taškuose: išteklių žodyno paieškose pagal /Resources, /ColorSpace, /Font ir /ExtGState; gama korekcijoje kiekvienam iškoduotam Lab, Indexed arba su ICC žyma susieto vaizdo pikseliui; operatoriaus pavadinimo atitikmens paieškoje kiekvienam kiekvieno turinio srauto žetonui; ir eilučių kūrime visur, kur biblioteka generuoja išvestį — pažodinių eilučių ekranavime išsaugojimo metu, XFDF eksportavime, antspaudo ir kintamųjų žetonų išplėtime. Kiekvienas iš šių veiksmų atskirai atlieka nedaug darbo, tačiau realiame dokumente kiekvienas vykdomas tūkstančius ar milijonus kartų, ir būtent tokios funkcijos atveju O(n) arba O(n²) įgyvendinimo detalė nustoja būti nepastebima ir tampa svarbiausiu profilio įrašu
Kodėl dideliame PDF išteklių žodynų paieškos sulėtėja
TPDFDictionary.FindIndexByKeyName yra funkcija, kurią atvaizdavimo priemonė kviečia kiekvienai /Resources, /ColorSpace, /Font ir /ExtGState paieškai išspręsti, o anksčiau ji kiekvieno iškvietimo metu nuo pradžios pereidavo per Entries masyvą — tai tinkama trijų įrašų Resources žodynui, bet brangu Form XObject arba ExtGState gausiam puslapiui, kuriame tas pats žodynas tikrinamas kiekvienam operatoriui, liečiančiam spalvą ar grafinę būseną. Dabar PDFlibPas tingų maišos indeksą sukuria, kai žodynas viršija DICT_HASH_THRESHOLD (16) įrašų, o mažesniems žodynams palieka linijinę paiešką, nes dauguma PDF žodynų niekada nebūna tokie dideli, o maišos lentelės sukūrimas trims raktams kainuotų daugiau, nei sutaupytų. Indeksas yra plokščia atviro adresavimo lentelė, kurios raktas yra PLAnsiStringHash — FNV-1a maiša su kanoniniu poslinkio pagrindu 2166136261 ir pirminiu skaičiumi 16777619, pasirinkta tam, kad dėl tokio dydžio jautrios užduoties nereikėtų įtraukti 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;Indeksas ne atnaujinamas inkrementaliai, o invaliduojamas: kiekvienas keičiantis iškvietimas — AddEntry, DeleteEntryByKeyName, Assign, AddDict — išvalo maišą ir leidžia kitai paieškai ją sukurti iš naujo. Tai atrodo švaistoma, kol nepastebime, kad žodyno raktas yra TPDFName objektas, o TPDFName.SetTo gali pervadinti raktą, jau esantį žodyno Entries masyve, nepasinaudodamas jokiais paties žodyno metodais — inkrementalus indeksas tokio pervadinimo negali pastebėti, o tingus indeksas tiesiog atkuriamas ir pagal konstrukciją išlieka teisingas. Šio saugumo kaina yra O(n) atkūrimas pirmą kartą po įrašymo užklausiant didelį žodyną, taip pat pačios maišos lentelės atmintis, maždaug po vieną Integer kiekvienai vietai esant dviejų trečdalių užpildymui — įprastame dokumente tai nereikšminga kelių didelių žodynų kaina, kurios PDFlibPas išvengia mažesniems žodynams, palikdama esamą ribą
Išankstinis sRGB gamos skaičiavimas vietoj Power kvietimo kiekvienam pikseliui
TPDFSimpleColorManager.XYZ2RGB sRGB perdavimo funkciją taiko kiekvienam iškoduotam Lab, Indexed arba ICC pagrindu veikiančio vaizdo pikseliui — virš linijinio segmento ribos naudojama 1.055 * Power(x, 1/2.4) - 0.055, o trupmeniniam y dydžiui skirta Power(x, y) Pascal RTL neturi pigaus uždaro pavidalo: ji išskaidoma į Ln(x), o tada į Exp(y * Ln(x)), ir šios dvi transcendentinės operacijos, vykdomos tris kartus kiekvienam pikseliui raudonam, žaliam ir mėlynam kanalui, sudaro didžiausią Lab arba ICC vaizdo dekodavimo po vieną pikselį kainą. PDFlibPas tris kiekvieno pikselio Power kvietimus pakeičia viena paieška GSRGBGammaLUT masyve — tai 4096 elementų Double masyvas, vieną kartą sukurtas per EnsureSRGBGammaLUT ir indeksuojamas suapvalinus apribotą įvestį iki artimiausios vietos
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 vietų lentelė įvesties intervale [0, 1] suteikia maždaug šešiolika kartų didesnę skiriamąją gebą nei 8 bitų išvesties kanalas, todėl LUT įvedamas kvantavimas yra mažesnis už tai, ką gali atvaizduoti galutinis RGB baitas — čia lentelės paieška pakeičia transcendentinę matematiką be matomos tikslumo kainos. Tas pats samprotavimas matomas šalia esančioje Lab2XYZ, kur Power(LMN[i], 3) tapo paprastu LMN[i]*LMN[i]*LMN[i]: sveikasis laipsnis iš pradžių nereikalauja Ln/Exp, todėl tai apskritai nėra LUT kompromisas, tik pašalintas perteklinis Power kvietimas. LUT sprendimas apsimoka tik todėl, kad perdavimo funkcija priklauso nuo vieno Double — jis nebūtų lengvai pritaikomas spalvų transformacijai, priklausančiai nuo kelių pikselio reikšmių ar nuo didesnės būsenos
Kaip greitai parinkti iš 73 turinio srauto operatorių
ContentOperatorFromName iškviečiama kiekvienam žetonui, kurį PDFlibPas perskaito iš turinio srauto, ir tikrina jį pagal visą ISO 32000-1 51 lentelės 73 operatorių rinkinį — nuo w ir q iki retai matomų d0 ir d1 Type 3 glifo metrikos operatorių — tačiau anksčiau kiekvieno žetono metu ji linijiškai pereidavo visą sąrašą, todėl kelių tūkstančių operatorių puslapis reikšdavo kelis tūkstančius linijinių tos pačios 73 įrašų lentelės perėjimų. Dabar PDFlibPas paleidimo metu suskirsto lentelę pagal pirmąjį operatoriaus baitą į fiksuotą AnsiChar indeksuojamą vietų masyvą, todėl paieška tampa vienu masyvo indeksu ir tik kelių tuo pačiu pirmuoju simboliu prasidedančių operatorių patikra
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 operatoriai skiria didžiąsias ir mažąsias raides — w ir W, f ir F, sc ir SC yra skirtingi operatoriai — todėl GOpBuckets naudoja neapdorotą baitą kaip raktą, o likęs palyginimas vietų grupėje yra paprastas, didžiąsias ir mažąsias raides skiriantis AnsiString lygybės tikrinimas. Masyvas turi po 16 vietų kiekvienai raidei, o to šiandienos lentelei patogiai pakanka — daugiausia naudojama grupė, T, turi trylika operatorių, nes beveik kiekvienas teksto būsenos ir teksto pozicionavimo operatorius prasideda šia raide — tačiau EnsureOpBuckets tyliai nustoja pridėti elementus, kai grupės skaičius pasiekia 16, todėl grupei kada nors prireikus keturiolikto įrašo klaida įvyktų tyliai, o ne aiškiai: operatorius būtų išspręstas kaip coUnknown, be išimties, paaiškinančios priežastį. Tai duomenų struktūros, kuri išlaiko veikimą didėjant apkrovai, pakeitimo tokia, kuri to nedaro, priežiūros kaina — parinkimas greitesnis, nes nereikia auginti masyvo tikrinant ribas, tačiau žmogus turi stebėti vienintelę grupę, artėjančią prie savo ribos
O(n²) pašalinimas iš eilučių kūrimo
Pascal Result := Result + Fragment šablonas kiekvienos iteracijos metu iš naujo paskirsto ir nukopijuoja visą sukauptą eilutę, todėl N simbolių išvesties kūrimas po vieną fragmentą kainuoja O(n²), o ne O(n) — tai lengva praleisti peržiūroje, nes kiekviena eilutė atrodo kaip vienas pigus pridėjimas, tačiau praktiškai brangu, nes PLDirectEscapeLiteralString vykdoma kiekvienai išsaugojimo metu įrašomai pažodinei PDF eilutei, o XFDFXMLEscape — kiekvienai į XFDF eksportuojamai lauko reikšmei. PDFlibPas šias dvi vietas sutvarko skirtingais būdais, parinktais pagal tai, ką kiekviena funkcija gali iš anksto numatyti. PLDirectEscapeLiteralString išvesties ilgį žino dar prieš įrašydama vieną baitą — vienu praėjimu kiekvienas simbolis priskiriamas paprastam arba ekranizuojamam ir susumuojamas bendras ilgis, SetLength paskiria atmintį vieną kartą, o antras praėjimas užpildo buferį pagal indeksą. XFDFXMLEscape negali nebrangiai numatyti išvesties ilgio, nes Unicode lauko tekstas per daug kinta, kad jį būtų galima iš anksto apskaičiuoti, todėl vietoj to funkcija prideda tekstą į maždaug įvesties ilgiui paruoštą 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('<');
'>': Builder.Append('>');
// ...'"', tab, CR and LF cases follow the same shape
Else
Builder.Append(W[I]);
End;
End;
Result:= Builder.ToString;
Finally
Builder.Free;
End;
End;Pasirinkimas tarp šių dviejų būdų iš esmės priklauso nuo to, ką žinote prieš prasidedant ciklui. Skaičiuoti ir tada užpildyti yra greičiau, kai išvesties dydį nebrangu apskaičiuoti, nes nereikia nė vieno perskirstymo ir jokios papildomos apskaitos, išskyrus Integer skaitiklį, tačiau klasifikavimo logiką reikia parašyti du kartus — vieną kartą skaičiuojant, kitą išvedant — o tai savaime kelia priežiūros riziką, jei abi kopijos pradeda skirtis. TStringBuilder atsisako nedidelės didžiausios spartos dalies, tačiau leidžia logiką parašyti vieną kartą ir dėl geometrinio buferio augimo gauti amortizuotus O(1) pridėjimus, todėl tai saugesnis numatytasis pasirinkimas, kai išvesties dydį iš anksto nustatyti sunku
Kur šis modelis taikomas, o kur netaikomas
Visi keturi pirmiau aprašyti pataisymai yra vienos idėjos pavyzdžiai: rasti iškvietimą, vykdomą kartą kiekvienam įvesties vienetui — žodyno raktui, pikseliui, operatoriaus žetonui ar simboliui — ir jo linijinę arba nenuspėjamą kainą pakeisti iš anksto apskaičiuota lentele, maišos indeksu arba iš anksto paruoštu buferiu. Tai nėra būdinga tik PDF: Delphi tarnyba, kuri tūkstančius kartų per užklausą sprendžia tą patį paieškos raktą, verčia reikšmes glaudžiame cikle, parenka operatorių iš fiksuoto žetonų žodyno arba po vieną simbolį kuria ilgas eilutes, susiduria su tokiais pačiais gedimo modeliais ir taiko tokius pačius pataisymus. Tačiau nė vienas iš šių keturių pakeitimų neliečia lygiagretumo ar atminties pėdsako: greitesnė vienos gijos žodyno paieška nieko nepadeda dviem gijoms varžantis dėl to paties TPDFlib egzemplioriaus, o tai struktūrinė problema, atskirai aptarta straipsnyje apie gijų saugą lygiagrečiai atvaizduojant puslapius, ir nieko nepadeda PDF, kuris per didelis, kad jį būtų galima įkelti į atmintį kaip objektų medį, nes tam PDFlibPas turi Direct Access sluoksnį, aptartą straipsnyje apie gigabaitų PDF sujungimą ir skaidymą
Čia aptartas žodyno, spalvų valdymo, turinio srauto parinkimo ir eilučių kūrimo kodas pateikiamas kaip standartinio PDFlibPas, losLab PDF bibliotekos, skirtos Delphi ir C++Builder, dalis, todėl norint visa tai naudoti nereikia jokios papildomos konfigūracijos