Возникла необходимость зафиксировать опыт с последнего проекта по прокачке производительности картографического сервиса. Так сказать, чтобы 2 раза не вставать при передаче опыта. И начнём с постановки, чтобы сразу определиться с аудиторией, кому мимо, а кому больше узнать как "прожевывать" и отображать на UI от 100К объектов в секунду и не лагать. Ну а кто-то вообще не в танке про картографические сервисы и хочет "на борт". Но для второй категории оговорюсь, что в статье минимальная теоретическая часть для затравки, но достаточно ссылок чтобы прокачаться до нужного уровня.

Что вас ждёт по катом.

1. MapTiler/Maplibre - картографический провайдер и UI фрэймворк для работы с ним.

2. Создание своих слоёв данных на карте.

3. Рендеринг большого объёма данных на WebGL/WebGPU. Начнём от 100К.

4. Оптимизация рендеринга с ручной подготовкой буферов для GPU.

5. Обновление данных слоя в realtime. Начнём молотить от 1M объектов.

6. Сериализация данных в ArrayBuffer для передачи напрямую в GPU.

Итак, имеется карта. В статье будет использоваться картографическая библиотека на основе форка Mapbox, - Maplibre. Имеется сервис, который генерирует большое количество объектов для их отображения на карте. Положение объектов часто меняется. В качестве примера для генераторов данных можно представить такси, самокаты, просто автомобили с трекерами. Задача, - отображать реальное или близкое к реальному положение объектов на карте. И поскольку данные у нас не статичные и их объём может быть довольно большим даже в области видимости, всё это нужно ещё умножить на FPS, с которым мы хотим видеть текущее состояние объектов мониторинга.

Ну очень коротко про устройство карт.

Многие картографические библиотеки имеют слоистую структуру. Такой бутерброд, на каждом слое которого данные определённого типа. Например: Ландшафт, горы, водоёмы. На другом слое дороги, тропинки. В следующем, городская инфраструктура, и так далее. Чтобы показать картинку ниже, используется 100+ разных слоёв.

Плавать научились, нальём таки в бассейн воды.

Начнём с заготовки проекта и установки основных библиотек.

Стартовый код.

npx create-react-app maplibre-demo --template typescriptipt

По доброй традиции, удаляем весь код в /src, который нагенерил CRA, оставляя только стартовый компонент App.tsx и index.tsx в девственно чистом виде...

import React from "react";
import ReactDOM from "react-dom/client";
import App from "./App";

const root = ReactDOM.createRoot(
  document.getElementById("root") as HTMLElement
);

root.render(
  <React.StrictMode>
    <App />
  </React.StrictMode>
);

import React from "react";

function App() {
  return <div></div>;
}

export default App;

Проверяем через npm start, что рендерится чистая страница, а в консоли нет ничего лишнего, что помешало бы потом с отладкой.

Далее сама JS библиотека maplibre и React-обёртка. У malibre очень хорошая документация и примеры кода на чистейшем Javascript. Мы же сразу воспользуемся React-обёрткой.

npm install react-map-gl maplibre-gl

Картой уже можно пользоваться, но нет данных. Их можно получить у провайдера Maptiler. Регистрируемся здесь и получаем api key (ну совершенно бесплатно, пока).

Добавим отдельный компонент для инициализации canvas карты. Не забудьте определить константу YOU_API_KEY

import Map from "react-map-gl/maplibre";

const MaplibreMap = () => {
  return (
    <Map
      initialViewState={{
        longitude: 37.6209903877284,
        latitude: 55.747710687697804,
        zoom: 15,
        pitch: 60,
      }}
      style={{ height: "calc(100vh - 70px)" }}
      mapStyle={`https://api.maptiler.com/maps/streets-v2/style.json?key=${YOU_API_KEY}`}
    ></Map>
  );
};

export default MaplibreMap;

function App() {
  return <MaplibreMap />;
}

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

Слои для рендеринга данных.

