Переменные и типы хороши, пока мы находимся внутри логики программы C++. Однако рано или поздно становится нужно передавать информацию между программами, между серверами или даже просто показать типы и значения переменных человеку разумному. В этом случае нам приходится заключать сделку со злобным Сериализатором и расплачиваться производительностью своего кода. В последней лекции Академии C++ мы наконец дошли до главного босса, которого нужно научиться побеждать с минимальными потерями в скорости выполнения кода. Поехали!

Давным-давно...


В стародавние времена мудрые отцы-основатели программирования научили последовательности байтов превращаться в числа, в логические условия, в последовательность действий и даже в объекты реального мира. В каждом языке было много сущностей, но строились они из байтов совершенно по-разному. Порой повторить на одном языке то, что в другом было из коробки, — задача для сильных духом. Куда проще передать объект класса в метод, написанный на другом, более приспособленном для этого языке. Но что делать, если нужный метод находится на удаленной машине или выполняется в отдельном процессе? Нужно превратить нашу логику в байты и передать принимающей стороне, готовой выполнить нужный метод. Так родилась идея сериализации — единое представление в байтах данных и логики программного кода, понятное как на стороне отправителя, так и на стороне получателя.

В этот момент начался хаос. Были попытки построить один Единственно верный эталонный механизм сериализации. Стали появляться и множиться несовместимые между собой протоколы передачи данных. Естественно, на это были свои причины: они служили разным целям и были оптимизированы для обработки разных данных. Сперва волна пошла в мире Java, позже к празднику жизни присоединился C#, искусственно ограниченный при рождении платформой от Microsoft (к счастью, зло частично повержено, славься, C# на всех платформах). Были и наивные попытки веб-разработчиков: от неуклюжего PHP до все более популярного JavaScript на сервере, на клиенте и в твоей кофеварке. Во всех случаях попытки объявить себя единственно верным путем в разработке были обречены. Слишком уж индивидуален каждый разработчик и каждая решаемая задача, а многообразие языков и их внутренних типов не позволяет передавать данные без потерь между двумя диаметрально противоположными по своей сути языками или технологиями. Во все времена языки и платформы объединяло, пожалуй, только одно: почти все они были написаны на C/C++.

Попытки охватить все очередным универсальным языком или технологией разработки будут предприниматься еще не раз. Но наиболее мудрые разработчики давно уже научились договариваться между собой, как упаковать байты сущности так, чтобы при получении можно было распаковать в аналогичную сущность на стороне получателя. Главное, помнить, что на берегу байтовых потоков тебя ждет всегда одно и то же — ненасытный паромщик Сериализатор. Раз за разом он будет поедать время выполнения твоей программы, такт за тактом, а взамен выдавать закодированный текст в XML-формате вместо объекта конфигурации программы или, например, последовательность байтов согласно ASN.1 вместо структуры каталогов файловой системы. И чем сложнее его задача — тем дольше он будет ее выполнять, отнимая драгоценное время и снижая производительность приложения…

Сколько сериализацию ни корми


Вообще говоря, страшных врагов у производительности нашего приложения обычно три:

  1. Бесконтрольное копирование объектов и подобъектов.
  2. Неоправданное динамическое выделение памяти на куче.
  3. Бездумное и неэффективное использование сериализации.

C первыми двумя мы эффективно воевали в предыдущих уроках — вред их явный и бесспорный, а потому основная борьба ведется с ними, и, как правило, успешно.

Но опаснее всех наш третий враг. Казалось бы, что такого в том, чтобы преобразовать несколько целых чисел в строку и передать по сети? В этот момент программист обычно забывает о сложности преобразования, хранения и передачи больших массивов байтов строки, вместо нескольких легковесных байтов числа, что были у него изначально.

