[Перевод] Абсурдно быстрое кодирование и декодирование base64
Об авторе: Дэниель Лемер — профессор компьютерных наук в Университете Квебека (Канада). Его исследования затрагивают производительность программного обеспечения и инженерию данных
Компьютеры хранят данные как поток бит. Как изображения, аудио- или видеофайлы, так и бинарные файлы могут содержать практически любую последовательность бит.
Однако мы часто используем текстовые форматы; например, веб-страницы и электронные письма должны быть в текстовом формате. Как же мы отправляем изображения по электронной почте? Как внедряем картинки на веб-страницы? Один из вариантов — поставить ссылку на реальный бинарный файл. Другой типичный подход — встроить бинарный файл непосредственно в тело письма или веб-страницы с помощью base64. Base64 — это просто стандартный текстовый формат, который можно использовать для кодирования любых бинарных данных. Если быть точным, то код base64 — всегда валидный текст ASCII (и поэтому также валидный UTF-8). Каждый байт кода base64 содержит 6 бит данных. То есть мы «теряем» примерно 2 бита на байт. Поэтому эквивалент base64 бинарного файла будет примерно на 33% больше. На практике такое увеличение размера редко становится проблемой. Насколько я знаю, приложения к электронным письмам почти всегда кодируются в base64.
При написании HTML я нашёл удобным внедрять изображения напрямую в HTML-код с помощью схемы data URI. Например, в недавней статье я таким образом закодировал файл PNG. Крупнейшие веб-сайты вроде Google постоянно используют эту схему. Небольшим недостатком становится то, что веб-страницы чуть увеличиваются в размере (что очевидно) и нельзя воспользоваться преимуществами кэширования изображений. Но зато браузер экономит один сетевой запрос.
Если вы веб-разработчик, то можете использовать Web Storage для создания базы данных для вашего приложения на клиентской стороне. Эта клиентская БД будет хранить изображения и произвольные данные, но они все должны быть закодированы в base64.
Большинство движков баз данных поддерживают бинарные данные, но некоторые требуют в какой-то момент кодирования в base64: это MongoDB, Elasticsearch, Amazon SimpleDB и Amazon DynamoDB. Вероятно, и какие-то ещё.
Base64 повсеместно используется в криптографии для обмена ключами. Форма base64 также используется для передачи произвольных данных в составе URI.
К счастью, кодирование и декодирование base64 происходят быстро. Хотя есть случаи, когда недостаточная скорость может стать проблемой. Мэтт Крейн и Джимми Лин обнаружили медленное декодирование бинарных атрибутов base64 в Amazon DynamoDB.
Насколько быстро вы можете декодировать данные base64? На последнем процессоре Intel это требует примерно двух циклов на байт (из кэша) при использовании быстрого декодера вроде того, что встроен в браузер Chrome. Этот быстрый декодер, в основном, занят обращениями к таблице. Это намного медленнее, чем копирование данных в кэше (что занимает менее 0,05 циклов на байт).
Это лучшее, что можно получить?
Несколько лет назад Альфред Клопп показал, что можно добиться гораздо лучшего результата при использовании векторных инструкций. Войцех Мула, я сам и несколько коллег (в том числе Говард и Курц) решили серьёзно пересмотреть проблему. Мула открыл веб-страничку, посвящённую этой теме.
Мы обнаружили, что можно ускорить обработку в 10 раз и использовать всего около 0,2 циклов на байт на последних процессорах Intel при использовании векторных инструкций. Это по-прежнему больше, чем копирование, но намного меньше лимита, способного когда-либо стать самым узким местом системы. Должен обратить внимание, что в эти 0,2 цикла на байт входит обработка ошибок: декодер должен декодировать и проверять входные данные (например, если найдены недопустимые символы, то декодирование отменяется).
Код для нашего исследования доступен, так что можете воспроизвести результаты. Наша статья опубликована на arXiv и принята для публикации в веб-версии ACM Transactions.
Насколько я понимаю, наши хорошие результаты интегрированы в библиотеку base64 Кломпа.
Дополнительные материалы:
Войцех Мула, Дэниель Лемер, «Более быстрое кодирование и декодирование Base64 с использованием инструкций AVX2», веб-версия ACM Transactions (скоро)
