Czy standard C ++ nakazuje słabą wydajność dla iostreams, czy po prostu mam do czynienia ze słabą implementacją?

197

Za każdym razem, gdy wspominam powolne działanie standardowych bibliotek i +++ C ++, spotykam się z falą niedowierzania. Mam jednak wyniki profilowania pokazujące dużą ilość czasu spędzonego na kodzie biblioteki iostream (pełne optymalizacje kompilatora), a przełączanie z iostreams na interfejsy API I / O specyficzne dla systemu operacyjnego i niestandardowe zarządzanie buforami daje pewien wzrost wielkości.

Jaką dodatkową pracę wykonuje standardowa biblioteka C ++, czy jest wymagana przez standard i czy jest przydatna w praktyce? Czy też niektóre kompilatory zapewniają implementacje iostreams, które są konkurencyjne w stosunku do ręcznego zarządzania buforami?

Benchmarki

Aby poruszyć sprawy, napisałem kilka krótkich programów do wykonywania wewnętrznego buforowania iostreams:

Zauważ, że wersje ostringstreami stringbufuruchamiają mniej iteracji, ponieważ są one znacznie wolniejsze.

Na ideonie ostringstreamjest około 3 razy wolniejszy niż std:copy+ back_inserter+ std::vectori około 15 razy wolniejszy niż memcpyw surowym buforze. Jest to spójne z profilowaniem przed i po, kiedy zmieniłem moją prawdziwą aplikację na niestandardowe buforowanie.

Są to wszystkie bufory pamięci, więc powolności iostreamów nie można winić za powolne operacje we / wy dysku, zbyt duże opróżnianie, synchronizację ze standardem lub jakiekolwiek inne rzeczy, których ludzie używają, aby usprawiedliwić spowolnienie standardowej biblioteki C ++ iostream.

Byłoby miło zobaczyć wyniki testów porównawczych na innych systemach i komentarze na temat czynności wykonywanych przez popularne implementacje (takich jak libc ++ gcc, Visual C ++, Intel C ++) oraz na ile narzutu narzuca norma.

Uzasadnienie tego testu

Wiele osób słusznie zauważyło, że iostreamy są częściej używane do sformatowanego wyjścia. Są to jednak jedyne nowoczesne interfejsy API zapewniane przez standard C ++ do dostępu do plików binarnych. Ale prawdziwy powód przeprowadzania testów wydajności na wewnętrznym buforowaniu dotyczy typowych sformatowanych operacji we / wy: jeśli iostreams nie może zapewnić, że kontroler dysku jest dostarczany z surowymi danymi, to jak mogą nadążyć, gdy są również odpowiedzialni za formatowanie?

Benchmark Timing

Wszystko to na iterację zewnętrznej ( k) pętli.

W systemie ideone (gcc-4.3.4, nieznany system operacyjny i sprzęt):

  • ostringstream: 53 milisekundy
  • stringbuf: 27 ms
  • vector<char>i back_inserter: 17,6 ms
  • vector<char> ze zwykłym iteratorem: 10,6 ms
  • vector<char> sprawdzanie iteratora i granic: 11,4 ms
  • char[]: 3,7 ms

Na moim laptopie (Visual C ++ 2010 x86, cl /Ox /EHscWindows 7 Ultimate 64-bit, Intel Core i7, 8 GB RAM):

  • ostringstream: 73,4 milisekund, 71,6 ms
  • stringbuf: 21,7 ms, 21,3 ms
  • vector<char>i back_inserter: 34,6 ms, 34,4 ms
  • vector<char> ze zwykłym iteratorem: 1,10 ms, 1,04 ms
  • vector<char> iterator i sprawdzanie granic: 1,11 ms, 0,87 ms, 1,12 ms, 0,89 ms, 1,02 ms, 1,14 ms
  • char[]: 1,48 ms, 1,57 ms

Visual C ++ 2010 x86, z profilu Guided Optimization cl /Ox /EHsc /GL /c, link /ltcg:pgi, biegać, link /ltcg:pgozmierz:

  • ostringstream: 61,2 ms, 60,5 ms
  • vector<char> ze zwykłym iteratorem: 1,04 ms, 1,03 ms

