Jak szybki jest std::string_view w porównaniu z operacjami na standardowym std::string? Zobaczcie kilka przykładów, gdzie porównuję wydajność obydwu rozwiązań.

Wstęp

Kiedy próbowałem znaleźć kilka przykładów wykorzystania std::string_view, po chwili zainteresował mnie temat wydajności.

Typ string_view jest koncepcyjnie widokiem na obiekt string: zazwyczaj implementowane jako [wskaźnik, długość]. Podczas tworzenia string_view nie ma miejsca kopiowanie danych (w przeciwieństwie do sytuacji, kiedy tworzymy kopię ciągu znakowego). Co więcej, string_view jest mniejsze od typu string - mam tutaj na myśli rozmiar na stosie i stercie.

Na przykład kiedy spojrzymy na przykładową (pseudo) implementację:

string_view {
    size_t _len;
    const CharT* _str;
}

W zależności od bieżącej architektury, rozmiar całości wynosi od 8 do 16 bajtów.

Z powodu optymalizacji na małych ciągach znakowych (Short String Optimisation - SSO) std::string wynosi zazwyczaj od 24 do 32 bajtów, zatem od dwóch do trzech razy więcej niż string_view. W tej formie, gdzie string może przechowywać od 15 (GCC, MSVC) do 22 znaków (Clang) nie ma potrzeby alokowania pamięci na stercie. Oczywiście, dłuższe ciągi znakowe będą używały więcej pamięci, ale 24/32 bajty to jest minimalny koszt dla typu std::string.

Więcej na temat samej optymalizacji możesz przeczytać we wspaniałym wpisie Exploring std::string oraz tutaj: SSO-23.

Oczywiście, tworzenie oraz zwracanie string_view jak i używanie substr jest stanowczo szybsze niż tworzenie głębokiej kopii typu std::string. Jednakże, jak testy wydajności wskazują, typ std::string jest mocno zoptymaliowany i czasami string_view nie wygrywa tak dużo.

Operacje na std::string_view

Typ string_view został zaprojektowany w bardzo podobny sposób co std::string. Jednakże jest “widokiem” czyli nie jest właścicielem danych, więc operacje modyfikujące przechowywane znaki nie mogły zostać zamieszczone w jego API.

Tutaj mamy krótką listę metod, których możemy używać z tym nowym typem:

• operator[]
• at
• front
• back
• data
• size/length
• max_size
• empty
• remove_prefix
• remove_suffix
• swap
• copy (nie constexpr)
• substr - złożoność O(1) w porównaniu do O(n) w std::string
• compare
• find
• rfind
• find_first_of
• find_last_of
• find_first_not_of
• find_last_not_of
• operatory porównywania: ==, !=, <=, >=, <, >
• operator<<

Należy zauważyć, że wszystkie te metody (poza copy oraz operator<<) posiadają modyfikator constexpr! Dzięki tej zdolności możemy teraz pracować ze stringami będącymi wyrażeniami stałymi.

Co więcej, w standardzie C++20 w prezencie dostaniemy conajmniej dwie nowe metody:

• starts_with
• ends_with

Zostają one zaimplementowane zarówno w std::string_view jak i std::string. Już Clang 6.0 wspiera te funkcje, zatem możemy rozpocząć eksperymenty z nimi.

Prosty test - substr

Metoda substr daje najprawdopodobniej największą przewagę string_view nad std::string. Ma ono złożoność O(1), kiedy std::string ma aż O(n).

Stworzyłem prosty test używając narzędzia Quick C++ Benchmark z następującymi efektami:

Użyłem kompilatora Clang 6.0.0 z flagą optymializacji -O3 oraz biblioteką libc++.

Kod dla std::string:

static  void StringSubStr(benchmark::State& state) {
    std::string s = "Hello Super Extra Programming World";
    for (auto _ : state) {
        auto oneStr = s.substr(0, 5);
        auto twoStr = s.substr(6, 5);
        auto threeStr = s.substr(12, 5);
        auto fourStr = s.substr(18, 11);
        auto fiveStr = s.substr(30, 5);
        // Make sure the variable is not optimized away by compiler
        benchmark::DoNotOptimize(oneStr);
        benchmark::DoNotOptimize(twoStr);
        benchmark::DoNotOptimize(threeStr);
        benchmark::DoNotOptimize(fourStr);
        benchmark::DoNotOptimize(fiveStr);
    }
}

Ten sam kod używający std::string_view:

static void StringViewSubStr(benchmark::State& state) {
    // Code before the loop is not measured
    std::string s = "Hello Super Extra Programming World";
    for (auto _ : state) {
        std::string_view sv = s;
        auto oneSv = sv.substr(0, 5);
        auto twoSv = sv.substr(6, 5);
        auto threeSv = sv.substr(12, 5);
        auto fourSv = sv.substr(18, 11);
        auto fiveSv = sv.substr(30, 5);
        benchmark::DoNotOptimize(oneSv);
        benchmark::DoNotOptimize(twoSv);
        benchmark::DoNotOptimize(threeSv);
        benchmark::DoNotOptimize(fourSv);
        benchmark::DoNotOptimize(fiveSv);
    }
}

