Оптимизируем отображение 10 000 объектов на карте09.09.2021 13:16

Проблема в том, что объявлений очень много: в одной только Москве более 10 000. Из-за этого наша карта работала не очень стабильно: при зуме и движении были тормоза, дёргалась и лагала картинка. С этим нужно было что-то делать. Чтобы разобраться в причинах проблем и найти решения, мы засучили рукава и начали копаться в используемых механизмах. Под катом подробно опишем весь путь оптимизации карт в Android-приложении: от постановки задачи до результата.

1. Постановка задачи

Введение

Для начала давайте разберёмся, для чего был выбран именно такой метод отображения объявлений. Ведь можно применить кластеризацию и просто повесить над Москвой один огромный пин с циферкой 10 000 посередине. Так почему же мы в итоге остановились на варианте «одно объявление — одна точка»?

• Это красиво.

• Легко читается плотность объявлений в конкретном районе.

• Все объявления на своих местах, и при масштабировании каждая точка остаётся на своём месте.

Внутри команды такой способ отображения мы назвали «Горошек на карте».

Выглядит просто прекрасно; ещё бы не лагало — было бы просто супер.

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

Как было реализовано

Для отображения у нас используются Яндекс.Карты. Общая логика работы выглядела следующим образом:

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

2. Когда камера останавливается, мобильное приложение запрашивает у сервера объявления в области видимости; для этого мы передаём координаты левого верхнего и правого нижнего углов.

3. Сервер с помощью ElasticSearch находит объявление в данной области и возвращает их мобильному приложению.

4. Переводим координаты объявления в позицию на экране.

5. Если на карте уже отображается пин Яндекс.Карт, то удаляем его.

6. Создаём Bitmap-картинку и через Canvas рисуем на ней точки объявлений в тех позициях, где они сейчас должны находиться.

7. В самом центре экрана добавляем пин Яндекс.Карт и в качестве картинки вставляем наш Bitmap с нарисованными на нём объявлениями.

8. Возвращаемся к шагу 1 и повторяем алгоритм, пока пользователь не уйдёт с карты.

Правда, тут есть нюанс: у Яндекс.Карт есть ограничение на размер вставляемой в пин картинки: 2048×2048. И если попытаться такую растровую картинку приблизить, то получится некрасиво:

Некоторые круги вообще стали почти квадратными!

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

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

Как это работало, мы разобрались. Теперь давайте посмотрим, что с этим подходом было не так.

Основные проблемы

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

2. Точки «моргают» после появления на карте. Мы синхронно добавляем четыре пина, а вот под капотом Яндекс.Карт они добавляются уже асинхронно. Из-за это возникает эффект, когда сначала появляются объявления в правом нижнем углу, затем в левом верхнем и так далее. Всё это происходит достаточно быстро, и карта выглядит как новогодняя ёлка.

3. Карта тормозит и подлагивает при взаимодействии с ней.

Причины проблем

Вся работа с отрисовкой точек на карте у нас происходила в классе PeasFourBitmapOverlay. Метод отрисовки отрабатывал очень медленно: в среднем 800 миллисекунд на Xiaomi Mi A3.

Также у Яндекс.Карт очень много методов, которые должны выполняться на главном потоке. На это мы повлиять никак не можем. Поэтому погрузимся в код именно с нашей стороны.

Разберём подробнее логику работы PeasFourBitmapOverlay. По сути, в одном методе происходило следующее:

• Сначала на главном потоке:

  • рассчитываем размер Bitmap-картинки;

  • конвертируем широту и долготу объявлений в точки на экране.

• Переходим на фоновый поток:

• Возвращаемся на главный поток:

  • убираем предыдущие пины;

  • рассчитываем ScaleFunction — это помогает Яндекс.Картам понять, насколько нужно увеличить или уменьшить Bitmap при зуме;

  • добавляем новые пины Яндекс.Карт с Bitmap в качестве изображения пина;

  • выставляем ScaleFunction.

Всё это происходит хоть и в многопоточном режиме, но синхронно.

Из описанного видно, что:

• Следует разбить процесс на шаги.

• Слишком много работы происходит в главном потоке, и только три действия — в фоновом.

• Рисование занимает слишком много времени.

• Выставление ScaleFunction тоже долгое: может занимать до 200 миллисекунд.

2. Решение

Создать конвейер

Что за конвейер? По сути это набор шагов, которые должны выполниться друг за другом; каждый из этих шагов изменяет или дополняет какой-то объект, который как бы движется по конвейеру. Отсюда и название. При этом результат следующих шагов зависит от предыдущих, например:

1. Рассчитываем размер Bitmap-картинки.

2. Конвертируем широту и долготу объявлений в точки на экране.

3. Создаём Bitmap; для этого нужны размеры из шага 1.

4. Рисуем на этом Bitmap точки объявлений; для этого Bitmap должен быть создан в шаге 3.

5. Делим Bitmap на четыре куска; для этого точки должны быть нарисованы в шаге 4.

Теперь перейдём к нашей реализации. Объектом, который будет двигаться по конвейеру, является ConveyorData. Это immutable-объект, содержащий всю информацию, которая может понадобиться любому из шагов. Под шаг конвейера сделали интерфейс ConveyorStep на Rx.

internal interface ConveyorStep {
   fun step(conveyorData: ConveyorData): Single
}

Метод step, по сути, является основным: в нём делается вся работа, предписанная конкретному шагу. Для этого в него передаётся ConveyorData, полученный от предыдущего шага, а сам метод возвращает Single от ConveyorData, который изменяет изначальный ConveyorData в результате работы шага.

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

Получается следующая схема работы:

Это и будет основной нашей оптимизации.

Параллельный конвейер

Если очень пристально всматриваться в картинку выше, то можно заметить, что для создания шага «Создаём большой Bitmap» необходим только результат шага «Расчёт размера Bitmap», а вот результат «Конвертации геоточек в точки на экране» этому шагу не нужен. А значит, эти шаги можно выполнить параллельно друг другу: сразу после «Расчёта размера Bitmap» можно запустить «Создаём большой Bitmap», а «Конвертация геоточек в точки на экране» будет идти параллельно.

Вот и первые признаки оптимизации! За счёт того, что «Создаём большой Bitmap» делается в фоновом потоке, мы сможем выиграть немного времени. Правда, теперь придётся научить наш конвейер выполнять шаги параллельно.

Для работы с параллельным выполнением интерфейс ConveyorStep придётся немного усложнить. Добавляем метод isAvailable (); в нём шаг может проверить, достаточно ли у него данных для выполнения. Шаг вернёт true, если он готов выполнить свою работу.

За счёт этого частичное распараллеливание потоков происходит автоматически. В конвейер добавляется 10 параллельных шагов, и происходит проверка, может ли выполниться каждый из них. Если да — шаг выполняется; если нет — ждёт завершения предварительных шагов.

Только теперь появляется проблема: если несколько шагов у нас могут выполняться параллельно, а ConveyorData является immutable, то как потом объединить результат их усилий? Ведь каждый шаг работает со своим экземпляром ConveyorData. Конечно, можно сделать объект mutable и передавать одну и ту же ссылку во все шаги, но это очень опасно. Так как мы не знаем, что делает отдельный шаг в конкретный момент времени, может возникнуть ситуация, когда несколько шагов одновременно используют и изменяют один и тот же набор данных. Самым простым и быстрым, но далеко не самым лучшим способом является добавление метода merge () в наш интерфейс. В нём мы будем объединять ConveyorData в один объект, после того как доступные (isAvailable == true) шаги закончат свою работу.

В итоге наш ConveyorStep выглядит следующим образом:

internal interface ConveyorStep {
   fun isAvailable(conveyorData: ConveyorData): Boolean
   fun step(conveyorData: ConveyorData): Single
   fun merge(original: ConveyorData, updated: ConveyorData): ConveyorData
}

Как работает конвейер

Давайте разберёмся, как теперь работает конвейер. Логика работы следующая:

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

2. Если список не пустой, то у каждого шага в списке спрашиваем, доступен он или нет.

3. Недоступные шаги заменяют собой список ещё не выполненных шагов.

4. Доступные шаги начинают выполняться параллельно.

5. После выполнения всех доступных шагов объединяем их результат.

6. Возвращаемся в начало.

Шаги конвейера

Для нашей задачи в итоге получились следующие шаги:

• CreatePlaceMarksStep — создание объектов Яндекс.Карт.

• CalcBitmapSizeStep — расчёт размера Bitmap-картинки в зависимости от входных данных. Картинка должна быть качественной, но при этом её размер не должен превышать 4096×4096 и не должен быть кратно больше, чем разрешение экрана.

• CalcScreenPointsStep — конвертация расположения объявлений из географических координат в координаты положения точек на экране устройства.

• CreateBitmapsStep — создание итоговых Bitmap-картинок, которые будут передаваться на отрисовку карте.

• CalcScaleFunctionStep — расчёт функции масштабирования в зависимости от зума.

• CalcDrawDataStep — нахождение центра экрана в географических координатах для пинов Яндекс.Карт, а также расчёт смещения картинки пина относительно его центра.

• SetWorldPointStep — изменение местоположения пина на карте.

• DrawStep — замена картинки у пина.

• SetScaleFunctionStep — установка функции масштабирования в зависимости от зума.

• ShowPlaceMarksStep — отображение новых пинов.

• HidePlaceMarksStep — скрытие предыдущих отображённых пинов.

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

Конвейер из конвейеров

Важной особенностью конвейерного подхода является то, что его легко масштабировать. Можно сделать разные конвейеры для разных ситуаций (например, если пользователь подвигал карту или приблизил/отдалил). Что это даст? При зуме можно использовать красивую анимацию, которая не нужна при движении. Для этого после создания объектов карты проверяем, изменился ли зум, и в зависимости от этого фактора запускаем разный набор шагов.

Оптимизировали MainThread

Как можно заметить, в главном потоке всё ещё выполняется большое количество действий. Это вынужденная мера, так как все эти шаги взаимодействуют с Яндекс.Картами, а они, в свою очередь, требуют обращения именно в главном потоке. Так что же, получается, лаги останутся и ничего не исправить? На самом деле после разбиения на шаги проблем уже стало ощутимо меньше. Чтобы понять, почему так происходит, давайте посмотрим, как происходила отрисовка раньше.

Представим, что у нас экран с частотой обновления 60 Гц, —, а это значит, что каждые 16 миллисекунд RenderThread отрисовывает результаты работы нашего потока. Ранее все действия выполнялись в одном методе —, а значит в одном сообщении Looper главного потока — следовательно, следующий кадр не рисовался, пока работа этого метода не завершится. Выглядело это примерно так (красным отмечены кадры, которые должны были отрисоваться, но не смогли из-за долгого выполнения метода):

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

Серьёзная проблема остаётся только с SetScaleFunctionStep, но с ней придется разбираться отдельно. Далее все остальные оптимизации касаются отдельных шагов.

Закешировали объекты Яндекс.Карт

В первом шаге CreatePlaceMarksStep вместо пересоздания пинов Яндекс.Карт мы теперь сохраняем их в двух кешах — текущие пины и предыдущие — которые меняем местами с каждым приходом новых данных. Два кеша вместо одного нужны, чтобы мы могли одновременно показывать анимации появления и исчезновения пинов; с одним набором кеша такое не провернуть. Таким образом экономим время в обмен на оперативную память.

Натянули цилиндр на сферу/эллипсоид

Шаг CalcScreenPointsStep, который переводит координаты объявлений из координат (lat, lon) в координаты пикселя на экране, тоже занимает много времени и не всегда успевает выполниться за 16 миллисекунд. Ведь даже очень простое действие может затянуться, если повторять его для более чем тысячи объявлений.

Кажется, что тут должна быть простая математическая операция перевода координат, так в чём же проблема? В том, что Земля сферическая (точнее, эллипсоидная), а карты квадратные, по сути являющиеся цилиндром. Для того чтобы превратить сферу в цилиндр, используется проекция Меркатора.

Превращение из сферы в цилиндр идёт по формуле:

Так делают Google Maps.

А вот превращение из эллипсоида в цилиндр уже происходит по сложной формуле:

И в Яндекс.Картах как раз используют эллипсоид, что, как видно, делает нашу задачу заметно сложнее.

В процессе поиска решения мы рассматривали три варианта этого шага:

• CalcScreenPointsAccuracyStep — считает максимально точно, но долго.

• CalcScreenPointsMediumStep — считает неточно, но быстрее.

• CalcScreenPointsFastStep — самый быстрый способ, но с погрешностью в 2–3 пикселя.

CalcScreenPointsAccuracyStep

В API Яндекс.Карт есть метод worldToScreen — в него можно передать координаты объявления и получить координаты на экране в пикселях. Но он может быть вызван только в главном потоке; в итоге для большого количества точек требуется много времени главного потока, что вызывает лаги.

CalcScreenPointsMediumStep

Помимо worldToScreen, в API Яндекс.Карт есть класс Projection — он делает за нас часть работы, переводя широту и долготу в x и y на карте, и, что самое прекрасное, не требует главного потока. Нам же остаётся определить координаты видимой на экране части карты. Дальше рассчитать положение точки на экране — это дело техники.

Звучит очень красиво, но есть один нюанс. В классе Projection точки передаются по одной, и для каждой требуется отдельный вызов C++-метода.