Ten sam laptop, ten sam system operacyjny, używając cygwin gcc 4.3.4 g++ -O3:

  • ostringstream: 62,7 ms, 60,5 ms
  • stringbuf: 44,4 ms, 44,5 ms
  • vector<char>i back_inserter: 13,5 ms, 13,6 ms
  • vector<char> ze zwykłym iteratorem: 4,1 ms, 3,9 ms
  • vector<char> sprawdzanie iteratora i granic: 4,0 ms, 4,0 ms
  • char[]: 3,57 ms, 3,75 ms

Sam laptop, Visual C ++ 2008 SP1 cl /Ox /EHsc:

  • ostringstream: 88,7 ms, 87,6 ms
  • stringbuf: 23,3 ms, 23,4 ms
  • vector<char>i back_inserter: 26,1 ms, 24,5 ms
  • vector<char> ze zwykłym iteratorem: 3,13 ms, 2,48 ms
  • vector<char> sprawdzanie iteratora i granic: 2,97 ms, 2,53 ms
  • char[]: 1,52 ms, 1,25 ms

Ten sam laptop, 64-bitowy kompilator Visual C ++ 2010:

  • ostringstream: 48,6 ms, 45,0 ms
  • stringbuf: 16,2 ms, 16,0 ms
  • vector<char>i back_inserter: 26,3 ms, 26,5 ms
  • vector<char> ze zwykłym iteratorem: 0,87 ms, 0,89 ms
  • vector<char> sprawdzanie iteratora i granic: 0,99 ms, 0,99 ms
  • char[]: 1,25 ms, 1,24 ms

EDYCJA: Przebiegł wszystko dwa razy, aby zobaczyć, jak spójne były wyniki. Dość spójny IMO.

UWAGA: Na moim laptopie, ponieważ mogę zaoszczędzić więcej czasu procesora niż pozwala ideone, ustawiłem liczbę iteracji na 1000 dla wszystkich metod. Oznacza to, że ostringstreami vectorrealokacja, która odbywa się tylko na pierwszym przejeździe, powinny mieć niewielki wpływ na końcowe wyniki.

EDYCJA: Ups, znaleziono błąd w vector-w zwykłym-iteratorze, iterator nie był zaawansowany i dlatego było zbyt wiele trafień w pamięci podręcznej. Zastanawiałem się, jak radził sobie vector<char>lepiej char[]. Nie miało to jednak większego znaczenia, vector<char>wciąż jest szybsze niż char[]w VC ++ 2010.

Wnioski

Buforowanie strumieni wyjściowych wymaga trzech kroków przy każdym dodawaniu danych:

  • Sprawdź, czy przychodzący blok pasuje do dostępnej przestrzeni bufora.
  • Skopiuj przychodzący blok.
  • Zaktualizuj wskaźnik końca danych.

Najnowszy fragment kodu, który opublikowałem, „ vector<char>prosty iterator plus sprawdzanie granic” nie tylko robi to, ale także przydziela dodatkową przestrzeń i przenosi istniejące dane, gdy nadchodzący blok nie pasuje. Jak zauważył Clifford, buforowanie w klasie I / O pliku nie musiałoby tego robić, wystarczyło opróżnić bieżący bufor i użyć go ponownie. Powinno to stanowić górną granicę kosztu buforowania danych wyjściowych. I to jest dokładnie to, czego potrzeba, aby stworzyć działający bufor w pamięci.

Dlaczego więc stringbuf2,5 razy wolniej działa na ideone, a co najmniej 10 razy wolniej, gdy go testuję? Nie jest on używany polimorficznie w tym prostym mikroprocesorze, więc to nie wyjaśnia.

