Równoległe analizowanie XLSX w Delphi: Wąskie gardło menedżera pamięci

HotXLS, natywna biblioteka Excel dla środowisk Delphi i C++Builder, analizuje arkusze XLSX w wielu wątkach poprzez trójfazowe ładowanie: XML arkusza jest dekompresowany szeregowo, analizowany równolegle, a małe części są następnie odczytywane szeregowo. Pierwsze wydanie tej funkcji przyniosło zaledwie 12–25% zysku wydajności, ponieważ domyślna blokada menedżera pamięci Delphi szeregowała wykonanie wątków roboczych. Zmniejszenie liczby alokacji na stercie z około 20 do 9,1 na komórkę zwiększyło przyspieszenie równoległe do 1,90x na ośmiu wątkach. Ten artykuł opisuje pomiary, błędne założenia oraz dwa rozwiązania, które naprawdę przyniosły rezultat

Jak HotXLS równolegle analizuje arkusze XLSX?

HotXLS dzieli metodę Open na trzy fazy, z których tylko środkowa działa na wątkach roboczych. Powodem jest kontener ZIP: archiwum ZIP to jeden współdzielony strumień wejściowy z jedną maszyną stanu dekompresji (inflate), a ta maszyna stanu nie może być odczytywana przez dwa wątki jednocześnie. Otoczenie jej blokadą byłoby bezcelowe, ponieważ dekompresja jest z natury szeregowa dla każdego wpisu, więc blokada odtworzyłaby po prostu wykonanie szeregowe z dodatkowym narzutem. Faza A dekompresuje zatem kod XML każdego arkusza do własnego strumienia TMemoryStream, wciąż na jednym wątku; w naszym pliku testowym zajęło to około 4 ms dla ośmiu części arkuszy, więc to nie tutaj leży wąskie gardło. Faza B uruchamia procedurę ParseWorksheetXml dla każdego arkusza w puli wątków roboczych — to tutaj upływa prawie cały czas ładowania. Faza C powraca szeregowo do pliku ZIP w celu pobrania małych części: komentarzy, rysunków, wykresów i tabel

Sama pula wątków jest celowo prosta. Wątki pobierają indeksy zadań ze współdzielonego licznika za pomocą funkcji InterlockedIncrement, dzięki czemu arkusze o różnych rozmiarach balansują się naturalnie bez udziału harmonogramu. Liczba wątków wynosi min(sheet count, CPU cores), pierwszy wyjątek wątku roboczego jest przechwytywany za pomocą AcquireExceptionObject i zgłaszany ponownie w wątku głównym po zakończeniu pracy, a dyspozytor przechodzi w zwykłą pętlę szeregową, gdy zadań jest zero lub jedno. Dwie właściwości klasy TXLSXWorkbook kontrolują tę funkcję: ParallelParse steruje pulą, a ParallelParseThreads ogranicza liczbę wątków, przy czym wartość 0 oznacza automatyczny wybór. Skoroszyty wieloarkuszowe to struktura, która czerpie z tego najwięcej korzyści, w tym te tworzone przez wielokrotne duplikowanie arkusza szablonu

var
  Book: TXLSXWorkbook;
begin
  Book := TXLSXWorkbook.Create;
  try
    Book.ParallelParse := True;      // enable the parallel worker pool
    Book.ParallelParseThreads := 0;  // 0 = auto: min(sheets, CPU cores)
    if Book.Open('quarterly-ledger.xlsx') <= 0 then
      raise Exception.Create('open failed');
    // ... read cells as usual; the workbook is fully materialized ...
  finally
    Book.Free;
  end;
end;

Dlaczego dodanie wątków spowalnia analizowanie XLSX w Delphi?

Ponieważ domyślny menedżer pamięci Delphi chroni swoją stertę za pomocą globalnej blokady, a analizowanie arkusza wiąże się z gęstym alokowaniem danych: milionami komórek, wariantów (Variants) i ciągów znaków (WideStrings). Każdy wątek roboczy odwołujący się do sterty ustawia się w kolejce do tej blokady, więc wątki, które w kodzie źródłowym wyglądają na niezależne, w praktyce wykonują się niemal pojedynczo. Nasz pierwszy test wykazał to nader wyraźnie. Na skoroszycie z 8 arkuszami o strukturze 5000 wierszy na 4 kolumny w arkuszu, zmierzonym na procesorze i5-11600K (6 rdzeni, 12 wątków) w środowisku Win64, równoległe wywołanie Open przyniosło poprawę o zaledwie 12–25% w porównaniu do szacunków planu zakładających co najmniej 40%. Przejście przez konfiguracje z 2, 3, 4, 6 i 8 wątkami dało płaską krzywą, a w późniejszych przebiegach konfiguracja z 2 wątkami była w rzeczywistości o 26% wolniejsza od szeregowej, co stanowi klasyczny objaw rywalizacji dwóch wątków o tę samą blokadę

