Bir PDF ayrıştırıcısının ilk yararlı okuması dosyanın yanlış ucundadır. Format, startxref işaretçisini (pointer) son baytlara koyar, bu nedenle 1,8 GB'lık bir arşivi işlemek kuyruğa (tail) bir arama (seek), bir kilobaytlık bir okuma (read) ve ardından çapraz referans (xref) tablosunun belge kataloğunun (document catalog) bulunduğunu söylediği yere bir atlama (hop) ile başlar. Oradan sonra ayrıştırma, tüm bayt aralığı boyunca rastgele bir yürüyüştür (random walk). Tamponlanmış (buffered) G/Ç'nin iyi olduğu her şey — dosya işaretçisinin arkasında sıralı ileriye doğru okuma (sequential read-ahead) — PDF'in sahip olmadığı bir iş yüküne yöneliktir
Bu makalenin ilk versiyonu, bellekle eşlenen bir dosyanın (memory-mapped file), TMemoryStream'in 2 GB'lık bir girdide karşılaştığı 32-bit bellek yetersizliği hatasını (out-of-memory failure) çözdüğünü iddia ediyordu. Bu iddia yanlıştır ve yanılma şekli gerçek düzeltmeyi işaret etmektedir: kayan (sliding) bir eşleme penceresi. Aşağıda, erişim modeli (access pattern), derlenebilir pencereli bir eşleyiciyle (windowed mapper) düzeltilmiş 32-bit hikayesi ve 1,8 GB'lık, 300.000 nesneli bir test dosyasındaki sistem çağrısı (syscall) aritmetiği yer almaktadır
PDF düzeni tamponlanmış okumaları neden alt eder
G/Ç modelini (IO pattern) üç yapısal gerçek şekillendirir. Birincisi, gezinme ofset güdümlüdür (offset-driven): çapraz referans tablosu her nesne numarasını mutlak bir bayt konumuyla eşleştirir ve hiçbir şey bu konumların sıralı olmasını gerektirmez. Yıllarca süren artımlı güncellemelerden (incremental updates) sonra, 4102 numaralı nesne 1,6 GB ofsetinde bulunurken 4103 numaralı nesne 30 KB ofsetinde bulunabilir. Bir TFileStream döngüsü her getirme (fetch) işlemini bir Seek artı bir Read (iki çekirdek geçişi) haline getirir ve bir sonraki getirme işlemi yüzlerce megabayt uzakta olduğu için tampon (buffer) hiçbir katkı sağlamaz
İkincisi, nesne akışları (object streams) (ISO 32000-1 §7.5.7) düzinelerce veya yüzlerce küçük sözlüğü indirilmiş (deflated) tek bir kapta (container) paketler. 300 baytlık bir sayfa sözlüğünü (page dictionary) getirmek, 100 KB'lık bir kümeyi (cluster) okumak ve şişirmek anlamına gelebilir. Madalyonun diğer yüzü: birlikte yazılan nesneler birlikte okunma eğilimindedir, bu nedenle kümeye göre boyutlandırılmış bir tampon (buffer), sonraki bir düzine getirme işlemini bedavaya sunar — formatta en çok istismar edilebilir (exploitable) düzenlilik (regularity) budur
Üçüncüsü, doğrusallaştırma (linearization). Doğrusallaştırılmış bir dosya, tüketicilerin (consumers) onu baştan sona okuyabilmesi için ilk sayfayı ve bir ipucu tablosunu önceden yükler (front-loads). Gigabaytlık arşivler neredeyse hiçbir zaman doğrusallaştırılmaz: doğrusallaştırma, dosyayı büyük hale getiren aynı artımlı güncellemeler ve birleştirmelerle yok edilir. Düşmanca duruma göre plan yapın: uzun atlamalar, sıra yok, sondan (tail-first) giriş
Düzeltilmiş 32-bit hikayesi
32-bitlik bir Windows süreci (process), 2 GB kullanıcı adres alanına (user address space) sahiptir ve bayt sayısı sıfır olan MapViewOfFile, dosya boyutunda tek bir bitişik (contiguous) rezervasyon (reservation) ister. 2 GB'lık bir girdi için bu rezervasyon başarılı olamaz: EXE, dağınık (scattered) DLL'ler ve iş parçacığı yığınlarından (thread stacks) sonra, tipik bir 32-bit Delphi sürecindeki en büyük boş bitişik blok 700 MB ile 1,4 GB arasında bir yerdedir. Çağrı (call), ERROR_NOT_ENOUGH_MEMORY ile başarısız olur, bu TMemoryStream.LoadFromFile'ın çarptığı aynı duvardır; yalnızca işlenmiş RAM'den (committed RAM) adres alanı rezervasyonuna (address-space reservation) taşınmıştır. Tüm dosyayı kapsayan bir eşleme (full-file mapping) 32-bitte hiçbir düzeltme (fix) değildir, daha iyi duyulan API isimlerinin ardındaki aynı başarısızlıktır
Çözüm (fix), eşlemenin (mapping) yaptığı iki şeyi birbirinden ayırmaktır. CreateFileMapping, bölüm nesnesini (section object) oluşturur ve dosya boyutu ne olursa olsun hiçbir adres alanı maliyeti (address-space cost) yoktur. Sadece MapViewOfFile adres alanı harcar ve onu tüm bölümü eşlemeye zorlayan hiçbir şey yoktur: 64-bitlik bir başlangıç ofseti (starting offset) ve bir görünüm uzunluğu (view length) alır. Bölümü bir kez oluşturun, ayrıştırılan bölge (region) üzerinde 64 ila 256 MB'lık bir görünümü eşleyin, ilerlemeden önce eşlemeyi kaldırın (unmap): adres alanı maliyeti tek bir dosyadır değil, tek bir penceredir (window). Bir kısıtlama: görünüm ofsetleri SYSTEM_INFO.dwAllocationGranularity değerinin, yani pratikte 64 KB'ın katları olmalıdır. Bu nedenle ofset 1.000.000 talebi (request) aşağıya doğru 983.040'a yuvarlanır ve çağıranın işaretçisi (caller's pointer) bu fark kadar ileriye ayarlanır
Delphi'de kayan pencereli eşleyici (sliding-window mapper)
Aşağıdaki sınıf tüm disiplini sarar (wraps): bir bölüm nesnesi (section object), bir canlı görünüm (live view), pürüzlülük hizalaması (granularity realignment) ve bir pencere sınırını (window boundary) aşan okumaların, iki görünümü birleştirmek (stitching) yerine bu tek görünümün büyütülmesiyle işlenmesi
uses
Winapi.Windows, System.SysUtils;
type
TWindowedFileMapper = class
private
FFile: THandle;
FMapping: THandle;
FFileSize: Int64;
FGranularity: DWORD; // SYSTEM_INFO.dwAllocationGranularity
FWindowSize: NativeUInt; // default view size
FViewBase: PByte; // base of the current view (aligned)
FViewOffset: Int64; // file offset FViewBase corresponds to
FViewSize: NativeUInt; // bytes mapped in the current view
procedure Unmap;
public
constructor Create(const FileName: string;
WindowSize: NativeUInt = 64 * 1024 * 1024);
destructor Destroy; override;
function Map(Offset: Int64; Size: NativeUInt): PByte;
procedure ReadBytes(Offset: Int64; var Buffer; Count: NativeUInt);
property FileSize: Int64 read FFileSize;
end;
constructor TWindowedFileMapper.Create(const FileName: string;
WindowSize: NativeUInt);
var
Info: TSystemInfo;
begin
inherited Create;
FFile := CreateFile(PChar(FileName), GENERIC_READ, FILE_SHARE_READ, nil,
OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, 0);
if FFile = INVALID_HANDLE_VALUE then
RaiseLastOSError;
if not GetFileSizeEx(FFile, FFileSize) then
RaiseLastOSError;
// The section object reserves no address space, whatever the file size
FMapping := CreateFileMapping(FFile, nil, PAGE_READONLY, 0, 0, nil);
if FMapping = 0 then
RaiseLastOSError;
GetSystemInfo(Info);
FGranularity := Info.dwAllocationGranularity; // 64 KB in practice
FWindowSize := WindowSize;
end;
destructor TWindowedFileMapper.Destroy;
begin
Unmap;
if FMapping <> 0 then CloseHandle(FMapping);
if FFile <> INVALID_HANDLE_VALUE then CloseHandle(FFile);
inherited;
end;
procedure TWindowedFileMapper.Unmap;
begin
if FViewBase <> nil then
begin
UnmapViewOfFile(FViewBase);
FViewBase := nil;
FViewSize := 0;
end;
end;
function TWindowedFileMapper.Map(Offset: Int64; Size: NativeUInt): PByte;
var
AlignedOffset: Int64;
Delta, MapSize: NativeUInt;
begin
if (Offset < 0) or (Offset + Int64(Size) > FFileSize) then
raise ERangeError.CreateFmt(
'Map request at %d for %d bytes is outside the file',
[Offset, Int64(Size)]);
// Fast path: the requested range already sits inside the live view
if (FViewBase <> nil) and (Offset >= FViewOffset) and
(Offset + Int64(Size) <= FViewOffset + Int64(FViewSize)) then
Exit(FViewBase + NativeInt(Offset - FViewOffset));
Unmap; // slide: never hold two views at once
// Views must start on an allocation-granularity boundary
AlignedOffset := Offset - (Offset mod FGranularity);
Delta := NativeUInt(Offset - AlignedOffset);
MapSize := FWindowSize;
if MapSize < Size + Delta then // request straddles the window end:
MapSize := Size + Delta; // grow this one view to cover it
if AlignedOffset + Int64(MapSize) > FFileSize then
MapSize := NativeUInt(FFileSize - AlignedOffset); // clamp at EOF
FViewBase := MapViewOfFile(FMapping, FILE_MAP_READ,
DWORD(AlignedOffset shr 32), DWORD(AlignedOffset and $FFFFFFFF),
MapSize);
if FViewBase = nil then
RaiseLastOSError;
FViewOffset := AlignedOffset;
FViewSize := MapSize;
Result := FViewBase + NativeInt(Delta);
end;
procedure TWindowedFileMapper.ReadBytes(Offset: Int64; var Buffer;
Count: NativeUInt);
begin
Move(Map(Offset, Count)^, Buffer, Count);
end;İki detay yükü taşır. İstenilen aralık (range) canlı görünümün içine yerleşmiş durumdaysa Map'in tepesindeki hızlı yol (fast path), çekirdek geçişi (kernel transition) olmadan bir işaretçi döndürür; nesne akışı kümelenmesi (object-stream clustering) sayesinde bu yaygın bir durumdur ve tasarrufun kaynağı burasıdır. Ve varsayılan pencerenin sonuna denk gelen bir talep (request), iki görünümü birleştirmek yerine o tek görünüm için MapSize'ı büyütür, bu da ReadBytes'i tek satırlık bir kod (one-liner) olarak tutar ve çağıranları (callers) kısmi okuma (partial-read) döngülerinden kurtarır
Pencere boyutu affedici bir ayardır: 64 MB'da 1,8 GB'lık bir dosyanın tam taranması (full sweep) 29 görünümdür, 256 MB'da bu 8'dir ancak parçalanmış (fragmented) bir 32-bit alana her rezervasyonu yerleştirmek daha zordur ve yaklaşık 16 MB'ın altında, çok fazla atlama yapan dosyalar dikkate değer ölçüde sık sık yeniden eşleme (remap) yapar. 64 ile 256 MB aralığındaki herhangi bir değerde eşleme trafiği istatistiksel bir gürültüdür
Sistem çağrılarını (syscalls) saymak
Şimdi aritmetik zamanı. Test dosyası: 1,8 GB, ortalama 600 baytlık veri (payload) içeren 300.000 dolaylı nesne (indirect objects). Nesne başına (per-object) bir ayrıştırıcı her birini SetFilePointerEx artı 4 KB'lık bir ReadFile ile getirir: 600.000 çekirdek geçişi (kernel transitions). Önbelleğe alınmış (cached) bir okuma sistem çağrısı (syscall), mevcut x64 donanımında gidiş-dönüş (round-trip) için yaklaşık 1,5 μs sürer, bu nedenle tek bir bayt bile ayrıştırmadan (parsing) önce saf çekirdek genel yükünün (pure kernel overhead) 600.000 × 1,5 μs ≈ 0,9 saniye olması demektir — bu sıcak önbellek (warm-cache) en iyi durumudur. Soğukken (cold), her bir atlama (hop) bir aygıt işlemi (device operation) olur: NVMe 4 KB rastgele okumaların (random reads) ~20 μs etkili gecikme süresinde (effective latency), bunlardan 300.000 tanesi yaklaşık 6 saniyelik aygıt zamanına (device time) mal olur; SATA sınıfı (SATA-class) depolamada ise dakikalarca sürer
Okumalar aynı zamanda yanlış verileri de taşır: 300.000 × 4 KB, kullanıcı arabelleklerine (user buffers) 1,2 GB iter (pushes) ve yaklaşık 180 MB veri teslim eder (delivers) — altı kat artış (amplification), çekirdekten kullanıcıya (kernel to user) kopyalanan her bir bayt
Nesne akışı kümeleri (object-stream clusters) boyutunda bir ileri okuma arabelleği (read-ahead buffer), ilk dürüst geliştirmedir: nesne başına bir tane yerine küme başına 256 KB'lık bir okuma, geçiş sayısını bir ila iki büyüklük derecesi (orders of magnitude) kadar azaltır. Bu aynı zamanda eşlemenin (mapping) garip olduğu yerlerde (genellikle ağ paylaşımları/network shares) doğru araçtır
Pencereli eşleyici (windowed mapper) daha ileri gider. Tam bir tarama (full sweep) 29 MapViewOfFile ve 29 UnmapViewOfFile çağrısıdır, yani 600.000'e karşı 58 açık geçiş (explicit transitions). Gerçek bir xref güdümlü (xref-driven) ayrıştırma (parse) temiz bir tarama değildir, ancak hızlı yol (fast path) her getirme (fetch) işlemini canlı pencere (live window) içinde emer (absorbs); test arşivi üzerinde bir metadata indeksleme geçişi (indexing pass) birkaç yüz yeniden eşlemeyle (remap) yerleşti. Eşleme, çekirdek çalışmasını kaldırmaz: açık sistem çağrılarını, bellek yöneticisinin (memory manager) kullanıcı alanı kopyası (user-space copy) olmadan doğrudan dosya önbelleğinden (file cache) çok sayfalı kümelerde çözdüğü (resolves) sayfa hatalarına (page faults) dönüştürür ve hiç dokunulmayan (never touched) bölgeler hiçbir şeye mal olmaz. Uçtan uca (End to end), indeksleme geçişi (indexing pass) nesne başı okumalarla (per-object reads) soğuk (cold) 23 saniyeden ve sıcak (warm) 7,1 saniyeden, eşleyici (mapper) ile soğuk 6,5 saniyeye ve sıcak 1,9 saniyeye düştü; geriye kalan G/Ç (IO) değil, zlib'in sıkıştırma açmasıdır (inflate)
FILE_FLAG_NO_BUFFERING nereye oturur
FILE_FLAG_NO_BUFFERING, katı hizalama kuralları (hard alignment rules) karşılığında sistem önbelleğini atlar (bypasses): ofsetler (offsets), uzunluklar (lengths) ve arabellek adresleri (buffer addresses) hep sektör hizalı (sector-aligned) olmalıdır. Eğer olmasaydı kimsenin iki kez okumadığı baytlarla önbelleği dolduracak olan tek geçişli (single-pass) sıralı işlerde maliyetini çıkarır — tüm arşivi yeniden yazan bir toplu yeniden serileştirme (batch re-serialization) veya tamamlanmış çıktıda bir doğrusallaştırma (linearization) geçişi gibi. 4 ila 8 MB hizalanmış (aligned) arabelleklerle, önbelleği (cache) kirletmeden aygıtın (device) sıralı bant genişliğine (sequential bandwidth) yaklaşır
Ayrıştırma (parsing) için tam olarak yanlıştır. Tamponsuz (unbuffered) bir işleyici (handle) üzerinden rastgele xref atlamaları (random xref hops), her 300 baytlık sözlük getirme (dictionary fetch) işlemini, ikinci ziyareti (second visit) emecek bir önbellek olmaksızın tam bir fiziksel okumaya dönüştürür — ve PDF ayrıştırma (PDF parsing) bölgeleri sürekli olarak yeniden ziyaret eder, çünkü farklı sayfalar aynı nesne akışlarına çözümlenir (resolves). Sıralı yeniden yazma (sequential rewrite) için tamponsuz (unbuffered) G/Ç (IO), rastgele ayrıştırma (random parse) için eşlenmiş (mapped) veya önbelleğe alınmış (cached) G/Ç (IO); bayrak (flag) işleyici başına (per-handle) uygulanır, bu nedenle bir süreç (pipeline) her ikisini de aynı dosyada tutabilir
64-bit, çalışma kümeleri (working sets) ve yazma tarafı
64 bitlik bir yapıda (build) adres alanı itirazı kaybolur: dosya boyutunu pencere (window) olarak geçirin ve yukarıdaki sınıf tek bir tam eşlemeye (full mapping) dejenere olur. Uzun süredir çalışan hizmetlerdeki yakalama (catch): salt okunur (read-only) dosya destekli (file-backed) sayfalar işlem (commit) ücreti almaz, böylece commit sayaçları (commit counters) sakin kalır, ancak dokunulan (touched) her sayfa çalışma kümesine (working set) katılır; 1,8 GB'nin çoğunu ayrıştırdığınızda (parse), çalışma kümesi diğer her şeyi çıkararak (evicting) onunla eşleşecek kadar büyür. Sınırlandırılmış (bounded) pencereler bunun üzerine bir tavan koyar (ceiling), bu nedenle adres alanının serbest (free) olduğu yerlerde bile kayan model (sliding pattern) doğru varsayılan (default) olarak kalır
Yazma (write) tarafında en ucuz G/Ç (IO), hiç verilmeyen G/Ç'dir. PDF'in artımlı güncelleme (incremental update) mekanizması (ISO 32000-1 §7.5.6), değişen nesneleri (changed objects) ve yeni bir çapraz referans bölümünü, hiçbir zaman hareket etmeyen orijinal baytlardan sonra ekler. 1,8 GB'lık arşive bir sayfa basmak, on binlerce kilobayt (tens of kilobytes) ekler; tam bir yeniden yazma işlemi (full rewrite) tüm 1,8 GB'ı hareket ettirir, (beş büyüklük sırası / five orders of magnitude) birbirinden farklıdır ve ekleme (append), kuyrukta (tail) yer alan tamamen ardışık (pure sequential) bir çıktıdır
losLab kütüphaneleri nereye oturur
Her iki losLab PDF kütüphanesi de bu disiplini bir API yüzeyi (API surface) olarak sunar. HotPDF Direct File API, nesne ağacını (object tree) oluşturmadan bir dosya işleyicisi (file handle) üzerinden sayfa sayılarını (page counts) ve yapıyı (structure) okur, dosya düzeyinde (file level) kopyalama ve şifre çözme yapar ve BeginIncrementalUpdate aracılığıyla farkları (deltas) yazar — yukarıdaki yalnızca ekleme (append-only) stratejisi, paketlenmiş hali. PDFlibPas Doğrudan Erişim (Direct Access) katmanıyla aynı yolu izler: çapraz referans (cross-reference) tablosunu yerinde dolaşan (walks), nesneleri tembelce (lazily) getiren, sayfaların aralıklarını (page ranges) dosyadan dosyaya çıkaran ve düzenlemeleri artımlı revizyonlar (incremental revisions) olarak devam ettiren (persists) bir akış okuyucu (streaming reader). Kendi ayrıştırıcınızı (parser) yazıyorsanız, eşleyici sınıfı (mapper class) tamamen sizindir; bir belge ardışık düzeni (document pipeline) çalıştırıyorsanız, kütüphanenin pencereyi dürüst tutmasına izin verin
Not: Gigabayt ölçekli belgeler için optimize edilmiş G/Ç (IO) işlemesi, Delphi ve C++Builder için HotPDF VCL Bileşenine doğrudan yerleştirilmiştir