Каждый слой, как писалось выше, отвечает за свой тип данных. Данные могут быть в различном виде: иконки, растры, геометрические фигуры и даже 3D объекты. И всё это можно рендерить на карте. Таким образом, именно слой реализует базовый функционал визуального представления данных, он же отвечает и за их загрузку и предварительную подготовку (парсинг). Мы будем использовать библиотеку deck.gl в которой уже решены все задачи с которыми столкнётся разработчик картографического сервиса. Для интереса, можете взглянуть какого типа данные умеет рендерить сегодня deck.gl. Это 30+ различных форматов. Хочу заметить, что в deck решены вопросы парсинга данных в WebWorker, разбиения данных на чанки, рендеринг через WebGL/WebGPU, оптимизация форматов данных и много чего ещё для оптимизации больших датасетов. Официальная документация манипулирует цифрами от 1М объектов.

npm install deck.gl

И протестируем слой для рендеринга "простых" точек. Для этого напишем сервис для генерации случайных данных в некоторых пределах.

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

for (let i = 0; i < count; i++) {
    const lng = random() * width * 3 + (boundingBox.nw[0] - width);
    const lat = random() * height * 3 + (boundingBox.sw[1] - height);
    const alt = random() * 1000;

    const point: Point = {
      coordinates: [lng, lat, alt],
      color: [
        round(random() * 255),
        round(random() * 255),
        round(random() * 255),
      ],
    };

    result.push(point);
  }

const POINT_COUNT = 100_000;
const data = generateData(POINT_COUNT);

const MaplibreMap = () => {
  const [loaded, setLoaded] = useState(false);
  const [layers, setLayers] = useState<Layer[]>([]);
  
  useEffect(() => {
    if (loaded) {
      setLayers([createPointLayer(data)]);
    }
  }, [loaded]);
  
  <Map
    // ...
    onLoad={() => setLoaded(true)}
  >
    <DeckGLOverlay layers={layers} />
  </Map>
}

export function createPointLayer(data: Point[]): PointLayer {
  return new PointLayer({
    id: "point-layer",
    data,
    getPosition: (d) => d.coordinates,
    getColor: (d) => d.color,
    getRadius: 5,
  });
}

Уже можно насладится как мы рендерим разное количество объектов на экране с помощью WebGPU или WebGL, если первый не поддерживается. Я сразу начал со 100К.

Двигаем.

Наступает самое интересное. Как обновлять данные? В нашем случае заставить объекты перемещаться по экрану.

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

Для начала напишем сервис для обновления координат объектов. В статье приводить его реализацию нет смысла. Так же как и примитивный сервис статистики, который снимает время работы двух ключевых методов слоя: draw и update.

Съём статистики в PointLayer

export class PointLayer extends ScatterplotLayer {
  public override draw(options: any): void {
    const startTime = performance.now();

    super.draw(options);

    addDrawTime(performance.now() - startTime);
  }

  public override _update(): void {
    const startTime = performance.now();

    super._update();

    addUpdateTime(performance.now() - startTime);
  }
}

MaplibreMap.tsx

useEffect(() => {
    if (loaded) {
      setLayers([createPointLayer(data)]);
      setInterval(() => {
        setLayers([createPointLayer((data = updatePoints(data)))]);
      }, 1000 / FPS);
    }
  }, [loaded]);

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

FPS: 10
COUNT_OBJECTS: 100_000
----
draw time: 0.1ms
update time: 15ms

И первые выводы, которые можно сделать. Основное время тратится на операцию update. Пришло время для следующей порции теории. Свойство data у слоя принимает массив данных определённой модели. DeckGL итерируется по этому массиву и на каждый элемент вызывает функцию, которая должна вернуть значение для рендеринга. Например getPosition и getColor. И собирает из этих значений буфер (массив чиселок) для отправки этого массива в GPU.

// Модель данных
export interface Point {
  coordinates: [number, number, number];
  color: [number, number, number];
  azimuth: number;
  speed: number;
}

// Фабрика для создания слоя
export function createPointLayer(data: Point[]): PointLayer {
  return new PointLayer({
    id: "point-layer",
    data,
    getPosition: (d) => d.coordinates,
    getColor: (d) => d.color,
    getRadius: 5,
  });
}

Обновление 100К объектов за 15ms, результат конечно неплохой, но надо понимать, что даже при 10FPS на обновление мы уже тратим 150ms центрального процессора. А если речь идёт о 1М объектов? Тогда ныряем глубже.

Пишем GPU буфер сами.

В deckgl есть способ указания свойства data в том виде, в котором он уже пригоден для отправки в GPU. Т.е. фактически можно пропустить проход по массиву в функции update, и сложность update из O(n) становится O(1).

Вот так выглядит подобный буфер

