Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 49
Комментируем! Создал «первый коммент», чтоб можно было комментить, пока Хабру не починят :) Подробности: habrahabr.ru/qa/12275/
Еще есть MessagePack.
Я как-то в него заглядывал. Код не комментирован, в wiki ошибки даже в hello world были (для Java) + достаточно много нерешенных проблем: jira.msgpack.org/browse/MSGPACK#selectedTab=com.atlassian.jira.plugin.system.project%3Aissues-panel
Почему BE, а не LE?
собственно говоря тоже задался таким вопросом. Ведь в мире большинство компьютеров с процессорами основанной на intel архитектуре(x86), где по умолчанию LE. А так получается еще и накладные расходы на преобразование из BE в LE
Network byte order. По стандарту IP протокола.
Да, но почему? Ведь при использовании LE значительно упрощается работа по разбору формата. Смотрите сами:
const void *lenPtr = ...;
uint32_t len = *((uint32_t*)lenPtr); // for 4-byte length
len &= 0xFFFFFF; // for 3-byte length
uint16_t len = *((uint16_t*)lenPtr); // for 2-byte length
uint8_t len = *((uint8_t*)lenPtr); // for 1-byte length
Зато для строк, целых в BE и флоатов совпадает функция сортировки… хотя хз зачем это тут.
На тему BE vs LE есть хороший текст Danny Cohen`а.
Мда, т.е. они переизобрели TLV и определили теги. Эко достижение!
С другой стороны, не велосипед (почти) :)
Буду присматриваться, может и попользуюсь.
С другой стороны, не велосипед (почти) :)
Буду присматриваться, может и попользуюсь.
Думаю было бы полезно написать про кодирование знака для целых типов, из описания формата это не очевидно, а код отправляет к документации Явы, в которой это тоже не просто ищется.
Немного не понятно на счет 100% совместимости, может быть хотя бы несколько реальных примеров?
Как будет выглядить в этом формате такое:
За счет чего прирост производительности по сравнению с gzip+json, тут разве не нужно преобразовывать обратно для работы как на сервере, так и на клиенте?
Как будет выглядить в этом формате такое:
{
"fruits":["apple", "orange"],
"sport":[{"football" : {"players" : 11, "goalkeeper" : true}, "hockey" : {"players" : 6, "goalkeeper" : true} }]
"note" : null
}
За счет чего прирост производительности по сравнению с gzip+json, тут разве не нужно преобразовывать обратно для работы как на сервере, так и на клиенте?
> [type, 1-byte char]([length, 1 or 4-byte integer])([data])
на будущее: в nix-like системах принят формат выражений <> — поле, [] — необязательное, т.е. строка должна выглядеть
<type, 1-byte char>[<length, 1 or 4-byte integer>][<data>]
я лично долго над ней втуплял. более того, я так понимаю, на деле оно имеет формат
<type, 1-byte char>[<length, 1 or 4-byte integer>[<data>]]
на будущее: в nix-like системах принят формат выражений <> — поле, [] — необязательное, т.е. строка должна выглядеть
<type, 1-byte char>[<length, 1 or 4-byte integer>][<data>]
я лично долго над ней втуплял. более того, я так понимаю, на деле оно имеет формат
<type, 1-byte char>[<length, 1 or 4-byte integer>[<data>]]
Я пол года назад сравнивал разные бинарные альтернативы JSON, включая MessagePack, Protocol Buffers и свой вариант преобразования JSON в TLV один-к-одному (аналогичный описываемому Вами Universal Binary JSON) — пытался избежать написания своего велосипеда быстрого парсера JSON на C для OS Inferno. Задача была получить максимальную скорость десериализации сложной структуры — чтение файла и создание структуры в памяти. И я был готов пожертвовать читабельностью и стандартностью JSON в пользу любого бинарного формата если бы это дало заметный выигрыш в скорости на наших данных. При этом я учитывал скорость всего процесса десериализации в целом (т.е. если, к примеру, бинарный формат занимал на X% меньше места, то это означало выигрыш в скорости на считывании файла, что тоже учитывалось). Так вот, в результате множества экспериментов и бенчмарков выяснилась любопытная вещь:
P.S. Впрочем, я всё-таки немного выкрутился и выиграл заметно в производительности реализовав не парсер, а токенайзер — поскольку мне нужно было грузить в память далеко не все поля/данные из десериализуемых структур, то я избежал полноценного разбора и вызовов malloc()-ов для ненужных данных возвращая пользователю отдельные токены по мере разбора и предоставив пользователю возможность управлять дальнейшим разбором (напр. пропуская ненужные ключи/значения объектов).
- бинарные форматы не дают заметного выигрыша, такого, из-за которого стоило бы жертвовать простотой и наглядностью текстового JSON;
- производительность десериализации упирается не в скорость парсинга скобочек и кавычек JSON, а в тормоза на большом количестве malloc()-ов, вызываемых для выделения в памяти динамических структур данных (по крайней мере при оптимизированной реализации парсинга на C, на других языках может тормозить сам парсинг).
P.S. Впрочем, я всё-таки немного выкрутился и выиграл заметно в производительности реализовав не парсер, а токенайзер — поскольку мне нужно было грузить в память далеко не все поля/данные из десериализуемых структур, то я избежал полноценного разбора и вызовов malloc()-ов для ненужных данных возвращая пользователю отдельные токены по мере разбора и предоставив пользователю возможность управлять дальнейшим разбором (напр. пропуская ненужные ключи/значения объектов).
Кстати, если надумаете сравнивать по скорости свой Universal Binary JSON с другими форматами включая сам JSON — не забудьте сравнить с Perl-модулем JSON::XS — я лично даже не подозревал, насколько он быстрый, пока не сравнил его с MessagePack, Protocol Buffers и своими ранними и ещё не оптимизированными версиями парсера JSON на C.
Вот цифры из моих тестов, на наших структурах данных (в данном случае все тесты были на perl, использовались модули Data::MessagePack, JSON::XS, и не помню что для ProtoBuf):
Рекомендую использовать вот такую команду:
Вот цифры из моих тестов, на наших структурах данных (в данном случае все тесты были на perl, использовались модули Data::MessagePack, JSON::XS, и не помню что для ProtoBuf):
Формат Кол-во байт на одну Кол-во десериализуемых
структуру данных структур в 1 секунду
(меньше - лучше) (больше - лучше)
ProtoBuf 219 32051/s
MsgPack 303 50505/s
JSON 343 52356/s
Рекомендую использовать вот такую команду:
$ time perl -MJSON::XS -ne 'push @a, decode_json($_)' file.json
Есть над чем поработать с памятью. Если заранее маллочить весь объём, а потом его тупо раздавать из своего буфера — должно получиться сильно быстрее. Preallocate не просто так придумали.
После десериализации структура данных отдаётся пользователю, и он с ней должен иметь возможность свободно работать. Т.е. в частности удалять из неё элементы, а значит освобождать память. И делать он это будет ничего не зная о том, что библиотека десериализации дооптимизировалась до того, что освобождать память надо не стандартными методами, а через её собственные malloc()/free(). Такое даже на голом C делать чревато. А моя реализация хоть и написана на C, но структуру данных подготавливает для использования из языка Limbo, в котором прямого доступа к памяти нет, и, соответственно, при всём желании невозможно обеспечить вызов нестандартной free() для элементов этой структуры данных.
Хотя, если совсем честно, я немного лукавлю — как раз в Inferno/Limbo это в принципе вообще-то возможно реализовать. Но, в любом случае, это потребует своей собственной реализации malloc(), free() а заодно и (не уверен, но это не исключено, надо подумать) сборщика мусора. В общем, это в любом случае выходит за все рамки и по факту полный неадекват поставленной задаче.
Хотя, если совсем честно, я немного лукавлю — как раз в Inferno/Limbo это в принципе вообще-то возможно реализовать. Но, в любом случае, это потребует своей собственной реализации malloc(), free() а заодно и (не уверен, но это не исключено, надо подумать) сборщика мусора. В общем, это в любом случае выходит за все рамки и по факту полный неадекват поставленной задаче.
С тестами дела, как всегда, интереснее. Желательно знать конфигурацию аппаратной и программной частей, и саму структуру. С очень оптимизированнным кодом относительно стабильным результатом было ~6200 нс/оп или 161290 оп/с на С# и .NET 4.5 без каких либо манимпуляций с аппаратной частью. Структура бралась с jvm тестов. И всёравно возникали вопросы. Обычное количество операций для тестов бралось в 1000000.
Зачем Вам конфигурации? Просто сравните скорость обработки на одной и той же тестовой машине. Что касается структуры — сделайте штук 5 максимально разных структур и прогоните тесты по всем.
Конкретно у нас структура была следующая: объект с 13-ю ключами, значения 12-ти это числа/строки (в основном строки, длиной в среднем 15-20 символов), 13-е значение — массив из 2-3 строк, общий размер одной структуры (в одну строку без опциональных пробельных символов) примерно 330 байт.
Конкретно у нас структура была следующая: объект с 13-ю ключами, значения 12-ти это числа/строки (в основном строки, длиной в среднем 15-20 символов), 13-е значение — массив из 2-3 строк, общий размер одной структуры (в одну строку без опциональных пробельных символов) примерно 330 байт.
Если уж тестировать, то нужно проверить как будут многократно вложенные массивы и объекты работать работать, как будет работать 1000 свойств внутри одного объекта и т.д. Но важнее всего — кейсы реальных случаев, т.к. сторонники сознательно или подсознательно придумывают тесты, дающие красивые результаты, а противники придумают тесты с плохими результатами. На себе убедился.
Для более подрбной информации об условиях и относительной адекватности в результате.
То, что бралось для предварительных тестов, можно найти здесь.
То, что бралось для предварительных тестов, можно найти здесь.
Абсолютно согласен с мнением powerman. Я неоднократно пытался ужать и ускорить XML, YAML и свои форматы сериализации, еще с 1999 года начиная, и давно уже забросил попытки оптимизации с помощью бинарных структур. JSON же имеет гораздо меньшую избыточность кодирования, чем XML и тут уже выиграть пару процентов сложно: вместо кавычек или скобочек (2 символа на строку любых размеров) будем хранить 1-4 байта длины, и еще нужно хранить типы, на строках выигрыш слишком мал, чтобы так напрягаться. На хранении чисел экономится больше, согласен, но часто ли у нас используются все разряды в 32-битном или 64-битном числе, точность обычно ограничивается 2 знаками после запятой, так что, например 3.14 (4 байта), а в бинарном виде при 32-битном float это займет 5 байт. При всем этом, нет читабильности формата и накладные расходы на обработку.
Если есть желание что-то соптимизировать, то уж лучше заняться такими направлениями:
— Одни и те же данные в JSON можно смоделировать многими способами, и прикладные программисты редко лишают себя соблазна лишний раз обвернуть в массив или объект. Т.е. нужно заниматься оптимизацией самих сруктур данных, а не их представления.
— Для ускорения парсинга можно ввести в JSON свои правила, например приняв конвенции о именовании свойств можно потом не парсить весь пакет/файл/буфер, а найти значение нужного свойства двумя операциями поиска подстроки в строке.
— В некоторых случаях можно отказаться от null, false, true, а использовать например -1, 0, 1. Это конечно не универсально, но когда вопрос доходит до оптимизации миллионов однотипных записей, то и это прощается.
— Если не лезть в ПО, а оптимизировать только формат, то можно ввести пре- и пост- обработку реплейсами самых часто повторяющихся фрагментов.
— Про минификацию (компактный вид) не буду подробно.
— Введя в протоколе или формате данных договоренности о значениях по умолчанию, часто можно опустить большую часть поле. Потому, что помните, что говорит нам теория информации и кодирования: самый лучший способ передать сообщение, принятое по-умолчанию (наиболее вероятное), это не передавать вообще ничего.
Если есть желание что-то соптимизировать, то уж лучше заняться такими направлениями:
— Одни и те же данные в JSON можно смоделировать многими способами, и прикладные программисты редко лишают себя соблазна лишний раз обвернуть в массив или объект. Т.е. нужно заниматься оптимизацией самих сруктур данных, а не их представления.
— Для ускорения парсинга можно ввести в JSON свои правила, например приняв конвенции о именовании свойств можно потом не парсить весь пакет/файл/буфер, а найти значение нужного свойства двумя операциями поиска подстроки в строке.
— В некоторых случаях можно отказаться от null, false, true, а использовать например -1, 0, 1. Это конечно не универсально, но когда вопрос доходит до оптимизации миллионов однотипных записей, то и это прощается.
— Если не лезть в ПО, а оптимизировать только формат, то можно ввести пре- и пост- обработку реплейсами самых часто повторяющихся фрагментов.
— Про минификацию (компактный вид) не буду подробно.
— Введя в протоколе или формате данных договоренности о значениях по умолчанию, часто можно опустить большую часть поле. Потому, что помните, что говорит нам теория информации и кодирования: самый лучший способ передать сообщение, принятое по-умолчанию (наиболее вероятное), это не передавать вообще ничего.
С чего это всё началось, насколько мне известно, есть вот ссылка. Предыстория всего мне не известна.
Лично для себя использование UBJSON было хорошим решением для внутреннего проекта. То, что бинарный формат, не смущало. В HEX виде всё довольно прилично смотрится.
Частные случаи мне известны. Они обычно очень специфические и узконаправленные. Тут надо смотреть и разбираться индивидуально.
Основные цели: соответствие JSON, совместимость, ускорение работы с данными на уровне спецификации. Ускорее на разных платформах, естественно будет зависить от реализации и «своих» доработках.
Лично для себя использование UBJSON было хорошим решением для внутреннего проекта. То, что бинарный формат, не смущало. В HEX виде всё довольно прилично смотрится.
Частные случаи мне известны. Они обычно очень специфические и узконаправленные. Тут надо смотреть и разбираться индивидуально.
Основные цели: соответствие JSON, совместимость, ускорение работы с данными на уровне спецификации. Ускорее на разных платформах, естественно будет зависить от реализации и «своих» доработках.
Чтобы ускорить работу нужно передавать по сети прямо ту же самую структуру памяти, которая получается при парсинге, т.е. дерево. А тут бинарным форматом пробуют решить две противоположные задачи: минимизацию размеров пакета/файла и скорость развертывания при получении. Так это ясно, что увеличение размера пакета/файла, могут существенно увеличить скорость развертывания, а вот уменьшение размера без вариантов приводит только к замедлению. В чем лежит JSON в памяти — в дереве, у кого в каком, это может быть простое двух-связное дерево (где каждый элемент имеет две ссылки: Parent, FirstChild). Если мы будем работать с 5-связным деревом (Parent, FirstChild, LastChild, NextSibling, PreviousSibling), то избыточность немного больше, а скорость работы заметно выше. При передаче нам нужно просто провести маршалинг. При развертывании маршализированного объекта в другом адресном пространстве нужно провести всего лишь сдвиг адресов. Накладных расходов не так много, 2-5 адресов на каждый узел (8-20 байт на узел) при 32-битной адресации. Но все это — решение только для низкоуровневых языков, где можно памятью манипулировать, а вот для высокоуровневых это может быть только встроено в язык, а этого мы вряд ли дождемся.
Уменьшение размера данных — побочный положительный эффект.
Непосредственное манипулирование памятью довольно опасная штука.
Задачи, платформы, языки могут иметь разнообразнейшее внутреннее представление подобных внешне вещей. При обмене данными между системами одной платформы освещаемые вопросы обычно не стоят.
Непосредственное манипулирование памятью довольно опасная штука.
Задачи, платформы, языки могут иметь разнообразнейшее внутреннее представление подобных внешне вещей. При обмене данными между системами одной платформы освещаемые вопросы обычно не стоят.
Но хочется увидеть результаты сравнительных тестов все же при разных вариантах применения, ну и кейсы какие-то увидеть, например, где без бинарного формата было невозможно что-то сделать или параметры работы системы были значительно хуже. Примеры пакетов в документации, по большей части надуманные, но задача то вышла из реальных проектов, не просто ж так руки зачесались написать. Вот про реальные проекты услышать хочется. Все это нужно по большей части в очень специфических задачах и при больших объемах данных, но типичное решение для этих случаев: вообще избавиться от имен параметров и передавать только значения, ведь имена заранее известны. Кроме того, для больших объемы данных почти всегда характерны повторяющиеся структуры, поэтому логично было бы отдельно описать структуру и имена свойств и потом передавать только данные без имен и даже типов, а длину указывать только для полей с переменной длиной. Это в два раза уменьшает объемы данных, если задача специфическая, то так и делают, но я не исключаю, что есть класс задач, где нужен именно бинарный JSON и с удовольствием бы почитал «истории успеха».
Для разработки реализаций на других языках было бы здоро иметь набор тестов (а не один тест со сложной структурой как в Java реализации). Пара JSON/UBJSON хорошо подойдёт.
Мои первые наброски для Node.js: github.com/Sannis/node-ubjson
Мои первые наброски для Node.js: github.com/Sannis/node-ubjson
Напишите, как можно подробнее, о своей реализации, возникших вопросах или пожеланиях Riyad Kalla по одному из его контактов. Любая информация будет полезной.
Набор тестов, насколько мне известно, в разработке.
Набор тестов, насколько мне известно, в разработке.
А чем плохи существующие стандарты? Ддя BSON, например, есть имплементация для десятка языков.
При сильно повторяющихся данных можно паковать, приняв соглашения о последовательности полей (то есть, преобразовать Object в Array, убрав ключи).
А если, например, нужно передавать массив id-шников, которые последовательные, то можно их отсортировать и потом заменять на разницу:
было 7000, 7001, 7004, 7010
стало 7000, 1, 3, 6
А при распаковке суммировать.
А если, например, нужно передавать массив id-шников, которые последовательные, то можно их отсортировать и потом заменять на разницу:
было 7000, 7001, 7004, 7010
стало 7000, 1, 3, 6
А при распаковке суммировать.
Можно даже не убрать ключи совсем, а задать их один раз (если нужно, то для полей можно даже метаданные один раз задать в заголовке: тип поля, маска/шаблон/регексп, допустимые значения, что угодно, но один раз), например:
Для больших объемов данных как раз характерны таблицы, поэтому выносить структуру в шапку — гораздо эффективнее, чем жать в бинарный вид, а можно еще поверх и бинарным форматом.
{"Table":{
"Header":["Id","Time","EventTypeId","ParameterId","UnitId","Multiplier","Value"],
"Data":[
[871,"08:12:04",57,12,3,7,120750049],
[872,"08:12:07",22,79,2,10,288386016],
...
[1325,"10:17:21",13,10,3,10,290537253]
]}}
Для больших объемов данных как раз характерны таблицы, поэтому выносить структуру в шапку — гораздо эффективнее, чем жать в бинарный вид, а можно еще поверх и бинарным форматом.
О круто! Спасибо за идею, добавлю в свой проект =)
Не столько круто, как очевидно, в XML этого вообще невозможно сделать, там массивов нет, а любой тег — именованное значение, я для этих целей 10 лет свои форматы выдумывал один другого лучше, оптимизированные для разных специфических случаев, но с распространением JSON, переступил через свою гордыню и отказался от всех этих изысканий, ведь «Не следует множить сущее без необходимости» Бритва Оккама.
Да я тоже не заморачиваюсь, но просто реально много повторяющихся данных сейчас нужно хранить в js-файле, и я даже такими простыми методами ужал с 1.4 Мб до 200 Кб. +gzip и клиенты со слабым инетом уже могут без последствий быстро пользоваться сайтом =)
Ну тогда еще Вам рекомендую ввести значения по умолчанию, или даже подстановку значений в значения по умолчанию через выбранный символ-маркер, например "%", чтобы сэкономить на повторяющихся частях строки, может пригодится техника (для чисел не так актуально, но для строк полезно), например:
{«Table»:{
«Header»:[«Id»,«Date»,«Category»,«City»,«Source»,«Link»],
«Default»:["%",«2011-10-%»,«Politics»,«Kiev»,«Interfax-Ukraine»,«www.interfax.com.ua/rus%»],
«Data»:[
[1,«29»,"","","","/pol/83814/"],
[2,«29»,"","","","/eco/83943/"],
[3,«30»,"",«UNIAN»,«www.unian.net/ukr/news/news-465271.html»],
[4,«30»,"","","","/eco/83914/"],
[5,«30»,"","","","/eco/83842/"]
]}}
Ну идея понятна, а дальше уже можно от ситуации или просто пустую строку "" значением по умолчанию или подставлять значения из записей в значения по умолчанию или наоборот — подставлять значения по умолчанию в саму запись заменяя маркер или с регулярными выражениями выдумать более сложный способ для специфического случая.
{«Table»:{
«Header»:[«Id»,«Date»,«Category»,«City»,«Source»,«Link»],
«Default»:["%",«2011-10-%»,«Politics»,«Kiev»,«Interfax-Ukraine»,«www.interfax.com.ua/rus%»],
«Data»:[
[1,«29»,"","","","/pol/83814/"],
[2,«29»,"","","","/eco/83943/"],
[3,«30»,"",«UNIAN»,«www.unian.net/ukr/news/news-465271.html»],
[4,«30»,"","","","/eco/83914/"],
[5,«30»,"","","","/eco/83842/"]
]}}
Ну идея понятна, а дальше уже можно от ситуации или просто пустую строку "" значением по умолчанию или подставлять значения из записей в значения по умолчанию или наоборот — подставлять значения по умолчанию в саму запись заменяя маркер или с регулярными выражениями выдумать более сложный способ для специфического случая.
Если необходимо хранить по сути табличные данные, то проще CSV использовать. Если данные фиксированных длины или типа, то можно и разделитель не использовать.
Или даже паковать всё в биты, если нужно запоминать только да или нет coding.smashingmagazine.com/2011/10/19/optimizing-long-lists-of-yesno-values-with-javascript/
JSON он быстрее в браузер импортируется, потому что для CSV нужна дополнительная операция вида explode (split).
JSON он быстрее в браузер импортируется, потому что для CSV нужна дополнительная операция вида explode (split).
Да, если значения только «да, нет» («вкл, выкл»), то обычно происходит упаковка в флаги, т.е. как по ссылке выше. Это стандартная практика.
Упаковка нескольких значений в тип достачного размера, тоже очень полезная вещь.
Относительно спецификации. Вопрос об включении подобных оптимизаций был, но решили отказаться, так как появляются вопросы, где надо принимать компромиссное решение (скорость или размер). В таких случаях разработчик/пользователь лучше знает или должен знать, что он делает.
Упаковка нескольких значений в тип достачного размера, тоже очень полезная вещь.
Относительно спецификации. Вопрос об включении подобных оптимизаций был, но решили отказаться, так как появляются вопросы, где надо принимать компромиссное решение (скорость или размер). В таких случаях разработчик/пользователь лучше знает или должен знать, что он делает.
Вы можете заюзать новую либу для компрессии JSON или JS объектов:
Эта библиотека проста в использовании:
// import library methods
import { encode, decode } from '@xobj/core';
// sample data object
const data = { x: 1, y: 2, name: 'Test' };
// encode to ArrayBuffer
const buffer = encode(data);
// decode to object from ArrayBuffer
const buffer = decode(buffer);
Так же это решение поддерживает все базовые JS типы а так же Date, RegExp, BigInt, Symbol, TypedArrays и другие. Кроме того вы можете использовать рекурсивные ссылки внутри ваших данных. Ну и конечно же можно добавлять кастомные типы.
https://github.com/superman2211/xobj/tree/master/packages/core
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Universal Binary JSON — ещё один бинарный JSON