Badania terenowe nad budowaniem stringów

2009-07-18 13:04

Cokolwiek kodujemy, konieczność zbudowania dużego łańcucha znaków składającego się z kolejno dołączanych fragmentów pojawia się bardzo często. To może być zapytanie do bazy danych, misternie wyrzeźbiony adres URL, dynamicznie generowany i kompilowany później shader czy w końcu obszerny i szczegółowy komunikat o błędzie.
Wspólną cechą tych tekstów jest to, że budujemy je stopniowo, kawałek po kawałku. Na takie okazje niektóre języki (jak .NET-owe lub Java) posiadają specjalne klasy w rodzaju StringBuilder. Mają one być efektywniejsze niż bezpośrednie używanie typów string, głównie ze względu na nietworzenie wielu łańcuchów i niezaśmiecanie nimi pamięci, co odciąża garbage collector z dodatkowej pracy.

W C++ nie ma oczywiście odśmiecacza, który musiałby po nas sprzątać, i nie ma też narzędzi typu StringBuilder. Czy to oznacza więc, że możemy radośnie korzystać z samej klasy std::string do budowania dowolnie długich tekstów, bo żadnej efektywniejszej alternatywy nie ma?… To właśnie zdecydowałem się sprawdzić, przeprowadzając mały eksperyment z tworzeniem długich łańcuchów znaków kilkoma sposobami, aby potomni nie musieli rozwiązywać tego jakże uciążliwego dylematu ;]
Przechodząc do rzeczy, wpierw wysmażyłem taką oto funkcję która generuje tekst o podanej minimalnej długości:

  1. const string GenerateString(string::size_type minLen)
  2. {
  3.     string res;
  4.     string::size_type currLen = 0;
  5.  
  6.     while (currLen < minLen)
  7.     {
  8.         string::size_type next = rand() % (MAX_FRAG_LEN + 1);
  9.         res += STRINGS&#91;next];
  10.         currLen += next;
  11.     }
  12.  
  13.     return res;
  14. }&#91;/cpp]
  15. Użyta w niej tablica <code>STRINGS</code> zawierała przygotowane wcześniej "kawałki" w postaci losowych napisów, z których składany był wynikowy tekst. Każdy element <code>STRINGS[n]</code> był tu tekstem o długości <code>n</code> znaków (z zakresu 0 do 111).
  16. Powyższej funkcji użyłem następnie do wygenerowania stringów o długościach 222.222, 555.555, 1.111.111, 5.555.555 i 11.111.111 znaków, mierząc czas każdej z tych operacji i uśredniając go z 10 powtórzeń. Skąd takie długości tych tekstów?... No cóż, tylko co najmniej takie wartości dawały sensowne i wystarczają długie czasy, które dawało się zmierzyć i porównać z innymi :)
  17.  
  18. No właśnie - a jakież to inne sposoby na konstruowanie napisów można było jeszcze wymyślić? Otóż wymyśliłem jeszcze dwa, polegające na wykorzystaniu wektora znaków (<code>vector&lt;char&gt;</code>). Operacja konkatenacji została w nich zaimplementowana jako rozszerzenie wektora (metoda <code>resize</code>), a następnie przekopiowanie zawartości stringa w powstałe miejsce - czyli mniej więcej tak:
  19. [cpp]// res to vector<char>
  20. res.resize (currLen + next);
  21. memcpy (&res[currLen], STRINGS[next].data(), next * sizeof(char));

Wyróżnienie dwóch sposobów polegało natomiast na tym, że w jednym z nich dodatkowo wywoływałem na samym początku metodę reserve w celu uprzedniej rezerwacji pamięci w wektorze na 3 * minLen / 2 elementów.

Testy przeprowadziłem na standardowej implementacji klas string i vector dostępnej w Visual C++ 2005. Wyniki eksperymentu przedstawiają się następująco:

Można w nich przede wszystkim zauważyć, że zarządzanie pamięcią w klasie string jest domyślnie znacząco lepsze niż w vector. Najszybszą metodą konstruowania napisów okazuje się jednak użycie wektora z uprzednią rezerwacją pamięci, która okazuje się o ok. 20% szybsza niż zwykła konkatenacja stringów.

Czy to oznacza, że powinniśmy stworzyć sobie własną klasę StringBuilder, opierającą się na wektorze właśnie, i jej używać? Niekoniecznie. Jak widać, znaczące różnice pojawiają się dopiero przy tworzeniu napisów o wielkościach rzędu megabajta lub więcej. Konia z rzędem temu, kto tworzy tak duże zapytania lub shadery :) Do większości typowych zastosowań bezpośrednie użycie typu string wydaje się więc wystarczające.
No chyba że istnieją bardziej efektywne sposoby na budowanie stringów w C++, których nie udało mi się wymyślić – co jest swoją drogą całkiem prawdopodobne :)

Tags: , , ,
Author: Xion, posted under Programming »


