Как продеть слона через игольное ушко. Обработка максимальных объемов данных за минимальное время
Чего только не услышишь от апологетов тех же Java или C# про разработку на C/C++! Якобы этот язык устарел и на нем никто не пишет. Вот только когда требуется создать no latency или low latency сервис или нужно сэкономить память и время выполнения узкого места обработки больших объемов данных, то тут же прибегают за помощью к «архаичным» разработчикам на C/C++. Просто потому, что эти ребята умеют вручную управлять памятью и прекрасно представляют, что за начинка у той или иной высокоуровневой операции. Сегодня наша задача — стать на шаг ближе к этим ребятам.
Под капотом гоночной машиныБизнес-логика сетевого приложения — это обычно не то место, где предпочитают использовать C++ как язык разработки. Как правило, для сетевого взаимодействия между клиентами приложения и серверами базы данных выбирают более высокоуровневые языки. Но рано или поздно приложение разрастается до уровня, когда его дешевле оптимизировать, чем закупать новые серверы. В этом случае нам предстоит увлекательный аттракцион встраивания реализации части бизнес-логики на C/C++ в устоявшуюся логику на C#, Java, Python, Ruby или JavaScript. Тут тебя, вероятно, ждет презабавный сюрприз: на C++ нужно уметь обрабатывать большие объемы данных эффективно. Навыки в Java или C# быстро сведут на нет все попытки оптимизации, если ты просто попробуешь написать примерно такой же код на C++.Дело в том, что применять new следует максимально экономно, а нерациональное использование не совсем подходящих к ситуации контейнеров сделает совершенно логичный код абсолютно непригодным на практике. Вполне возможно, что после «оптимизации», проведенной сотрудником, не вполне квалифицированным именно в C++, время выполнения может остаться примерно тем же или даже увеличиться. Кто-то разведет руками, мол, старались, но тут все и так оптимизировано донельзя. Кто-то попытается убедить коллег в немыслимой скорости высокоуровневого языка. Наша задача в том, чтобы деньги фирмы не были потрачены зря. Чтобы затраты ресурсов на встраивание C/C++ в критические участки кода не только не оказались напрасными, но многократно окупились. Ценятся не те специалисты, что разводят руками и говорят «ну не смогли», а те, что добиваются невозможного. Ведь невозможным оно только кажется, и ничего сложного в этом уроке не будет. Все, что потребуется, — это запомнить несколько важных вещей, которые пригодятся при обработке данных на C++.
Выбираем инструменты тщательно Если тебе еще не посчастливилось прочитать замечательную книгу «Эффективное использование STL» Скотта Мейерса, я ее крайне рекомендую. Без детального понимания того, для какой ситуации в C++ нужен тот или иной контейнер, использование STL будет сродни ремонту асфальта в дождь. Некоторые основные советы я все же дам, но важно досконально разбираться в предназначении разных контейнеров и устройстве их методов.Первое, что следует всегда помнить: `std: vector` — это не массив, а именно вектор. Используй этот контейнер, если нужна именно векторизация непрерывного куска памяти в виде однотипных элементов. Если же требуется регулярное добавление и удаление при неконтролируемом размере, то `std: vector` вряд ли пригодится. Когда нужен именно массив с поэлементным доступом и недорогим увеличением размера, смотри лучше в сторону `std: deque`. Ведь если нам не будет хватать зарезервированной памяти, то произойдет сначала выделение нового непрерывного (!) блока, а затем перенос данных из старой памяти объекта `std: vector` в новую поэлементно. Поскольку мы рассматриваем обработку больших объемов данных за наименьшее время, перераспределение памяти под уже существующие объекты — это совсем не то, на что хочется тратить процессорное время.
Второе необходимое условие — это тщательный выбор контейнера с соотношением уникального ключа и значения. В случае больших данных, вероятно, проще всего сразу построить `std: unordered_map` и стараться как можно реже его изменять. Дело в том, что взятие по ключу в `std: unordered_map` куда эффективнее, чем в `std: map`, опять же для больших объемов данных не нужно выстраивать и поддерживать в памяти красно-черное дерево с непомерным количеством узлов. Но если соотношение ключ — значение часто изменяется (удаляются соотношения, добавляются новые, и это делается достаточно интенсивно), то проще смириться с поддержанием `std: map`, чем раз за разом перестраивать внутреннее представление `std: unordered_map`. Ведь внутри `std: unordered_map`, по сути, массив цепочек значений, и чем чаще мы изменяем соотношение ключ — значение, тем менее эффективным становится его использование. Здесь не спасет даже более быстрое извлечение по ключу: перестроение больших массивов — это всегда дорого.
Третий важный момент — это логика. Сначала напиши наиболее эффективный алгоритм, а затем смотри, что логически подходит для хранения данных при его работе. Всегда старайся выбирать контейнер единственно очевидным способом. Нужен набор уникальных значений — бери `std: set`, нужен словарь, который редко меняется — смело используй `std: unordered_map`, нужен массив, и заранее не знаешь его размер — скорее всего, понадобится `std: deque`, если же размер массива заранее известен, то может подойти и обычный `std: vector`.
Четвертое — это замеры производительности. Всегда следует проверять свое решение о выборе контейнера или алгоритма сравнительным анализом с тестированием времени выполнения на схожих контейнерах. Так, может статься, что отсортированный `std: vector` пар ключ — значение может быть эффективнее в обработке, чем логично подходящий `std: map`, построенный по этому соотношению.
У тебя могут быть любые идеологические взгляды на программный код, но единственный авторитет, которому ты должен доверять, — это профилировщик, который выдает замеры времени выполнения кода при разных вариантах его построения.
Затраты на текст Первое и главное, что следует усвоить при работе с текстом: `std: string` не единственный способ сохранить и обработать текст или его часть. В случае подстроки совершенно не обязательно заводить под каждый кусок большой строки миллионы новых контейнеров `std: string`, достаточно указать на начало и конец каждой подстроки. Лучше завести свою структуру с парой итераторов begin/end на исходной строке, чем для каждой подстроки строить новый непрерывный блок памяти и копировать в него часть и так хранящегося в исходной строке текста.Пример: находим все слова в тексте, представленном в виде указателя на null-terminated строку. Пусть для простоты наши слова разделены символом точки с запятой.
template
JSON, XML и все-все-все К работе с текстовыми протоколами следует подходить как можно аккуратнее. Как показывает предыдущий пример, малейший просчет при создании вспомогательных объектов может убить производительность совершенно безобидным на первый взгляд кодом.Для каждого из общепринятых протоколов есть целый выводок библиотек. Но следует помнить простые истины.
Первое и главное. Тебе почти никогда не стоит строить полное дерево для структуры XML/JSON/YAML при ее чтении откуда бы то ни было. Обычно все сводится к извлечению ряда однотипных значений.
Второе: не гнушайся изобретать велосипед, если задача критична по производительности, а случай у тебя настолько частный, что отказаться от протоптанной тропинки будет верным решением.
Третье: при сериализации, пожалуйста, постарайся обойтись генерацией в буфер на стеке. Если это невозможно, то пиши в `std: string` с заблаговременным вызовом reserve. Код никогда не получится эффективным, если ты сначала мусоришь по всей оперативной памяти использованием `std: stringstream`, а затем еще и собираешь из него строку, дополнительно склеивая то, что можно сразу собрать в результат.
В качестве домашнего задания сравни по производительности генерацию большой текстовой конфигурации в тот же XML с использованием `std: stringstream` и без него. Оперативная память в виде сыра с кучей дырок фрагментации не располагает к быстродействию.
База ответит При запросе к базе данных мы на этапе компиляции не знаем, какого типа значения к нам придут. Точнее, мы можем построить строку запроса, можем даже обернуть это в простенький SQL-like ORM на стороне C++, но главное — на этапе компиляции мы почти никогда не знаем, что база данных говорит в ответ.В этом плане динамически типизируемые языки с генерацией атрибутов на лету вроде тех же Python, Ruby и JavaScript имеют перед компилируемыми языками со статической типизацией несомненное преимущество.
Можно, конечно, понаделать всевозможных типов вроде `IntField`, `FloatField` и прочих `*Field` с общим предком наподобие `BaseField`, а затем мучиться по всем веткам кода, используя приведение ссылок и указателей. Это приведет к фрагментации единого, в общем-то, ответа от базы данных — он окажется распихан по маленьким ячейкам памяти.
Однако, вспомнив первые три урока нашей академии, мы можем легко обойти ограничения языка C++ и при этом получить удобоваримый API. Все, что нам остается, — это минимизировать затраты на динамическое выделение памяти на каждое поле в каждой записи. Это сделать не так уж и сложно.
Классические СУБД в ответ на SQL-запрос выдают нам табличные данные, то есть мы знаем формат каждой записи, пусть и на этапе выполнения, а не на этапе компиляции. По структуре записи мы можем изначально выделить память под все данные всех полей в сумме. В дальнейшем рассовывать значения полей по заготовленным ячейкам памяти нам поможет старый добрый `placement new`. Выглядит это примерно так:
Из метаданных запроса мы узнаем тип данных каждого поля в результатах запроса. Для каждого типа на стороне базы данных у нас есть аналогичный тип на стороне бизнес-логики. Скалярные данные — это данные с фиксированным размером, выделять память для них означает оставлять место в буфере, им не нужен даже конструктор. Чуть сложнее с данными, которые выделяют дополнительную память в куче, как, например, `std: string` для представления типа `text`. Однако сам `std: string` имеет определенный размер, так что можем сказать, будто для любого типа поля в базе данным мы знаем тип и размер на стороне бизнес-логики.
Далее банально складываем размеры типов полей записи и получаем размер блока данных под каждую запись. Для выделения памяти под весь результат запроса мы можем выделить память один раз для всех полей. Получится, что в кучу за памятью мы лезем лишь однажды, сразу после чтения полей из метаданных результата запроса. Сложность операции кратна количеству полей в результате запроса: даже если запрошена тысяча полей, это куда проще, чем выделять память под 1000 × *количество записей в результате* под малопонятные IField*.
Для удобства обработки данных некий класс field нам все же придется построить. Он будет представлять собой контейнер с динамически типизируемыми данными из первых двух лекций «Академии C++». По сути, в каждом будет по значению, но опционально хранится тип — он соответствует типу в результате запроса в соответствующей ячейке данных, либо NULL.
Поскольку подавляющее большинство хранящихся в базе типов данных — текстовые, возможно, имеет смысл инлайнить небольшие строки с ограниченным размером на стороне базы данных не в `std: string`, который полезет в кучу, а непосредственно в память `field`. В этом случае мы получим неплохую оптимизацию при выделении памяти, но придется помучиться с реализацией нужных методов, поскольку сам по себе `char m_text[SIZE]` делать ничего не будет, а возможности чистого си по работе со строками и памятью не адаптированы для работы с базой данных.
Теперь главное: выделив память под каждый тип в записи, создаем данные поля с помощью конструкции `new (<куда>) Тип (<параметры>)`.
Вот как это должно выглядеть в реализации. Главный класс — это контейнер поля, динамически типизируемый от любого используемого тобой типа в базе данных. Если у тебя только скалярные типы, текстовые данные и NULL, то получится примерно вот так:
class field
{
public:
template
template
template
bool is_null () const;
protected: class data;
private: data* m_data; };
class field: data {…};
template
template
<остальное не меняется> private: data* m_data; uint8_t m_buffer[MAX_FIELD_SIZE]; }; Теперь тебе понятна и тщательность, с которой я описывал механизмы динамической типизации в начале курса «Академии», и то, почему еще во втором уроке говорилось об экономии памяти при размещении данных заранее неизвестного типа внутри класса.Какой бы путь ты ни выбрал, единый блок памяти для всей записи или даже для всего результата запроса на стороне бизнес-логики либо гибкое управление деком полей в каждой записи все равно будет лучше, чем массовое выделение памяти под каждое поле и работа с ними через указатели на интерфейсы, между которыми будет постоянное приведение типов.
Тихо! Идет запись! В обоих случаях класс записи будет работать примерно так: Инициализация некоторым набором информации о полях. Выделение памяти по метаинформации произойдет лишь однажды. Затем в цикле заполняется список полей записи, со смещением относительно общей памяти для каждого последующего поля записи. Если информация о полях пришла сразу со значениями, то сразу инициализируем поля вместе со значениями прямо по нужному адресу. Реализация записи будет выглядеть немного по-разному в зависимости от того, будет ли у тебя монолитный блок данных под всю запись, или же это набор взаимозаменяемых однотипных элементов с динамически типизуемым содержимым. Приведу пример того, как может выглядеть реализация записи для единого блока памяти: class record { public: record (query_result const& result, size_t row);
// Доступ к данным через контейнер field field [const]& operator[](<здесь нужны перегрузки от int, char const* и std::string const&>) [const];
private:
std: vector
record: record (query_result const& result, size_t row)
{
size_t buffer_size = std: accumulate (
result.types ().begin (),
result.types ().end (),
0,
[](size_t init, field: type type){
return init + type.size ();
});
m_buffer.resize (buffer_size);
m_fields.reserve (result.types ().size ());
for (size_t offset=0, index=0;
index <здесь все останется как было> private:
std: vector Не добавляй в алгоритм лишних шагов — это и есть самая главная оптимизация. Бессмертный и бессменный
Главное, что нужно усвоить, — язык C++, как и си, предоставляет прямой доступ к памяти процесса, причем в первую очередь важна память в стеке, а во вторую — память внутри заранее выделенных и подготовленных к использованию буферов. Никакие Java, C# или Python и близко не подойдут к показателям программ, грамотно написанных на C/C++, именно потому, что защищают программиста от неправильной работы с памятью. Мы можем выделить на стеке несколько килобайтов памяти под пакет протокола, заполнить ее, пробежав указателем, и выдать ссылку на буфер на стеке в функцию отправки по сети. Нам не нужно городить никаких `std: vector` для этого, достаточно `uint8_t packet_buffer[MAX_PACKET_SIZE]` в стиле чистого и незамутненного си.Язык C++, в свою очередь, предоставляет возможность надстраивать удобные высокоуровневые языковые конструкции поверх конструкций языка си, и этим нужно пользоваться. Грех не использовать конструкторы и деструкторы и генерацию исключений, не говоря уже о шаблонах. Если этой кухней владеешь, то и печеньки получатся годными, а если нет, то извини: по соседству есть автоматическая микроволновка (та же Java), попробуй испечь печеньки в ней. Язык C++ отлично подходит как для оптимизаций алгоритмов, реализованных на высокоуровневых языках, так и для того, чтобы выжать все из своего кода. Для этого совсем не обязательно знать сложность обхода `std: map` — порой нужно просто взять и использовать вместо `vector of vector` обычный `T**`. Или вместо генерации непотребных размеров `std: string` для отправки по сети просто взять и сделать все на стеке. Главное — иметь светлую голову и немножко думать над тем, что ты делаешь в каждой строчке кода. Не делается ли что-то лишнее? Ведь именно отсекая лишнее, подобно скульптору, мы оптимизируем скорость выполнения нашего кода. Успехов тебе в высоком искусстве оптимизации! Впервые опубликовано в журнале Хакер #195.Автор: Владимир Qualab Керимов, ведущий С++ разработчик компании Parallels Подпишись на «Хакер»
