[Из песочницы] Масштабируемая библиотека сериализации/десериализации JSON01.10.2015 13:48

Не так давно я участвовал в проекте написания прошивки для некоторого устройства. В процессе работы возник вопрос, а как, собственно, взаимодействовать с «большим братом» (управляющим компьютером)? Поскольку в качестве «большого брата» закладывались совершенно разные устройства (различные смартфоны, планшеты, ноутбуки с различными ОС и прочее), планировалось использовать web-приложение, что диктовало использование JSON для обмена сообщениями.

В итоге получилась легкая и быстрая библиотека сериализации/десериализации JSON. Основные фичи данной библиотеки:

• в базовом функционале (без использования контейнеров STL) не использует динамическую память, вообще;
  
• состоит только из заголовочных файлов (headers-only);
  
• есть поддержка контейнеров STL;
  
• позволяет создавать расширения для обработки произвольных типов.
  

Немного лирики

Изначально, на написание своей библиотеки сериализации меня сподвиг этот пост. К сожалению, тот вариант мне не подходил, поскольку использует STL и использовать его на контроллере, в котором всего-то 1МБайт флеша и 198кБайт ОЗУ, мягко говоря, странно. Но понравилась идея описания полей для сериализации. Примерно аналогично выглядит синтаксис и у boost::serialization. Он и был взят за основу.

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

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

1. строят дерево разбора по входной строке, потом примеряют данное дерево к объекту, в который десериализуют сообщение (это, например, Qt, jsoncpp или jsmn);
   
2. строят дерево разбора по переданному объекту, а уже к нему примеряют принятую строку (парсер из cxxtools и предлагаемая библиотека).
   

Также парсеры можно разделить на:

1. парсеры, требующие для своей работы строки, целиком содержащей JSON сообщение (Qt, jsoncpp и jsmn);
   
2. «онлайн»-парсеры, перерабатывающие отдельные символы сообщения (cxxtools и предлагаемая библиотека).
   

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

{ one : 10.01, two : 20.02 },

Но ответ приходит такой:

{ error : <какая-то причина> }.

В данной ситуации мы можем попробовать отобразить поля сообщения на ожидаемую структуру и если не получится — а мы знаем, что нам могут вернуть ошибку, — попробовать («вручную») отобразить сообщение на структуру с ошибкой. Парсеры, строящие дерево разбора по переданному объекту, менее гибкие — они просто отбросят сообщение как ошибочное.

Почему я считаю данное преимущество сомнительным? Рассмотрим пример на основе REST API от digitalocean.

Возьмем, к примеру, серверную часть. При взаимодействии с сервером, клиент обращается к конкретному URL'у конкретным методом, в теле сообщения передавая JSON. Например:

Create a new Domain
To create a new domain, send a POST request to /v2/domains. Set the «name» attribute to the domain name you are adding. Set the «ip_address» attribute to the IP address you want to point the domain to.

URL — «api.digitalocean.com/v2/domains».
Метод — POST.

JSON сообщение:

{"name":"example.com","ip_address":"1.2.3.4"}.

Любое другое сообщение будет ошибкой.

Тоже и с клиентской частью. В случае успеха сервер отвечает статусом «201 Created» и конкретным JSON сообщением:

{
  "domain": {
    "name": "example.com",
    "ttl": 1800,
    "zone_file": null
  }
}.

Если при выполнении запроса происходит ошибка, соответственно, меняется статус:

HTTP/1.1 403 Forbidden

{
  "id":       "forbidden",
  "message":  "You do not have access for the attempted action."
}.

Таким образом, при грамотном построении протокола взаимодействия клиента и сервера, проблем не возникнет ни у одного десериализатора.

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

И тут мы приходим к главному. В разрабатываемом устройстве было решено использовать scmRTOS (ну нравится она мне — мелкая и работает), а в ней нет никакого диспетчера памяти, что намекало на написание своего. А поскольку вся остальная логика была реализована без использования динамической памяти и из курса алгоритмов давно известно, что контекстно-свободные грамматики (к коим и относиться JSON) можно парсить стековым автоматом, было решено попробовать написать десериализатор с использованием только стека.