Trzy pomiary pozwoliły na postawienie diagnozy, a każdy z nich obalił wcześniejsze przypuszczenia. Po pierwsze, malutki plik (8 arkuszy po 1 wierszu) otworzył się w 1,2 ms, co dowodzi, że analizowanie stanowi niemal 100% czasu Open i nie było ukrytych stałych kosztów. Po segundo, mikrotest czystej alokacji wykazał, że menedżer pamięci Delphi skaluje się negatywnie: ta sama łączna objętość 2 milionów alokacji obiektów i typów AnsiString działała o 60% wolniej na 8 wątkach niż na jednym, podczas gang to samo alokowanie na stercie WideString (która używa alokatora COM BSTR, a nie menedżera pamięci Delphi) skalowało się do poziomu 3,7x. Fakt, że HotXLS używa WideString w całej swojej strukturze, okazał się korzystnym zbiegiem okoliczności. Po trzecie, funkcja GetProcessTimes wykazała, że podczas równoległego wywołania Open czas procesora niemal odpowiadał czasowi rzeczywistemu: osiem wątków zużywało moc obliczeniową odpowiadającą około 1,3 wątka. Wątki robocze nie wykonywały pracy — spały w ścieżce blokowania menedżera pamięci, pozostając zablokowane zamiast zajęte

Praktyczna lekcja wykracza poza arkusze kalkulacyjne. Jeśli obciążenie w Delphi gęsto alokuje pamięć, zwiększenie liczby wątków nic nie da, dopóki wskaźnik alokacji nie spadnie, a może nawet pogorszyć sytuację. Przed wdrożeniem tej poprawki mówiliśmy użytkownikom dostrajającym właściwość ParallelParseThreads szczery fakt: w przypadku plików ograniczonych alokacją więcej wątków nie dawało niemal nic

Skąd bierze się 20 alokacji na stercie na jedną komórkę?

Licznik alokacji zainstalowany za pomocą SetMemoryManager dał precyzyjną odpowiedź: około 20 alokacji menedżera pamięci Delphi na komórkę, z czego 2,87 miliona z nich miało rozmiar 32 bajtów lub mniej. Winowajcą wcale nie były obiekty komórek. Funkcja TXMLScaner.GetTokenValue tworzyła nowy ciąg AnsiString przy każdym wywołaniu, a jest wywoływana około 15–20 razy na komórkę: po jednym razie dla nazw elementów, nazw atrybutów, wartości atrybutów oraz zawartości tekstowej. Co więcej, biblioteczna procedura UTF8ToWideString generowała tymczasowy ciąg UnicodeString dla każdej konwersji. Obiekty komórek odpowiadały za zaledwie 160 tysięcy alokacji, czyli około 8% całości, co przekreśliło nasz pierwotny plan: zamierzaliśmy zbudować pulę obiektów komórek, ale liczby wykazały, że to się nigdy nie opłaci

var
  OldMM, NewMM: TMemoryManagerEx;
  AllocCount, TinyCount: Int64;

function CountingGetMem(Size: NativeInt): Pointer;
begin
  AtomicIncrement(AllocCount);
  if Size <= 32 then
    AtomicIncrement(TinyCount);   // the small-object churn we care about
  Result := OldMM.GetMem(Size);
end;

// install before Open, restore afterwards
GetMemoryManager(OldMM);
NewMM := OldMM;
NewMM.GetMem := CountingGetMem;
SetMemoryManager(NewMM);

Ta dziesięciominutowa diagnostyka jest warta wdrożenia w każdym badaniu wydajności w Delphi. Zliczanie alokacji według kubełków rozmiaru jest niezwykle proste do zaimplementowania i precyzyjnie pokazuje, skąd pochodzi nacisk na menedżera pamięci — w naszym przypadku były to dwa nawyki na poziomie biblioteki RTL wewnątrz skanera XML, a nie cokolwiek w modelu obiektowym. Profilery wskazywały na parser jako całość; licznik wskazał dwie konkretne linie

Rozwiązanie: stałe tokenów (interning) i dekoder UTF-8 bez struktur tymczasowych

Dwie ukierunkowane zmiany w czytniku XML usunęły ponad połowę alokacji na komórkę bez modyfikacji struktury parsera. Pierwsza z nich to internowanie nazw elementów (interning). Kod XML arkusza bez końca powtarza niewielki słownik: row, c, v, r, t, s oraz kilka nazw atrybutów. Metoda InternTokenName przechowuje 64-pozycyjną pamięć podręczną wcześniej widzianych nazw i porównuje bufor skanera z wpisem w pamięci podręcznej za pomocą TokenEqualsAnsi — to bezpośrednie porównanie bajtów, które niczego nie alokuje. W przypadku trafienia zwraca buforowany ciąg AnsiString, i tutaj wybór typu ma kluczowe znaczenie: AnsiString podlega zliczaniu referencji, więc zwrócenie buforowanej instancji kosztuje jedno zwiększenie licznika odwołań i zerowy ruch na stercie. WideString nie ma licznika referencji, a każde przypisanie przechodzi przez SysAllocString, więc internowanie typów WideString nic by nie dało. Internowanie ma sens tylko w przypadku typu łańcuchowego z licznikiem referencji

