2008-08-24 04:14:26
Konsekwencje używania Reference Countingu

Za "Reference-Counted Long Strings" po prostu kocham Delphi. Ta mała ale przydatna cecha tego środowiska umożliwia łatwe wprowadzenie paru czasem bardzo poważnych optymalizacji do kodu - nie tylko przyspieszenia ale także zmniejszenia użycia pamięci przez program. Niestety, wymagają one trochę uwagi, ale... Po prostu warto.

Pierwsze, co przychodzi na myśl, to zredukowanie użycia pamięci, dzięki przypisaniu jednego fizycznego łańcucha dwóm lub większej ilości zmiennych bądź pól rekordów/obiektów. Oczywiście, absolutnie nie wchodzi w grę coś takiego:

for a:=1 to max do
   begin;
   LString:=tablica[a];
   for b:=1 to max do
      if a<>b then
         begin;
         if tablica[b]=LString then
            tablica[b]:=LString;
         end;
   end;

Chociaż na pewno zlikwiduje to duplikaty łańcuchów z tablicy, a zmienne Delphi'owego alokatora pamięci (AllocMemCount i AllocMemSize) przyjmą mniejsze wartości, to jednak fizyczne użycie pamięci nie zmieni się, a dodatkowo wzrośnie fragmentacja pamięci, nie mówiąc o tym, że dla dużych tablic powyższe jest po prostu śmiertelnie powolne (max*(max-1) porównań).
Można inaczej. Na przykład, dodając łańcuchy do tablicy, możemy sprawdzić, czy nowy łańcuch (pobrany z bazy danych czy innego źródła) jest identyczny jak ostatnio (poprzednio) dodany. Wtedy uzyskujemy mniejsze zyski wskazywane przez Delphi'owy alokator pamięci, ale większe realne zmniejszenie użycia pamięci i dodatkowo nie zwiększa się fragmentacja pamięci. Sama operacja ładowania tablicy wydłuża się, jednak nie o tyle, co przez porównanie każdego łańcucha z każdym (max porównań) - jednak i to da się przyspieszyć (np. porównując ze sobą tylko łańcuchy o identycznej długości - tylko trzeba wiedzieć z góry jak długie one są - a resztę ładować bez porównywania).

Dzięki takiemu "popodwiązywaniu" łańcuchów można wyraźnie przyspieszyć wiele operacji, np. sortowanie czy wyszukiwanie. Po co porównywać znak po znaku dwa identyczne łańcuchy? Po co wyszukiwać ponownie w tym samym (choć wskazywanym przez inną zmienną) łańcuchu? Właśnie - to bezsens.
W Delphi i FreePascalu, długie stringi (Long Strings) to tak naprawdę rekordy (struktury) składające się z trzech pól - długości, ilości odwołań i właściwego łańcucha zakończonego zerem. Czym więc jest zmienna typu Long String? To... wskaźnik na właściwy łańcuch. Konsekwencją tego jest to, że nie ma problemu ze zrzutowaniem Long Stringa na PChar (czyli wskaźnik na łańcuch zakończony zerem, praktycznie jedyny akceptowany przez funkcje Win32 API): PChar = Pointer(String)! (Tylko nie próbujcie zwalniać takiego PChara...).
Po co o tym napisałem? Bo gdy dwie zmienne typu Long String są tym samym fizycznym łańcuchem, to te dwie zmienne będą dwoma tymi samymi wskaźnikami. Tak więc dla stwierdzenia czy łańcuch A jest łańcuchem B, wystarczy to:

if pointer(a)=pointer(b) then [..]

Jednak uwaga: gdy łańcuch jest pusty (jego długość to zero), odpowiadająca mu zmienna ma wartość zerową (nil). Jeśli ktoś uważnie czytał wszystko co napisałem do tej pory, może pokusić się o użycie funkcji Win32 API o nazwie CompareString (celem chociażby pominięcia Delphi'owych spowalniaczy), ale ta funkcja bardzo nie lubi NULLi (nil'ów) - zatem nie można "jechać wprost" - trzeba albo odizolować puste łańcuchy, albo używać własnej funkcji porównującej łańcuchy, ... Albo przygotować się na dziwne niespodzianki (polecam przeczytać komentarze, funkcja CompareString lubi szaleć też dla innych przypadków). Poza tym, jeżeli w jednym miejscu kodu zmiennej (typu Long String) "A" przypiszemy jakąś konkretną wartość, a w innym miejscu zmiennej "B" - tą samą, tylko że wziętą z innego źródła (np. "A" będzie zapisana na sztywno w kodzie, a "B" przyjdzie z kontrolki TEdit), to chociaż łańcuchy będą takie same, to zmienne "A" i "B" będą miały zupełnie inne wartości.
W każdym razie, dzięki sprawdzeniu czy porównywane wskaźniki są identyczne (a więc czy dwa łańcuchy na pewno są takie same) spada liczba rzeczywistych porównań łańcuchów, a kod przyspiesza.