Ben Voigt
źródło
24
Piszesz milion znaków pojedynczo i zastanawiasz się, dlaczego jest to wolniejsze niż kopiowanie do wstępnie przydzielonego bufora?
Anon.
20
@Anon: Buforuję cztery miliony bajtów cztery na raz i tak, zastanawiam się, dlaczego to jest wolne. Jeśli std::ostringstreamnie jest wystarczająco inteligentny, aby wykładniczo zwiększyć rozmiar bufora, std::vectorrobi to (A) głupie i (B) coś, co ludzie myślą o wydajności I / O, powinni pomyśleć. W każdym razie bufor jest ponownie wykorzystywany, nie jest ponownie przydzielany za każdym razem. I std::vectorużywa również dynamicznie rosnącego bufora. Staram się być tutaj sprawiedliwy.
Ben Voigt,
14
Jakie zadanie faktycznie próbujesz przeprowadzić? Jeśli nie korzystasz z żadnej z funkcji formatowania ostringstreami chcesz uzyskać jak najszybszą wydajność, powinieneś rozważyć przejście od razu do stringbuf. Te ostreamzajęcia są przypuszczać, aby związać ze sobą narodowe świadomy funkcjonalność formatowania z elastycznego wyboru bufora (plik, łańcuch, itp) przez rdbuf()a jego interfejs funkcji wirtualnej. Jeśli nie wykonujesz żadnego formatowania, ten dodatkowy poziom pośredni z pewnością będzie wyglądał proporcjonalnie drogo w porównaniu z innymi podejściami.
CB Bailey
5
+1 za prawdę op. Przyspieszyliśmy porządek lub wielkość, przechodząc od ofstreamdo fprintfpodczas wysyłania informacji rejestracyjnych dotyczących podwójnych. MSVC 2008 na WinXPsp3. iostreams jest po prostu psie.
KitsuneYMG,
6
Oto test na stronie komisji: open-std.org/jtc1/sc22/wg21/docs/D_5.cpp
Johannes Schaub - litb

Odpowiedzi:

49

Nie odpowiadając na specyfikę twojego pytania tak bardzo jak tytuł: Raport techniczny z 2006 roku na temat wydajności C ++ zawiera interesującą sekcję dotyczącą IOStreams (str. 68). Najbardziej odpowiedni dla twojego pytania znajduje się w Rozdziale 6.1.2 („Szybkość wykonania”):

Ponieważ niektóre aspekty przetwarzania IOStreams są rozłożone na wiele aspektów, wydaje się, że Standard nakazuje nieefektywną implementację. Ale tak nie jest - przy użyciu jakiejś formy wstępnego przetwarzania można uniknąć wielu prac. Za pomocą nieco inteligentniejszego linkera niż zwykle jest możliwe, można usunąć niektóre z tych nieefektywności. Jest to omówione w § 6.2.3 i § 6.2.5.

Ponieważ raport został napisany w 2006 roku, można mieć nadzieję, że wiele zaleceń zostanie uwzględnionych w obecnych kompilatorach, ale być może tak nie jest.

Jak wspomniałeś, aspekty mogą się nie pojawiać write()(ale nie zakładam tego na ślepo). Więc co zawiera? Uruchomienie GProf na ostringstreamkodzie skompilowanym za pomocą GCC daje następujący podział:

  • 44,23% w std::basic_streambuf<char>::xsputn(char const*, int)
  • 34,62% ​​w std::ostream::write(char const*, int)
  • 12,50% w calach main
  • 6,73% w std::ostream::sentry::sentry(std::ostream&)
  • 0,96% w std::string::_M_replace_safe(unsigned int, unsigned int, char const*, unsigned int)
  • 0,96% w std::basic_ostringstream<char>::basic_ostringstream(std::_Ios_Openmode)
  • 0,00% w std::fpos<int>::fpos(long long)

Spędza się więc większość czasu xsputn, który ostatecznie wywołuje std::copy()po wielu sprawdzeniach i aktualizacjach pozycji kursora i buforów (sprawdź c++\bits\streambuf.tccszczegóły).