12 comments for post “Badania terenowe nad budowaniem stringów”.
  1. TeWu:
    July 18th, 2009 o 16:28

    Wydaje mi się, że _jedynym_ powodem stosowania napisów modyfikowalnych (np. Javowski StringBuilder) w językach z garbage collectorami jest właśnie zapobieżenie śmietnika w pamięci. W językach (jak C++) w których samemu należy zwalniać pamięć, nigdy nie powstaje śmietnik w pamięci… czyli taki normalny string musi przy konkatenacji jakoś sobie radzić by nie naśmiecić (w Javie robi to dopiero StringBuilder). Właśnie brakiem możliwości odciążenia GC bym tłumaczył brak klas typu StringBuildera w językach bez GC.

    Jak można wyczytać ze statystyk które zrobiłeś, faktycznie, tak jak myślałem, na szybkości nie wiele można tutaj zyskać. Względem stringa udało Ci się to dopiero alokując miejsce zawczasu – czyli poniekąd oszukując :D bo taki biedny string nie ma pojęcia ile możesz chcieć do niego zapisać. Proponowałbym zrobienie jeszcze jednej wersji, w której wykorzystany był by string, ale z rezerwacją miejsca (poprzez wywołanie string.resize(3 * minLen / 2) na początku).

  2. Aithne:
    July 18th, 2009 o 19:18

    Ja bym na samiuteńkim początku zrobiła string o wymaganym rozmiarze, a potem go tylko wypełniała…

  3. vashpan:
    July 18th, 2009 o 20:48

    Hmm. Czemu nie znalazl sie wsrod tych sposobow stringstream ? Czyzby z zalozenia slowko “stream” zakladalo jego powolnosc ( co w sumie jest calkiem prawdopodobne ) ;) ?

    Poza tym wydaje mi sie ze mozliwosc prostych konwersji z roznych typow to plus dla tej metody przy roznych zapytaniach wlasnie.

  4. Dabroz:
    July 18th, 2009 o 23:22

    A stringstream? Jak wypada na tle powyższych?

  5. Xion:
    July 19th, 2009 o 1:06

    Zrobiłem na szybko testy dla dwóch zaproponowanych sposobów i wyniki są całkiem ciekawe ;]

    stringstream jest absolutnie do kitu, z czasem działania dla dwóch ostatnich przypadków równym odpowiednio 175 i 338 ms. To akurat mało zaskakujące, zważywszy na to jak złożonym tworem są strumienie IOStreams.

    Za to użycie klasy string z uprzednim wywołaniem reserve (bo chyba o to ci chodziło TeWu, a nie o resize? :)) daje dwa ostatnie wyniki rzędu 18 i 37 ms. Czyli zdecydowanie wygrywa :)

    Tak więc w sumie w obu kategoriach (z oszacowaniem długości i bez niego) wygrywa klasa string. Wygląda zatem, że C++ rzeczywiście żadnego StringBuildera nie potrzebuje i że w językach go zawierających cała sprawa rozbija się o garbage collector.

  6. Aithne:
    July 19th, 2009 o 12:42

    Sprawdź jeszcze strstream. Wtedy test będzie kompletny.

  7. Dabroz:
    July 20th, 2009 o 1:45

    Jeszcze tylko char* + memcpy i każdy znajdzie swojego faworyta. ;)
    Chociaż dziwi mnie różnica między string+reserve i vector+reserve. W końcu co vector robi w resize(), gdy ma wymagany rozmiar? Zakładam, że nic.

  8. Aithne:
    July 20th, 2009 o 18:52

    char* + memcpy? Brzydko, lepiej char* + ofastream – niby strumień, a potrafi pokonać ręczne zarządzanie char*.

  9. KanePL:
    July 22nd, 2009 o 10:23

    hmm…
    http://www.msobczak.com/prog/fastreams/

  10. lmilewski:
    July 23rd, 2009 o 19:44

    Robisz dużo złączeń długich stringów, więc może rope z STL się nada?
    http://www.sgi.com/tech/stl/Rope.html

    Faktem jest, że ten test pokazuje jak bardzo nie opłaca się zbyt wcześnie optymalizować kodu :-)

  11. Aithne:
    July 24th, 2009 o 11:46

    fatal error C1083: Cannot open include file: ‘rope’: No such file or directory ;)

  12. noisy - Krzysztof Szumny:
    December 17th, 2010 o 7:19

    jeżeli chodzi o inne struktury, spróbowałbym jeszcze z STLową Listą. Wszakże gdy znamy przewidywalną długość stringa, to string z reserve znów powinien być szybszy, jednakże nie znając owej długości, powinniśmy się skupić na strukturze, która gwarantuje szybkie wykonanie operacji dodawania.

    Takie budowanie składało by się kolejno z wywołań

    1. list.push_back(string);
    2. len+=string.size();

    dopiero na sam koniec używałbym stringa do zebrania wszystkiego w kupę, rezerwując wcześniej obszar o długości len

Comments are disabled.
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.