Если вы занимались профилированием своего приложения, то, глядя на CPU Flame Chart, вероятно испытывали смесь досады и азарта, глядя на особо «жирный» метод. Досады – что ваша программа всё ещё не идеальна по скорости. Азарт – от того, что вы можете докопаться до причины проблемы и отжать для процессора ещё немного свободного времени на более полезные вычисления. По крайней мере, я регулярно становлюсь жертвой обоих этих чувств, чему данная статья и обязана своим появлением.

Мой кейс – это попытка выжать из игрового движка Flame больше скорости и возможностей, чем он может «из коробки». Гейм-разработка имеет свои особенности по сравнению с «парсингом большого json» или устранением подлагивания при разовом проигрывании анимации, как минимум потому что здесь потенциально объёмные вычисления производятся абсолютно на каждом кадре. Так что, наверное, мой опыт не сильно будет перекликаться с теми проблемами, которые встречает большинство Flutter-разработчиков.

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

Визуализируем проблему

Итак, допустим вы открыли Flame Chart и видите какие-то огромные forEach, неэффективные HashSet и HashMap:

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

Конечно, когда на графике на первые места выплывают «внутренности» движка и приватные методы встроенных структур данных, первым шагом стоит посмотреть, а можем ли мы как-то уменьшить количество циклов? Здесь решение зависит от вашего конкретного случая. Беда в том, что это может не решить проблему, и набивать массив кучей элементов, а потом неоднократно в цикле по ним ходить может оказаться просто необходимо для логики вашего приложения. Как, например, в игровом движке – там просто нельзя надолго выбросить часть игровых объектов из обработки, не создав этим заметных багов.

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

Обманчивый Iterable

Языки высокого уровня – это прекрасно. Они берут на себя кучу мелкого головняка, позволяя сконцентрироваться на главном. Но если вам приходится заниматься глубокой оптимизацией, то от части этих удобств придётся отказаться.

Вот взять, например, Iterable. Он одинаковый и для List, и для Map, и для Set – но только на уровне интерфейса. А реализации совсем не идентичны. Поэтому если у вас есть набор данных внутри HashSet или HashMap, и вам приходится много раз циклом по ним проходиться – стоит сделать один лишний проход, чтобы сохранить эти данные в обычный List. Итерация по простому списку будет самой дешевой. И да, лучше бы этот список сделать немодифицируемым (List.filled(emptyObject,growable:false)), а элементы в него добавлять через перезапись индексов в цикле for – в том случае, если код для заполнения списка у вас тоже находится в критичной для производительности зоне.  

Вот вам наглядный пример из недр исходников Dart. Сравните работу итератора обычного списка и HashSet:

Лично удостовериться можно тут и тут.

В обычном списке итерация идёт по одному списку, что ожидаемо, а внутри HashSet находится множество списков, по которым итератор скачет согласно какой-то логике. Сейчас не так важно, какой именно, важно, что этой логики больше, чем просто увеличение индекса.

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

Как использовать List вместо Map

Внимание! Рецепт уровня «Капитан Очевидность»!

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

1. Вы знаете, сколько элементов будет в коллекции ещё до начала её заполнения и использования.

2. Сами эти классы есть возможность хранить в обычном индексированном списке, немодифицируемом по крайней мере на период работы с Map.

3. Операций вытаскивания значения из Map достаточно много: вызов жирной полоской светится в Flame Chart. В противном случае оптимизация не имеет смысла, т.к. дополнительный обход элементов в списке сделает алгоритм только медленнее.

Если всё сходится, тогда можно оптимизироваться:

1. Объекты, которые раньше были ключом для Map, соберите в немодифицируемый массив List<T>

2. Создайте немодицифируемый массив List<T> , в котором вы будете хранить ваше значение для Map. Количество элементов равно количеству объектов из предыдущего шага

3. Ну а дальше всё совсем просто: позиция в массиве «ключей» соответствует позиции в массиве «значений», и пока оба эти массива остаются неизменяемыми, вы можете получать данные просто по индексу вместо дорогого доступа по ключу.

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

Предсказуемые итоги бенчмарка:

Кажется, ради 15-кратного прироста стоит и заморочиться и откатиться со сложной структуры данных на простую, с сексуальных итераторов на дедовский «for(i=0….»

Ускоряем Set и Map, не отказываясь от них

Но что если условия задачи откатиться обратно на списки не дают? Даже в этом случае у нас всё ещё есть возможность увеличить производительность.

Всё дело в хэш-функциях. Set и Map для хранения любого типа данных используют hashCode, поле, которое есть у любого объекта Dart. Но тут как с итераторами, интерфейс общий, а реализация под капотом разная. Если снова заняться гуглением, можно обнаружить в анналах истории баг репорты разработчикам языка, что реализации хэшей для похожих типов данных работают с ощутимо разной скоростью.  Вот, например, коммит, который улучшает скорость работы hashCode для целых чисел: https://github.com/dart-lang/sdk/commit/8c0df46887744e229b74bfb8c6bfc05df67f67eb . А вот до сих пор открытое обсуждение того, что Object.hashCode мог бы работать и быстрее (но это не точно): https://github.com/dart-lang/sdk/issues/24206

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

int mapAccessHashSetByIndex(int objectsCount) {
  final objects = MyObject.createObjects(objectsCount, true);

  final keyValueMap = <int, bool>{}; // <--- Key is integer, not object!!!
  for (var i = 0; i < objects.length; i++) {
    final object = objects[i];
    if (int.parse(object.data) < 1000) {
      keyValueMap[i] = true;
    }
  }

  ///
  /// Performance-critical part: working with data, checking a result that was
  /// previously calculated
  ///
  final sw = Stopwatch();
  sw.start();
  for (var i = 0; i < objects.length; i++) {
    for (var j = 0; j < objects.length; j++) {
      if (i == j) continue;
      if (keyValueMap[i] == keyValueMap[j]) { // <-- access by int index, not object itself!
        // any useful logic here
      }
    }
  }
  sw.stop();
  return sw.elapsedMicroseconds;
}

Что ж, ну не в 15 раз, так хотя бы в 2 раза быстрее мы ещё можем наш код сделать. Всё ещё неплохой результат, всё ещё стоит того, чтобы немного заморочиться!

Когда нельзя, но очень хочется ЕЩЁ быстрее!..

Как говорится, если нельзя, но очень хочется – то можно!

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

Ну прям самый простой кейс:

1. У вас есть пары объектов

2. Вам нужно сохранить где-то данные для каждого соотношения пар

Думая о задаче так, чтобы особо думать не приходилось, быстро и просто создаём структуру данных Map<Object,Map<Object,ObjectData>> и получаем медленного тяжелого монстра. Хотя задачу он решит.

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

Ну а если на списки переписать нельзя, тогда сохраняем данные в Map<int,Data>, а целочисленный ключ, идентифицирующий пару объектов, получаем с помощью побитового И, например: final key = a.hashCode & b.hashCode

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

Лично я для себя в нем открыл такую штуку, как BloomFilter и XorFilter, а также репозиторий https://github.com/FastFilter/ с реализацией под кучу языков... кроме Dart. Мне очень хотелось бы встроить Xor Filter, т.к. в моей задаче список фильтруемых объектов формировался на этапе загрузки игры, и долгие вычисления здесь были допустимы, а по скорости проверки данных Xor должен обгонять Bloom. Но увы, из готового для Dart нашелся только Bloom Filter, зато аж две реализации. Для экспериментов я выбрал эту: https://pub.dev/packages/dart_bloom_filter

Дальше, как всегда, бенчмарки. Но сперва стоит сделать несколько оговорок:

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

2. По этой же причине на небольших объёмах данных / количествах запусков / отладочных режимах разница может быть на уровне вычислительной погрешности.

Собственно, запуская бенчмарк на 10000 элементах в режиме VM я получал идентичную производительность что для HashSet, что для BloomFilter. А вот скомпилировав приложение под Windows и увеличив число элементов и итераций до 10000000 сразу стала видна разница.

int hashSetCheck(int elementsCount) {
  ///
  /// Preparing data. No need to benchmark here
  ///
  final objects = MyObject.createObjects(elementsCount, false);

  final random = Random();
  final objectsSet = <int>{};

  for (var i = 0; i < objects.length; i++) {
    if (random.nextBool()) {
      objectsSet.add(i);
    }
  }

  ///
  /// Performance-critical part: working with data, checking a result that was
  /// previously calculated
  ///
  final sw = Stopwatch();
  sw.start();
  for (var i = 0; i < objects.length; i++) {
    if (objectsSet.contains(i)) {
      // do something
    }
  }

  sw.stop();
  return sw.elapsedMicroseconds;
}

int bloomCheck(int elementsCount) {
  ///
  /// Preparing data. No need to benchmark here
  ///
  final objects = MyObject.createObjects(elementsCount, false);

  final random = Random();

  final bloomTrue = BloomFilter<int>(objects.length, 0.1);

  for (var i = 0; i < objects.length; i++) {
    if (random.nextBool()) {
      bloomTrue.add(item: i);
    }
  }

  ///
  /// Performance-critical part: working with data, checking a result that was
  /// previously calculated
  ///
  final sw = Stopwatch();
  sw.start();
  for (var i = 0; i < objects.length; i++) {
    if (bloomTrue.contains(item: i)) {
      // do something
    }
  }
  sw.stop();
  return sw.elapsedMicroseconds;
}

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

Я переписал свой код по рекомендациям из статьи, но быстрее не стало!

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

В моём случае итераций переписывания и последующего перепрофилирования было не менее восьми, хотя специально я их и не считал. Каждое внесённое изменение само по себе не увеличивало воспринимаемую пользователем скорость работы приложения, но убирало из Flame Chart блок с долгим кодом, либо существенно его сокращало.

В итоге эффект стал ощутим только когда все оптимизации стали работать вместе. А именно эффект выражался в том, что вместо 28 FPS моя демка игрового движка стала выдавать стабильные 60, обрабатывая столкновения одновременно для 161 движущегося объекта. Ну или покажу так:

Да, BloomFilter хоть весьма мал, но всё ещё отсвечивает. Хотя HashSet.[] отсвечивал ещё сильнее. В остальном никаких «особо затяжных» циклов больше не наблюдается, как было на скринах в начале статьи, что, в целом, можно считать успехом.

Почему не изоляты?

У некоторых может возникнуть вопрос, а зачем так заморачиваться производительностью в одном потоке, если теоретически можно распихать вычисления по разным изолятом? Но увы, тут у Dart большие проблемы:

1. Копировать большое количество данных между изолятами на каждый кадр – это 100% слишком накладно, а разделяемой памяти нам не завезли (разве что через костыли с ffi и проброс указателя в виде integer значения, но там мы уже уходим в разработку на C++, что не комильфо)

2. Данные можно преобразовать в бинарный вид, например с помощью вот этой прекрасной библиотеки https://github.com/google/flatbuffers , что я и сделал в той области движка, где это было легче всего. Но при большом количестве объектов гонять сериализацию в бинарный вид всё равно накладно. Отсутствие поддержки запуска некоторых нужных библиотек внутри изолятов, наличие колбэков в переменных класса, необходимость отдельно всё переписывать для того, чтобы можно было запустить изолят в вебе – всё это добавляет поставленной задаче особой остроты и хитровыпендренности. Хотя и это я реализовал в той части фреймворка, где не потребовалось бы глубинного рефакторинга. Но так себе квест.

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

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

5. По итогу больше ресурсов тратится даже не на сам ваш код, а на поддержание работы async-await, и у вас в флеймчарте будут быстро выполняющиеся функции на дарте и ооочень долго работающий код нативных библиотек платформы.

Итого, оптимизировать работу в одном потоке порою надёжнее и проще, чем раскинуть по нескольким. Вот такой вот он, наш хвалёный Dart, что уж тут поделаешь. Зато json-ы вон как парсит ????

Использованная «литература»

Код бенчмарков есть не только в спойлерах, всё можно найти в репозитории и потыкать самому: https://github.com/ASGAlex/dart_iterables_benchmarks

Важная ремарка! Каждый тест лучше запускать отдельно, т.к. если просто запустить последовательно функции в рамках одного приложения, то неизвестно в какой момент придёт Garbage Collector и испортит вам все замеры, зачищая память после предыдущего теста.

Если кому-то интересно потыкать, что там у меня за игровой движок, пожалуйте в исходники https://github.com/ASGAlex/flame_spatial_grid и в демку в вебе: https://asgalex.github.io/flame_spatial_grid/

В статье я упоминал про использование flat buffers для ускорения коммуникации с изолятом и запуск изолятов в вебе через web-workers. Вообще это отдельная тема, так что тут глубоко в неё не погружаюсь, но если кому-то интересно посмотреть примеры использования – прошу:

1. Схемы для flat buffers и сгенерированный код с некоторыми ручными добавками

2. Конвертация данных в бинарный буфер, отправка в изолят (в 4 параллельных потока), получение результатов в бинарном формате с декодированием «под капотом» в читабельный

3. Сам изолят, адаптированный для работы в вебе в том числе

Надеюсь, когда-нибудь я и о многопоточности в Dart смогу рассказать историю успеха или хотя бы частичной победы ????