const GPU_ITEM_SIZE = 16; // Размер модели данных в байтах

return {
  length: data.length / GPU_ITEM_SIZE,
  attributes: {
    getPosition: { value: buffer, type: 'float32', size: 3, offset: 0, stride: GPU_ITEM_SIZE },
    getFillColor: { value: buffer, type: 'uint8', size: 4, offset: 12, stride: GPU_ITEM_SIZE },
  },
};

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

value: Float32Array с чередующимися друг за другом атрибутами объекта
type: тип данных, как GPU должен воспринимать поток байтов
size: количество отднотипных значений, т.е. размер массива
stride: количество байтов на все значения одного элемента модели
offset: смещение в байтах с которого нужно читать значение атрибута

Таким образом, имея такое описание, render запустит цикл по буферу и на каждой итерации будет считать смещение как i * stride + offset.

// Итерация по обычному массиву с данными
getPosition: (d) => d.coordinates,
getColor: (d) => d.color

// Описание итератора по TypedArray
getPosition: { value: buffer, type: 'float32', size: 3, offset: 0, stride: GPU_ITEM_SIZE },
getFillColor: { value: buffer, type: 'uint8', size: 4, offset: 12, stride: GPU_ITEM_SIZE }

Для получения координаты объекта он прочитает данные по полученному смещению используя соответствующий тип и столько раз, сколько указано в size. Довольно просто понять, как [lon, lat, alt] получается из первой строки, а [R, G, B, A] из второй, которые записаны в буфере друг за другом.

Вот так, 16 байт
|LNG |LAT |ALT |R|G|B|A|

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

function makeGPUBuffer(data: Point[]): PointDataBuffer {
  const buffer = new Float32Array(data.length * 4);
  const dataView = new DataView(buffer.buffer);

  let offset = 0;
  for (let i = 0; i < data.length; i++) {
    offset = i << 4; // i * 16
    dataView.setFloat32(offset + 0, data[i].coordinates[0], true);
    dataView.setFloat32(offset + 4, data[i].coordinates[1], true);
    dataView.setFloat32(offset + 8, data[i].coordinates[2], true);

    dataView.setUint8(offset + 12, data[i].color[0]);
    dataView.setUint8(offset + 13, data[i].color[1]);
    dataView.setUint8(offset + 14, data[i].color[2]);
    dataView.setUint8(offset + 15, 255);
  }

  return {
    length: data.length / 4,
    attributes: {
      getPosition: { value: buffer, type: 'float32', size: 3, offset: 0, stride: GPU_ITEM_SIZE },
      getFillColor: { value: buffer, type: 'uint8', size: 4, offset: 12, stride: GPU_ITEM_SIZE },
    },
  };
}

Обращу отдельное внимание на функцию DataView.setFloat (и все остальные, которые пишут значения размеров больше 1-го байта). Значения в GPU должны быть выравнены в LE, поэтому последним параметров это указывается. Теория о том, как наши девайсы, и не только, хранят многобайтовые величины.

Ну и результат.

FPS: 10
COUNT_OBJECTS: 100_000
----
draw time: 0.1ms
update time: 0.4ms

И продолжается бой

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

1. GPU буферы готовятся на бэкенде и передаются на UI в пригодном для рендеринга виде.

2. Буферы на UI не пересоздаются, как в примере, а делается точечное обновление объектов. Ведь не все они меняют координаты. А создание нового ArrayBuffer большого объёма, дело затратное, поскольку после выделения памяти он ещё и затирается нулями.

3. Объекты добавляются и удаляются со сцены, поэтому написан наследник Float32Array, который размечается с б`ольшим размером, чем необходимо и новые объекты добавляются в конец, а удаляемые просто затираются значением Infinity. Только по необходимости, при переполнении буфера, он перестраивается.

4. Сделана разбивка всей сцены на тайлы с помощью TileLayer, для того, чтобы не процессить объекты, которые не видны на сцене. Это, кстати, стандартный подход для картографических сервисов.

5. Весь процессинг, а он всё равно появляется, происходит в WebWorker`ах.

6. Данные ходят не по HTTP, а через WebSocket в двоичном виде, без всяких JSON.

Ссылки

1. Maptiler

2. Maplibre

3. DeckGL

4. Репозиторий из данной статьи.

5. Проекты-компаньоны deck.gl