function TXMLScaner.InternTokenName: AnsiString;
var
  Slot: Integer;
begin
  Slot := TokenHash mod 64;
  if TokenEqualsAnsi(FInternNames[Slot]) then
    Result := FInternNames[Slot]    // refcount++ only, no allocation
  else
  begin
    Result := GetTokenValue;        // materialize once, then cache
    FInternNames[Slot] := Result;
  end;
end;

Druga zmiana dotyczy tekstu komórki. Stara ścieżka budowała token AnsiString, przekazywała go do UTF8ToWideString, co tworzyło tymczasowy UnicodeString, konwertowany ostatecznie do formatu WideString zapisanego w komórce: łącznie dwie alokacje menedżera pamięci Delphi na token przed alokacją docelową. Zamiennik, XmlUtf8ToWide(TokenPtr, TokenLen), to dwuprzebiegowy czysty dekoder UTF-8 w języku Pascal, który czyta bezpośrednio z bufora skanera: przebieg pierwszy mierzy długość UTF-16, przebieg drugi dekoduje dane do WideString alokowanego tylko raz. Koszt netto na token tekstowy: jedna alokacja COM, zero alokacji menedżera pamięci Delphi. Jedna uwaga semantyczna: w przypadku uszkodzonych sekwencji UTF-8 nowy dekoder przepuszcza bajty bezpośrednio, zamiast zastępować je znakami zastępczymi (tak jak robi to biblioteka RTL), co wpływa tylko na zachowanie przy uszkodzonych plikach; dla prawidłowych danych wejściowych wyjście jest identyczne. Encje znakowe XML nigdy nie trafiają do dekodera, ponieważ skaner rozwiązał je już wcześniej na UTF-8 w buforze tokenów

Co to przyniosło i kiedy analizowanie równoległe nadal nie pomoże

Dwie poprawki zmniejszyły liczbę alokacji na komórkę z około 20 do 9,1, a wyniki równoległe przesunęły się dokładnie tak, jak wskazywała teoria. Na tym samym skoroszycie z 8 arkuszami o strukturze 5000 wierszy i tej samej maszynie 6C12T wydajność przy 8 wątkach wzrosła z 14% do 47,4%, co stanowi 1,90-krotne przyspieszenie w stosunku do metody szeregowej. Wariant z 2 wątkami zmienił się z wolniejszego o 26% na szybszy o 23,6%, a zmierzone zużycie procesora wzrosło z 1,0x do 2,2x. Ścieżka szeregowa przyspieszyła o około 3%, ponieważ mniejsza liczba alokacji pomaga również jednemu wątkowi. Pozostałe około 9 alokacji na komórkę to w przybliżeniu w połowie obiekty komórek i w połowie zamortyzowany wzrost kontenera; zmierzyliśmy je, uznaliśmy, że dalsza optymalizacja przyniesie znikome korzyści i zakończyliśmy prace, pozostawiając licznik alokacji w gotowości na wypadek, gdyby przyszłe testy uzasadniały kolejną rundę

Granice te warto określić równie jasno, jak same sukcesy. HotXLS parallelizuje pracę na poziomie arkuszy, więc skoroszyt będący jednym gigantycznym arkuszem jest analizowany w jednym wątku bez względu na ustawienia ParallelParseThreads — w takim przypadku lepszym narzędziem jest czytnik strumieniowy, ponieważ całkowicie unika on tworzenia skoroszytu w pamięci. Pliki, których przetwarzanie skupia się na elementach Fazy C (rysunki, wykresy i komentarze), odczują mniejszą korzyść, ponieważ faza ta pozostaje szeregowa z założenia. Małe pliki nie są w ogóle warte wielowątkowości, dlatego dyspozytor po cichu uruchamia tryb szeregowy dla niewielkich zadań. Limit narzucany przez menedżera pamięci również nie zniknął, a jedynie się przesunął: przy 9,1 alokacji na komórkę globalna blokada wciąż obciąża wątki, dlatego osiem wątków daje wynik 1,90x zamiast 4x. Aby poznać szerszy pakiet narzędzi do skracania czasu ładowania i zapisu (style, pule, zbiorcze wywołania wierszy), zobacz nasz przewodnik po wydajności dużych skoroszytów w Delphi

Równoległe analizowanie XLSX, właściwości ParallelParse i ParallelParseThreads oraz oszczędzający alokacje czytnik XML opisany w tym artykule są dostarczane jako standardowe elementy komponentu HotXLS Delphi Excel Component, który odczytuje i zapisuje formaty XLS, XLSX oraz ODS natywnie w Delphi i C++Builder bez użycia automatyzacji programu Excel