C++. Optymalizacja kodu

Book description

C++. Optymalizacja kodu

Table of contents

  1. Okładka Strona
  2. Tytuł Strona
  3. Prawa autorskich Strona
  4. Poświęcenie Strona
  5. Spis treści
  6. Przedmowa
    1. Potencjalne problemy z kodem
    2. Korzystanie z przykładowego kodu
    3. Konwencje użyte w tej książce
  7. 1 Wprowadzenie do optymalizacji
    1. Optymalizacja to część procesu rozwoju oprogramowania
    2. Optymalizacja jest efektywna
    3. Optymalizacja jest OK
    4. Nanosekunda tu, nanosekunda tam
    5. Podsumowanie strategii optymalizacji kodu C++
      1. Użyj lepszego kompilatora, lepiej używaj kompilatora
      2. Użyj lepszych algorytmów
      3. Użyj lepszych bibliotek
      4. Zredukuj alokację pamięci i kopiowanie
      5. Usuń obliczenia
      6. Użyj lepszych struktur danych
      7. Zwiększ równoległość
      8. Zoptymalizuj zarządzanie pamięcią
    6. Podsumowanie
  8. 2 Wpływ działania komputera na optymalizację
    1. Nieprawdziwe przekonania języka C++ o komputerach
    2. Prawda o komputerach
      1. Pamięć jest powolna
      2. Dostęp do pamięci nie zamyka się w bajtach
      3. Nie wszystkie operacje dostępu do pamięci są równie wolne
      4. Słowa mają najbardziej i najmniej znaczący koniec
      5. Pamięć ma ograniczoną pojemność
      6. Wykonanie instrukcji zabiera dużo czasu
      7. Komputery mają trudności z podejmowaniem decyzji
      8. Istnieje wiele strumieni wykonania programu
      9. Wywoływanie systemu operacyjnego jest kosztowne
    3. C++ również kłamie
      1. Różne instrukcje mają różny koszt
      2. Instrukcje nie są wykonywane kolejno
    4. Podsumowanie
  9. 3 Mierzenie wydajności
    1. Mentalność optymalizatora
      1. Wydajność musi być mierzona
      2. Optymalizatorzy polują na grubą zwierzynę
      3. Reguła 90/10
      4. Prawo Amdahla
    2. Przeprowadzanie eksperymentów
      1. Prowadź notatnik laboratoryjny
      2. Mierzenie bazowej wydajności i wyznaczanie celów
      3. Można poprawić tylko to, co zostało zmierzone
    3. Działanie programu profilującego
    4. Pomiary czasowe długotrwałych zadań
      1. „Odrobina wiedzy” o mierzeniu czasu
      2. Mierzenie czasu przy użyciu komputerów
      3. Pokonywanie trudności w mierzeniu
      4. Tworzenie klasy stopera
      5. Mierzenie czasu aktywnych funkcji w warunkach testowych
    5. Szacowanie kosztu kodu w celu znalezienia aktywnego kodu
      1. Szacowanie kosztu pojedynczych instrukcji C++
      2. Szacowanie kosztu pętli
    6. Inne sposoby odnajdowania aktywnych punktów
    7. Podsumowanie
  10. 4 Optymalizowanie użycia ciągów: przykład
    1. Dlaczego ciągi są tak problematyczne
      1. Ciągi są dynamicznie alokowane
      2. Ciągi to wartości
      3. Ciągi wymagają wiele kopiowania
    2. Pierwsze podejście do optymalizacji ciągów
      1. Użyj operacji mutujących do eliminowania wartości tymczasowych
      2. Redukuj realokację poprzez rezerwację obszaru
      3. Eliminuj kopiowanie argumentów std::string
      4. Eliminuj wyłuskania wskaźników przy użyciu iteratorów
      5. Eliminuj kopiowanie wartości zwrotnych
      6. Użyj tablic znaków zamiast ciągów
      7. Podsumowanie pierwszego podejścia do optymalizacji
    3. Drugie podejście do optymalizacji ciągów
      1. Użyj lepszego algorytmu
      2. Użyj lepszego kompilatora
      3. Użyj lepszej biblioteki ciągów
      4. Użyj lepszego alokatora
    4. Eliminowanie konwersji ciągów
      1. Konwersja z ciągu C do std::string
      2. Konwersja między kodowaniami znaków
    5. Podsumowanie
  11. 5 Optymalizowanie algorytmów
    1. Koszt czasowy algorytmów
      1. Koszt czasowy w najlepszym, średnim i najgorszym przypadku
      2. Amortyzowany koszt czasowy
      3. Inne koszty
    2. Zestaw narzędzi do optymalizacji wyszukiwania i sortowania
    3. Efektywne algorytmy wyszukiwania
      1. Koszt czasowy algorytmów wyszukiwania
      2. Wszystkie wyszukania są równie dobre dla małych n
    4. Efektywne algorytmy sortowania
      1. Koszt czasowy algorytmów sortowania
      2. Zastąpienie algorytmów sortowania o niewydajnym najgorszym przypadku
      3. Eksploatowanie znanych właściwości danych wejściowych
    5. Wzorce optymalizacji
      1. Wstępne obliczanie
      2. Opóźnione obliczanie
      3. Przetwarzanie wsadowe
      4. Buforowanie
      5. Specjalizacja
      6. Pobieranie większych porcji
      7. Wskazówki
      8. Optymalizowanie oczekiwanej ścieżki
      9. Mieszanie
      10. Podwójne sprawdzanie
    6. Podsumowanie
  12. 6 Optymalizacja zmiennych dynamicznych
    1. Powtórzenie wiadomości o zmiennych C++
      1. Czas magazynowania
      2. Własność zmiennych
      3. Obiekty wartości i obiekty encji
    2. Powtórzenie wiadomości o API zmiennych dynamicznych w C++
      1. Sprytne wskaźniki automatyzują zarządzanie własnością zmiennych dynamicznych
      2. Dynamiczne zmienne wpływają na koszt czasowy wykonania
    3. Redukowanie użycia zmiennych dynamicznych
      1. Twórz instancje klas statycznie
      2. Używaj statycznych struktur danych
      3. Użyj std::make_shared zamiast new
      4. Nie dziel się własnością niepotrzebnie
      5. Użyj „głównego wskaźnika” jako właściciela zmiennych dynamicznych
    4. Redukowanie realokacji zmiennych dynamicznych
      1. Wstępnie alokuj zmienne dynamiczne, aby zapobiec realokacji
      2. Twórz zmienne dynamiczne poza pętlą
    5. Eliminowanie niepotrzebnego kopiowania
      1. Wyłącz nieumyślne kopiowanie w definicji klasy
      2. Wyeliminuj kopiowanie podczas wywoływania funkcji
      3. Wyeliminuj kopiowanie podczas powrotów z funkcji
      4. Biblioteki bez kopiowania
      5. Implementuj idiom „kopiowanie przy zapisie”
      6. Stosuj wycinki struktur danych
    6. Implementowanie semantyki przenoszenia
      1. Niestandardowa semantyka kopiowania: desperackie rozwiązanie
      2. std::swap(): semantyka przenoszenia dla ubogich
      3. Współwłasność encji
      4. Przenoszone części semantyki przenoszenia
      5. Uaktualnij kod w celu użycia semantyki przenoszenia
      6. Subtelności semantyki przenoszenia
    7. Spłaszczanie struktur danych
    8. Podsumowanie
  13. 7 Optymalizowanie aktywnych instrukcji
    1. Usuwanie kodu z pętli
      1. Buforuj wartość końcową pętli
      2. Użyj bardziej efektywnych instrukcji pętli
      3. Odliczaj w dół zamiast w górę
      4. Usuń z pętli niezależny kod
      5. Usuń z pętli niepotrzebne wywołania funkcji
      6. Usuń z pętli ukryte wywołania funkcji
      7. Usuń z pętli kosztowne, wolno zmieniające się wywołania
      8. Przesuń pętle do funkcji, aby zredukować dodatkowy koszt wywołań
      9. Rzadziej wykonuj niektóre akcje
      10. A co z całą resztą?
    2. Usuwanie kodu z funkcji
      1. Koszt wywołań funkcji
      2. Deklaruj krótkie funkcje jako inline
      3. Definiuj funkcje przed pierwszym użyciem
      4. Eliminuj niepotrzebny polimorfizm
      5. Usuń nieużywane interfejsy
      6. Wybieraj implementację w czasie kompilacji przy użyciu szablonów
      7. Eliminuj zastosowania idiomu PIMPL
      8. Eliminuj wywołania bibliotek DLL
      9. Użyj statycznych funkcji składowych zamiast funkcji składowych
      10. Przenieś wirtualny destruktor do klasy podstawowej
    3. Optymalizowanie wyrażeń
      1. Uprość wyrażenia
      2. Grupowanie stałych
      3. Użyj mniej kosztownych operatorów
      4. Używaj arytmetyki liczb całkowitych zamiast arytmetyki liczb zmiennoprzecinkowych
      5. Typ double może być szybszy niż float
      6. Zastąp obliczenia iteracyjne wzorami
    4. Optymalizacja idiomów przepływu sterowania
      1. Użyj switch zamiast if – else if – else
      2. Użyj funkcji wirtualnych zamiast switch lub if
      3. Korzystaj z bezkosztowej obsługi wyjątków
    5. Podsumowanie
  14. 8 Zastosowanie lepszych bibliotek
    1. Optymalizacja użycia biblioteki standardowej
      1. Filozofia standardowej biblioteki C++
      2. Problemy ze stosowaniem standardowej biblioteki C++
    2. Optymalizowanie istniejących bibliotek
      1. Zmieniaj tak mało, jak to tylko możliwe
      2. Dodawaj funkcje zamiast zmieniać funkcjonalność
    3. Projektowanie zoptymalizowanych bibliotek
      1. Koduj szybko, ubolewaj w czasie wolnym
      2. W projektowaniu bibliotek ascetyzm to zaleta
      3. Podejmuj decyzje o alokacji pamięci poza biblioteką
      4. Programuj szybkie biblioteki
      5. Łatwiej jest optymalizować funkcje niż framework
      6. Spłaszcz hierarchie dziedziczenia
      7. Spłaszcz łańcuchy wywołań
      8. Spłaszcz wielowarstwowe projekty
      9. Unikaj dynamicznego wyszukiwania
      10. Wystrzegaj się „wszechmocnych funkcji”
    4. Podsumowanie
  15. 9 Optymalizacja wyszukiwania i sortowania
    1. Tabele klucz/wartość wykorzystujące std::map i std::string
    2. Zestaw narzędzi do podnoszenia wydajności wyszukiwania
      1. Dokonywanie bazowego pomiaru
      2. Zidentyfikuj aktywność do zoptymalizowania
      3. Rozłóż aktywność do zoptymalizowania
      4. Zmodyfikuj lub zastąp algorytmy i struktury danych
      5. Przeprowadź proces optymalizacji na niestandardowych abstrakcjach
    3. Optymalizowanie wyszukiwania przy użyciu std::map
      1. Użyj tablic znaków o stałym rozmiarze w roli kluczy std::map
      2. Użyj std::map z kluczami ciągu w stylu języka C
      3. Użyj std::set dla kluczy zawartych w wartościach
    4. Optymalizowanie wyszukiwania przy użyciu nagłówka <algorithm>
      1. Przeszukiwana tabela klucz/wartość w kontenerach sekwencji
      2. std::find(): oczywista nazwa, koszt czasowy O(n)
      3. std::binary_search(): nie zwraca wartości
      4. Wyszukiwanie binarne przy użyciu std::equal_range()
      5. Wyszukiwanie binarne przy użyciu std::lower_bound()
      6. Własna implementacja wyszukiwania binarnego
      7. Własna implementacja wyszukiwania binarnego przy użyciu strcmp()
    5. Optymalizowanie wyszukiwania w tabelach mieszania klucz/wartość
      1. Mieszanie przy użyciu std::unordered_map
      2. Mieszanie, gdy klucze są tablicami o stałej liczbie znaków
      3. Mieszanie, gdy klucze są ciągami zakończonymi znakiem null
      4. Mieszanie z niestandardową tabelą
    6. Konsekwencje abstrakcji Stepanova
    7. Optymalizuj sortowanie przy użyciu standardowej biblioteki C++
    8. Podsumowanie
  16. 10 Optymalizowanie struktur danych
    1. Poznaj kontenery z biblioteki standardowej
      1. Kontenery sekwencji
      2. Kontenery asocjacyjne
      3. Eksperymentowanie z kontenerami biblioteki standardowej
    2. std::vector i std::string
      1. Wpływ realokacji na wydajność
      2. Wstawianie i usuwanie z std::vector
      3. Iterowanie po kontenerze std::vector
      4. Sortowanie kontenera std::vector
      5. Przeszukiwanie kontenera std::vector
    3. std::deque
      1. Wstawianie i usuwanie z std::deque
      2. Iterowanie po kontenerze std::deque
      3. Sortowanie kontenera std::deque
      4. Przeszukiwanie kontenera std::deque
    4. std::list
      1. Wstawianie i usuwanie z std::list
      2. Iterowanie po kontenerze std::list
      3. Sortowanie kontenera std::list
      4. Przeszukiwanie kontenera std::list
    5. std::forward_list
      1. Wstawianie i usuwanie z std::forward_list
      2. Iterowanie po kontenerze std::forward_list
      3. Sortowanie kontenera std::forward_list
      4. Przeszukiwanie kontenera std::forward_list
    6. std::map i std::multimap
      1. Wstawianie i usuwanie z std::map
      2. Iterowanie po kontenerze std::map
      3. Sortowanie kontenera std::map
      4. Przeszukiwanie kontenera std::map
    7. std::set i std::multiset
    8. std::unordered_map i std::unordered_multimap
      1. Wstawianie i usuwanie z std::unordered_map
      2. Iterowanie po kontenerze std::unordered_map
      3. Przeszukiwanie kontenera std::unordered_map
    9. Inne struktury danych
    10. Podsumowanie
  17. 11 Optymalizowanie we/wy
    1. Przepis na odczytywanie plików
      1. Tworzenie ascetycznej sygnatury funkcji
      2. Skracanie łańcucha wywoływania
      3. Redukowanie realokacji
      4. Pobierz większe porcje – użyj większego bufora wejściowego
      5. Pobieraj większe porcje – odczytuj pojedyncze wiersze
      6. Ponowne skracanie łańcucha wywołań
      7. Zmiany, które nie pomogły
    2. Zapisywanie plików
    3. Odczytywanie z std::cin i zapisywanie w std::cout
    4. Podsumowanie
  18. 12 Optymalizowanie równoległości
    1. Powtórzenie informacji o równoległości
      1. Wprowadzenie do świata równoległości
      2. Wykonanie z przeplotem
      3. Spójność sekwencyjna
      4. Wyścigi
      5. Synchronizacja
      6. Atomowość
    2. Powtórzenie informacji o obsłudze równoległości w języku C++
      1. Wątki
      2. Obietnice i przyszłości
      3. Zadania asynchroniczne
      4. Mutexy
      5. Blokady
      6. Zmienne warunkowe
      7. Atomowe operacje na współdzielonych zmiennych
      8. Plany: Przyszłość równoległości w języku C++
    3. Optymalizowanie wielowątkowych programów C++
      1. Wybieraj std::async zamiast std::thread
      2. Dopasuj liczbę wątków do liczby rdzeni
      3. Implementuj kolejkę zadań i pulę wątków
      4. Wykonywanie operacji we/wy w osobnym wątku
      5. Program bez synchronizacji
      6. Usuwanie kodu z uruchamiania i zamykania
    4. Zwiększenie wydajności synchronizacji
      1. Redukuj zakres sekcji krytycznych
      2. Ograniczaj liczbę równoległych wątków
      3. Unikaj problemu masowego pędu
      4. Unikaj konwoju blokady
      5. Zredukuj rywalizację
      6. Nie oczekuj aktywnie w jednordzeniowym systemie
      7. Nie czekaj w nieskończoność
      8. Tworzenie własnego mutexu może być nieefektywne
      9. Ogranicz długość kolejki wyjściowej producenta
    5. Biblioteki wspierające równoległość
    6. Podsumowanie
  19. 13 Optymalizowanie zarządzania pamięcią
    1. Powtórzenie wiadomości o API zarządzania pamięcią w języku C++
      1. Cykl życia zmiennych dynamicznych
      2. Funkcje zarządzania pamięcią alokują i zwalniają pamięć
      3. Wyrażenia new konstruują zmienne dynamiczne
      4. Wyrażenia delete usuwają zmienne dynamiczne
      5. Jawne wywołania destruktora usuwają zmienne dynamiczne
    2. Wysoko wydajne menedżery pamięci
    3. Dostarczanie menedżera pamięci specyficznego dla klasy
      1. Menedżer pamięci o stałym rozmiarze bloku
      2. Arena bloków
      3. Dodawanie specyficznego dla klasy operator new()
      4. Wydajność menedżera pamięci o stałym rozmiarze bloku
      5. Różne warianty menedżera pamięci o stałym rozmiarze bloku
      6. Menedżery pamięci nieobsługujące wielowątkowości są wydajne
    4. Dostarczanie niestandardowych alokatorów
      1. Minimalny alokator C++11
      2. Dodatkowe definicje dla alokatora C++98
      3. Alokator o stałym rozmiarze bloków
      4. Alokator o stałym rozmiarze bloków dla ciągów
    5. Podsumowanie
  20. Indeks
  21. O autorze

Product information

  • Title: C++. Optymalizacja kodu
  • Author(s): Kurt Guntheroth
  • Release date: January 2016
  • Publisher(s): APN Promise
  • ISBN: 9788375411911