A co z wyszukiwaniem? W moim konkrentym przypadku, implementowałem w HCMie funkcję Szybkiego Wyszukiwania, czyli coś, co Thunderbirdowcy znają od dawna - okienko, w którym w trakcie wpisywania ciągu znaków, lista wiadomości automatycznie filtruje się do tych, które we wskazanych polach posiadają poszukiwany ciąg. Na czym polega optymalizacja?
Mamy dane łańcuchy do przeszukania i łańcuch szukany. Aby wyszukiwanie przebiegało w wygodny dla (wiecznie komplikującego życie programistów i helpdeskowców) użyszkodnika sposób, wyszukiwanie musi ignorować wielkość liter. Zatem na początku zmieniamy wielkość liter w poszukiwanym łańcuchu na małe. Potem wykonujemy właściwe wyszukiwanie polegające na:

  • Skopiowaniu łańcucha który będziemy przeszukiwać
  • Zmianie wielkości liter na małe w skopiowanym łańcuchu
  • Właściwym przeszukaniu skopiowanego łańcucha pod kątem poszukiwanego łańcucha.

(wiem, że funkcje LowerCase oraz AnsiLowerCase wykonują pierwszy i drugi krok "automatycznie" - o ile ja używam czego innego, to innym radzę pamiętać, co się dzieje "wewnątrz")

W grę wchodzi bardzo wiele optymalizacji, w tym użycie wyszukiwania Boyer-Moore-Horspoola czy Knuth-Morris-Pratta, ale warto zwrócić uwagę na to, że mając tablicę z "podwiązanymi" łańcuchami, łatwo możemy z góry stwierdzić, czy łańcuch A zawiera się we wskazanym łańcuchu. Wystarczy... Sprawdzić czy wskaźnik na poprzednio przeszukiwany łańcuch jest taki sam, co wskaźnik na kolejny w kolejce łańcuch. Jeśli tak, przywołujemy poprzedni wynik przeszukiwania. I to wszystko! Jeśli nie, wykonujemy całą operację od początku. W praktyce, jeśli wskaźniki są te same, odpada nam nie tylko porównywanie, ale także generowanie kopii łańcucha z ujednoliconą wielkością liter. Konkretniej? Czas naiwnego (binarnego, litera po literze) wyszukiwania wszystkich maili zawierających w temacie literę "w" - bez powyższej optymalizacji, bez "podwiązanych" łańcuchów, w zbiorze 200,000 maili - archiwum grupy pl.pregierz, na Athlonie 850 - trwa ok. 400ms. Po podwiązaniu łańcuchów, czas skraca się do ok. 340ms (dzięki lepszemu wykorzystaniu pamięci Cache). Po podwiązaniu łańcuchów i zlikwidowaniu wyszukiwania w już przeszukanych łańcuchach - nawet 90ms! Niemal 4,5 raza szybciej, niż na samym początku, za praktyczne darmo! Z czego to wynika? Z mniejszej ilości konwersji łańcuchów z dużych liter na małe - to jest największy spowalniacz! I choć możliwe jest dalsze optymalizowanie, to nie będę już o tym pisał.

Należy jednak zachować ostrożność przy takich zabawach. Bezpośrednie grzebanie w powiązanym łańcuchu (via wskaźniki) spowoduje zmianę w wielu miejscach. Delphi częściowo nas przed nim chroni, w momencie gdy do elementów danego łańcucha odwołujemy się via indeks (lancuch[idx]), zmiennej "lancuch" przydzielany jest nowy łańcuch, będący kopią oryginalnego łańcucha, ale będący powiązany jedynie ze zmienną "lancuch". To jest w pewnych przypadkach zbawienne, ale w innych zabójcze - nieostrożne użycie indeksów, i kod drastycznie spowalnia oraz skacze użycie pamięci. Poza tym, Delphi oferuje trzy rodzaje łańcuchów:

  • Krótkie (shortstring; tablica 255 ośmiobitowych znaków)
  • Długie ANSI (ansistring/string; do ~2147483648 ośmiobitowych znaków, wiązanie referencjami)
  • Długie Unicode (widestring; do ~1073741824 szesnastobitowych znaków)

Jak widać, tylko te trzecie umożliwiają przechowywanie symboli innych niż ASCII i spoza lokalnej strony kodowej, a tylko te drugie posiadają możliwość zliczania odwołań. Obejścia problemu są co najmniej trzy: wykorzystać własny typ zmiennej i ręcznie wykonywać całą brudną robotę związaną m. in. ze zliczaniem odwołań (duuużo problemów z zarządzalnością takim kodem), zapisywać łańcuch Unicode w długim łańcuchu (zabójcze dla już działających rozwiązań, niezwykle podatne na różne dziwne, trudne do oddebugowania problemy), lub zapisywać w długim łańcuchu łańcuch Unicode po konwersji do łańcucha UTF-8 (j/w, ale nieco łatwiej je oddebugować, poza tym - cierpi wydajność). Wiem że Kylix nie ma z tym problemów, podobno Freepascal też. Czemu twórcy Delphi do tej pory tego nie zrobili? Trudno mi to wyjaśnić. Niemniej warto o tym wiedzieć.

Sortowanie, wyszukiwanie, użycie pamięci - co jeszcze można przyspieszyć używając zliczania odwołań zamiast kopiowania danych? Na pewno nie tylko to. Trzeba tylko wiedzieć, że taka technika istnieje i że można ją wykorzystać. Nie tylko do łańcuchów.

Cocoon Ibiza Summer Mix (CD 2) - Mixed by Raresh


Może Cię zainteresować...

Link | Komentarzy: 1 | Programowanie, Tech, Techblog
Pokazuj komentarze.
Komentowanie wyłączone dla tego wpisu.
Powered by:
Hellcore Mailer - polski program pocztowyOpera Web BrowserFreeBSD - The Power to Serve!Slackware
RSSy:
Sidekick:
Projekty:
O autorze:
Zobacz:
Kategorie:
Archiwum:
Szukaj: