Efficient Dart: оптимизация нагрузки на процессор во Flutter без пропуска кадра

На прошлой неделе я создал приложение Flutter для запуска генератора наборов Julia на сервере Python gRPC. В этом примере проекта обсуждается интеграция Flutter и Python. У меня было предубеждение по поводу того, что Python очень медленный. Удивительно, но, используя Numba и внося несколько изменений (@njit(parallel=True) и prange()) в исходный код Python, я добился прироста производительности примерно в 350 раз, измеряемого в кадрах в секунду (FPS) в пользовательском интерфейсе. Все происходит через gRPC с издержками сериализации/десериализации между процессами Flutter и Python.

Что меня удивило еще больше, так это реализация аналога Dart кода Python. Я ожидал, что современные Dart и Flutter будут быстрыми, но обнаружил, что они в три раза медленнее с точки зрения FPS, чем Python, работают внутри процесса и имеют заметные подтормаживания пользовательского интерфейса.

Можем ли мы оптимизировать производительность Dart для этой задачи, связанной с процессором, и победить Python/Numba? Давай выясним!

О задаче

Множество Жюлия— фрактал, тесно связанный с множеством Мандельброта. Вычисление множеств Джулии/Мандельброта может вызвать нагрузку на процессор и используется во многих тестах, таких как Mojo. Я выбрал набор Julia для создания анимированных фракталов путем изменения одного из параметров формулы.

Я использовал алгоритм escape для расчета набора для заданной области точек. Для каждой координаты (x, y), представляющей точку на комплексной плоскости, мы выполняем итерацию в цикле, составляя threshold количество итераций (по умолчанию — 100), вычисляя, принадлежит ли точка множеству или нет (расходится). Для каждой точки мы можем сохранить количество итераций, необходимых для ее проверки, а затем использовать его для раскрашивания и рендеринга пикселя. По сути, мы создаем метод, который может генерировать карту пикселей width и height, где каждый пиксель описывается количеством итераций цикла, необходимых для проверки числа (x, y).

Обзор приложения

Репозиторий Git можно найти здесь. Проект Flutter находится в папке app/. Остальные папки можно игнорировать (часть примера Python/gRPC):

app/
|-- grpc_generated/
|-- julia_native/
|-- julia_service.dart
|-- main.dart

• main.dart содержит пользовательский интерфейс и логику рендеринга, используя виджет RawImage для отображения набора Julia, полученного из потока, предоставленного...
• julia_service.dart, предлагающий абстрактный интерфейс для различных генераторов.
  
• julia_native/ содержит варианты реализации генератора наборов Julia в Dart, рассмотренные ниже.
  

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

Версия 1: Прямой перевод с Python на Dart

Вариант 1 представляет собой прямое преобразование этого кода Python. Он выполняется в основном потоке пользовательского интерфейса и служит основой для измерения производительности. Средний показатель FPS, достигнутый этим вариантом, составляет 37,4.

Во-первых, мы начнем с реализации некоторых недостающих частей, необходимых для расчета (воссоздание Complex числа и linespace из NumPy):

class _Complex {
  double real;
  double imag;

  _Complex(this.real, this.imag);

  _Complex operator +(_Complex other) =>
      _Complex(real + other.real, imag + other.imag);
  _Complex operator *(_Complex other) => _Complex(
      real * other.real - imag * other.imag,
      real * other.imag + imag * other.real);

  double abs() => sqrt(real * real + imag * imag);
}

List<double> _linspace(double start, double end, int num) {
  double step = (end - start) / (num - 1);
  return List<double>.generate(num, (i) => start + (step * i));
}

Далее делаем расчет:

List<int> _getSetAsHeightMap(
    int widthPoints, int heightPoints, int threshold, double position) {
  List<int> result = List<int>.filled(widthPoints * heightPoints, 0);
  double width = 4, height = 4 * heightPoints / widthPoints;
  double xStart = -width / 2, yStart = -height / 2;

  List<double> re = _linspace(xStart, xStart + width, widthPoints);
  List<double> im = _linspace(yStart, yStart + height, heightPoints);

  double r = 0.7;
  double a = 2 * pi * position;
  double cx = r * cos(a), cy = r * sin(a);

  for (int i = 0; i < heightPoints; i++) {
    for (int j = 0; j < widthPoints; j++) {
      result[i * widthPoints + j] =
          _checkInJuliaSet(re[j], im[i], cx, cy, threshold);
    }
  }

  return result;
}