Сериализатор в прошивке использовался весьма активно и (субъективно, ибо ни с чем не сравнивался) показал отличные результаты. К сожалению к моменту окончания работы над прибором десериализатор еще не был написан. Тем не менее, идея захватила и в результате он был дописан, т. о. «в продакшене» пока не использовался.

Сериализатор

Сам сериализатор состоит из двух классов: класса JSONSerializer и наследующегося от него класса Serializer (что позволит в дальнейшем реализовать сериализацию в XML, по крайней мере, я на это надеюсь). Собственно Serializer реализует логику обхода дерева, а JSONSerializer — преобразования данных в текст и передачи текста Handler'у для дальнейшей отправки контрагенту.

Интерфейс Handler'а выглядит следующим образом:

struct SerializeHandler {
    bool operator()( const char *str, uint32_t len );
    bool SerializeEnd( );
};

Оператор bool operator()( const char *str, uint32_t len ) получает порциями сообщение по мере его сериализации. Вызов bool SerializeEnd( ) сообщает о завершении сериализации объекта. Так было сделано по одной простой причине: т. к. сериализатор ничего не знает о том, куда выводится итоговое сообщение (например, в USB) и, соответственно, не знает, будет ли сообщение фрагментироваться при передаче или оборачиваться дополнительными полями — формирование (при необходимости), заполнение и пересылка буфера была возложена на Handler.Сериализация конкретного класса
Для сериализации объекта некоего класса требуется наследовать данный класс от класса jsmincpp::serialize::Serialized. Данное действие необходимо для выбора правильной перегруженной функции внутри сериализатора. Это не несет особой нагрузки, т. к. класс jsmincpp::serialize::Serialized не содержит полей.

Так же, необходимо реализовать функцию

bool Serialize(Serializer &) const {
    …
}

Например, для некоторого класса это будет выглядеть так:

struct SerializedClass : public Serialized {
  int8_t One;
  uint8_t Two;

  SerializedClass( )
      :
          One( 0 ),
          Two( 0 ) {
  }

  SerializedClass( int8_t one, uint8_t two )
      :
          One( one ),
          Two( two ) {
  }

  template < typename S >
  bool Serialize( S &serializer ) const {
    SERIALIZE( One );
    SERIALIZE( Two );
    return true;
  }
};

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

Далее сериализация выглядит элементарно:

typedef Serializer < JSONSerializer < SerializeHandler > > Serializer_t;

SerializeHandler handler;
Serializer_t serializer( handler );
SerializedClass obj;

       …

serializer.Serialize( obj )

Сериализация из указателя на базовый класс или, как протащить верблюда в игольное ушко
Если у Вас, как и у меня, сериализатор находится в отдельном потоке и забирает объекты для сериализации из своей очереди сообщений, предыдущий вариант не подходит (зачем тащить RTTI на контроллер, когда мы и так отказались от динамической памяти?). Возникает пресловутый вопрос с верблюдом. Решить его поможет некий базовый класс, от которого мы и унаследуем наш сериализуемый класс и указатель на который положим в очередь. Таким классом является AbstractSerialized. Он, в свою очередь, наследуется от Serialized, что позволяет сериализовать полученный класс и по выше приведенному сценарию (при необходимости).

Выглядит это так:

typedef Serializer < JSONSerializer < SerializeHandler > > Serializer_t;

class SerializeObj : public AbstractSerialized < Serializer_t > {

     … 
  virtual bool Serialize( Serializer_t &serializer ) const override {
     … 
  }
};
   … 
  SerializeObj *obj = new SerializeObj;
   … 
  queue.Send( obj );
   … 

  SerializeHandler handler;
  Serializer_t serializer( handler );
  AbstractSerialized < Serializer_t > *obj = queue.Get( );
  serializer.Serialize( obj );
   … 

