Курт Гантерот. Оптимизация программ на C++. Проверенные методы для повышения производительности

400 страниц. Альфа-книга, 2017

Kurt Guntheroth. Optimized C++. Proven Techniques for Heightened Performance. O’Reilly, 2016

«Приветствую вас! Меня зовут Курт, и я кодоголик».

Подход обстоятельный. В начале книги описывается закон Амдала — улучшение времени выполнения \(S_T\):

\(S_T = \dfrac{1}{(1-P)+\frac{P}{S_p}}\),

где \(P\) — доля оптимизированного общего времени выполнения, \(S_p\) — показатель улучшения в оптимизированной части \(P\). Например, если некоторая функция выполнялась 80 процентов всего времени работы программы, а улучшенная её версия стала работать на 30 процентов быстрее, иначе говоря, \(P=0{,}8\), \(S_p=1{,}3\), то \(S_T\approx 1{,}22\).

Глава «Оптимизация, влияющая на поведение компьютера» — очерк того, с какими абстракциями аппаратного и программного обеспечения приходится иметь дело. Большая часть тем — это последовательное улучшение некоторого базового примера.

Boost — огромный набор библиотек.

Антон Полухин. Разработка приложений на C++ с использованием Boost

346 страниц. ДМК Пресс, 2020

Antony Polukhin. Boost C++ Application Development Cookbook. Packt, 2013

Антон Полухин — автор нескольких библиотек Boost, поддерживает ряд старых библиотек и сейчас представляет Россию в международном комитете по стандартизации C++.

Оглавление:

1. Приступаем к написанию приложения
2. Управление ресурсами
3. Преобразование и приведение
4. Уловки времени компиляции
5. Многопоточность
6. Манипулирование задачами
7. Манипулирование строками
8. Метапрограммирование
9. Контейнеры
10. Сбор информации о платформе и компиляторе
11. Работа с системой
12. Касаясь верхушки айсберга

Последняя глава посвящена графам, генератору истинно случайных чисел, переносимым математическим функциям, объединению нескольких тестовых случаев в одном тестовом модуле и манипулированию изображениями.

$ ./our_program.exe --apples=10 --oranges=20

Fruits count: 30

Какие-то вещи уже устарели, потому что стали частью стандарта, например, Boost.Any, Boost.Variant, Boost.Optional, Boost.Tuple, Boost.Bind, Boost.Move (семантика перемещения до C++11), Boost.SmartPtr, Boost.Function. Какие-то вещи просто любопытны. Как, например, имитация finally из языка Java. Полезных вещей в книге можно подсмотреть много, скажем, синтаксический анализ (parsing) сложного ввода с помощью Boost.Spirit. Там используется расширенная форма Бэкуса — Наура (РБНФ, Extended Backus–Naur Form; EBNF).

const bool success = boost::spirit::qi::parse(first, end,

    u4_[y] >> char_('-') >> u2_[m] >> char_('-') >> u2_[d]

);

Книга рассказывает о многих вещах, но довольно поверхностно. Но как ознакомительный обзор вполне годится.

Джереми Сик, Лай-Кван Ли, Эндрю Ламсдэйн. C++ Boost Graph Library

304 страницы. Питер, 2006

Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine. The Boost Graph Library. Addison-Wesley, 2002

Книга по довольно сложной части библиотеки Boost — графовой библиотеке.

Часть I — основные алгоритмы, поиск кратчайшего пути, минимальное о́стовное дерево, компоненты связности, максимальный поток, неявные графы («обход конём»), а также взаимодействие с другими графовыми библиотеками и производительность. Часть II — справочник.

Авторы подробно рассказывают о библиотеке, показывают на примерах, приближённых к реальным, как ею пользоваться: это интернет-маршрутизация, планирование телефонных сетей, задачи молекулярной биологии.

Предисловия Александра Степанова — отдельный жанр. В этом своём четырёхстраничном эссе Александр Александрович успевает снова кратко изложить идеи обобщённого программирования, упомянуть что-нибудь сложное (multi-sorted algebras — многосортные алгебры), написать код на Лиспе, похвалить C++ за выразительность и тут же поругать:

За прошедшие два с лишним десятка лет в языке появились концепции, которых для ещё большей выразительности раньше не хватало. Тогда использовались собственные инструменты библиотеки Boost вместо полноценных концепций. Иначе, как показали авторы, сообщения даже из-за каких-то небольших ошибок были бы абсолютно непонятными, даже сбивающими с толку.

Содержание первой части:

1. Введение
2. Обобщённое программирование в C++
3. Изучаем BGL
4. Основные алгоритмы на графах
5. Задачи нахождения кратчайших путей
6. Задача минимального остовного дерева
7. Компоненты связности
8. Максимальный поток
9. Неявные графы: обход конём
10. Взаимодействие с другими графовыми библиотеками
11. Руководство по производительности

Вторая часть (а это половина книги) — справочное руководство.

Книга не только рассказывает о графах и о том, как пользоваться библиотекой. Также есть главы, которые объясняют, почему во время проектирования создатели выбрали то или иное решение. Например, в деталях описана проблема бинарного метода.

Поизучать, как устроена библиотека BGL, стоит уже хотя бы ради того, чтобы посмотреть, как проектируют библиотеки в рамках парадигмы обобщённого программирования. Там пересекаются многие темы, причём иногда с неожиданной стороны: специализация шаблонов, поиск Кёнига, типажи (traits) и т. д.