Uważam, że skupiłeś się na najgorszej sytuacji. Wszystkie przeprowadzone kontrole byłyby niewielkim ułamkiem całkowitej pracy wykonanej, gdybyś miał do czynienia z dość dużymi fragmentami danych. Ale twój kod przesuwa dane o cztery bajty na raz i za każdym razem ponosi dodatkowe koszty. Najwyraźniej należałoby tego uniknąć w rzeczywistej sytuacji - zastanów się, jak mało znacząca byłaby kara, gdyby writezostał wywołany na tablicy 1 mln int zamiast na 1 mln razy na jedną int. A w rzeczywistej sytuacji naprawdę docenilibyśmy ważne cechy IOStreams, a mianowicie bezpieczną pamięć i konstrukcję. Takie korzyści mają swoją cenę, a ty napisałeś test, który sprawia, że ​​koszty te dominują w czasie realizacji.

Beldaz
źródło
Brzmi jak świetna informacja na przyszłe pytanie o wydajność sformatowanego wstawiania / wydobywania iostreams, które prawdopodobnie wkrótce zapytam. Ale nie wierzę, że są w to jakieś aspekty ostream::write().
Ben Voigt,
4
+1 za profilowanie (zakładam, że to maszyna z systemem Linux?). Jednak tak naprawdę dodaję cztery bajty naraz (tak naprawdę sizeof i, ale wszystkie kompilatory, z którymi testuję, mają 4 bajty int). I nie wydaje mi się to wcale nierealistyczne, jak myślisz, jakie fragmenty wielkości są przekazywane w każdym wywołaniu xsputnw typowym kodzie stream << "VAR: " << var.x << ", " << var.y << endl;.
Ben Voigt,
39
@beldaz: Ten „typowy” przykład kodu, który wywołuje tylko xsputnpięciokrotnie, równie dobrze może znajdować się w pętli, która zapisuje 10 milionów plików linii. Przekazywanie danych do iostreams w dużych porcjach to o wiele mniej rzeczywisty scenariusz niż mój kod testowy. Dlaczego powinienem pisać do buforowanego strumienia przy minimalnej liczbie połączeń? Jeśli muszę zrobić własne buforowanie, jaki jest sens iostreams? A w przypadku danych binarnych mam opcję samodzielnego buforowania, gdy piszę miliony cyfr do pliku tekstowego, opcja zbiorcza po prostu nie istnieje, muszę zadzwonić operator <<do każdego z nich.
Ben Voigt,
1
@beldaz: Można oszacować, kiedy I / O zaczyna dominować za pomocą prostych obliczeń. Przy średniej szybkości zapisu 90 MB / s, która jest typowa dla obecnych dysków twardych klasy konsumenckiej, opróżnienie bufora 4 MB zajmuje <45 ms (przepustowość, opóźnienie nie jest ważne z powodu pamięci podręcznej zapisu systemu operacyjnego). Jeśli uruchomienie wewnętrznej pętli zajmuje więcej czasu niż zapełnienie bufora, to procesor będzie czynnikiem ograniczającym. Jeśli pętla wewnętrzna działa szybciej, to we / wy będzie czynnikiem ograniczającym lub przynajmniej pozostało trochę czasu procesora do wykonania prawdziwej pracy.
Ben Voigt,
5
Oczywiście nie oznacza to, że używanie iostreams niekoniecznie oznacza powolny program. Jeśli We / Wy jest bardzo małą częścią programu, to użycie biblioteki We / Wy o niskiej wydajności nie będzie miało większego wpływu. Ale to, że nie jest się wystarczająco często wywoływanym, by mieć znaczenie, nie jest tym samym, co dobra wydajność, aw przypadku ciężkich aplikacji we / wy ma to znaczenie.
Ben Voigt,
27

Jestem raczej rozczarowany użytkownikami Visual Studio, którzy raczej się na tym dali:

  • W ramach realizacji programu Visual Studio ostreamThe sentryobiektu (co jest wymagane przez standard) wchodzi do sekcji krytycznej chroniąc streambuf(co nie jest wymagane). Nie wydaje się to opcjonalne, więc płacisz za synchronizację wątków nawet za strumień lokalny używany przez pojedynczy wątek, który nie wymaga synchronizacji.