За сим с сериализацией объектов мы покончили.Расширение функционала сериализатора
Мне категорически не нравятся «вещи в себе». Если есть выбор, я предпочитаю что-то, что можно расширять (особенно здорово, если это жилплощадь) и приспосабливать под свои нужды. Данный сериализатор так же можно расширять, позволяя специфическим образом выводить в канал произвольные классы. Поясню на примере, что это значит.

В разрабатываемом устройстве обмен сообщениями с «большим братом» осуществлялся (в первом приближении) через USART со скоростью 19200 бит/с. Самое длинное сообщение содержало массив из 6 float'тов. Поскольку в разрабатываемом устройстве использовались 6 абсолютных энкодеров с точностью порядка 0.5 градуса и, соответственно, абсолютные величины значений не превышали 360 градусов, сериализованное значение для float'а выглядело так: 222.001999. В нем 5 лишних цифр (собственно, последняя половина символов лишняя и не несет смысловой нагрузки). Можно несколько ускорить обмен сообщениями, если выкинуть лишние символы. Воздействовать на сериализацию float'а библиотекой мы никак не можем, но можем написать сериализатор для произвольного класса. Таким образом был создан класс FloatPoint_3x1.

Сам класс выглядит так:

class FloatPoint_3x1 {
public:
  FloatPoint_3x1( )
      :
          _val( 0.0f ) {
  }

  FloatPoint_3x1( float val )
      :
          _val( val ) {
  }

  float GetValue( ) const {
    return _val;
  }

private:
  float _val;

};

Ничего особенного — контейнер для данных. Заметьте, наследовать его от Serialized не нужно!

Функция сериализации для него выглядит так:

template < typename S >
bool operator <<( S &serializer, const FloatPoint_3x1 &data ) {
  const char f [ ] = "%3.1f";
  char buffer [ 10 ];
  uint32_t len = ::sprintf( buffer, f, data.GetValue( ) );
  if( len > 0 )
    return serializer.GetHandler( )( buffer, len );
  return false;
}

Все просто — формируем в буфере текстовую строку и выводим ее в Handler. В результате сериализованное значение выглядит так: 222.0.

Данная возможность является весьма мощной штукой — у нас появляется полный контроль над потоком вывода.

Десериализатор

Десериализация осуществляется классом Deserializer (неожиданно, да?), который может работать в двух режимах:

1. получает при создании список классов, в которые будет пытаться десериализовать принятые сообщения;
   
2. получает на вход объект конкретного класса, в поля которого попытается десериализовать принятое сообщение.
   

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

class InputStream {
public:
  SymbolStream & operator++( );

  char operator*( );

  bool operator==( const SymbolStream &other );
  SymbolStream End( );
};

Идея подсмотрена у итераторов ввода STL и работа с ним должна выглядеть знакомо.

Метод SymbolStream & operator++( ) читает следующий символ из устройства ввода (если чтение буферизовано — переходит к следующему символу в буфере) или встает в ожидании поступления нового символа.

Метод char operator*( ) возвращает текущий символ.

Методы SymbolStream End( ) и bool operator==( const SymbolStream &other ) предназначены для определения достижения потоком ввода состояния end-of-stream (конец потока).

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

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

{"<имя десериализуемого класса>":{<поля десериализуемого класса>}}.

Вложенные классы допускаются, уровень вложенности определяется свободным местом в стеке. Данный режим подходит, например, для встраиваемых устройств с обменом данными через USB CDC ACM (виртуальный COM-порт) или USART, т. е. там, где есть один канал для обмена всеми сообщениями и нет никаких признаков для определения к какому классу относится принимаемое сообщение. Это несколько ограничивает использование десериализатора в готовых решениях без дополнительной адаптации, зато идеально подходит для вновь проектируемых систем.

В программе это выглядит следующим образом:

class  Object;
class  OtherObject;

  typedef ObjectsList <
     DESERIALIZEOBJ( Object ),
     DESERIALIZEOBJ( OtherObject )
  > SerializeList_t;

Где «Object» и «OtherObject» – названия десериализуемых классов (не инстанцированных объектов! Объекты десериализатор создаст сам).

Третьим шаблонным параметром и вторым параметром конструктора передается аллокатор (хотя, наверное, правильнее сказать — фабрика). Данный класс имеет следующий интерфейс:

class Creator {
public:
  template < typename T >
  T * Create( const T & );

  template < typename T >
  void Delete( T * );
}; 

Метод T * Create( const T & ) выделяет память и размещает в ней создаваемый объект типа «T».

Метод void Delete( T * ), соответственно, удаляет конкретный объект, созданный ранее.
Сама десериализация выполняется методом bool Deserialize( H &handler ) десериализатора. Ему на вход передается обработчик, который получит управление в случае успешной десериализации принятого сообщения. Его интерфейс выглядит следующим образом:

class Handler {
public:
  bool operator()( Object *param );
  bool operator()( OtherObject *param );
               …
};

Собственно, по одному перегруженному operator( ) на класс из списка десериализуемых сообщений.

Это необходимо из-за того, что я не могу возвращать разные классы из метода bool Deserialize( H &handler ) десериализатора. Только в методах Handler'а мы имеем доступ к типу десериализованного сообщения. Зная тип, принятое сообщение можно, например, поместить в нужную очередь для последующей обработки другим потоком или обработать «на месте».
В случае успешной десериализации, метод bool Deserialize( H &handler ) возвращает true и false в случае ошибки.

За раз десериализуем по одному сообщению, для продолжения обработки вызываем метод еще раз (нужное количество раз).
Выглядет вышеописанное так:

class  Object;
class  OtherObject;

     …
  typedef ObjectsList <
     DESERIALIZEOBJ( Object ),
     DESERIALIZEOBJ( OtherObject )
  > SerializeList_t;

     …
  SocketStream s( socket );
  DeserializeHandler h( );

  Deserializer <
      SymbolStream,
      SerializeList_t
  > d( s );

  if( !d.Deserialize( h ) ) DeserializeErrorHandler( );

Несколько слов про неиспользование динамической памяти
По умолчанию в качестве Creator'а используется класс StaticCreator:

template < uint32_t BuffSize >
class StaticCreator {
public:
  uint32_t _buff [ BuffSize / 4 + 1 ];

  template < typename T >
  T * Create( const T & ) {
    return new ( _buff ) T;
  }

  template < typename T >
  void Delete( T * ) {
  }
};

Он создает требуемые объекты в своем буфере.

Таким образом, после десериализации, в обработчике Handler'а необходимо скопировать десериализованный объект куда-либо. В прототипе данного сериализатора я передавал объект по значению в очередь другого потока для дальнейшей обработки (что и позволило полностью отказаться от использования динамической памяти). Если данное поведение не устраивает и есть возможность использовать динамическую память, нужно использовать другой Creator либо написать свой.

В библиотеке доступен MallocCreator, использующий Malloc( ) для размещения объектов и SharedPrtCreator, позволяющий использовать умные указатели (std::shared_ptr). На большее у меня не хватило фантазии.

Десериализация конкретного класса
Если мы знаем конкретный тип десериализуемого сообщения, можно использовать второй режим работы десериализатора. Просто передать указатель на объект, в который мы хотим десериализовать принятое сообщение, перегруженному методу bool Deserialize( O *obj ).

В качестве единственного члена списка десериализации можно указать объект-пустышку NullObj. Выглядит это так:

  SocketStream s( socket );

  typedef ObjectsList <
     DESERIALIZEOBJ(NullObj)
  > SerializeList_t;

  Deserializer <
      SymbolStream,
      SerializeList_t
  > d( s );

  Object obj;
  d.Deserialize( &obj );