В качестве примера строится граф на основе файла с данными об актёрах (для разбора используется библиотека Boost Tokenizer Library), нужно найти кратчайший путь от заданного актёра до Кевина Бэкона. Такую задачу решают в Университете Вирджинии.

Дан ряд целых чисел \(a_i \geqslant 0,\) \(i=\overline{1,n}\). Числа символизируют высоту стен. Сверху идёт дождь, и вода скапливается в ячейках между стенами. В каждом столбце скапливается \(w_i\) воды. Нужно найти количество ячеек с водой: \[W=\sum_{i=1}^{n} w_i.\]

Пример: \[a=(2, 4, 1, 3, 2, 5, 2, 1, 3, 1).\]

⬛⬛⬛⬛⬛⬜⬛⬛⬛⬛

⬛⬜🟦🟦🟦⬜⬛⬛⬛⬛

⬛⬜🟦⬜🟦⬜🟦🟦⬜⬛

⬜⬜🟦⬜⬜⬜⬜🟦⬜⬛

⬜⬜⬜⬜⬜⬜⬜⬜⬜⬜

В столбцах скопилось воды \(w=(0,0,3,1,2,0,1,2,0,0),\) в сумме \(W = 9.\)

В C++11 появились три вида умных (интеллектуальных) указателей: std::unique_ptr, std::shared_ptr и std::weak_ptr. Они избавляют от заботы освобождать память и другие ресурсы (если с ними правильно обращаться).

struct Base

{

    virtual void print() const noexcept

    {

        std::cout << "Base (const)" << std::endl;

    }

 

    virtual void print() noexcept

    {

        std::cout << "Base" << std::endl;

    }

 

    virtual ~Base() = default;

};

У классов в C++03 есть специальные члены-функции: пользовательские конструкторы (custom constructors), конструктор по умолчанию (default constructor), деструктор (destructor), конструктор копирующего присваивания (copy constructor), оператор копирующего присваивания (copy assignment operator). C++11 добавляет перемещающий конструктор (move constructor) и оператор перемещающего присваивания (move assignment operator) и спецификаторы = default и = delete.

Правила, по которым компилятор неявно объявляет и удаляет такие функции, очень сложные. Есть разные версии таблиц с подсказками. Но они показывают только особенности каждой специальной функции в отдельности.

// User declares:

// Compiler implicitly declares:

Конструирование std::shared_ptr

Умный указатель std::shared_ptr имеет очень хитрую вещь — конструктор псевдонима (aliasing constructor).

template <class U>

shared_ptr(const shared_ptr<U>& x, element_type* ptr) noexcept; // C++11

 

template <class U>

shared_ptr(shared_ptr<U>&& x, element_type* ptr) noexcept;      // C++20

Указатель x — владеемый указатель (owned pointer). Ниже подробно рассмотрим его роль.

Указатель ptr — это хранимый указатель (stored pointer), он хранится, но std::shared_ptr им не владеет и не управляет его временем жизни (сюда нужно передать «сырой» указатель).

Представим, что есть класс, например, произвольного числа с плавающей запятой: с помощью шаблона пользователь может задать любые размеры экспоненты и мантиссы (size_t E, size_t M).

template <size_t E, size_t M>

class CustomFloat

{

    // ...

};

Как ограничить пользователя и задать: \(E\geqslant 5\) и \(M\geqslant 10\)? То есть значения \(E=8,\) \(M=23\) подходят:

CustomFloat<8, 23> f{};

А, например, значения \(E=4,\) \(M=10\) должны приводить к ошибке компиляции.

C++11

Стандарт C++11 для таких целей ввёл шаблонную структуру std::enable_if.

template <size_t E, size_t M, std::enable_if<(E >= 5 && M >= 10), size_t>::type = 0>

class CustomFloat

{

    // ...

};

Дана строка, содержащая цифры и некоторые латинские буквы. Нужно найти сумму всех цифр. Рассмотрим несколько решений.

unsigned sumOnlyDigits(const std::string& data)

{

    unsigned sum{};

    for (auto c : data)

    {

        if (isNumber(c))

        {

            sum += c - '0';

        }

    }

    return sum;

}

Код вполне прозрачный, он перебирает символы и находит сумму всех цифр с учётом того, что код '0' — 48, код '1' — 49, код '2' — 50 и т. д. То есть выражение c - '0' даёт числа в диапазоне 0...9 вместо 48...57.

std::accumulate

В STL есть функция std::accumulate из заголовочного файла <numeric>.

unsigned sumOnlyDigits(const std::string& str) noexcept

{

    return std::accumulate(str.cbegin(), str.cend(), 0u,

        [](unsigned partialSum, auto symbol) noexcept {

            return std::isdigit(symbol)

                ? (partialSum + static_cast<unsigned>(symbol - '0')) : partialSum;

        });

}

В языке C++ практически с самого начала его существования есть две реализации ссылочного типа: это указатели (pointers) и ссылки (references). Указатели достались от языка C. Ссылки не заменили указатели во всём, а умные/интеллектуальные указатели (smart pointers) не всегда стоит использовать вместо «сырых» (raw pointers). В C++11 появился новый тип — rvalue-ссылки — который преследует совсем иные цели.

Ссылки появились в C++ ещё в тот момент, когда он миновал этап C with Classes, для перегрузки операторов:

В первом приближении разница между указателями и ссылками такова (для сравнения — ссылки в языках Java и C♯).