int _checkInJuliaSet(
    double zx, double zy, double constX, double constY, int threshold) {
  _Complex z = _Complex(zx, zy);
  _Complex c = _Complex(constX, constY);

  for (int i = 0; i < threshold; i++) {
    z = z * z + c;
    if (z.abs() > 4.0) {
      return i;
    }
  }

  return threshold - 1;
}

_getSetAsHeightMap() возвращает сглаженную матрицу widthPointsxheightPoints с количеством итераций для каждой точки.

Функция _checkInJuliaSet() оценивает конкретную точку (x,y). Из приведенного выше кода вы можете понять, почему эти вычисления могут быть ресурсоемкими: существует 3 вложенных цикла. Например, для области 1000x1000 пикселей и средней итерации на точку, равной 50, мы можем ожидать, что на каждый пиксель будет выполнено 50 миллионов вычислений!

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

Darts изоляты

Я буду использовать изоляты, чтобы:

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

В Dart нет потоков, параллелизм достигается с помощью изолятов. Проще говоря, они поддерживаются потоками ОС и могут работать параллельно, но при использовании в Dart они не разделяют память (т. е. вы не можете напрямую обращаться к переменным в разных изолятах) и общаются через сообщения — аналогично веб-работникам в JS.

Изоляты — это золотая середина между параллелизмом без параллелизма (как в Python, JS/TS и Dart с одним изолятом) и параллелизмом с общей памятью и потоками (как в C/C++, C#, Java). За счет накладных расходов при перекрестной изоляции (все объекты должны быть скопированы по значению, в некоторых случаях сериализованы/десериализованы) Dart обеспечивает более надежную модель, менее подверженную сложным ошибкам (состояния гонки, взаимоблокировки, повреждение общего состояния и т. д.).

По умолчанию Dart предоставляет два API для работы с изолятами:

• Класс изоляции — API более низкого уровня, который требует времени и усилий для начала использования изолятов, предоставляет базовые средства, такие как порты, потоки, и оставляет на усмотрение разработчика решение и реализацию.
• Служебный метод compute() Flutter, который позволяет развернуть новый изолят, передать сообщение и обратный вызов и получить результат обратно.
  

В этом примере я буду использовать пакет isolate_pool_2, который является оболочкой API Dart Isolate и имеет несколько полезных функций:

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

Версия 2: Распараллеливание с использованием изолятов

Используя 10 изолятов, V2 достигает среднего значения FPS 97,1, что является значительным улучшением по сравнению с базовой производительностью.

// Skipping imports and _canceled, cancelSetGeneration(), and _position for brevity

late IsolatePool _pool;

Future<List<int>> _getSetAsHeightMapParallel(
    int widthPoints, int heightPoints, IsolatePool pool, int threshold) async {
  // ...
}

class GetBlockJob extends PooledJob<List<int>> {
  // ...

  @override
  Future<List<int>> job() async {
    List<int> result = List<int>.filled(widthPoints * im.length, 0);
    // ...
    for (int i = 0; i < im.length; i++) {
      for (int j = 0; j < widthPoints; j++) {
        result[i * widthPoints + j] =
            _checkInJuliaSet(re[j], im[i], cx, cy, threshold);
      }
    }

    return result;
  }
}

В V2 генерация набора Julia распараллеливается с использованием библиотеки IsolatePool, а та же логика из V1 заключена в класс GetBlockJob. Поскольку мы можем независимо работать над несколькими частями изображения, мы можем назначить разные «полосы», которые будут создаваться заданиями и затем объединяться в один список:

Future<List<int>> _getSetAsHeightMapParallel(
    int widthPoints, int heightPoints, IsolatePool pool, int threshold) async {
  var list = List.filled(widthPoints * heightPoints, 0);

  double width = 4, height = 4 * heightPoints / widthPoints;
  double xStart = -width / 2, yStart = -height / 2;
  List<double> im = _linspace(yStart, yStart + height, heightPoints);  

  int blockSize = (heightPoints / pool.numberOfIsolates).ceil();

  List<Future> futures = [];

  for (var i = 0; i < heightPoints; i += blockSize) {
    futures.add(pool
        .scheduleJob<List<int>>(GetBlockJob(
            widthPoints: widthPoints,
            heightPoints: heightPoints,
            width: width,
            height: height,
            xStart: xStart,
            yStart: yStart,
            im: im.sublist(i, min(i + blockSize, heightPoints)),
            threshold: threshold,
            position: _position))
        .then((v) {
      list.setAll(i * widthPoints, v);
    }));
  }

  await Future.wait(futures);
  return list;
}

Эта реализация устраняет заикания/зависания пользовательского интерфейса V1, поскольку в потоке пользовательского интерфейса не происходит тяжелой работы.

Версия 3: Использование Uint8List вместо списка

Давайте внимательно посмотрим, какие данные возвращаются нашим заданием по изоляции:

 @override
  Future<List<int>> job() async {

Мы возвращаем список целых чисел, размер которых по умолчанию составляет 64 бита/8 байт.

С другой стороны, каждая точка в нашем наборе Julia никогда не описывается числом больше 255, в julia_service.dart даже есть утверждение, которое не допускает более высоких пороговых значений:

  assert(iterationThreshold >= 1 && iterationThreshold <= 255,
      'Threshold must be between 1 and 255');

Хотя в Dart нельзя использовать однобайтовые целые числа, или можно?

К счастью, в Dart есть специальная библиотека typed_data, в которой есть ряд встроенных функций, помогающих эффективно перемещать байты. Давайте заменим List<int> на UintList8 повсюду в файле, вот так:

Future<Uint8List> _getSetAsHeightMapParallel(
    int widthPoints, int heightPoints, IsolatePool pool, int threshold) async {
  var list = Uint8List(widthPoints * heightPoints);
...

Обратите внимание, что внешние клиенты нашего кода ожидают получения List<int>, и, к счастью, Uint8List можно привести неявно, поэтому нет необходимости что-либо менять в методе getSetAsHeightMapAsBytesStream().

Помимо того, что Uint8List более компактен и экономит циклы ЦП при маршаллинге, обратите внимание, что его инициализация может быть быстрее. Например. List<int> требует, чтобы вы инициализировали его значениями при создании списка фиксированной длины, конструктор Uint8List не требует значения по умолчанию.

Благодаря этому небольшому изменению мы увеличим производительность почти на 400%! 178,5 фпс против базовых 37,4!

Версия 4: Улучшение однопоточной производительности

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

Мы можем прочитать класс _Complex и работать с отдельными координатами, пропустить операцию sqrt() (мы можем проверить условие выхода, сравнивая сумму в квадрате с 16, а не квадратный корень с 4), реализовать несколько оптимизаций вычислений в цикле. (используйте zx0zy0):

// Skipping imports for brevity

int _checkInJuliaSet(
    double zx, double zy, double constX, double constY, int threshold) {
  var zx0 = zx;
  var zy0 = zy;

  for (int i = 0; i < threshold; i++) {
    final zx0zy0 = zx0 * zy0;
    zx0 = zx0 * zx0 - zy0 * zy0 + constX;
    zy0 = zx0zy0 + zx0zy0 + constY;
    if ((zx0 * zx0 + zy0 * zy0) > 16) {
      return i;
    }
  }

  return threshold - 1;
}

Эта оптимизация позволяет достичь среднего значения FPS 47,2 в однопоточном режиме.

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

Версия 5: Объединение оптимизаций версий 3 и 4.

Вариант 5 включает улучшенные вычисления из версии 4 в параллельную реализацию версии 3. Он достигает 198,1 кадров в секунду (против 178,5 кадров в секунду).

Версия 6: Оптимизированное распределение работы между изолятами

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

При разделении работы между изолятами некоторые могут получить регионы с меньшим количеством точек, требующие большого количества итераций, а некоторые — больше. Таким образом, перегруженным изолятам потребуется больше времени, чтобы вернуть свою часть, которая будет объединена в конечные результаты. Чтобы преодолеть эту неравномерную нагрузку, мы можем еще больше разбить области, отданные изолятам, т. е. вместо 10 областей, отданных 10 изолятам, мы можем дать им 40 меньших полос, и в этом случае менее вероятно, что один изолят будет усердно работать над одной большой полосой, требующей больших вычислительных ресурсов.

В версии 6 основным отличием от версии 5 является новый расчет размера блока, который включает коэффициент 4x для более равномерного распределения рабочей нагрузки между изолятами.

Future<List<int>> _getSetAsHeightMapParallel(
    int widthPoints, int heightPoints, IsolatePool pool, int threshold) async {
  // ...
  int blockSize = (heightPoints / (pool.numberOfIsolates * 4)).ceil();
  // ...
}

// Rest of the code remains the same as V5

Получаем дальнейший скачок с 198,1 до 219,1 fps. Путем точной настройки количества изолятов и коэффициента разделения мы стремимся к дальнейшим улучшениям. Я попробовал 9 изолятов и разделение x3, и это работало лучше, чем 10/x4 - 225,9 кадров в секунду.

Измерения и предположения

В качестве меры я использую количество кадров в секунду (FPS). Счетчик FPS отображается в верхнем левом углу окна. Чтобы начать измерение, дважды щелкните кнопку Play, и анимация будет повторяться три раза с регистрацией среднего значения FPS.

Номера указаны для Flutter 3.13.5, macOS 13.6, релизной сборки; MacBook Pro с процессором M1 Pro (8 ядер производительности и 2 ядра эффективности).

FPS показывает, сколько наборов Julia (пиксельных карт, преобразованных в List<int>) получено за данную секунду в событии Stream.listen. Счетчик FPS включает в себя расчеты набора Джулии, времени сборки виджета и накладных расходов на создание асинхронных/потоковых/списков, а также других факторов. Он не измеряет чистое время выполнения цикла Julia, а загружает весь конвейер Flutter, предполагая, что большая часть времени ЦП тратится на генерацию набора Julia.

Рендеринг/растеризация игнорируется как фактор, поскольку предполагается, что он выполняется быстро и выполняется в отдельном потоке растеризации. Как видно на странице «Производительность инструментов разработчика Dart», время растра почти ни в одном кадре не превышает 1 мс, что указывает на то, что большая часть работы ЦП происходит в потоке пользовательского интерфейса (вычисления, создание виджетов, распределение списков и т. д.).

Заключение

Изменив исходную реализацию, мы смогли получить шестикратный прирост производительности и восстановить отзывчивость пользовательского интерфейса!

Мы опробовали шесть различных вариантов реализации Dart (по умолчанию 10 вариантов):

И график:  

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

Принципы можно экстраполировать на любое приложение Flutter/Dart:

• Разгрузите интенсивные вычисления на изоляты
• Тщательно продумайте, какие данные распределяются между изолятами, старайтесь сохранять их небольшими, чтобы минимизировать накладные расходы на сериализацию/десериализацию
  
• Используйте много изолятов, балансируйте рабочую нагрузку между ними
  
• Повозитесь со своим алгоритмом, особенно при использовании в цикле
  
• Используйте DevTools, профилируйте свой код
  

DevTools

В этой статье я почти не коснулся инструментов разработчика (доступных в VSCode, если у вас установлено расширение Dart/Flutter), хотя я использовал их, чтобы поэкспериментировать и поработать с кодом:

1. Представление производительности для быстрой оценки частоты кадров и понимания проблем с пользовательским интерфейсом и потоками растеризации.
2. CPU Profiler — чтобы узнать, где было потрачено больше всего процессорного времени.
   
3. Просмотр памяти — для диагностики снижения производительности при запуске анимации и выявления утечек памяти, которые я исправил.