Tutaj jest link do pełnego eksperymentu: @Quick C++ Bench

W tym teście mamy aż 10-ciokrotny wzrost wydajności!

Czy możemy osiągnąć podobne efekty w innych sytuacjach?

Dzielenie ciągu - funkcja split

Po prostym teście możemy zrobić jeden krok naprzód i spróbować skomponować bardziej zaawansowany algorytm: spróbujmy podzielić ciąg znakowy na kilka mniejszych.

Dla tego eksperymentu posłużyłem się kodem z następujących zasobów:

• string_view odi et amo - Marco Arena
• A Quicker Study on Tokenising - tristanbrindle.com

Mamy tutaj dwie wersje kodu, jedną dla std::string, a drugą dla std::string_view:

std::vector<std::string>
split(const std::string& str, const std::string& delims = " ")
{
    std::vector<std::string> output;
    auto first = std::cbegin(str);

    while (first != std::cend(str))
    {
        const auto second = std::find_first_of(first, std::cend(str), 
                  std::cbegin(delims), std::cend(delims));

        if (first != second)
            output.emplace_back(first, second);

        if (second == std::cend(str))
            break;

        first = std::next(second);
    }

    return output;
}

A teraz wersja dla std::string_view:

std::vector<std::string_view>
splitSV(std::string_view strv, std::string_view delims = " ")
{
    std::vector<std::string_view> output;
    size_t first = 0;

    while (first < strv.size())
    {
        const auto second = strv.find_first_of(delims, first);

        if (first != second)
            output.emplace_back(strv.substr(first, second-first));

        if (second == std::string_view::npos)
            break;

        first = second + 1;
    }

    return output;
}

A tutaj mamy benchmark:

const std::string_view LoremIpsumStrv {
    /*one paragraph of lorem ipsum */ 
};

static void StringSplit(benchmark::State& state) {
  std::string str { LoremIpsumStrv };
  for (auto _ : state) {
    auto v = split(str);
    benchmark::DoNotOptimize(v);
  }
}
// Register the function as a benchmark
BENCHMARK(StringSplit);

static void StringViewSplit(benchmark::State& state) {
  for (auto _ : state) {
    auto v = splitSV(LoremIpsumStrv);
    benchmark::DoNotOptimize(v);
  }
}
BENCHMARK(StringViewSplit);

Sprawdźmy, czy tutaj również osiągniemy 10-ciokrotne przebicie jak poprzednio… hmmm…

Niestety, ale std::string_view okazuje się wolniejsze na benchmarku dla funkcji split.

To był kompilator GCC 8.1, z flagą -O3

Odrobinę lepiej wygląda to dla kompilatora Clang 6.0.0, z flagą -O3:

Odrobinę lepsze wyniki osiągnąłem kiedy uruchomiłem kod lokalnie używając MSVC 2017:

string length: 486
test iterations: 10000
string split: 36.7115 ms
string_view split: 30.2734 ms

Tutaj jest pełny benchmark: @Quick C++ Bench

Czy macie jakieś pomysły, dlaczego nie mamy wzrostu wydajności podobnego do tego z początkowego eksperymentu?

Oczywiście, nie możemy założyć, że mnożnik 10x jest tutaj miarodajny.

Po pierwsze, mamy tutaj kontener - std::vector, który jest używany przez algorytm do zwrócenia wyników. Alokacja pamięci wewnątrz std::vector wpływa na ogólną prędkość.

Jeżeli uruchomimy iterację tylko jeden raz po wcześniejszym nadpisaniu operatora new, pojawią nam się następujące liczby (MSVC):

string length: 486
test iterations: 1
string split: 0.011448 ms, Allocation count: 15, size 6912
string_view split: 0.006316 ms, Allocation count: 12, size 2272

Mamy 69 słów wewnątrz tego stringa. Wersja std::string wygenerowała 15 alokowań pamięci (zarówno dla stringów jak i dla zwiększenia rozmiaru wektora), w sumie alokując 6912 bajtów.

Wersja std::string_view wykonała 12 alokacji pamięci (tylko dla wektora, ponieważ wewnątrz string_view nie było żadnej alokacji), w sumie alokując 2272 bajtów (3x mniej niż wersja std::string).

Pomysły na ulepszenie

Zobaczcie komenarz od JFT (w oryginalnym artykule), w którym poprawił on implementację algorytmów funkcji split poprzez zamianę iteratorów na wskaźniki. Udało mu się uzyskać stanowczo lepszą wydajność.

