Всем привет! Эта статья - про очень простой алгоритм маскирования данных при пересылке по протоколу WebSocket. Но рассказать я хочу не про сам алгоритм, а про путь оптимизации, который я прошел, чтобы сделать его эффективным. Я уверен, что можно еще лучше и если так, то надеюсь уважаемые читатели мне подскажут! Приступим...
WebSocket
Это протокол общения, который работает поверх HTTP. В момент создания соединения клиент отправляет серверу "рукопожатие" примерно вот такого вида:
GET / HTTP/1.1
Connection: Upgrade
Upgrade: websocket
Sec-WebSocket-Key: dGhlIHNhbXBsZSBub25jZQ==
...Сервер отвечает примерно вот так:
HTTP/1.1 101 Switching Protocols
Upgrade: websocket
Connection: Upgrade
Sec-WebSocket-Accept: s3pPLMBiTxaQ9kYGzzhZRbK+xOo=
...А дальше соединение не закрывается и между сервером и клиентом начинается двусторонний обмен сообщениями. Клиент и сервер в любой момент могут отправить по открытому соединению сообщение, а другая сторона его примет и обработает, но не ответит, а просто отправит сообщение сама тогда, когда это необходимо. В общем это очень полезная и эффективная технология, которая позволяет реализовать асинхронное взаимодействие с сервером.
Framing
После того как соединение установлено клиент и сервер отправляют друг другу так называемые "фреймы". Это сообщения со специально структурой. Подробно о них можно прочитать в спецификации. Но если коротко, то они состоят из:
[metadata][length][masking-key][payload-data]metadata - некая информация о сообщении и резервные биты
length - длина сообщения
masking-key - ключ для размаскирования
payload-data - сами данные
То есть данные сообщения приходят не в чистом виде, а специальным образом измененные при помощи ключа. Причем клиент обязан всегда посылать маскированные данные, а сервер может отвечать как чистыми данными, так и маскированными, о чем он сообщает в мета-данных фрейма.
Нас интересует сам способ маскирования!
Masking/unmasking
Есть ключ - это 4 случайных байта. Нужно взять его и пройтись по всему массиву данных операцией побитового исключения. Допустим вот ключ:
key = {0, 1, 2, 3}; Вот данные:
payload = {0, 1, 2, 3, 4, 5}Вот что делает функция маскирования (^ - побитовое исключение):
k ^ p == m
0 ^ 0 == 0
1 ^ 1 == 0
2 ^ 2 == 0
3 ^ 3 == 0
0 ^ 4 == 4
1 ^ 5 == 4То есть вычисляет побитовое исключение каждого байта ключа с каждым байтом данных. Затем, дойдя до 5-го байта данных, алгоритм перемещает начало ключа на эту позицию и повторяет.
Проблема
А в чем проблема-то? Дело в том, что мы (мы - это группа из двух разработчиков WLJS Notebook) в своем проекте используем язык Wolfram. А он, как известно тем, кто этот язык не использует, "очень медленный", так как это символьный и интерпретируемый язык. И когда мы реализовывали протокол WebSocket для Wolfram Language (WL), то в полной мере это почувствовали. Дело в том, что нам требуется максимально быстрая скорость ответа сервера по протоколу WebSocket, но самая первая наивная реализация маскирования была медленная и тормозила взаимодействие браузера с сервером. Поэтому я занялся поиском путей решения этой проблемы. Этот путь я и изложу ниже.
Стандартная реализация
Итак, у нас язык Wolfram и алгоритм маскирования на нем выглядит вот так:
mask1 = Function[{maskingKey, payload},
ByteArray[Table[
BitXor[payload[[i]], maskingKey[[Mod[i - 1, 4] + 1]]],
{i, 1, Length[payload]}
]]
]; Function[{args}, expr]- чистая функцияByteArray[]- мы должны вернуть массив байт для записи в сокетTable[f[i], {i, 1, n}]- создает список с помощью циклаBitXor[a, b]- побитовое исключениеMod[a, b]- остаток от деления
Создадим один ключ:
maskingKey = ByteArray[{192, 168, 13, 7}]И набор данных:
payload = StringToByteArray["{\"type\": \"point\", \"x\": 1.23, \"y\": 4.56}"]Применим функцию маскирования:
payloadMasked = mask1[maskingKey, payload] (* => ByteArray[..] *)В результате мы передали на вход два массива байт и получили на выходе один массив. Отобразить его в виде строки не получится, так как он содержит символы, которые не используются в UTF-8. Но мы знаем, что это нечитаемый текст. Еще у маскирования есть одно важное свойство! Повторное применение восстанавливает данные, т.е. выполняет размаскирование. Это значит что клиент присылает данные, сервер их размаскирует, затем создает ответ и маскирует той же функцией и отправляет клиенту. Клиент в свою очередь восстанавливает их той же операцией, зная ключ из заголовка фрейма. Получается, что выполняется следующее равенство:
mask1[maskingKey, mask1[maskingKey, payload]] == payload
Быстродействие
Замеры проводятся на ноутбуке ASUS TUF с Windows 11 и процессором AMD Ryzen 4800H 2.90 GHz. Но нас конечно в первую очередь будет интересовать относительный прирост производительности.
А теперь проверим насколько быстра и эффективна первая наивная реализация. Запустим код несколько раз на данных длиной 1 Мб:
payload1Mb = ByteArray[RandomInteger[{0, 255}, 2^20]]И замер времени:
t1 = RepeatedTiming[mask1[maskingKey, payload1Mb]]
Запомним этот результат. От него мы и будем отталкиваться в дальнейших замерах. Уважаемым читателям, может показаться, что 1.7 секунд на 1 мегабайт информации это какое-то издевательство. Все так и есть. И этому эффекту есть объяснение, если очень глубоко покопаться в устройстве языка. Я постараюсь ответить на вопрос какого почему таааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааак долго.
Чтобы понять почему такая чудовищная в плохом смысле скорость вообще возможна, нам нужно провести небольшой ликбез по устройству языка Wolfram.
WL - это язык с неизменяемыми структурами данных.
Это значит, что практически любое выражение, переменная, массив и все что угодно созданное в языке является константами. Всякий раз когда мы пытаемся, например, изменить значение в списке чисел - происходит создание нового списка. Т.е. это жутко неэффективно, но зато надежно и безопасно если писать код в функциональном стиле.Он функциональный и символьный одновременно.
Функциональный - это значит что он придерживается принципа, что есть данные и некие алгоритмы преобразования, которые возвращают данные. А символьный он по принципу исполнения кода на основе правил и замен, что тоже является очень неэффективной концепцией с точки зрения производительности, но супер крутой штукой концептуально. Подробнее про символьное программирование в WL можно почитать вот здесь.Он интерпретируемый.
Это главная проблема. Ведь каждая атомарная операция проходит долгий путь прежде чем выполниться на процессоре. Вот как этот путь выглядит:
[user] -> [ui] -> [interpreter] -> [byte-code] -> [machine code] -> [cpu]т.е. сначала пользователь вводит строку, на UI она выглядит как аналог HTML-разметки в виде так называемых "боксов", UI разбирает боксы и вытаскивает из них выражение, выражение интерпретатором превращается в полную форму, полная форма компилируется в байт-код виртуальной машины ядра, байт-код отправляется на ядро, ядро исполняет байт код превращая его в машинный код и отправляя на процессор. Затем эта цепочка выполняется в обратную сторону и заканчивается все тем, что фотоны/электромагнитные волны испущенные экраном компьютера попадают на сетчатку глаза и нервные импульсы двигаются в мозг передавая ответ ядра пользователю. То есть вся эта длинная цепочка выполняется на каждое атомарное действие. В нашем коде первый этап правда выполнится один раз, но затем каждый шаг цикла будет проходить через байт код и машинный код, а затем обратно. Сами по себе операции на CPU выполняются быстро, но если их очень много то эффективность сильно падает.
Еще одним важным фактором является то, что мы записали в наивной версии все очень просто и мы не обращали внимание на типы данных. На них тоже нужно остановиться. Как мы понимаем из условия на вход передаются массивы байт. Массив байт - это сложный композитный объект. На абсолютно каждой итерации цикла это объект целиком прогоняется до процессора и обратно, где у массива извлекается i-ый элемент. Что конечно же абсолютно неэффективно. Дело в том, что из-за сложной структуры массива байт, язык не способен применить одну из своих технологий, которая называется "автокомпиляция". Она срабатывает для численных алгоритмов, в тех случаях когда это простой цикл с численными операциями. Тогда ядро понимает, что ему не нужно каждый переход от итерации к итерации гонять через виртуальную машину и обратно. А выполняет итерации по циклу сразу в виртуальной машине, что сокращает оверхед. Но как этого добиться?
Автокомпиляция
Чтобы заставить ядро использовать эту технологию мы должны избавиться от того, что мешает этот код ускорить. У нас должны быть на входе два списка чисел и на выходе список чисел. Значит массив байт надо превратить в список перед циклом вот так:
mask2 = Function[{maskingKey, payload},
Module[{k = Normal[maskingKey], p = Normal[payload]},
ByteArray[Table[
BitXor[p[[i]], k[[Mod[i - 1, 4] + 1]]],
{i, 1, Length[p]}
]]
]];
t2 = RepeatedTiming[mask2[maskingKey, payload1Mb]]
В примере выше внутри цикла уже не осталось сложного объекта ByteArray, который мешал применить автокомпиляцию. Именно этим объясняется такое ускорение сразу в 23 раза. Важно помнить этой свойство языка и правильно работать с типами.
Compile
Если WL умеет самостоятельно применять автокомпиляцию - т.е. отбрасывать промежуточные шаги при обращении к ядру, то может быть можно и в ручную заставить язык это сделать? Конечно, да! Именно для этого предназначена функция Compile. Она создает байт-код для ядра, который не выполняется построчно, а весь исполняется в виртуальной машине. Вот как можно переделать код выше:
cmask3 = Compile[{{k, _Integer, 1}, {p, _Integer, 1}},
Table[
BitXor[p[[i]], k[[Mod[i - 1, 4] + 1]]],
{i, 1, Length[p]}
]
];
mask3[maskingKey_ByteArray, payload_ByteArray] :=
Module[{k = Normal[maskingKey], p = Normal[payload]},
ByteArray[cmask3[k, p]]
]
t3 = RepeatedTiming[mask3[maskingKey, payload1Mb]]
И снова внимательно посмотрим на типы данных. На вход передаются массивы байт. Специальная структура данных для хранения чисел ubyte. Она хранит их наиболее эффективно. Но когда мы вызываем функцию Normal, то массив байт превращается в список целых чисел с типом long ли Integer64. То есть размер массива увеличивается в 8 раз, а эффективность атомарных операцией на 64-битных числах падает. Поему мы используем long? Увы, таковы ограничения Compile. Эта функция может работать только с 64-битными целыми, действительными машинной точности, комплексными числами и булевыми значениями True|False. Кроме того Compile работает с тензорами из перечисленных типов. Т.е. передать туда массив из чисел 8-битной точности невозможно. Есть ли способ это сделать другим путем? Конечно, да!
FunctionCompile
Начиная с 12 версии в языке появилась функция FunctionCompile. Это функция делает примерно тоже самое, что и Compile, т.е. превращает код на языке Wolfram в байт-код. Но если Compile возвращает функцию для вызывает байт-кода на виртуальной машине WL, то FunctionCompile компилирует IR-код для LLVM. Это самое важное отличие в концептуальном плане нового способа компиляции от старого. Еще одним отличием является то, что FunctionCompile поддерживает гораздо больше типов данных. И одним из них является как раз нужный нам массив байт. Что ж, возьмем тот же алгоритм и перепишем его вот так:
cmask4 = FunctionCompile[Function[
{
Typed[maskingKey, "NumericArray"::["MachineInteger", 1]],
Typed[payload, "NumericArray"::["MachineInteger", 1]]
},
Table[
BitXor[payload[[i]], maskingKey[[Mod[i - 1, 4] + 1]]],
{i, 1, Length[payload]}
]
]];
mask4[maskingKey_ByteArray, payload1Mb_ByteArray] :=
ByteArray[cmask4[maskingKey, payload1Mb]]
t4 = RepeatedTiming[mask4[maskingKey, payload1Mb]]Синтаксис очень похож на Compile, только теперь нужно использовать двойную конструкцию из FunctionCompile[Function[]], а типы аргументов следует указывать явно. Важно, что такая скомпилированная функция сразу может принимать на вход массивы байт без дополнительных преобразований. Но возвращает по прежнему список, который мы приводим к типу ByteArray[].
Опять же, внимательный читатель заметит, что я снова использовал 64-битные целые, вместо беззнаковых 8-битных. Все потому, что FunctionCompile в таком виде, как записано выше по умолчанию выводит тип, который возвращает Table как "PackedArray"::["MachineInteger", 1]. Т.е. это упакованный обычный список. Можно ли заставить Table явно возвращать массив байт? Увы, ответ - нет. Внутри скомпилированного кода функция Table может вернуть только упакованный список. Но можно переписать код с использованием другого цикла, как это принято делать в некоторых других языках. Сначала мы создаем копию входного массива, а затем в цикле изменяем его значения выполняя побитовое исключение. Почему не менять сам входной массив? Потому что входные параметры неизменяемы и это сделать невозможно внутри FunctionCompile. Вот как выглядит новый код:
dec5 = FunctionDeclaration[
fmask5,
Typed[{
"NumericArray"::["UnsignedInteger8", 1],
"NumericArray"::["UnsignedInteger8", 1]
} -> "NumericArray"::["UnsignedInteger8", 1]] @
Function[{maskingKey, payload},
Module[{result = payload},
Do[
result[[i]] =
BitXor[payload[[i]], maskingKey[[Mod[i - 1, 4] + 1]]],
{i, 1, Length[payload]}
];
result
]
]
];
cmask5 = FunctionCompile[dec5, fmask5];
mask5[maskingKey_ByteArray, payload1Mb_ByteArray] :=
ByteArray[cmask5[maskingKey, payload1Mb]]FunctionDeclaration[name, dec] - декларирует сигнатуру функции с точным указанием типов аргументов и возвращаемого результата. Затем задекларированную функцию можно скомпилировать.
result = payload - эта строчка копирует исходный массив. Именно поэтому значения в result теперь можно менять.
Проверим быстродействие:
t5 = RepeatedTiming[mask5[maskingKey, payload1Mb]]
Что мы видим? Все эти накладные расходы на копирование, преобразования, передачу по значению и изменение значений в копии напрямую сделали код только медленнее! Но зато он эффективнее по использованию памяти.
У этого способа есть еще один минус. Не всякий пользователь сможет эту функцию скомпилировать из-за того что технология появилась относительно недавно и в версиях языка 12, 13 и 14 ведет себя по разному. Где-то код выше в принципе не скомпилируется. Плюс сама по себе компиляция занимает много времени. Конечно результат можно сохранить на диск, но это нужно сделать для всех поддерживаемых операционных систем. В итоге накладные расходы и сложность поддержки экспериментальной функции имею свои минусы и я продолжил поиск путей оптимизации.
LibraryLink
Как известно, ядро Wolfram Language написано на Си. Плюс многие критически важные функции тоже реализованы на Си. Можно ли самостоятельно загрузить в ядро такую функцию? Конечно да, это делается при помощи встроенной библиотеки LibraryLink. Она предоставляет функции для компиляции и использования кода на языке Си прямо в WL.
Как выглядит работа с ней:
Пишем код на Си
Оборачиваем его в специальные инструкции из библиотеки "WolframLibrary.h"
На стороне WL компилируем при помощи CreateLibrary
И загружаем при помощи LibraryFunctionLoad
Готово!
Но лучше один раз увидеть... Далее будет часть кода на Си.
В каждой библиотеке на языке Си необходимо всегда выполнять ритуал импорта вот такой:
#include "WolframLibrary.h"
#include "WolframNumericArrayLibrary.h"Затем для ядра WL необходимо определить три функции, которые инициализируют библиотеку, деинициализируют и возвращают версию LibraryLink, под которую библиотека была скомпилирована:
DLLEXPORT mint WolframLibrary_getVersion() {
return WolframLibraryVersion;
}
DLLEXPORT int WolframLibrary_initialize(WolframLibraryData libData) {
return LIBRARY_NO_ERROR;
}
DLLEXPORT void WolframLibrary_uninitialize(WolframLibraryData libData) {
return;
}Есть еще небольшая тонкость для работы этой библиотеки на всех ОС. Надо добавить зависимости и одну инструкцию вот так:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BYTE uint8_t
Все готово. Теперь приступим к написанию основного кода.
Первое, что я сделал - это переписал алгоритм маскирования в лоб. Вот как выглядит функция, которая его реализует:
DLLEXPORT int mask6(WolframLibraryData libData, mint Argc, MArgument *Args, MArgument Res) {
//get payload and length
MNumericArray nMask = MArgument_getMNumericArray(Args[0]);
BYTE* mask = (BYTE *)libData->numericarrayLibraryFunctions->MNumericArray_getData(nMask);
mint maskLen = MArgument_getInteger(Args[1]);
//get maskingKey and length
MNumericArray nArr = MArgument_getMNumericArray(Args[2]);
BYTE* arr = (BYTE *)libData->numericarrayLibraryFunctions->MNumericArray_getData(nArr);
mint arrLen = MArgument_getInteger(Args[3]);
//create new result array
BYTE *result = (BYTE*)malloc(sizeof(BYTE) * arrLen);
//bit xor
for (size_t i = 0; i < arrLen; i++) {
result[i] = arr[i] ^ mask[i % maskLen];
}
//creating a struct for sending to WL side
MNumericArray nResult;
libData->numericarrayLibraryFunctions->MNumericArray_new(MNumericArray_Type_UBit8, 1, &arrLen, &nResult);
memcpy((uint8_t*)libData->numericarrayLibraryFunctions->MNumericArray_getData(nResult), result, arrLen);
//return result and free memory
MArgument_setMNumericArray(Res, nResult);
free(result);
return LIBRARY_NO_ERROR;
}
Важно отметить, что:
Все функции подключаемые к ядру WL должны иметь аргумент и возвращаемые результат как указано выше.
libData- структура с набором функций для связи с ядромArgc- число аргументов на стороне WLArgs- сами аргументыRes- структура в которую записывается результат - то, что вернется на стороне WLНа стороне Си возвращается код ошибки
Вернемся обратно в блокнот и скомпилируем этот исходник вот так:
Get["CCompilerDriver`"];
Get["LibraryLink`"];
lib = CreateLibrary[File["internal.c"], "internal"]; В lib сохранился путь к dll-файлу с машинным кодом, специфичным для ОС. Загрузить из него созданную функцию можно вот так:
cmask6 = LibraryFunctionLoad[
lib,
"mask6",
{"ByteArray", Integer, "ByteArray", Integer},
"ByteArray"
]А затем создаем более удобное определение, вид которого совпадет с предыдущими вариантами:
mask6[maskingKey_ByteArray, payload_ByteArray] :=
cmask6[
maskingKey, Length[maskingKey],
payload, Length[payload]
]И измерим время:
t6 = RepeatedTiming[mask6[maskingKey, payload1Mb]]
Да, действительно эффективность снизилась значительно сильно по сравнению с двумя последними вариантами. Но зато теперь мы можем без особых сложностей и преобразований передавать массив байт и возвращать массив байт. Далее необходимо очень внимательно посмотреть на код и понять как теперь улучшить сам алгоритм!
Я приведу сразу весь список улучшений, которые можно сделать:
Можно избавится от i % maskLen используя двойной цикл
int k;
int len = arrLen - arrLen % maskLen;
for (size_t i = 0; i < len; i = i + maskLen) {
for (size_t j = 0; j < maskLen; j++) {
k = i + j;
result[k] = arr[k] ^ mask[j];
}
}
for (size_t i = len; i < arrLen; i++) {
result[i] = arr[i] ^ mask[i % maskLen];
}
/* вместо
for (size_t i = 0; i < arrLen; i++) {
result[i] = arr[i] ^ mask[i % maskLen];
}*/Кажется, что операций стало больше, но хвост почти не занимает времени, а вот замена одного оператора остатка от деления на одно присвоение и одно сложение дает очень существенную разницу.
Далее если внимательно изучить руководство по LibraryLink, то можно понять, что создание
result- лишняя операция и тем более копирование результата в итоговый массив. Дело в том, что у любого созданного массива (MNumericArray()) можно извлечь указатель на сам участок памяти где хранятся сырые данные в виде массива чисел. Поэтому можно его и использовать в качествеresult:
MNumericArray nResult;
libData->numericarrayLibraryFunctions->MNumericArray_new(MNumericArray_Type_UBit8, 1, &arrLen, &nResult);
BYTE *result = (BYTE*)libData->numericarrayLibraryFunctions->MNumericArray_getData(nResult);
/* вместо
BYTE *result = (BYTE*)malloc(sizeof(BYTE) * arrLen);
MNumericArray nResult;
libData->numericarrayLibraryFunctions->MNumericArray_new(MNumericArray_Type_UBit8, 1, &arrLen, &nResult);
memcpy((uint8_t*)libData->numericarrayLibraryFunctions->MNumericArray_getData(nResult), result, arrLen);
free(result);*/Итоговый код на Си будет вот такой:
DLLEXPORT int mask7(WolframLibraryData libData, mint Argc, MArgument *Args, MArgument Res) {
MNumericArray nMask = MArgument_getMNumericArray(Args[0]);
BYTE* mask = (BYTE *)libData->numericarrayLibraryFunctions->MNumericArray_getData(nMask);
mint maskLen = MArgument_getInteger(Args[1]);
MNumericArray nArr = MArgument_getMNumericArray(Args[2]);
BYTE* arr = (BYTE *)libData->numericarrayLibraryFunctions->MNumericArray_getData(nArr);
mint arrLen = MArgument_getInteger(Args[3]);
MNumericArray nResult;
libData->numericarrayLibraryFunctions->MNumericArray_new(MNumericArray_Type_UBit8, 1, &arrLen, &nResult);
BYTE *result = (BYTE*)libData->numericarrayLibraryFunctions->MNumericArray_getData(nResult);
const int len = arrLen - arrLen % maskLen;
int k;
for (size_t i = 0; i < len; i = i + maskLen) {
for (size_t j = 0; j < maskLen; j++) {
k = i + j;
result[k] = arr[k] ^ mask[j];
}
}
for (size_t i = len; i < arrLen; i++) {
result[i] = arr[i] ^ mask[i % maskLen];
}
MArgument_setMNumericArray(Res, nResult);
return LIBRARY_NO_ERROR;
}И последнее, но уже на стороне WL. Каждый раз при вызове библиотечной функции массив байт будет копировать из памяти, которая доступна ядру в ту память, которая доступна библиотечной функции. С одной стороны это более безопасно, так как даже если внутри библиотечной функции изменить входной массив, то это не повлияет на то, что происходит в сессии ядра. С другой стороны - копирование занимает время. Но у LibraryLink есть механизм использования общей памяти для аргументов. Это значит, что копирования не будет, а будет передача ссылки на уже существующий в сессии массив. Платой за это является то, что попытки поменять значения в общем массиве или очистить его приводят к падению ядра. В общем использовать этот механизм можно вот так:
cmask7 = LibraryFunctionLoad[
lib,
"mask7",
{
"ByteArray",
Integer,
{LibraryDataType["ByteArray"], "Shared"},
Integer
},
"ByteArray"
]Ну а далее все как обычно:
mask7[maskingKey_ByteArray, payload_ByteArray] :=
cmask7[
maskingKey, Length[maskingKey],
payload, Length[payload]
]
t7 = RepeatedTiming[mask7[maskingKey, payload1Mb]]Посмотрим, что получилось!
Итоговая разница в скорости выполнения с самой первой наивной реализацией в 2550 раз, а с самой быстрой предыдущей реализацией, скомпилированной для LLVM в 5.8 раз. В итоге теперь данные размером в 1 Мб маскируются и демаскируются примерно за 666 мкс, что как бы намекает...
Выводы
Еще раз повторюсь, что в первую очередь пытался продемонстрировать подход к написанию эффективного кода для Wolfram Language. Да, в итоге я обратился к Си, но и этот способ имеет право на жизнь и часто нами используется в различных библиотеках. Подтвердилось ли, что WL - медленный язык? И да и нет. Если писать код бездумно - то уже ничего не поможет, если же погрузиться в WL дальше уровня решения уравнений и взятия интегралов и использовать его как язык программирования - то всегда можно найти эффективное решение для многих задач. Всем спасибо за внимание!
