Привет, Хабр!

В прошлой статье мы, команда разработки платформы для А/Б экспериментов в компании Okko, начали рассказывать историю создания одного из компонентов этой платформы— сервис сплитования трафика.

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

В статье мы продолжим рассказ об оптимизациях и улучшениях, однако здесь речь пойдет про детальные и последовательные изменения в самом узком месте сервиса. Приготовьтесь к более высокому уровню Python-магии.

Предыстория

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

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

На клиенте стоит таймаут всего в 10 мс. Значит, сервис без учёта сети и прочих инфраструктурных задержек должен отвечать быстрее. Ставим себе условный таргет в 5 мс на расчёт всех сегментов. Цель есть.

Собственно, а что такое сегмент? Сегменты пользователей бывают абсолютно разными. Сегмент — это алгебрологическое выражение с использованием информации о пользователе и его устройстве.

Примеры некоторых сегментов:

• мужчина

• мужчина старше 18

• мужчина старше 18 и с активной подпиской

• мужчина старше 18 и с активной подпиской на платформе Smart TV

• мужчина старше 18 и с активной подпиской на платформе Smart TV c версией клиента 42 и более

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

Инструмент был найден довольно быстро — json-logic. Это те же выражения, но в формате json, а json’ы писать в базу и кидать между сервисами мы все умеем :)

Пример json-logic выражения для сегмента «возраст 18 и старше и с устройства на iOS»:

{
  "and": [
    {">=": [{"var": "age"}, 18]},
    {"==": [{"var":  "client_os"}, "IOS"]}
  ]
}

GitHub solution

За первую версию вычислялки сегментов взяли одну из реализаций json-logic, найденную в GitHub. Всё завелось, сегменты считаются, сервис работает. Надо оценить качество работы — за сколько отвечает сервис.

12 мс — неприемлемо много. Сразу же стали искать ботлнек.

Как видно из флеймграфа, почти 70% времени уходит только на расчёт сегментов, а значит, надо ускоряться в этом месте

Локальный замер показал, что время расчета сегментов очень быстро растёт с ростом количества сегментов. Уже при каких-то 100 сегментах расчёт занимает 5 мс.

Ленивые вычисления

Чтобы легко и удобно работать с json в других процессах платформы, было решено зафиксировать структуру построения сегментов таким образом:

segment ::= user_segments AND device_segments
user_segments ::= user_segment_1 AND user_segment_2 AND … AND user_segment_N
device_segments ::= device_segment_1 OR device_segment_2 OR … OR device_segment_N,

• user_segment_i — произвольный сегмент о пользователе, проверяющий наличие подписки, дату регистрации, пол, возраст  и т.п.

• device_segment_i — произвольный сегмент об устройстве, проверяющий платформу, вендора, версию и т.п.

Сегменты часто проводятся не над одной платформой пользователей. Бывает сразу  Android и iOS, и всякие телевизоры. Когда надо проверить несколько раз, какая у пользователя платформа, по правилам алгебры логики достаточно найти только первое истинное утверждение, а значит, остальные можно не считать.

Такая оптимизация известна нашему сообществу как «Ленивые вычисления».

И по ожиданиям, при равномерном распределении пользователей по платформам и типам устройств, оптимизация должна была кратно уменьшить количество операций в json-logic. Что и произошло:

Статические оптимизации выражений

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

Одна из таких закономерностей: иногда встречались операции, у которых один или несколько операндов не зависели от информации о пользователе и его устройстве. 

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

Так появился этап статических оптимизаций, при котором все выражения сегментов максимально упрощались, а затем можно было вычислять «в бою» уже оптимизированные выражения.

В список оптимизаций попали:

• предрассчитывать ветви выражения, которые не зависят от информации о пользователе;

• убирать недостижимые ветви путем оптимизации логических операций, когда результат может быть однозначно определен заранее.

Также этот подход позволил добавлять в виртуальную машину оптимизаторы и других операторов, в том числе наших самописных (среди таких сравнение версий устройства).

Динамические оптимизации выражения

Пока заводились сегменты, заметили другую интересную особенность — часть экспериментов проводятся над одними и теми же группами пользователей. Получается, когда приходит запрос, надо вычислить 100 сегментов, среди которых несколько раз проверить, что пользователь с подпиской, и несколько раз проверить, что версия его телевизора не ниже 42.

И тут появилась классическая идея оптимизации — добавить кеш.

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

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

user = {"platform": "android", "version": "42.1.10", "sex": "male", "subscription": True}
expression = {
    "and": [
        {"or": [
            {"==": [{"var": "platform"}, "android"]},
            {"compareVersion": [{"var": "version"}, "42.0"]}
        ]},
	    {"and": [...]},
    ]
}

Тогда кеш должен получиться таким:

{"==": [{"var": "platform"}, "android"]} => True
{"compareVersion": [{"var": "version"}, "42.0"]} => True
{"or": [{"==": [{"var": "platform"}, "android"]},{"compareVersion": [{"var": "version"}, "42.0"]}]} => True
...