Сериализатор — наш самый страшный враг. Без него нам не обойтись, а он все шепчет о том, что если все оставить строками, то мы получим аналог динамической типизации. «И нет смысла трепыхаться, — говорит он, — ведь на стороне клиента от нас ждут строку JSON или XML. Зачем же нам целое число, храни в классе набор строк!» Страшные вещи творят несчастные разработчики, порабощенные таинственным шепотом, повсюду в их коде строки. Те же, что сильнее духом, но не окрепшие разумом, напротив, преобразуют зазря туда-сюда данные в байты и обратно. Радостно потирает руки Сериализатор, видя, как страдает эффективность. И сегодня мы вместе с тобой победим это зло!

Как закалялся код


Чтобы укротить Сериализатор, следует сначала изучить его слабые стороны. Для этого нам, во-первых, потребуются навыки, полученные в предыдущих уровнях:

  • умение обращаться со строками и байтами;
  • понимание сути динамической типизации;
  • оптимизация кода при создании и копировании объектов;
  • представление вещественных чисел в бинарном виде;
  • все остальное из предыдущих уроков.

Во-вторых, как мы помним, строки при передаче данных становятся обычным набором байтов, поэтому любой протокол, что текстовый, что бинарный, оперирует, по сути, байтами. Однако текстовый, как правило, должен быть «человекочитаемым», что означает дополнительную работу Сериализатору при представлении скалярных значений в байтовом эквиваленте. Ведь для того, чтобы просто превратить целое число –123 в байты строки с десятичным представлением числа –123, нужно выполнить не такую уж и простую операцию. Для подобного преобразования в самом C/C++ не предусмотрено совсем ничего, да и стандартная библиотека не радует своим набором:

  • sprintf — позволяет не просто преобразовать число в строку, но и создать форматированное сообщение, что нам пока не нужно;
  • itoa — делает ровно то, что нам нужно: integer-to-array-of-characters;
  • stringstream — очень удобен для создания читаемого кода, но и максимально питателен для Сериализатора.

Также есть библиотека Boost, чей lexical_cast еще менее предназначен для эффективного преобразования числа в строку.

Но для начала давай сами создадим максимально простой велосипед, который решит нашу задачу — представит целое число в десятичном виде, и погоняемся наперегонки с библиотечными функциями. Код нашей функции будет максимально прост, никакого ассемблера:

size_t decstr(char* output, size_t maxlen, int value)
{
  if (!output || !maxlen)
        return 0;
  char* tail = output;
  // Разбираемся со знаком
  if (value < 0)
  {
        *tail++ = '-';
        value = -value;
  }
  // Строим строку наоборот
  size_t len = 0;
  for (; len < maxlen; ++len)
  {
        *tail++ = value % 10 + '0';
        if (!(value /= 10)) break;
  }
  // Поместилось ли
  if (value) return 0;
  // Завершаем строку
  if (len < maxlen) *tail = '\0';
  // Разворачиваем строку
  char *head = output;
  if (*head == '-') ++head; // Пропускаем знак
  for (--tail; head < tail; ++head, --tail)
  {
      char value = *head;
      *head = *tail;
      *tail = value;
  }
  // Возвращаем длину строки
  return len;
}

Теперь смотрим, насколько наша прямолинейная реализация оправдала затраченное на нее время по сравнению с библиотечными функциями (100 миллионов итераций в секундах, процессор i5-2410M, RAM DDR3 4GB, Windows 8.1 x64):

  • decstr: ~3,5;
  • snprintf: ~26;
  • itoa: ~6,2.

В тестах с включенной оптимизацией мы обгоняем стандартные библиотечные функции с соотношением ~1: 8: 2.

Происходит это неслучайно. Дело в том, что алгоритм itoa завязан на базу исчисления, — не всегда 10, часто также требуется 16, и не только. Что до snprintf, то эта функция вообще не знает, что преобразует именно число, так как сперва ей приходится разобрать формат. Наша же функция не делает практически ничего лишнего.

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

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

Погружение в поток байтов


Возвращение сущностей программной логики обратно в первозданную природу байтовых последовательностей никогда не бывает простым. Но для бинарных протоколов превращение целых чисел в байты, как правило, сводится к побайтовой передаче числа, причем принято правило, что старший байт числа передается первым. Другими словами, это означает, что на стороне приемника на подавляющем большинстве машин, где архитектура представления целых чисел идет начиная от младшего байта, мы не сможем просто взять четыре или восемь полученных байт и привести их соответственно к int32_t или int64_t простым приведением типа указателя по смещению, наподобие `*reinterpret_cast<int32_t*>(value_pointer)`.

