Путь к миллиону точек: как я переписывал плоттер три раза, прежде чем он перестал лагать

Путь к миллиону точек: как я переписывал плоттер три раза, прежде чем он перестал лагать

Или: как embedded-разработчик случайно написал визуализатор временных рядов

Это моя первая статья и сразу на тему в которой я разбираюсь примерно никак. Ее можно воспринимать как условный "дневник разработчика".

Статья написана не без помощи LLM, от нее по большей части редактура. Прошу камнями не кидаться

Приятного чтения!

С чего всё началось

В миру я позиционирую себя как Embedded-разработчик, а как принято во многих местах в России разработчик встраиваемых систем - это инженер-разнорабочий. Написать firmware, развести не сложную PCB, поколдовать над ядром Linux,  провести исследования датчиков с китайского завода, напаять концевиков, собрать тестовый стенд, а если еще и осталось время - по возможности спроектировать корпус для устройства и произвести его прототип.

И в этот(и так немаленький список) периодически добавляется потребность в написании ПО под Пк, для работы с разрабатываемыми устройствами/датчиками и т.д. В основном, это несложные внутренние консольные утилиты, которые помогают общаться с устройством, логгировать данные, калибровать датчики и все в таком духе.

Но иногда появляется потребность в визуализации. Пока речь идет о низкочастотных датчиках и малом количестве данных - все довольно просто, но как только данных становится больше, а частоты выше - всплывает множество нюансов. При 70 кГц через 10 секунд работы датчика у меня уже 700 000 точек. Через минуту – 4.2 миллиона. А пользователь при этом хочет масштабировать/панорамировать оси, выделять области, нажимать кнопки – и всё это должно отзываться мгновенно. Стандартный подход «передать всё в библиотеку» ломается очень быстро.

О моем пути в процессе разработки ПО для визуализации realtime измерений и о том с чем я столкнулся в процессе(как инженер с опытом в визуализации +- равным нулю) и пойдет речь в данной статье. Ниже – история трёх попыток решить эту задачу, с честным описанием того, что шло не так на каждом шаге.

Стек и окружение

Немного вводных для лучшего понимания контекста: GUI написан на C++ с использованием Dear ImGui и ImPlot поверх OpenGL(ES). Важный момент - визуализация писалась с расчетом работы с комфортным откликом и FPS как на довольно мощных платформах,  так на старых ноутбуках и даже на ARM одноплатниках.

 Целевой датчик: датчик расстояния RIFTEK RF603HS, имеет частоту выдачи измерений порядка 70 кГц, данные передаются UDP пакетами по 168 измерений(что в дальнейшем будет использовано в архитектуре хранения данных)

Тесты проводил на следующих платформах:

1. Основной рабочий ноутбук(Ryzen 7 5xxx).

2. Одноплатник LattePanda(Intel N5105).

3. Arm одноплатник(A40i GPU: Mali-400).

Попытка первая: «нарисуем всё»

Первая реализация была канонически простой. Есть vector<double> xs, ys, в него пишем все точки по мере поступления, в каждом кадре передаём в ImPlot:

ImPlot::PlotLine("sensor value", xs.data(), ys.data(), (int)xs.size());

Работает отлично. До тех пор, пока данных мало.

ImPlot без видимых проблем справляется с десятками и сотнями тысяч точек – но при подходе к миллиону производительность начинает падать. При 70 кГц миллион точек – это меньше 15 секунд работы датчика. То есть окно комфортной работы катастрофически мало.

Проблема двойная. Во-первых, ImPlot вынужден каждый кадр обходить весь массив и генерировать вершины для GPU. Во-вторых, на экране шириной 1920 px при отображении 2.1 млн точек за 30 секунд на каждый пиксель приходится более 1000 точек – GPU рисует их все, хотя пользователь видит одну линию. Это форма геометрического overdraw: тысячи вершин накрываются в одном пикселе, а результат тот же, что от одной.

Вывод: подход годится для прототипов и небольших объёмов. При 70 кГц он перестаёт справляться уже через 10-15 секунд работы датчика.