Uszkadza to kod, który ostringstreamdość poważnie używa do formatowania wiadomości. Użycie stringbufbezpośredniego pozwala uniknąć użycia sentry, ale sformatowane operatory wstawiania nie mogą działać bezpośrednio na streambufs. W Visual C ++ 2010 sekcja krytyczna zwalnia ostringstream::writetrzykrotnie w porównaniu do stringbuf::sputnwywołania bazowego .

Patrząc na dane profilera beldaz na newlib , wydaje się jasne, że gcc sentrynie robi nic takiego szalonego. ostringstream::writepod gcc zajmuje tylko około 50% dłużej niż stringbuf::sputn, ale stringbufsam jest znacznie wolniejszy niż pod VC ++. I oba nadal bardzo niekorzystnie porównują się do korzystania z vector<char>buforowania dla operacji we / wy, chociaż nie o taki sam margines jak w VC ++.

Ben Voigt
źródło
Czy te informacje są wciąż aktualne? Implementacja AFAIK, C ++ 11 dostarczana z GCC wykonuje tę „szaloną” blokadę. Z pewnością VS2010 nadal to robi. Czy ktokolwiek mógłby wyjaśnić to zachowanie, a jeśli „co nie jest wymagane” nadal obowiązuje w C ++ 11?
mloskot
2
@mloskot: Nie widzę żadnych wymagań dotyczących bezpieczeństwa wątków na sentry... „Wartownik klasy definiuje klasę, która jest odpowiedzialna za wykonywanie wyjątkowo bezpiecznych operacji na prefiksach i sufiksach”. oraz notatkę „Konstruktor wartowników i destruktor mogą także wykonywać dodatkowe operacje zależne od implementacji”. Można również przypuszczać, że z zasady C ++ „nie płacisz za to, czego nie używasz”, komitet C ++ nigdy nie zatwierdzi tak marnotrawnego wymogu. Ale nie krępuj się zadać pytanie dotyczące bezpieczeństwa wątku iostream.
Ben Voigt,
8

Problem, który widzisz, jest narzutem wokół każdego wywołania write (). Każdy dodany poziom abstrakcji (char [] -> vector -> string -> ostringstream) dodaje jeszcze kilka wywołań funkcji / zwrotów i inne funkcje porządkowe, które - jeśli wywołasz to milion razy - sumują się.

Zmodyfikowałem dwa przykłady na ideone, aby napisać dziesięć liczb na raz. Czas ostringstream wyniósł od 53 do 6 ms (prawie 10-krotna poprawa), podczas gdy pętla char poprawiła się (3,7 do 1,5) - użyteczne, ale tylko dwa razy.

Jeśli obawiasz się o wydajność, musisz wybrać odpowiednie narzędzie do pracy. Ostringstream jest użyteczny i elastyczny, ale za używanie go w sposób, w jaki próbujesz, grozi kara. char [] to trudniejsza praca, ale wzrost wydajności może być świetny (pamiętaj, że gcc prawdopodobnie wstawi również memcpys dla ciebie).

Krótko mówiąc, ostringstream nie jest zepsuty, ale im bardziej zbliżasz się do metalu, tym szybciej działa Twój kod. Asembler nadal ma zalety dla niektórych ludzi.