Прямой вызов невиртуального метода занимает 25 наносекунд. Если метод виртуальный — то уже 50 наносекунд. Кроме того, метод вызывается из Java в С++ — в итоге вызов занимает 225 наносекунд, то есть в 4,5 раза больше.

При этом отдельный вызов приходится делать для каждого из объявлений на карте, а их в нашем случае может быть до 10 000. Простые расчёты показывают, что только лишь на вызовы методов, не считая времени их выполнения, мы можем потратить 2,25 миллисекунды, что составляет ⅛ всего времени, что у нас есть. В итоге этот шаг хоть и быстрее предыдущего, но всё же ещё далёк от оптимального варианта.

CalcScreenPointsFastStep

Пробуем вычислять сами в Java-коде, быстро и с погрешностью. Для этого нам нужны три точки: верхний левый угол, нижний правый угол и вычисляемая точка. Определяем, на какой относительной высоте и ширине находится точка (например, в 60% от ширины и 20% от высоты), и ставим её в соответствующее место. Таким образом мы просто игнорируем проекцию Меркатора и считаем без неё — в итоге появляется погрешность. И чем сильнее отдаление, тем она больше, так что этот метод подходит только при достаточно большом приближении карты.

Итоговый CalcScreenPointsStep

Из трёх описанных вариантов шагов конвертации мы выбрали CalcScreenPointsMediumStep с использованием кеша. Если x- и y-точки на карте уже вычислялись ранее, то берём результаты вычислений из кеша и экономим время на отказе от вызова C++-метода.

Сгладили пин

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

При десятикратном увеличении:

То же самое, но в нормальном размере:

Это позволяет немного уменьшить разрешение Bitmap, сохраняя качество и вместе с тем повысив производительность шагов, связанных с рисованием на Bitmap и работой с пином Яндекс.Карт.

Это позволяет немного уменьшить разрешение Bitmap, сохраняя качество и вместе с тем повысив производительность шагов, связанных с рисованием на Bitmap и работой с пином Яндекс.Карт.

Раз уж мы заговорили о рисовании, то хочется обсудить ещё один момент. Раньше у нас каждая точка на Bitmap рисовалась с помощью отдельного вызова drawCircle у Canvas. Такой метод не вполне оптимален, так как каждый раз идёт процесс растеризации — превращение круга в набор пикселей. Это довольно затратная операция, даже учитывая малое разрешение отдельной точки.

Более производительным решением является использование спрайтов. Мы просто создаём отдельный Bitmap, на котором рисуем точку; такой Bitmap и будет являться нашим спрайтом.

Затем вызываем метод drawBitmap у Canvas и передаём в него координаты и наш спрайт. Bitmap является простой матрицей. Ускорение достигается за счет того, что при отрисовке на нём другого Bitmap произойдёт перемножение матриц, а это достаточно дешёвая математическая операция.

Оптимизировали масштабирование

Шаг SetScaleFunctionStep нужен для корректного масштабирования Bitmap при зуме. По умолчанию изображение в пине Яндекс.Карт при зуме вообще не изменяется; в нашем же случае при приближении карты Bitmap тоже должен увеличиться, чтобы объявления остались на своих местах. Для этого мы можем указать, какого размера должен быть Bitmap на конкретном уровне приближения. Сам расчёт — дело несложное. Проблема в том, что выставление этой функции для пина Яндекс.Карт занимает много времени, и при этом оно должно быть выполнено на главном потоке. Избежать этого или оптимизировать процесс никак нельзя. Но если призадуматься, то можно понять, что эта задача не является срочной, —, а значит, можно использовать IdleHandler, чтобы избежать части видимых лагов.

Когда в главном потоке ничего не происходит из-за отсутствия задач, начинается idle-время, и можно подсунуть нашу задачу с помощью IdleHandler. То есть SetScaleFunctionStep выполнится в тот момент, когда на главном потоке ничего не будет происходить, а значит, прочие действия не будут задерживаться из-за долгого исполнения этого шага, и визуальных задержек не случится.

Оптимизировали стили

В Яндекс.Картах есть возможность убирать с карты часть элементов, например светофоры и прочие объекты, которые могут быть не очень важны при выборе квартиры.

Если это сделать, то сама карта начнёт работать немного быстрее.

3. Заключение

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

А теперь давайте оценим результат всех наших доработок.

Для сравнения посмотрим, как было:

И как стало теперь:

Что ещё можно оптимизировать?

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

Запрашивать точки большей области.

Попытаться предсказать действия пользователя.

Кешировать точки, полученные с бэкенда.

Готовые расчёты с сервера.

Улучшить ParallelStep.

© Habrahabr.ru