Как увеличить скорость обработки solidity sourcemappings строк
Существует бесконечное количество интересных и крутых задач. Когда такая прилетает, разработчик, как правило, готов ко всяким трудностям и неожиданностям. Закладывается время на решение, проводится планирование и риск пролюбить все сроки минимизируется.
Но этот случай казался простейшей рутиной. Один из наших проектов связан с solidity. Команда ̶з̶а̶н̶и̶м̶а̶е̶т̶с̶я̶ ̶ч̶е̶р̶н̶о̶й̶ ̶м̶а̶г̶и̶е̶й̶ разрабатывает анализатор байт-кода, который находит разные уязвимости. И чтобы потом пользователю показать, где именно в его коде уязвимость, помимо прочего используются данные solidity sourcemappings. Одна из подзадач — парсить эти строки.
Если вкратце, то выглядят они следующим образом. Строка в этом формате представляет собой список узлов, разделенных символом ;. В свою очередь узел состоит из пяти элементов (s:l:f:j:m), разделенных символом :. Более подробно о том, что значит каждое поле узла и какие значения они могут принимать можно почитать в документации. Пример такой строки: 1:2:1;1:9:1;2:1:2;2:1:2;2:1:2
С этими строками не всё так просто — есть алгоритм их сжатия. Он очень простой и реализует всего 2 правила:
- Если поле пустое — используется значение этого поля из предыдущего узла,
- Если символ
:пропущен — все последующие поля в этом узле считаются пустыми.
Реализация этих правил приводит вот к такому преобразованию:1:2:1;:9;2:1:2;; => 1:2:1;1:9:1;2:1:2;2:1:2;2:1:2
Собственно, задача простейшая. На вход подается сжатая строка и индекс. На выходе должен быть распакованный узел под этим номером. EZ! Единственный подвох — на вход подаётся очень большая строка (для тестов использовали строку в 84 610 000 символов).
Первый вариант отрабатывал около 40 секунд. К сожалению его исходники не сохранились, но общая идея там была неправильная: сначала разбивали строку на массив подстрок с помощью функции split, потом парсили каждый узел отдельно, каждый раз пробегая до ближайшего ненулевого. В связи с медленной работой первого варианта возникла потребность в оптимизации.
Сначала я избавился от всех ненужных операций. Нам не нужна коллекция узлов, только один конкретный узел. Просто буду бежать от начала строки, искать символ ;. Затем брать подстроку и заполнять данными узел. Бежать надо до тех пор, пока номер узла не станет равным целевому индексу (ну или мы больше не найдем ни одного узла).
Первый вариант выглядит так:
Не самый точный вариант измерения, но в целом для этой функции сойдет. Нам ведь не нужна борьба за микросекунды, правильно? Но на случай, если кто-то вдруг ищет как можно профилировать Python скрипты:
# place your filename instead of sourcemappings.py
python -m cProfile -o out.prof sourcemappings.py && snakeviz out.profВ результате работы этого скрипта получаем вот такую удобную web страницу:
Реализация алгоритма для поиска последнего узла в очень большой строке дает вот такой результат:
node_at took: 8.769877910614014Почти 9 секунд. По сравнению с прошлым вариантом — ускорение в 4 раза, отлично!
По идее здесь надо было успокоиться и пойти заняться чем-нибудь полезным. Но стало интересно, можно ли как-то эффективнее распаковывать sourcemappings. К примеру, давным давно в sse4.2 завезли функции работы со строками. Может они тут помогут? А может дело вообще в каких-то внутренних механизмах работы Python?
Короче, решил продолжить и для начала написал почти то же самое на golang.
Накидал вот такой код:
Интересно то, что сначала сделал без switch, красиво. Но оно работало чуть-чуть медленнее. Где-то 0.1–0.2 секунды в среднем. Но средний результат — 0.88 секунды. В 10 раз быстрее чем самый быстрый мой вариант, написанный на Python.
Предложил команде подружить Python приложение с таким вот демоном, написанном на golang. Отправлять ему строку через redis, сокет, pipe или вообще создавать файл в /dev/shm/. Во всех этих случаях накладные расходы будут значительно меньше выигрыша, как я думал. Но это решение оказалось не подходящим — всё-таки слишком много времени тратится на получение результата и отправку запроса. К сожалению, результатов профилирования такой связки нет, поверил на слово команде, которая занимается проектом.
Тогда я решил написать библиотеку на C, потому что уж её точно можно интегрировать почти в любое место.
И получился вот такой код:
Здесь кода больше, чем в двух предыдущих версиях, но только потому, что используется два разных метода. Один не работает с read only строками, точнее модифицирует входную строку, использует strsep функцию. Но зато реализуется за 12 строк кода, довольно лаконично и эффективно (строки 26–39). Второй никак не модифицирует входную строку и работает ещё быстрее.
После пары сессий с профайлером (использую valgrind) добился лучшего результата: 0.1 секунды. Этот вариант меня полностью устроил и я спокойно пошел спать, потому что красноглазил над ним довольно долго.
Ниже 2 скрина, на которых видно на что в основном тратит время версия библиотеки на C. Вывод — стандартную библиотеку оптимизируют по максимуму, к примеру здесь используется AVX и SSE4.2 инструкции.
Пару дней решение тестировалось, после чего пришел вердикт — не подходит. Оказывается нам нужно все узлы поместить в коллекцию и потом каким-то хитрым алгоритмом их обрабатывать дальше.
Штош! Вернемся к решению на Python, потому что зачем нам все эти биндинги и ctype-ы?
Чуть-чуть доработав код получил вот такой вариант:
Этот вариант реализуется относительно быстро и работает не так уж долго — около 10 секунд. Возможно его будет достаточно, хотя я и подготовил вариант интеграции C библиотеки.
Пришлось немного модифицировать код. Полностью с ним можно ознакомиться здесь:
Идея достаточно простая. Делаем всё то же самое, что при поиске, только ещё попутно в выходной массив записываем текущий узел. То есть строка обрабатывается за 2 прохода — в первом считается количество разделителей узлов, а второй проход заполняет выходной массив. Данные узла при этом всё время остаются актуальными.
Загвоздка в том, как вернуть все эти узлы в Python код из библиотеки и как потом использовать результат. Есть много разных вариантов. Знающие люди рекомендуют SWIG и CFFI. Но здесь всего 2 функции, зачем стрелять пушкой по воробьям? Поэтому взял ctypes. Сначала очень хотел использовать как-нибудь пакет numpy, потому что его массивы как раз то, что мне надо в плане внутреннего устройства. Но не нашел, как правильно создать массив с нужными мне структурами внутри. Если кто-то это точно знает — оставьте коммент, пожалуйста.
Итак, код библиотеки возвращает указатель на массив. Поэтому в библиотеке есть функция, которая эту память освобождает. Сделаем RAII обертку, чтоб эта функция вызывалась в деструкторе, а указатель хранился в этом объекте. В целом достаточно простой код получился. Из минусов:
1. Не работает intellisense в VSCode. Т.е. он не предлагает список доступных полей и методов для объекта cnode_t.
2. Требуется собирать библиотеку перед использованием.
Результат работы такой:
C took: 0.5122084617614746last_node: b’9359':b’71':b’-1':b’o’:b’8', nodes_count: 26830000python took: 10.238852500915527last_node: b’9359':b’71':b’-1':b’o’:b’8', nodes_count: 26830000
Думаю если задаться целью, то можно еще немного ускорить. Наверняка здесь подойдет SSO (small string optimization), которая, возможно, позволит сократить количество копирований памяти. Но это попробую когда-нибудь потом.
Выводов на самом деле новых и нет. Просто можно без особых усилий связывать Python с эффективными библиотеками и не париться с микрооптимизациями Python кода, если уж возникла необходимость что-то ускорить. Очень рабочий вариант, подошедший нашей команде.