Чтобы стало понятнее, проиллюстрирую, в каком виде передается 32-разрядное целое число со знаком с машины с x86-архитектурой в большинство бинарных протоколов для передачи по сети. Само число, например –123456789, на уровне обработки процессором и, соответственно, в логике программы будет выглядеть так:

    |  0   |  1   |  2   |  3   |
    | 0xF8 | 0xA4 | 0x32 | 0xEB |

В то время как по сети это значение передастся в обратном порядке:

    |  0   |  1   |  2   |  3   |
    | 0xEB | 0x32 | 0xA4 | 0xF8 |

Если мы просто возьмем массив из байтов и попытаемся получить из него число, интерпретировав наши четыре байта как 32-разрядное целое, у нас на выходе образуется совсем другое число: –349002504. Общего у них, как правило, ничего нет. Для того же, чтобы получить исходное число, нужно либо к полученному значению применить функцию `ntohl` — net-to-host-long-integer, либо просто собрать по указателю на значение в байтовом массиве из четырех последующих байт нужное целое:

inline int32_t splice_bytes(uint8_t const* data_ptr)
{
  return (data_ptr[0] << 24) |
      (data_ptr[1] << 16) |
      (data_ptr[2] <<  8) | 
  data_ptr[3];
}

Эта функция будет чуть дешевле и эффективнее, чем собирать сперва ненужный int32_t в ненужном порядке, чтобы потом перевернуть, как надо, его байты. Кроме всего прочего, эта функция будет работать под любой ARM-платформой, а вот попытка разыменовывать под некоторые ARM-платформы байты как int32_t со смещением, не кратным четырем, приведет к завершению процесса. В общем, при десериализации лучше не делать ничего лишнего.

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

Простой пример мы разбирали в уроке про кодировки. В кодировке текста UTF-8 первым байтом передается метаинформация о том, сколько байтов нужно считать для получения закодированного символа. Для кириллицы, использующей два байта под код в таблице Юникода, первые три бита первого байта всегда 110, а затем уже идет кусок кода символа.

Так же и с целыми числами — старшие байты их в беззнаковых целых почти не используются и прекрасно подходят для передачи метаинформации, для которой зачастую хватает нескольких битов, например разрядность целого: 1, 2, 4 или 8 под кодировку числа. Проще всего, получив первый байт, понять, сколько байтов требуется для считывания числа, потом считать байты как целое и побитово сделать AND с маской без битов метаинформации, получится нужное число за минимум операций.

Для символьных данных внутри бинарного пакета текст кодируется в байты согласно одной из общепринятых кодировок. Преобразования байтов в строки и обратно мы уже проходили.

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

На порядок сложнее разбирать структуры, которые формируются динамически. Здесь пространства для маневра меньше и в помощь нам лишь протокол и условия решаемой нами задачи. Например, для пакета данных в формате ASN.1 нужно сперва прочитать размер заголовка с описанием полей данных, их размера и смещения, разобрать заголовок, после чего настанет пора разбирать уже сами поля по смещению, которое мы изначально не знаем, так как информация об этом приходит на этапе заполнения данных.

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

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

  • идентификатор платежа (UUID 16 байт);
  • сумма платежа (32-разрядное беззнаковое целое);
  • описание (null-terminated строка в UTF-8);
  • адрес оплаты (null-terminated строка в UTF-8).