В теории всё очень просто, но продвинутый пользователь Python знает, как задушить змею что дикт, коим является выражение, нельзя просто так сделать ключом другого дикта, которым будет кеш.

Конечно, можно  написать свой сабкласс дикта с определенным хеш-методом, ведь экспрешены всё равно не меняются по ходу работы сервиса. Однако появился вариант приятнее в реализации и поддержке.

По синтаксису выражения у дикта всегда один ключ, соответственно, и одно значение, а значение всегда список из примитивов либо других таких же выражений. Так давайте заменим все выражения на тюпл. У выражения-тюпла будет два элемента, ключ и значение, а список-значение тоже преобразуем к тюплу. Такая структура уже хешируемая.

Преобразование выглядит примерно так:

{"+": [42, 123]} => ("+", (42, 123))

Занимательно, что такое преобразование тоже дало ускорение. Выходит, что итерироваться по тюплу оказывается быстрее, чем по дикту. Мелочь, а принесла ускорение.

Когда выражение упаковано в тюпл, можно реализовать и кеширование.

Вот вы сейчас наверняка удивились, что кеш успеха не принес. Даже наоборот, стало только хуже. Мы, честно, тоже удивились такому результату.

После некоторых исследований поняли, почему реальность не совпала с ожиданиями.

Оказалось, запись и проверка в кеше оказывались дольше, чем просто вычислить выражение. Ускорение получалось только в искусственном кейсе, когда части выражения дублировались неестественно много. А поскольку реальность не искусственный кейс, от изменений в таком виде отказались.

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

И тут мы плавно подходим к тому, чтобы заметно усложнить логику библиотеки, в частности, основного метода вычисления выражений. Задача становится  похожа на написание своего интерпретатора языка на Python, а нам в проекте хотелось бы не космолёт конструировать, а простое в поддержке решение.

Компиляция Python

Статические оптимизации исчерпали себя, с динамическими не особо получилось. Решили прибегнуть к тёмной магии, о которой принято говорить только на собесах, чтобы блеснуть познаниями,  — компиляция Python-кода в машинные инструкции.

Немного полистав интернет, нашли три основных кандидата.

Mypyc

В кругах разработчиков на Python есть популярный анализатор кода Mypy.

Уникальность в том, что он проверяет аннотации в коде и подсвечивает несостыковки.

Мы в Okko очень любим его использовать, наш код полностью аннотирован, везде указаны типы с точностью до объектов, вложенных в дженерики.

Однако мало кто знает, что у Mypy есть подпроект — Mypyc. Это транслятор строго типизированного кода в Си, с возможностью потом его компилировать в динамические библиотеки и бесшовно линковать к Python.

По заявкам авторов проекта можно получить ускорение x4 на голом коде и x10 на коде, специально оптимизированном под транслятор. Интерфейс использования очень прост, а дополнительных изменений в Python-коде не нужно.

Сложилось ощущение, что достаточно выполнить в проекте mypyc app/utils/json_logic и всё заработает быстрее как минимум в 4 раза.

Но реальность оказалась не такой сказочной:  вместо кратного ускорения увидели кратное замедление!

Как так-то?! Звучит как бред.

Потратив немало времени и литры кофе, нашли причину.

Чтобы рассказать, как так вышло, нужно еще немного рассказать вам о Mypyc.

Транслируя код в Си, никто не обещает, что int в Python будет переложен в int32 или int64, какой есть в Си, и по аналогии float, str и bool (речь о сложных объектах пока не идёт).

В Mypyc существует собственная реализация стандартных типов данных Python, которые работают быстрее будут использованы, если транслятор однозначно определит, что ими можно пользоваться

Все эти типы также поддерживают стандартные операции арифметики и сравнения: числа можно складывать с числами, а строки со строками. 

Например, такая вот функция, которая складывает два целых числа:

Немного кода

После компиляции будет выглядеть вот так:

Немного кода

CPyTagged — представление целых чисел, о котором написано в документации к Мypyc. 

Наблюдательный читатель заметит, что CPython оперирует PyObject, а эта функция отдает CPyTagged. А значит, где-то в коде есть конвертация в PyObject.

И она действительно есть. Вот она:

Много кода

В ней происходят проверки, что, вызывая из python функцию, в неё передаются именно целые числа, а не что-то иное.

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

А что будет, когда заявляется, что функция может сложить две переменные, которые могут быть либо целыми числами, либо вещественными?

В такой ситуации Mypyc не знает на этапе компиляции, какой выбрать тип. Он сможет динамически выбирать? Давайте исследовать!

Оригинальная функция:

Много кода

Из неё получаются две функции на Си:

Очень много кода

В них всё так же:  проверка входных параметров на соответствие заявленным типам, затем вызов функции PyNumber_Add, которая, вероятно, и складывает числа. И опять проверка возвращаемого значения на соответствие заявленным типам.

Вроде также, но что это за функция? Первая строка в гугле и переходим к документации к CPython!

