~ttt/accumulate_performance

Imported from Bitbucket
9bd73433 — Tomasz Kłak 7 years ago
typo fix
9fe8fc29 — tumdum 7 years ago
added README
31b9a30d — tumdum 7 years ago
many small simplifications

refs

master
browse  log 

clone

read-only
https://git.sr.ht/~ttt/accumulate_performance
read/write
git@git.sr.ht:~ttt/accumulate_performance

You can also use your local clone with git send-email.

DISCLAIMER

Nie mam dostępu do źródeł i możliwe, że nie pamiętam treści problemu.

PROBLEM

Przejrzeć całą kolekcję trójek, wybrać najmniejsze wartości jakie wystąpiły na
miejscach pierwszym i drugim. Dodatkowo zebrać stringi będące na miejscu
trzecim rozdzielając je jedną spacją.

Pytanie jakie się nasuneło to czy (mając wydajność na uwadze) tracimy dużo
implementując rozwiązanie przy użyciu std::accumulate w porównaniu do ręcznie
napisanej pętli (ignorując kompletnie wszystkie potencjalne zyski i straty w
czytelności kodu wynikające z tego)?

ANALIZA

Podstawowym problemem tego 'zadania' jest użycie stringów. Jeżeli coś ma być
wydajne, to nie może 'frywolnie' alokować pamięci. Jeżeli możemy pozwolić sobie
na wywalenie tych nieszczęsnych stringów dostaniemy przyśpieszenie o jeden rząd
wielkości (niezależnie czy z użyciem ręcznie pisanej pętli czy std::accumulate).

Drugi problem jaki się narzuca jest potencjalnie moim urojeniem. Otóż, z tego
co pamiętam oryginalny kod wyglądał tak:

    cośtam += " " + aktualnyString;

Jeżeli faktycznie tak było, to już tutaj jest świetna okazja do poprawy.
Zamieniając tą linijkę na:

    cośtam += " ";
    cośtam += aktualnyString;

Zyskamy około 60%. Dlaczego? Wynika to ze sposobu w jaki większość implementacji
realizuje funkcję składową std::string::append. Jeżeli w danym stringu nie ma
już miejsca (capacity) następuje alokacja większego bufora i przeniesienie
zawartości wraz z nową jej częścią już do nowego buffora który staje się
wewnętrznym buforem stringa. Przy realokacji nowy rozmiar bufora jest dobierany
tak aby zminimalizować przyszłe realokację (w gcc, nowy rozmiar jest 2 razy
większy od starego). Tak więc sklejanie jednoznakowego literału ze stringiem
zawsze podowuję kosztowną realokację. Doklejanie do potencjalnie już dużego
ciągu znaków niekoniecznie.

Co do samego problemu ręcznej pętli vs accumulate. Najprostsze rozwiązanie ma
ciekawą charakterystykę wydajności. Jest aż 1300 razy wolniejsze od
najwydajniejszej wersji :D. Jest to spowodowane poleganiem na wersji
std::accumulate używającej operatora +. To ograniczenie 'wymusza' zwracanie
wyniku przez wartość i kosztowne kopiowanie długiego ciągu znaków.

Na szczęście jest też druga wersja std::accumulate, która oczekuje dodatkowego
operatora binarnego w postaći funktora. Treść standardu nie narzuca sposobu
zwracania wartość przez ten funktor. Nie jest też on częścią jakiejkolwiek
konwencji w światku c++, co pozwala na zwracanie przez referencję i 'sprytny'
operator przypisania wykrywający przypisanie do samego siebie. Różnica pomiędzy
taką implementacją a pętlą ręczną z poprawionym łączeniem stringów jest
niewielka, około 9%.

NOTATKI

main.cpp zawiera testy wydajnościowe porównujące rożne implementacje.
append_performance.cpp pokazuje empirycznie jak się zachowuje std::string z gcc.