Поскольку поля 3 и 4, скорее всего, произвольной длины, мы не можем просто взять и получить адрес четвертого поля, для нас это слишком дорого. Если роль логики нашего приложения — ВСЕГДА считывать и обрабатывать эти поля, можно сразу вычислить метку начала четвертого поля и ссылаться на него как на обычную сишную строку. Ни в коем случае не высчитываем значения в std::string без особой на то необходимости — это, во-первых, почти наверняка динамическое выделение памяти под еще одну строку, а во вторых, ненужное копирование данных, которые уже представлены в виде строки, закодированной в UTF-8. Экономить на разборе суммы платежа не имеет смысла, здесь нам в помощь наша функция splice_bytes, а вот идентификатор платежа можно интерпретировать как UUID, просто сославшись на первые байты в начале пакета. На самом деле если и целое число присылать не в обычном для сети формате начиная со старшего байта, а в виде, обычном для серверной логики, то мы получим не просто пакет данных, а вполне рабочий набор данных с указателями на значения, готовые к работе в C/C++.

Теперь пару слов о вещественных числах. На самом деле типы C/C++ float и double по размеру не отличаются от uint32_t и uint64_t и кодируются согласно стандарту IEEE 754 (вспоминаем урок «Все, точка, приплыли!»). Как правило, в бинарных протоколах вещественные числа с плавающей точкой единичной и двойной точности передают и обрабатывают так же, как и целые числа соответствующей разрядности, просто абстрагируясь от наполнения. Ведь для битов в байте неважно, что они значат, целое ли или вещественное число с плавающей точкой.

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

Жатва сериализации


Поговорим о XML, JSON, YAML, где числа становятся строками, а байтовые последовательности дополнительно экранируются, чтобы их можно было передать как строки. Что может быть затратнее попытки закодировать даже килобайтный файл в строку JSON с помощью, например, Base64? Даже простое экранирование кавычек в обычных строках, передаваемых в JSON, уже недешевая операция, и при десериализации, разумеется, потребуется обратная операция. То же касается и экранирования XML-тегов в строках с угловыми скобками в том же SOAP. Здесь Сериализатор властвует безраздельно и собирает такую жатву, о которой в бинарных протоколах даже и не мечтал.

WARNING


Если дорожишь эффективностью при передаче данных, то отдавай предпочтение бинарным протоколам (если, конечно, у тебя есть выбор).

Здесь, в текстовых протоколах, потери чудовищны и неизбежны. Единственный способ их хоть как-то снизить — это придерживаться ряда простых правил. Их всего десять, простыми словами они звучат так:

  1. Минимизируй количество преобразований между сериализованным и десериализованным значением. В идеале мы должны один раз прочитать либо один раз записать одно значение, и то по требованию, только в момент надобности этого поля. Если логика обработки данных у нас сквозная и мы реализуем некий механизм дообработки данных пакета перед передачей его дальше, то есть смысл сохранить исходный пакет данных, передав его же дальше с необходимыми изменениями, и так минимизировать затраты на промежуточную сериализацию/десериализацию.
  2. Не плоди везде и всюду строки под предлогом, что весь пакет данных в JSON или XML по сути одна большая строка. Данные почти всегда приходят типизированными, и тип им дан не просто так. Не так уж и удобно обрабатывать рост/возраст/вес/сумму в виде строки. Особенно учитывая то, что для хранения строки почти наверняка использован контейнер std::string/std::wstring и это привело к копированию данных строкового представления числа и наверняка к выделению данных на куче, вместо того чтобы привести к целому числу, или UUID, или логическому значению true/false.
  3. Оптимизируй по максимуму процесс экранирования строк, преобразования целых и вещественных чисел и логических констант в строку и обратно. Вообще, процесс сериализации и десериализации должен быть тем местом в коде, в котором ты должен быть уверен. Ты должен знать, что уж тут-то не тратится ни одного лишнего кванта времени ни на одно преобразование. Ну не нужно для замены `\"` на `"` в строке реализовывать алгоритм кубической сложности! Также стоит минимизировать создание промежуточных объектов типа std::string для хранения временных результатов, вполне достаточно указателей на исходную строку и строку с выводимым результатом.
  4. Убей в себе желание использовать `std::stringstream`. Помни о том, что в итоге придется делать str() или бегать итератором еще раз по всему, что насобиралось. Это не говоря о сегментированности памяти после активного использования `std::stringstream` во всех местах, где нужна сериализация!
  5. Еще раз: приоритет указателей на символы в строке перед всяческими промежуточными std::string с временными результатами!
  6. Если используешь функции Boost, замеряй время выполнения их работы в сравнении с простейшими велосипедами. Если оказывается, что функции Boost работают в 35 раз медленнее прямого подхода, не делающего ничего лишнего, значит, используются они зря!
  7. Не бойся страшного кода, если на кону эффективность выполнения самого узкого участка кода. Пусть у тебя будет switch в две страницы кода, который выполняет работу 100 миллионов итераций за две секунды, чем полиморфизм с кучей visitor’ов и огромным стеком вызовов, выполняющих ту же работу за пять секунд. Помни, что это по пять серверов вместо каждых двух!
  8. Файлы и прочие бинарные данные не стоит пихать строками в XML/JSON/YAML, есть смысл запросить и передать их отдельным запросом. Самое бестолковое занятие — запаковывать большой бинарный пакет в строку, перекодируя каждый байт, чтобы потом передать его снова как байты, но уже в текстовом протоколе.
  9. Нет ничего зазорного в том, чтобы отказаться от чего-то ненужного или опционального. Например, совершенно необязательно на каждый чих в сериализации писать в лог или генерировать «Войну и мир». Минимизируй любые затраты на сериализацию, не корми Сериализатор сверх того, что он должен получить как неизбежное зло.
  10. Нет никаких авторитетов, за всеми нужно проверять, экспериментируй, замеряй, не верь никому — ни разработчикам библиотек, ни автору книг, ни автору этой статьи, ни самому себе. Верь результату выполнения своего кода, верь только тем цифрам, которые тебе нужно улучшить.