Попытка вторая: прореживание (stride decimation)

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

int stride = visible_points / (int)ImPlot::GetPlotSize().x;
if (stride < 1) stride = 1;

for (int i = first_visible; i < last_visible; i += stride)

 {
    xs.push_back(data[i].time);
    ys.push_back(data[i].value);
}
ImPlot::PlotLine("sensor value", xs.data(), ys.data(), (int)xs.size());

FPS вернулся. Zoom и pan работают плавно. Казалось бы, задача решена – и именно здесь начинается самое интересное.

Проблема: пики исчезают

На тестовом сигнале с периодическими острыми выбросами я заметил, что при определённых масштабах они просто пропадают с графика. Датчик честно фиксировал выброс – два-три сэмпла длиной, но на экране его не было. График улыбался мне гладкой красивой линией и врал.

Выброс длительностью 3–4 точки при шаге прореживания stride=10 пропадёт в 70–80% случаев – просто потому что «нужные» точки не попали в выборку. При 70 кГц короткое событие длительностью 100 мкс – это всего 7 точек. При stride=20 шанс его заметить ничтожен.

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

Красота данных, обратно пропорциональная их честности.

Вывод: stride decimation неприемлем для измерительных сигналов с динамичными пиками. Нужен алгоритм, который гарантированно их сохраняет.

Попытка третья: min/max агрегация с фиксированным окном

Следующая идея: вместо выбора «каждой N-й точки» – выбирать минимум и максимум в каждом временном окне. Если в окне есть пик – он обязательно окажется либо как max, либо как min. Пики больше не теряются.

Этот подход известен как базовый MinMax, а его расширенная версия – алгоритм M4 – дополнительно сохраняет первую и последнюю точку каждого окна, что позволяет точнее восстановить характер нарастания/спада:

// Для каждого пиксельного бакета по X:
double ymin = +INF, ymax = -INF;
for (int i = bucket_start; i < bucket_end; i++)
{
    if (data[i].value < ymin) ymin = data[i].value;
    if (data[i].value > ymax) ymax = data[i].value;
}

Это работает надёжно. Выбросы видны. FPS хороший. Я снова был доволен собой, правда совсем недолго.

Новая проблема: zoom меняет всё

При каждом изменении масштаба нужно пересчитывать агрегаты для нового диапазона. Пока данных немного – незаметно. Но при нескольких миллионах точек (а их у нас 70 000 в секунду и буфер порядка 100млн) пересчёт агрегатов за весь видимый диапазон при каждом событии zoom/pan – это перебор всего массива данных прямо в UI-потоке. Интерфейс начинает «подвисать» именно в тот момент, когда пользователь активно с ним взаимодействует. Что несколько иронично.

Кроме того, возникает проблема долгой истории: если писать данные бесконечно, std::vector рано или поздно съест всю память. Нужно ограничивать объём хранимых данных – при этом сохраняя корректность агрегатов.

Вывод: простая MinMax с фиксированным окном – огромный шаг вперёд по сравнению со stride decimation, но при 70 кГц она упирается в производительность пересчёта слишком быстро.

Финальная архитектура: иерархическая агрегация

К финальному решению я пришёл через идею, хорошо известную в компьютерной графике: mip-map. Это был первый момент в проекте, когда мне пришлось всерьёз разбираться в том, как устроены текстуры в 3D-движках. Как embedded-разработчик я привык к тому, что «оптимизация» – это убрать сложную обработку из прерывании или или уменьшить количество обращений к медленной памяти. Оказывается, у графических программистов свои радости – и они тоже вполне логичны.

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

Структура хранения: кольцевой буфер чанков

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

Размер чанка – 168 точек – выбран не произвольно: именно столько значений датчик RF603HS передаёт в одном UDP пакете. Это естественная граница: пришёл пакет – сформировался чанк, сразу вычислили ymin, ymax, starttime, endtime. Никакой дополнительной буферизации, никакого переупаковывания данных – протокол датчика и архитектура хранения идеально совпали.