Inna możliwość to zarezerwowanie części pamięci up-front wewnątrz wektora (później możemy użyć shrink_to_fit) - dzięki temu oszczędzamy na liczbie alokacji pamięci.

Dodatkowo, jak się okazało podczas testów możemy dostać różne wyniki w zależności jaką funkcję wyszukującą użyjemy. Czy string_view::find_first_of (metoda string_view), czy może std::find_first_of (ogólny algorythm). Ogólny algorytm okazuje się działać szybciej.

Trzeci słupek - implementacja algorytmu z wykorzystaniem std::find_first_of pokazuje lepszą wydajność!

Więcej w kontynuacji artykułu: Bartek’s coding blog: Speeding Up string_view String Split Implementation

Porównanie z boost::split

Dla kompletności uruchomiłem również benchmark dla boost::split (1.67). Obydwie wersje były znacznie szybsze:

Uruchomione na WandBox, GCC 8.1

string length: 489
test iterations: 10000
string split: 42.8627 ms, Allocation count: 110000, size 82330000
string_view split: 45.6841 ms, Allocation count: 80000, size 40800000
boost split: 117.521 ms, Allocation count: 160000, size 83930000

Wygląda na to, że ręcznie dostosowana wersja jest niemalże trzy razy szybsza niż algorytm boost.split!

Uruchom ten kod na @WandBox

String split a ładowanie danych z pliku

Mogliście zaobserwować, że mój testowy string jest tylko jednym akapitem z “lorem ipsum”. Ten prosty test mógł wywołać dodatkowe optymalizacje kompilatora, przez co wyniki mogły zostać odrobinę naciągnięte.

Znalazłem świetny post Rianer Grimm’a: C++17 - Avoid Copying with std::string_view - ModernesCpp.com. W tym artykule wykorzystał on pliki tekstowe podczas przetwarzania stringów. To jest o wiele lepszy pomysł, ponieważ pracujemy na prawdziwym i dużym zestawie danych, zamiast na zwykłych stringach.

Teraz, amiast mojego akapitu z lorem ipsum, po prostu ładuję plik: na przykład 540 KB tekstu (Projekt Gutenberg).

Tutaj jest wynik testu wykorzystującego ten plik:

string length: 547412
test iterations: 100
string split: 564.215 ms, Allocation count: 191800, size 669900000
string_view split: 363.506 ms, Allocation count: 2900, size 221262300

Ten test został wykonany 100 razy, zatem podczas jednej iteracji alokujemy pamięć 191800/100 = 1918 razy (w sumie daje to 669900000/100 = 6699000 bajtów per iterację) dla std::string.
The test is run 100 times, so for one iteration we have 191800/100 = 1918 memory allocations (in total we use 669900000/100 = 6699000 bytes per iteration) for std::string.

Dla string_view mamy tylko 2900/100 = 29 alokowań pamięci i tylko 221262300/100 = 2212623 bajtów wykorzystywanych per iterację.

Co prawda nie jest to przyrost 10-ciokrotny, ale zużywamy za to 3x mniej pamięci i 1.5x skok wydajności.

Ryzyko związane z używaniem std::string_view

Myślę, że każdy artykuł dotyczący string_view powinien wspominać również o potencjalnym ryzyku związanym z tym nowym typem:

• Bądźmy wyczuleni na ciągi znakowe niezakończone znakiem null - string_view może nie zawierać znaku NULL na końcu. Musimy być przygotowani na tego typu przypadki:
  • Problematyczne staje się to podczas wywoływania funkcji takich jak atoi, czy printf, które akceptują stringi zakończone null-em.
  • Konwersje do typu std::string
• Referencje i tymczasowe obiekty - string_view nie jest właścicielem obiektu przechowywanego w pamięci, zatem musimy być ostrożni, kiedy pracujemy z tymczasowymi obiektami kiedy:
  • zwracamy string_view z funkcji
  • przechowywujemy string_view wewnątrz obiektu lub kontenera

Podsumowanie

Wykorzystując string_view możemy osiągnąć o wiele lepszą wydajność w wielu sytuacjach. Jednakże, ważmym jest, aby wiedzieć, że są wyjątki, których wydajność będzie gorsza w porównaniu do std::string!

Pierwsza sprawa to fakt, że string_view nie jest właścicielem przechowywanej wewnątrz wartości - musimy zatem uważać, aby nie odwoływać się do zwolnionego obszaru pamięci!

Drugą sprawą jest to, że kompilatory przetwarzają stringi bardzo mądrze, zwłaszcza kiedy te są krótkie (a zatem dobrze się je optymalizuje). W tym przypadku przyrost wydajności nie będzie już taki widoczny.

Wiecej na temat wydajności string_view możecie poczytać w kolejnym artykule na blogu bfilipek.com:
Speeding Up string_view String Split Implementation

Pytanie do Was

Jakie jest Wasze doświadczenie z string_view?