Не делай ничего лишнего сверх того что ты должен делать.

FIN


Итак, наш Сериализатор если не повержен, то уж точно останется недокормленным. Из неизбежного пожирателя эффективности приложения он превратился в твоего послушного слугу. Мы прошли игру под названием Академия C++ до конца. Пришла пора титров.

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

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

Не стесняйся применять новые знания! Ведь только путем проб и ошибок ты получаешь бесценный и в чем-то уникальный опыт. Ни одна книга и ни одна статья в журнале не заменит набитых тобой самим шишек. Дерзай, пробуй! Вероятно, библиотеки STL в свое время не было бы, если бы Александр Степанов не решил, что миру C++ не хватает библиотеки с обобщенными алгоритмами и удобными контейнерами с общей логикой. Не думай, что опыт дается с рождением, он прямо пропорционален пройденному тобой пути по дороге освоения новых возможностей. Главное, чтобы то, что ты делаешь, то, что создаешь сам, тебе нравилось. Это значит — ты на верном пути. Так держать!

image

Впервые опубликовано в журнале Хакер #194.
Автор: Владимир Qualab Керимов, ведущий С++ разработчик компании Parallels


Подпишись на «Хакер»

Комментарии (7)


  1. SerJook
    28.05.2015 15:16
    +9

    А можно просто взять google/protobuf


    1. Qualab
      29.05.2015 19:17
      +1

      Кроме сериализации для передачи по сети, есть ещё сериализация в общепринятые протоколы: JSON, XML, YAML, ASN.1 или любой протокол, которого требует задача. И тут, увы, ваш google/protobuf становится ненужен чуть менее, чем абсолютно.


  1. pinebit
    28.05.2015 23:45

    Или Microsoft Bond


    1. Qualab
      29.05.2015 19:18

      Кто это?


      1. pinebit
        29.05.2015 19:21

        Поищите на гит хабе. Это «новая» технология от Микрософта с открытой лицензией.


  1. gleb_l
    29.05.2015 02:21
    +3

    Очень много лирики и пугания иностранными агентами страшными врагами — хоть енумы делай — враг_программиста_1, враг_программиста_2… враг_программиста_N… Хотя если подумать — выявление врагов у нас сейчас в тренде, так что все наверное ок :(


    1. Qualab
      29.05.2015 19:18

      Не смотрите новости, читайте лучше хорошие журналы.