Получается, что Си-код просто проверяет, что переменные нужных типов и вызывает через c-api то, что было бы вызвано, если не компилировать оригинальный код. 

Потому на каждую арифметическую или логическую операцию в json-logic идёт бонусом валидация. Это и производит такую значительную задержку.

Второй раз за проект натыкаемся на универсальную либу, которая ввиду своей универсальности нас только тормозит.

Cython

Второй популярный инструмент для ускорения python кода — Cython. Что это такое и как его использовать довольно подробно описано в других статьях. Скажу только, что он тоже умеет компилировать нативный код, а также имеет свой собственный синтаксис, переписав на который нативный код, можно получить еще большее ускорение.

Естественно, первым шагом было попробовать скормить компилятору код «как есть», надеясь, что он нас правильно поймет, и получится хорошее ускорение.

Но нет, такой вариант не прокатил, компилятор не смог его скомпилировать.

Вторым этапом стала разбивка кода на модули по несколько функций-операторов и частичная компиляция их. Тут уже какой-то успех появился, получилось скомпилировать операторы. Немного  и не самые используемые операторы, которые к работают только с одним типом данных.

Третий этап — попытка что-то переписать на синтаксис Cython. С этим инструментом пришлось взаимодействовать впервые, поэтому попытки хоть как-то ускорить работу операторов обламывались на невозможность описать полиморфный код на таком языке. Либо не получалось добиться ускорения больше, чем получили на втором этапе.

Четвертый этап. Пытаемся собрать основную функцию библиотеки json-logic, которая производит вызов операторов и рекурсивно вычисляет подвыражения. К собственном удивлению, это получилось. Функция скомпилировалась и стала работать быстрее. Правда, всего на 10-15%.

Небольшое, но ускорение. Однако! Если решиться его использовать в проекте, значит, заносим зависимость от компилятора, усложняем процесс сборки, а часть проекта становится вообще на другом языке. Учитывая это, решили пока повременить с этим инструментом.

Pypy

Помимо привычного нам CPython существуют и другие интерпретаторы языка, которые чем-то лучше и чем-то хуже CPython. Один из таких интерпретаторов — PyPy. Его уникальная особенность в обладании  JIT-компилятором, то есть во время работы сервиса, самые используемые места компилируются из байт-кода в машинные инструкции.

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

Тестовые замеры библиотеки json-logic показали, что PyPy ускоряет код. На некоторых примерах до x2. Теоретически можно использовать РуРу  как решение проблемы скорости, однако есть нюанс!

Нельзя использовать РуРу только для одной какой-то библиотеки, как Cython или Mypyc. Если переезжать на РуРу, то всем проектом. А это значит, необходимо тщательное тестирование остальных этапов сплитования и других процессов, проверка на совместимость с РуРу используемых библиотек.  Главное, появляется риск, что РуРу отличается от Cython в каких-то узких вопросах, например, в работе с GIL или GC, что может выстрелить в ногу.

GIL и GC нам и так мешали в проекте. С ними тоже связано много исследований, но об этом будет в следующей статье. Ставьте лайк, подписку, колокольчик, чтоб не пропустить статью.

Было решено использовать РуРу, только если не будет менее рискованных способов ускориться.

Компиляция json

Как часто вам приходится думать о Римской империи о деревьях? Примечательно, что json выражения имеют древовидную структуру. То есть в узле дерева находится операция, а листья — примитивы.

По определению это abstract syntax tree или AST, а построение ast дерева — один из этапов, которые проходит Python-код при запуске программы.

Тогда для любого json-выражения должно быть Python-выражение, которое всегда имеет тот же результат вычислений. Но Python-выражение должно быть быстрее интерпретации json-logic.

Оценим это на примере.
Экспериментальный сегмент в виде json:

Он же записанный в виде Python-выражения:

Замеряем время исполнения:

Результат невероятный — в 30 раз быстрее!

Как будто то, что искали. Если найти способ автоматизированным путём переводить любое json-выражения в Python байт-код, его можно будет использовать без риска для остального проекта, как было бы с PyPy или Cython.

И такой способ был найден. Команда реализовала транслятор, который превращал json-logic выражение в Python callable-объект, который можно вызывать в коде как обычную функцию.

Много кода

Сравнение AST-компилятора с предыдущими версиями json-logic:

Невероятное ускорение! И это не предел, его можно сочетать с предыдущими идеями, хоть они и не дают такого же фееричного эффекта.

Цель в 5 мс и менее для 100 сегментов таким способом была достигнута.

Получается, самый быстрый способ вычислять выражения — переписать их на наш любимый Python. Чтобы добиться невероятной скорости в этой задаче, нет необходимости ни в магических компиляторах Python в С, ни в оптимизациях библиотеки вычисления json-выражений. 

PS: В ходе работы над проектом получилось де факто написать собственную реализацию библиотеки json-logic, заточенную под максимальную производительность. Если у вас есть потребность, напишите, и, если желающих будет много, мы выложим нашу реализацию в Open-Source