Roddy
źródło
8
Co ostringstream::write()musi to zrobić, że vector::push_back()nie? Jeśli już, to powinno być szybsze, ponieważ przekazał blok zamiast czterech pojedynczych elementów. Jeśli ostringstreamjest wolniejszy niż std::vectorbez żadnych dodatkowych funkcji, to tak nazwałbym to zepsute.
Ben Voigt,
1
@Ben Voigt: Wręcz przeciwnie, jego coś musi zrobić, że ostringstream NIE musi tego robić, dzięki czemu wektor jest bardziej wydajny w tym przypadku. Wektor ma zagwarantowaną ciągłość w pamięci, podczas gdy ostringstream nie. Wektor jest jedną z klas zaprojektowanych z myślą o wydajności, podczas gdy ostringstream nie.
Dragontamer5788,
2
@Ben Voigt: stringbufBezpośrednie użycie nie spowoduje usunięcia wszystkich wywołań funkcji, ponieważ stringbufpubliczny interfejs składa się z publicznych nie-wirtualnych funkcji w klasie bazowej, które następnie wysyłają do chronionej funkcji wirtualnej w klasie pochodnej.
CB Bailey,
2
@Charles: Powinien to zrobić każdy przyzwoity kompilator, ponieważ publiczne wywołanie funkcji zostanie wprowadzone do kontekstu, w którym typ dynamiczny jest znany kompilatorowi, może usunąć pośrednie, a nawet wbudować te wywołania.
Ben Voigt,
6
@Roddy: Myślę, że to wszystko wbudowany kod szablonu, widoczny w każdej jednostce kompilacyjnej. Ale myślę, że może się to różnić w zależności od wdrożenia. Z pewnością spodziewałbym się, że omawiane połączenie, sputnfunkcja publiczna, która wywołuje funkcję wirtualnej ochrony xsputn, zostanie podkreślona. Nawet jeśli xsputnnie jest wbudowany sputn, kompilator może podczas wstawiania określić dokładne xsputnwymagane zastąpienie i wygenerować bezpośrednie wywołanie bez przechodzenia przez vtable.
Ben Voigt,
1

Aby uzyskać lepszą wydajność, musisz zrozumieć, w jaki sposób działają używane pojemniki. W przykładzie tablicy char [] tablica o wymaganym rozmiarze jest przydzielana z góry. W przykładzie wektorowym i ostringstream wymuszasz na obiektach wielokrotne przydzielanie, realokację i ewentualnie kopiowanie danych wiele razy w miarę wzrostu obiektu.

W przypadku std :: vector można to łatwo rozwiązać, inicjując rozmiar wektora do ostatecznego rozmiaru, podobnie jak w przypadku tablicy znaków; zamiast tego raczej niesprawiedliwie paraliżujesz wydajność, zmieniając rozmiar na zero! To nie jest sprawiedliwe porównanie.

Jeśli chodzi o ostringstream, wstępna alokacja przestrzeni nie jest możliwa, sugerowałbym, że jest to niewłaściwe zastosowanie. Klasa ma znacznie większą użyteczność niż zwykła tablica znaków, ale jeśli nie potrzebujesz tego narzędzia, nie używaj go, ponieważ w każdym razie zapłacisz koszty ogólne. Zamiast tego należy go użyć do tego, do czego jest dobry - formatowanie danych w łańcuch. C ++ zapewnia szeroką gamę pojemników, a ostringstram należy do najmniej odpowiednich do tego celu.

W przypadku wektora i ostringstream otrzymujesz ochronę przed przepełnieniem bufora, nie dostajesz tego z tablicą char, a ta ochrona nie jest bezpłatna.

Clifford
źródło
1
Przydział nie wydaje się być problemem dla ostringstream. Po prostu dąży do zera w kolejnych iteracjach. Bez obcinania. Próbowałem też ostringstream.str.reserve(4000000)i to nie miało znaczenia.
Roddy
Myślę, że za pomocą ostringstreammożna „zarezerwować”, przekazując fikcyjny ciąg, tzn .: ostringstream str(string(1000000 * sizeof(int), '\0'));Za pomocą vector, resizenie zwalnia żadnej przestrzeni, rozszerza się tylko w razie potrzeby.
Nim,
1
„wektor .. ochrona przed przepełnieniem bufora”. Powszechne nieporozumienie - vector[]operator zazwyczaj NIE jest sprawdzany pod kątem błędów granic. vector.at()jest jednak.
Roddy
2
vector<T>::resize(0)zwykle nie
przenosi
2
@Roddy: Nie używam operator[], ale push_back()(przy okazji back_inserter), które zdecydowanie testują przepełnienie. Dodano kolejną wersję, która nie używa push_back.
Ben Voigt,