typedef struct {
    dataPlotLine_t points[CHUNKSIZE]; // 168 точек = 1 пакет от датчика
    double ymin, ymax;               // экстремумы чанка
    double starttime, endtime;       // временной диапазон (~2.4 мс при 70 кГц)
} Chunk;

При 70 кГц один чанк покрывает ~2.4 мс. Кольцевой буфер ёмкостью ~595k чанков даёт ~24 минуты истории – и автоматически вытесняет старые данные при заполнении. Старые данные уходят тихо и с достоинством.

Иерархия агрегатов

Поверх кольцевого буфера строится иерархия агрегатов – бинарное дерево по времени:

Level 0: [chunk_0] [chunk_1] [chunk_2] [chunk_3] ...
          ↑ 168 точек, ~2.4 мс каждый (при 70 кГц)
Level 1:     [agg_0-1]        [agg_2-3]         ...
              ↑ min/max двух чанков, ~4.8 мс
Level 2:         [agg_0-3]                       ...
                  ↑ ~9.6 мс
...

Каждый агрегат хранит ymin, ymax, starttime, endtime. При добавлении нового чанка агрегаты поднимаются вверх по уровням инкрементально – без пересчёта всей истории:

void feed_element(dataPlott *dp, int level, double ymin, double ymax, 
                  double tstart, double tend, uint64_t firstid)
 {
    PartialAgg *pa = &dp->partial_aggs[level];
    uint64_t needed = 1ull << level;
    if (pa->count >= needed)
    {
        AggregateChunk agg = { pa->ymin, pa->ymax, pa->starttime, tend, pa->firstchunkid };
        dp->agg_deques[level].push_back(agg);
        pa->count = 0;
        feed_element(dp, level + 1, agg.ymin, agg.ymax, agg.starttime, tend, agg.firstchunkid);
    }
}

Это классическая структура типа segment tree – только ориентированная на потоковое добавление данных в реальном времени. Когда я это понял, стало значительно спокойнее: за красивым словом «иерархическая агрегация» скрывается довольно привычная логика накопления и свёртки.

Выбор уровня при рендеринге

При отрисовке алгоритм смотрит на количество видимых чанков и ширину графика в пикселях – и выбирает уровень агрегации так, чтобы количество отрисовываемых элементов оставалось разумным:

int visible_chunks = last_ch - first_ch;
double plot_width_px = ImPlot::GetPlotSize().x;
int target_stride = (int)ceil((double)visible_chunks / plot_width_px);

int render_level = 0;
uint64_t stride = 2;
while (render_level < dp->num_agg_levels && stride < (uint64_t)target_stride)
{
    stride *= 2;
    render_level++;
}

При небольшом zoom (видны сырые данные) – рисуем сырые точки через ImPlotPlotLine. При zoom out – переключаемся на агрегаты нужного уровня и рисуем min/max полосы. Переключение мгновенное: данные уже готовы, пересчёт не нужен.

Auto-follow и синхронизация по времени

Для режима «следования за живыми данными» ось X обновляется каждый кадр. Здесь есть неочевидная деталь: нельзя просто прибавлять DeltaTime к правой границе – джиттер в частоте поступления данных накапливается, и окно начинает «плыть» относительно реальных данных. Медленно, но верно, как часы без кварцевого резонатора.

Решение: синхронизировать окно по wall-clock времени последней полученной точки (lastrawwall = glfwGetTime()), а не просто сдвигать его кадр за кадром:

double now = glfwGetTime();
double last_target_width = dp->lastlimits.XMax - dp->lastlimits.XMin;
newxmax = dp->lastlimits.XMax + ImGui::GetIO().DeltaTime * dp->calcdt;
// dp->calcdt = реальный период данных, вычисленный из разницы wall-clock
newxmin = newxmax - last_target_width;

Сравнение подходов: итоговая таблица

Что в итоге

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

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

Возможно весь этот процесс можно назвать изобретением велосипеда, но для меня(как для человека пишущем на преимущественно низком уровне и не разрабатывавшем сложных GUI-инструментов доселя) данная разработка оказалось весьма увлекательным занятием

Если кто то вдруг дочитал до конца – премного благодарен и буду рад фидбеку