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

Шёл 2018 год, и я как раз присоединился к команде, которая поднимала новую среду выполнения для Python (тогда её прозвали Pyro, а теперь она называется Skybison). Была поставлена цель: опираясь на 30-летний опыт инженерных исследований в инженерии VM и народную мудрость заново спроектировать всё с нуля, чтобы получилась система с высокой производительностью. Важное уточнение: мы могли применять только одну кодировку строк: UTF-8 [1] (с прицелом на будущее).

Мы начали с маленького ядра на C++, на котором можно было запускать только байт-код, выданный компилятором среды выполнения CPython. Когда я подключился к работе, акцент делался на добавлении новых возможностей. В тот момент основная задача была — заставить importlib работать. Нам требовались некоторые строковые функции, например, str.rpartition, так что я просто набросал её реализацию на коленке. С её помощью удалось наладить работу find_spec и некоторых других функций.

В конце концов, мы довели до ума importlib, затем приступили к работе над «минимальной версией Django», а потом стали расставлять бенчмарки для «рабочей нагрузки Django». Это было примерно через год после начала работы, в октябре 2019.

Реально круто наблюдать, как проект вырастает у тебя на глазах. Тот код, который сначала выводился в оболочку CPython, чтобы можно было компилировать байт-код, управляя этим процессом прямо из среды выполнения (в реальной практике это дикость, но, чтобы дать проекту ход — в самый раз) теперь был оснащён собственным компилятором байт-кода и мог работать на веб-сервере. Кроме того, мы его отпрофилировали и оптимизировали для повышения производительности.

К сожалению, чтобы среда выполнения на Python работала быстро, приходится повышать скорость кода Python. Вскоре мы сталкиваемся с самым странным узким местом, возникающим при парсинге URL в Django. Выглядит это несколько нелепо, как будто на strIndex затрачивается 90% времени выполнения для каждого запроса.

Теперь разрешите напомнить вам, как работает UTF-8: индексирование с входом в произвольную строку — это операция со сложностью O(N), так как длина разных кодовых пунктов (грубо говоря, символов) отличается. Приходится начать с начала и считать до тех пор, пока не доберётесь до искомой позиции в индексе. В тех средах выполнения, где используется UTF-8, хочется избегать вот таких циклов:

for i in range(len(s)):
    s[i]  # каждая операция над индексом имеет сложность O(N)!

а писать код примерно так:

for c in s:
    c  # у нас уже есть символ из str.__iter__, это быстро

Наш код на C++ для индексирования строки был похож на приведённый ниже. Основной его смысл в том, что str.__getitem__ вызывает offsetByCodePoints, чтобы превратить индекс (состоящий из кодовых пунктов) в сдвиг (в байтовом пространстве). Далее вызывается offset, при помощи которого циклически перебирается закодированная строка и совершается переход на numChars байт (в зависимости от ширины каждого кодового пункта):

bool METH(str, __getitem___intrinsic)(Thread* thread) {
  // ...
  if (0 <= idx && idx < len) {
    word offset = self.offsetByCodePoints(0, idx);
    if (offset < len) {
      // .. выбрать кодовый пункт и поместить его в стек ...
      return true;
    }
  }
  // ...
}

word RawDataArray::offsetByCodePoints(word index, word count) const {
  const byte* data = dataArrayData(*this);
  return offset(data, length(), index, count);
}

static inline word offset(const byte* data, word len, word index, word count) {
  if (count >= 0) {
    while (count-- && index < len) {
      index += UTF8::numChars(data[index]);
    }
    return Utils::minimum(index, len);
  }
  while (count < 0) {
    index--;
    if (index < 0) return -1;
    if (UTF8::isLeadByte(data[index])) count++;
  }
  return index;
}

Теперь, имея всё это в виду, рассмотрим мою реализацию str.rpartition, ту самую наскоро сработанную, о которой я упоминал выше (полностью коммит здесь):

class str:
    # ...
    def rpartition(self, sep):
        # TODO(T37438017): написать на C++
        before, itself, after = self[::-1].partition(sep[::-1])[::-1]
        return before[::-1], itself[::-1], after[::-1]

Хаха. Ох. Уф. Нет. Посчитаем, со скольких сторон она выглядит ужасно? В самом деле, rpartition должна работать совсем иначе, а именно перебирать строку в обратном направлении один раз (быстро!), разделяя её ровно дважды. А эта функция:

• Перестраивает строку в обратном порядке (выделяя для этого множество короткоживущих новых строк)
• Вызывает целую кучу методов
• Снова перестраивает строки в обратном направлении

Я переписал функцию, чтобы она работала правильно, и для этого пришлось вынести на поверхность детали реализации, заложенные в Python (парсинг аргументов, проверка типов), после чего результаты выводились в нашу быструю строковую утилиту из ядра:

class str:
    # ...
    def rpartition(self, sep):
        _str_guard(self)
        _str_guard(sep)
        return _str_rpartition(self, sep)

Разумеется, на тот момент этой быстрой строковой утилиты у нас ещё не было, и мне предстояло её реализовать. Посмотрите коммит, в котором она переписана, там есть интересный код на C++.

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

Заключение

Довольно скромный вывод из этой статьи будет в том, что по профилям производительности всей истории не расскажешь. Если бы мы рассмотрели только профили C++ для нашей среды выполнения в Python, то увидели бы, что функция среды выполнения, strIndex — горячая. В данном случае важно не то, что нам требуется ускорить функцию strIndex.

Напротив, дело в том, что функцию strIndex слишком часто вызывает какая-то другая функция. Притом, что мне это было известно — в конце концов, именно я провоцировал проблемы с производительностью, зачастую судить о таких случаях гораздо сложнее, особенно, в сравнительно крупных и старых системах. Многоязычный профилировщик может подсказать, что str.rpartition вызывалась N раз, и что во вложенных кадрах вызова str.__getitem__ вызывалась N*1000 раз (например), и именно оттуда опосредованно шли вызовы strIndex. После этого напрашивается вывод, что реализация str.rpartition оставляет желать лучшего.

---

1. Точнее, UTF-8 с суррогатными парами. Но не UCS-1, UCS-2 или UCS-4. Один парень из нашей команды так много занимался реализацией новых кодеков, что мы прозвали его UTF-8. Иногда UTF-8 случайно находил переполнения буферов кучи в CPython, пытаясь разобраться, как именно работает их реализация CJK. ↩

P.S. Обращаем ваше внимание на то, что у нас на сайте проходит распродажа.