Или в случае использования shared_ptr, так:

  SocketStream s( socket );

  typedef ObjectsList <
     DESERIALIZEOBJ(NullObj)
  > SerializeList_t;

  Deserializer <
      SymbolStream,
      SerializeList_t
  > d( s );

  auto obj = make_shared< Object >();
  d.Deserialize( obj.get( ) );

В данном режиме работы (вне зависимости от переданного Creator'а) динамическая память десериализатором не используется (Creator инстанцируется, но его методы не вызываются).Расширение функционала десериализатора
Данный десериализатор позволяет расширение своего функционала. Во-первых возможностью расширения числа десериализуемых классов пользователя. Во-вторых возможностью изменения стратегии выделения памяти под десериализуемый класс.

Рассмотрим расширение функционала на примере некоторого класса StaticString. Данный класс позволит нам десериализовать строки в системах, где отсутствует динамическая память. Конечно, он содержит много ограничений, но при некоторой сноровке пользоваться можно. Выглядит класс так:

template < uint32_t Num >
class StaticString {
public:
  StaticString( )
      :
          _length( 0 ) {
    _buff [ 0 ] = 0;
  }

  StaticString( const char *str ) {
    Assign( str );
  }

  bool Add( char symbol ) {
    if( Num == _length )
      return false;
    _buff[ _length++ ] = symbol;
    _buff[ _length ] = 0;

    return true;
  }

  bool Add( const char *str ) {
    uint32_t strSize = ::strlen( str );
    if( strSize > Num - _length )
      return false;
    ::strcpy( _buff, str );
    _length += strSize;
    _buff[ _length + 1 ] = 0;
    return true;
  }

  bool Assign( const char *str ) {
    _length = 0;
    _buff[ _length ] = 0;
    return Add( str );
  }

  const char * GetString( ) {
    return _buff;
  }

  uint32_t GetLength( ) {
    return _length;
  }

private:
  uint32_t _length;
  char _buff [ Num + 1 ];
};

Собственно, ничего особенного — статический массив для символов, вокруг которого построена логика работы со строкой.

Десериализация осуществляется следующим кодом:

template < uint32_t Hash, uint32_t Num >
class StaticStringParam {
public:
  enum {
    HASH = Hash
  };

  StaticStringParam( StaticString< Num > &param )
      :
          _param( param ) {
  }

  template < typename D >
  bool Parse( D &deserializer ) {
    return ParseStaticString( _param, deserializer.GetStream( ) );
  }

private:
  StaticString< Num > &_param;
};

template < uint32_t Hash, uint32_t Num >
StaticStringParam < Hash, Num > MakeParam( StaticString< Num > &param ) {
  return StaticStringParam < Hash, Num >( param );
}

Как видим, у нас полный доступ к входному потоку символов, следовательно, можно десериализовать все, что угодно.Некоторые ограничения при использовании данного десериализатора
Еще на стадии написании концепта возникла следующая проблема: сам по себе JSON никак не ограничивает длину имени параметра, что требует, вообще говоря, необходимости использования динамической памяти (с возможностью увеличения размера выделенного буфера), либо статического буфера достаточного размера для размещения самого длинного имени. Памяти было жалко (разработка, напомню, изначально велась для микроконтроллера), так что была реализована следующая идея: а что если не накапливать символы имени параметра в буфере и в последующим сравнивать его с именами десериализуемых параметров, а считать CRC32 от входной строки, а впоследствии сравнивать с посчитанными на этапе компиляции (constexpr функция) CRC32 от имен полей десериализуемого класса. Это экономит нам память (вместо строки храниться лишь uint32_t) и ускоряет сравнение, но добавляет головной боли с возможными коллизиями CRC32 от имен параметров. Что тут сказать… Тестируйте ваш код больше, тесты должны отловить подобные проблемы! Вы ведь тестируете свой код?

Поддержка контейнеров STL

В процессе чтения форумов порой натыкался на сообщения страждущих с просьбой указать им сериализатор/десериализатор JSON с поддержкой STL «искаропки». Возникло непреодолимое желание поддержать страждущих. Что и было реализовано — вроде все основные контейнеры STL поддерживаются, как сериализатором, так и десериализатором. Если что-то не поддерживается, всегда можно допилить поддержку. Больше сказать по этому поводу нечего.

Сравнение и бенчмарки

Сериализатор сам по себе достаточно тривиален, так что сравнивать его ни с кем желания даже и не возникло.
Интереснее было сравнить десериализатор с конкурирующими библиотеками. Поскольку C++ библиотек пригодных для использования на контроллере я не нашел (да в общем и не искал), а добавление поддержки STL и возможность расширения перевело продукт в другую потребительскую категорию – возможность использовать на полноценных серверах, сравнение проводил с теми библиотеками, рекомендации использовать которые, находил на форумах. Сравнение, конечно, не всеобъемлющее — всего-то четыре конкурента. Но мне расхотелось тестировать конкурентов дальше, ибо результаты, на мой взгляд, были весьма удручающими. Сами тесты лежат здесь, в подкаталогах каталога /src в файлах *.mk поправьте пути к компилятору и библиотекам (кроме Qt. Для его сборке создайте проект в QtCreator'е и копируйте *.cpp в него). Сборка осуществляется в корневом каталоге вызовом make . Посмотреть проекты для сборки можно просто вызвав make.

Итак, тестировались следующие библиотеки (помимо разработанной):

• jsmn — проект на C, но не использует динамическую память, интересно было сравнить;
  
• Qt;
  
• jsoncpp;
  
• cxxtools.
  

Сравнение производилось следующим образом: по документации конкретной библиотеки (ну, естественно, так как я ее понимал) писалось приложение, задача которого состояла в десериализации некоторой (синтаксически и семантически корректной) строки в объект некоторого класса. И так 1 000 000 раз, ибо на моем ноутбуке (i3) меньшее число итераций проходило за совсем короткое время. Время работы измерялось командой time и бралось из строчки «user: XXX». Понятно, что тест не претендует на серьезность, но некие выводы сделать можно. Тесты прогонялись 100 раз. Результаты представлены в таблице.

Библиотека / фреймворк	Наилучшее время исполнения, с	Отношение к лидеру теста	Среднее время исполнения, с	Отношение к лидеру теста
jsmincpp	0.219	—	0.22252	—
jsmn	0.595	2.716895	0.60017	2.697151
Qt	1.359	6.205479	1.54353	6.93659
jsoncpp	4.981	22.74429	5.89901	26.51002
cxxtools	5.26	24.01826	5.95608	26.76649

Некоторые комментарии.

• По скорости исполнения мы почти в трое уделали программу с библиотекой на C (кто там утверждал, что C++ медленный? Если Вы пишете на C++, не стоит ли задуматься о своей профпригодности?).
  
• По возможности все функции, вызывающиеся в цикле, линковались статически. Это было сделано после того, как выяснилось, что для cxxtools при использовании shared библиотек лучшее время ухудшается до 6.391 с, а среднее до 7.63804 с, т. е. больше секунды в результате съедают вызовы функций из shared библиотек. Отсюда следует интересный вывод: поскольку Qt бралось с офф. сайта, а там в наличии только shared библиотеки, возможно, при статической линковке время Qt оказалась бы существенно меньше — порядка 0.4 — 0.6 с. (Вы все еще утверждаете, что C++ медленный?!).
  
• Ну и размер striped бинарников программ:
  
  • для jsmincpp – 8040 Байт,
    
  • для jsmn – 8792 Байт.
    
  
  Более чем на 700 Байт (почти 10%) меньше чем в C'шной реализации библиотеки. (Кто там утверждал, что C++ делает монструозные программы? Определенно, задумайтесь о собственной профпригодности!)
  

А если серьезно, может кто знает быстрые библиотечки десериализации JSON? Любопытно было бы сравнить по предоставляемым возможностям и глянуть на внутреннее устройство.

© Habrahabr.ru