Я бросил себе вызов: симулировать 1000000 (миллион) частиц на чистом Javascript на телефоне, используя только CPU и добившись 60 FPS.

Поехали.

Задача не особо сложна, если выполнять всю работу на GPU, но правило гласит, что нужно пользоваться только CPU, при этом работая на JS, так что никакого WASM.

Я знаю, о чём вы подумали: это не особо сложно, достаточно создать массив и засунуть в него миллион объектов.

Возможно, что-то типа такого?

const count = 1_000_000;
const particles = new Array(count).fill().map(() => ({
	//информация частиц
});

Затем можно просто обойти частицы в цикле:

function simulate(deltaTime) {
  particles.forEach((particle) => {
    //обновляем частицу
  });
}

А учитывая, что мы работаем в браузере, нужен запрос кадра анимации с canvas для рендеринга

requestAnimationFrame(simulateAndRender);

Этого могло бы быть достаточно, если бы у нас был один быстрый CPU, но мобильные устройства не могут похвастаться хорошей одноядерной производительностью. У них есть множество мелких энергоэффективных ядер. Поэтому чтобы решить задачу, мне нужно опуститься на более низкий уровень.

Вопрос на засыпку

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

Плотно упакованные сплошные массивы данных.

А что такое плотно упакованные сплошные массивы данных?

Не знаю, давайте спросим у Интернета,

То есть, по словам GPT, если хочешь, чтобы всё летало, нужно хранить максимальный объём данных в кэше CPU. Это будет справедливо всегда, на каком бы языке ты ни писал. Если ты просто обрабатываешь большие массивы данных и выполняешь с ними какие-то вычисления, что я и делаю, то самое важное — сделать так, чтобы CPU никогда не пришлось ожидать данные.

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

Вопрос на засыпку 2

Как гарантированно получить плотно упакованный сплошной массив данных в Javascript?

Если сделать что-то такое

const myArray = [...myData, myOtherData];

или такое

const myArray = [];
myArray.push({
  data: "hello there",
});

то вы совершите ошибку.

Хотя V8 и другие Javascript-движки умны и способны на потрясающие оптимизации, массивы в JS не всегда гарантированно оказываются реальными сплошными массивами данных, как в других языках, особенно если они заполнены объектами.

Кроме того, объекты в Javascript не так плотно упакованы, как это может быть при работе на низкоуровневом языке.

Если у меня есть в Javascript такой объект

const obj = {
  x: 11.01,
  y: -17,
};

то он занимает в памяти больше места, чем просто два 32-битных числа с плавающей запятой. Более низкоуровневые языки могут упорядочивать данные в похожие на объекты структуры таким образом, чтобы избежать лишней траты, связанной с объектами. Обычно такие структуры обозначаются struct.

struct {
  int x;
  int y;
} Particle;

К сожалению, Javascript не поддерживает ничего похожего на struct

К счастью, Javascript поддерживает TypedArray. TypedArray позволяют нам максимально близко подобраться в Javascript к низкоуровневому программированию. Они позволяют создавать в памяти массив фиксированного размера из смежных байтов. Это наш максимум приближения к низкоуровневому управлению памятью. Можно использовать TypedArray для хранения данных частиц, что гарантированно обеспечит плотную упаковку и непрерывность памяти.

Здорово, но хватит теории, пока писать работающий пример.

Первый проход

Я знаю, что симуляция должна выполняться на всех ядрах CPU, и знаю, что многопоточность реализуется в Javascript при помощи веб-воркеров. Да, переходить сразу на многопоточность в первом проходе — не лучший выбор, но это должно когда-нибудь случиться. Первым делом я подумал об использовании огромного SharedArrayBuffer (особого вида типизированного массива), что теоретически позволило бы мне распределить работу на несколько веб-воркеров. SharedArrayBuffer в Javascript позволяют сделать любой TypedArray общим для веб-воркеров и для основного потока при помощи «eventual visibility». По сути, это «простой режим» многопоточности без необходимости заботиться о блокировках. Отличная вещь.

Как будто ничего не предвещает проблем...

Я решил использовать «сигнальный» SharedArrayBuffer для коммуникаций между основным потоком и потоками воркеров, задействовав фичу «eventual visibility». Благодаря этому воркеры смогут ждать, пока основной поток не сигнализирует им запустить следующий такт симуляции, а основной поток будет знать, когда все воркеры закончат симуляцию. Помните, что пока только один воркер выполняет чтение/запись в адрес памяти, мне не нужно беспокоиться о синхронизации данных между воркерами.

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

Почему плохо, когда несколько потоков выполняют запись в одну память? При этом теряется детерминированность. Когда два потока выполняют чтение и запись в один адрес памяти, то нет гарантий чёткого порядка операций. Иногда первым выполняет запись поток А, иногда — поток Б. Это приводит к недетерминированным результатам.

Для реализации детерминированного доступа к памяти можно использовать мьютекс или семафор, но их сложно реализовать правильно. Javascript поддерживает Atomics API, но в нём применяются промисы, а это ужасно. Фу-у-у.

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

Я столкнулся с проблемой при реализации кода с SharedArrayBuffer, так как для их работы браузер требует специальных заголовков. Что-то связанное с атакой Spectre на CPU? Не знаю.

Но для справки покажу, что как нужно настроить заголовки, чтобы работали SharedArrayBuffer.

headers: {
  "Cross-Origin-Embedder-Policy": "require-corp",
	"Cross-Origin-Opener-Policy": "same-origin",
}

Теперь мы можем создавать SharedArrayBuffer, поэтому пришло время разобраться, как будем хранить данные.

Я решил, что каждая частица будет описываться четырьмя числами: x, y, dx и dy. Каждое из них будет 32-битным числом с плавающей запятой. При работе с подобными плоскими блоками памяти хорошей идеей будет использование концепции шага по индексу (stride). Это позволит нам оставаться в здравом уме. Подобное хранение данных называется плоским буфером, оно распространено в программировании для GPU.

Вот, как выглядит создание данных частиц при помощи SharedArrayBuffer.

const stride = 4; // 4 числа float: x,y,dx,dy;
const byte_stride = stride*4; // 4 байта на float
const sabParticles = new SharedArrayBuffer(PARTICLE_COUNT * byte_stride);
const sabViewParticles = new Float32Array(sabParticles);
...
//инициалиация частиц
for(let i = 0;i < PARTICLE_COUNT;i++) {
	sabViewParticles[i*stride] = Math.random() * canvas.width;
	sabViewParticles[i*stride+1] = Math.random() * canvas.height;
	sabViewParticles[i*stride+2] = (Math.random()*2-1)*10;
	sabViewParticles[i*stride+3] = (Math.random()*2-1)*10;
}

Стоит отметить, что SharedArrayBuffer требуют использовать «отображение» (view) данных, потому что нативно это просто множество беззнаковых байтов. В данном случае я использую отображение Float32Array.

Симуляция будет простой: мы будем прибавлять dx и dy к x и y, вот и всё.

Отлично. Замечательно.

А как же нам отрисовывать частицу на экране? Как они будут выглядеть? Круги? Квадраты? Кубы? Космические единороги? Надо подумать.

Я решил использовать объект ImageData  в котором каждая частица будет иметь размер в один пиксель. ImageData — это объект, входящий в браузерную спецификацию по работе с пиксельными данными, поэтому выбор был очевиден. Для отрисовки пикселей ImageData на экране можно использовать canvas HTML. По сути, это растеризатор на CPU, так что мы не нарушаем нашего правила.

А ещё благодаря этому код остаётся довольно простым, мне не приходится работать с библиотеками или бойлерплейтом для GPU, что могло бы быть очень сложным процессом.

Вот функция рендеринга.

function render() {
  const width = canvas.width;
  const height = canvas.height;
  backbuffer.data.fill(0); // ImageData
  for (let i = 0; i < PARTICLE_COUNT; i++) {
    const x = sabViewParticles[i * 4];
    if (x < 0 || x >= width) continue;
    const y = sabViewParticles[i * 4 + 1];
    if (y < 0 || y >= height) continue;
    const pixelIndex = ((y | 0) * width + (x | 0)) * 4;
    backbuffer.data[pixelIndex] += 30; // Красный канал
    backbuffer.data[pixelIndex + 1] += 40; // Зелёный канал
    backbuffer.data[pixelIndex + 2] += 65; // Синий канал
    backbuffer.data[pixelIndex + 3] = 255; // Альфа-канал (непрозрачность)
  }
context.putImageData(backbuffer, 0, 0);
}

Я должен кое в чём признаться. Для помощи в индексировании в плоском буфере пиксельных данных я на 100% использовал ChatGPT. Это можно понять по тому, что я оставил в коде очень полезные комментарии GPT. В данных заэкранного буфера (backbuffer) содержатся 4 беззнаковых байта на пиксель. Альфе я всегда присваиваю максимальное значение 255. Я буду прибавлять по биту цвета на частицу, пока все каналы не станут равными 255 (белый цвет). Кроме того, я не буду выполнять никаких действий с частицами, находящимися вне экрана. Это нужно и для отсечения частиц, которые нам не требуется отрисовывать, и для того, чтобы защититься от индексирования за пределами массива.

Связать эту функцию рендеринга с requestAnimationFrame, а также реализовать обмен сигналами с воркерами достаточно просто.

let lastTime = 1;
function runSimulation(currentTime) {
  const dt = Math.min(1, (currentTime - lastTime) / 1000);
  lastTime = currentTime;
  sabViewSimData[0] = dt;
  for (let i = 0; i < CPU_CORES; i++) {
    sabViewSignals[i] = SIGNAL_RUN;
  }
  render();
  requestAnimationFrame(runSimulation);
}

Чтобы учесть переменную частоту кадров, я добавил простое вычисление дельты времени. Такое вычисление дельты времени подойдёт не для всех симуляций, но здесь его вполне достаточно. Стоит также отметить, что я использую ещё один SharedArrayBuffer для хранения общих данных симуляции, например, дельты времени. Воркеры никогда не выполняют туда запись, так что синхронизировать ничего не нужно. И мы можем смириться с небольшими задержками.

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

Осталось только настроить воркеров

//подготавливаем воркеров
for (let i = 0; i < CPU_CORES; i++) {
  const worker = new Worker("./worker.js");
  workerPool.push(worker);
  worker.postMessage({
    sabParticles,
    sabSignals,
    id: i,
    chunkSize,
    chunkOffset: chunkSize * i,
    stride,
    sabSimData,
  });
}

Из кода понятно, как распределить работу на несколько ядер. Принцип всегда один и тот же: разбиваем данные на блоки и отправляем блоки пулу воркеров. Мне нужно лишь отправить одно post-сообщение, содержащее массивы SharedArrayBuffer, а также ещё несколько полезных битов данных.

Код воркера разочаровывающе прост.

setInterval(() => {
  if (signalsView[id] !== SIGNAL_RUN) return;
  const delta = dt();
  for (let i = chunkOffset; i < chunkOffset + chunkSize; i++) {
    particlesView[i * stride] += particlesView[i * stride + 2] * delta;
    particlesView[i * stride + 1] += particlesView[i * stride + 3] * delta;
  }
  signalsView[id] = SIGNAL_READY;
}, 1);

Знаю, знаю, что вы скажете. Я действительно использую setInterval со значением 1 мс как способ «засыпания» между проверками сигнала от основного потока? Да. Знал ли я, что интервалы и таймауты не могут выполняться меньше, чем 4 мс? Нет. Сработало ли это? Да, сработало.

Из-за сжатия видео процесс выглядит как настоящий хаос, так что попробуйте запустить реальную версию, просто выполнив bun http.ts в терминале. CodeSandbox уже не тот, что прежде. Здесь происходит только обновление позиций частиц и рендеринг кадра. Выглядит неплохо и мы реализовали миллион частиц. Челлендж выполнен?

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

Похоже, множество воркеров выполняет свою задачу.

И интервальные проверки тоже работают. Здорово.

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

Можно заметить, что почти не создаётся мусора, потому что память распределяется один раз, при запуске, а в цикле симуляции ничего не создаётся.

Хорошее начало.

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

Второй проход

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

Чтобы передавать ввод воркерам, я снова использую тот же SharedArrayBuffer состояния симуляции, в котором есть дельта времени. Можно добавить окну несколько слушателей ввода и настроить данные ввода, как нам удобно. Любые обновления из основного потока рано или поздно доберутся до воркеров.

// dt + mouse x + mouse y + touch down + screen with + screen height
const sabSimData = new SharedArrayBuffer(4 + 4 + 4 + 4 + 4 + 4);
// слушатели событий
window.addEventListener("mousemove", (e) => {
  sabViewSimData[1] = e.clientX;
  sabViewSimData[2] = e.clientY;
});
window.addEventListener("mousedown", (e) => {
  sabViewSimData[3] = 1;
});
window.addEventListener("mouseup", (e) => {
  sabViewSimData[3] = 0;
});

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

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

Есть только одна проблема: за свою жизнь я сходил только на одно занятие по физике. Физика — это страшно, даже страшнее математики. Но я знаю, что гравитация — это что-то про обратный квадрат. К счастью, у моей девушки есть степень по физике. Она любезно написала мне уравнение.

Сила равна гравитационной постоянной G, умноженной на массы обоих объектов m₁ и m₂ и делённой на r², где r — это расстояние между объектами.

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

Обновлённый код симуляции вполне неплох

const delta = dt();
const [mx, my, isTouch] = input();
for (let i = chunkOffset; i < chunkOffset + chunkSize; i++) {
  const decay = 1 / (1 + delta * 1);
  const x = particlesView[i * stride];
  const y = particlesView[i * stride + 1];
  let dx = particlesView[i * stride + 2] * decay;
  let dy = particlesView[i * stride + 3] * decay;

  if (isTouch) {
    const tx = mx - x;
    const ty = my - y;
    const dist = Math.sqrt(tx * tx + ty * ty);
    const dirX = tx / dist;
    const dirY = ty / dist;
    const force = 3 * Math.min(1200, 25830000 / (dist * dist));
    dx += dirX * force * delta;
    dy += dirY * force * delta;
  }
  particlesView[i * stride] = x + dx * delta;
  particlesView[i * stride + 1] = y + dy * delta;
  particlesView[i * stride + 2] = dx;
  particlesView[i * stride + 3] = dy;
}

Первым делом я добавил к скорости частиц немного трения. Это мешает частицам улететь за экран в бесконечность. При касании экрана мы вычисляем силу на основании расстояния между точкой касания и частицей. Далее обновляем положение частицы на основании dx и dy.

В силе используется постоянная масса и обратный квадрат расстояния прямиком из уравнения гравитации. Я ограничил это значение, а затем умножил результат на 3. Это умножение делает степенную функцию чуть более плоской, мне показалось, что так интереснее. Любопытно было бы поэкспериментировать со значениями.

Я немного поменял способ рендеринга частиц.

for (let i = 0; i < PARTICLE_COUNT; i++) {
  const x = sabViewParticles[i * 4];
  if (x < 0 || x >= width) continue;
  const y = sabViewParticles[i * 4 + 1];
  if (y < 0 || y >= height) continue;
  const pixelIndex = ((y | 0) * width + (x | 0)) * 4;
  const rx = x / width;
  const ry = y / height;
  pixels[pixelIndex] += 25 + 50 * rx; // Красный канал
  pixels[pixelIndex + 1] += 25 + 50 * ry; // Зелёный канал
  pixels[pixelIndex + 2] += 25 + 50 * (1 - rx); // Синий канал
  pixels[pixelIndex + 3] = 255; // Альфа-канал (непрозрачность)
}

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

Мне нравится. Можно часами играть с двумя миллионами частиц, что я и делал! Можно использовать в URL параметр запроса count и задать любое количество частиц. Сжатие видео не позволяет оценить всю красоту, запустите интерактивный пример.

А как насчёт десяти миллионов?

Да, при таком значении частота кадров упала. Плавность позволяет сохранить дельта времени.

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

Ага, ничего удивительного. Воркеры снова почти ничего не делают! Даже при таком огромном количестве частиц. Однако основной поток замедляется при отрисовке частиц на экран. Похоже, десять миллионов частиц — это слишком медленно.

Чтобы найти виновный в этом код, можно воспользоваться Chrome Inspector. Похоже, медленная часть — это задание пикселей в структуре ImageData.

Чтобы убедиться в этом, можно сделать так, чтобы код задавал только синий канал и альфа-канал.

Это существенно повышает производительность, примерно с 80-90 мс до 16-18 мс. Эта разница зависит от используемого CPU. На моём Macbook Air с чипом M1 разница менее заметна, чем на десктопе с Ryzen. Тому есть причина, которую мы изучим в следующих нескольких итерациях, когда будем исследовать стратегии оптимизации.

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

Пришло время для нескольких проходов оптимизации.

Третий проход

У нас есть простая симуляция частиц, способная без особого труда справляться примерно с миллионом частиц. Однако она едва использует все ядра CPU. Проще всего ускорить её работу, распределив больше работы на все ядра. Один из способов сделать это — заставить воркеры заниматься и отрисовкой пикселей. Это компромисс, потому что чтобы не дать воркерам выполнять запись в один адрес памяти, нам придётся выделить каждому воркеру собственный пиксельный буфер. Так мы покупаем потенциальное увеличение скорости ценой использования большего объёма памяти.

Это можно сделать несколькими способами. Я добавил ещё один огромный SharedArrayBuffer (SAB), в котором будут храниться пиксельные данные для каждого воркера. Существенно увеличится использование памяти, но я надеюсь в обмен получить значительный рост скорости.

let sabPixelBuffs = new SharedArrayBuffer(
  CPU_CORES * window.innerWidth * window.innerHeight * 3
);

Я храню для каждого пикселя экрана только каналы RGB и для каждого воркера храню пиксели размером с экран.

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

function render() {
  const width = canvas.width;
  const height = canvas.height;
  const pixels = backbuffer.data;
  const pixStride = width * height * 3;
  for (let i = 0; i < width * height; i++) {
    let r = 0,
      g = 0,
      b = 0;
    for (let j = 0; j < CPU_CORES; j++) {
      r += sabViewPixelBuffs[j * pixStride + i * 3];
      g += sabViewPixelBuffs[j * pixStride + i * 3 + 1];
      b += sabViewPixelBuffs[j * pixStride + i * 3 + 2];
    }
    pixels[i * 4] = r;
    pixels[i * 4 + 1] = g;
    pixels[i * 4 + 2] = b;
    pixels[i * 4 + 3] = 255;
  }
  context.putImageData(backbuffer, 0, 0);
}

Изменения в воркере достаточно просты: достаточно скопировать в него старый код рендеринга.

const buffStride = width * height * 3;
pixelBuffs.fill(0, buffStride * id, buffStride * id + width * height * 3);
for (let i = chunkOffset; i < chunkOffset + chunkSize; i++) {
  // код симуляции
  if (x < 0 || x >= width) continue;
  if (y < 0 || y >= height) continue;
  const pixelIndex = ((y | 0) * width + (x | 0)) * 3;
  const rx = x / width;
  const ry = y / height;
  pixelBuffs[buffStride * id + pixelIndex] += 25 + 50 * rx;
  pixelBuffs[buffStride * id + pixelIndex + 1] += 25 + 50 * ry;
  pixelBuffs[buffStride * id + pixelIndex + 2] += 25 + 50 * (1 - rx);
}

Отлично, а теперь посмотрим на результаты. ПРЕДУПРЕЖДЕНИЕ: присутствует сильное мерцание

Хм... это довольно странно. Картинка мерцает, но почему?

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

Вот строка, в которой я нарушил правило

pixelBuffs.fill(0, buffStride * id, buffStride * id + width * height * 3);

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

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

А теперь с ней всё плохо.

Это можно исправить несколькими способами:

1. Использовать Atomics API для синхронизации чтения и записи

2. Использовать post-сообщения для блокировки рендеринга, пока не завершат работу все воркеры

3. Реализовать двойную буферизацию ценой удвоения памяти пиксельных буферов.

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

Четвёртый проход

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

Чтобы сделать это, мне нужно отказаться от массива сигналов.

Вместо него основной поток будет хранить массив воркеров и переменную с количеством активных воркеров.

const workerPool = [];
let activeWorkers = 0;

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

function onWorkerMessage() {
  activeWorkers--;
  if (activeWorkers !== 0) {
    return;
  }
  render();
  requestAnimationFrame(runSimulation);
}

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

function runSimulation(currentTime) {
  const dt = Math.min(1, (currentTime - lastTime) / 1000);
  lastTime = currentTime;
  sabViewSimData[0] = dt;
  activeWorkers = WORKER_COUNT;
  workerPool.forEach((worker, i) => {
    worker.postMessage({});
  });
}

Остальная часть кода основного потока осталась такой же.

В целом код воркеров остался таким же, но теперь вместо массива сигналов для передачи состояния воркеров передаётся post-сообщение.

self.postMessage({ id: SIGNAL_READY });

Результат показывает, что проблема мерцания решена.

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

Хм… ситуация в основном потоке стала лучше, а воркеры начали выполнять существенно больше работы, но время кадра не улучшилось, а даже ухудшилось. В чём причина?

Ответы можно найти в профилировщике

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

Самый популярный способ этого решения встроен в большинство графических драйверов, он называется двойной буферизацией (double buffering). Смысл заключается в наличии двух пиксельных буферов вместо одного и попеременное использование их в каждом кадре. Пока основной поток выполняет отрисовку из одного буфера, воркеры могут подготовить к отрисовке второй. Это значит, что воркеры могут обрабатывать следующий кадр симуляции, пока рендерится предыдущий.

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

Пятый проход

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

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

let sabViewPixelsA, sabViewPixelsB, activePixelBuff;
// другой код
function resize() {
  canvas.width = window.innerWidth;
  canvas.height = window.innerHeight;
  sabViewSimData[4] = canvas.width;
  sabViewSimData[5] = canvas.height;
  backbuffer = new ImageData(canvas.width, canvas.height);
  sabViewPixelsA = new Uint8Array(
    new SharedArrayBuffer(width * height * 3 * WORKER_COUNT)
  );
  sabViewPixelsB = new Uint8Array(
    new SharedArrayBuffer(width * height * 3 * WORKER_COUNT)
  );
  activePixelBuff = sabViewPixelsB;
}

В код основного потока внесём лишь небольшое изменение

let lastTime = 1;
function runSimulation(currentTime) {
  const dt = Math.min(1, (currentTime - lastTime) / 1000);
  lastTime = currentTime;
  sabViewSimData[0] = dt;
  activeWorkers = WORKER_COUNT;
  workerPool.forEach((worker, i) => {
    worker.postMessage({
      sabViewPixels: activePixelBuff,
    });
  });
  activePixelBuff =
    activePixelBuff === sabViewPixelsA ? sabViewPixelsB : sabViewPixelsA;
  render(activePixelBuff);
}

Мы можем менять буферы местами до или после обновления воркеров, выбор за нами. Я решил делать это после.

Код воркеров не требует изменений. На этом мы закончили с двойной буферизацией.

Настало время протестировать её.

Здорово, стало лучше, чем было. И профилировщик действительно показывает, что воркеры больше не ждут рендеринга в основном потоке. Раньше завершение некоторых кадров требовало больше 50 мс, а теперь оно гораздо ближе к 16 мс.

Отлично.

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

pixelBuffs[buffStride * id + pixelIndex] += 25 + 50 * rx;
pixelBuffs[buffStride * id + pixelIndex + 1] += 25 + 50 * ry;
pixelBuffs[buffStride * id + pixelIndex + 2] += 25 + 50 * (1 - rx);

Но почему они медленные?

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

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

const pixelIndex = (y | 0) * width + (x | 0);

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

Сколько же данных используется и помещаются ли они в кэш CPU?

Формула для расчёта: ширина экрана * высота экрана * байтов на пиксель + байтов на частицу * количество частиц / количество воркеров

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

Если использовать для примера iPhone, то получим:

2532 * 1170 * 3 + 16 * 2000000 / 5

Это больше 15 МБ, то есть слишком много для любого кэша CPU первого уровня.

Именно поэтому медленно выполняются те три строки. Они приводят к порче кэша, а это плохо.

Я поэкспериментировал с несколькими идеями для решения этой проблемы, и даже попробовал сортировать частицы перед рендерингом по порядку пикселей. Я попробовал и версию с использованием Atomics API, чтобы проверить, изменит ли она что-нибудь. Это было крайне неудобно из-за применения промисов. А иногда она вылетала, и в причинах вылетов я так и не разобрался. Возможно, я сделал что-то не так, но из-за использования промисов она очень некрасивая.

У текущей версии на шаг симуляции на чипе M1 первого поколения и при двух миллионах частиц уходит примерно 4 мс. Доступ к пиксельным данным добавляет ещё 3,5 мс. Запись данных в пиксельный буфер — ещё 7 мс. Отрисовка в буфер в основном потоке занимает примерно 8 мс, но она происходит параллельно с рендерингом.

При тестировании на моём iPhone симуляция сохраняла частоту 60 FPS при одном миллионе частиц. Потрясающе.

Однако на моём десктопе с более чем двадцатью потоками она работала очень медленно. С частотой менее 60 FPS. Что?

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

Я не знал, как решить эту проблему и проблему повреждения кэша, поэтому вернулся к самой симуляции.

У меня появилась новая идея по реализации интерактивности и прежде чем добавлять новые оптимизации, мне хотелось кое-что подчистить.

Шестой проход

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

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

const particleStride = 6; // 4 float x,y,dx,dy,sx,sy;
const particleByteStride = particleStride * 4; // 4 байтов на float
const sabViewParticles = new Float32Array(
  new SharedArrayBuffer(PARTICLE_COUNT * particleByteStride)
);

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

forceSqr(sx, sy, x, y, 1);
dx += cacher.x * delta * 1;
dy += cacher.y * delta * 1;

Посмотрим, получилось ли у нас.

Снова крайне рекомендую вам запустить симуляцию самостоятельно, потому что сжатое видео вообще не даёт никакого представления о ней.

Это так круто, похоже на желе.

Завитки напоминают смятую бумагу или ткань. Симуляция и похожа, и непохожа на жидкость.

Я немного поразмышлял о превращении частиц в боиды. Для этого бы, скорее всего, понадобилась бы некая структура пространственного ускорения. Самым простым вариантом была бы сетка. Хм... сетка...

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

Настало время для ещё одного прохода оптимизации

Седьмой проход

Для хранения количества частиц в пикселе потребуется треть памяти от хранения данных RGB. Это не решает проблему паттерна доступа к кэшу, но сильно снижает объём необходимой памяти, то есть в кэше можно будет уместить больше данных.

Это сработало только потому, что информация цвета частицы записана в координаты x и y, а не в дополнительные данные каждой частицы.

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

Важно сделать всё это, потому что это решает проблему этапа аккумулирования рендера основного потока, замедляющегося с увеличением количества воркеров. Мы решили эту проблему, полностью избавившись от необходимости в этапе аккумуляции. Так мы экономим много памяти не только с точки зрения того, что умещается в кэш, но и ОЗУ.

Теперь формула кэша имеет вид ширина экрана * высота экрана + байтов на частицу * количество частиц / количество воркеров

Снова воспользовавшись для примера iPhone, получим

2532 * 1170 + 16 * 2000000 / 5

Это примерно 9,3 МБ, то есть снижение составило примерно 30%. Но 9 МБ — это всё равно слишком много для кэша первого уровня.

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

function render(grid) {
  const width = canvas.width;
  const height = canvas.height;
  const pixels = backbuffer.data;
  pixels.fill(0);
  for (let i = 0; i < width * height; i++) {
    const particleCount = grid[i];
    const y = Math.floor(i / width);
    const x = i % width;
    const rx = x / width;
    const ry = y / height;
    pixels[i * 4] = (25 + 35 * rx) * particleCount;
    pixels[i * 4 + 1] = (25 + 35 * ry) * particleCount;
    pixels[i * 4 + 2] = (25 + 35 * (1 - ry)) * particleCount;
    pixels[i * 4 + 3] = 255;
  }
  grid.fill(0);

  context.putImageData(backbuffer, 0, 0);
}

Изменение в коде воркеров тоже было простым.

const start = particleOffsetStart;
const end = particleOffsetEnd;

for (let i = start; i < end; i++) {
  // выполняем код симуляции

  if (x < 0 || x >= width) continue;
  if (y < 0 || y >= height) continue;
  const pCountIndex = (y | 0) * width + (x | 0);
  activeGrid[pCountIndex]++;
}

Это практически не влияет на производительность, если только количество воркеров не станет большим. Мой десктоп теперь может использовать все 24 ядра. Однако он всё равно оказывается медленнее, чем Macbook Air с чипом M1 первого поколения. Что за дела?

Оказывается, чипы Apple Silicone обладают до неприличия большими кэшами L1. Просто огромными. У моего десктопного Ryzen 9 3900x кэш L3 имеет размер 64 МБ, но L1 — всего 64 КБ. Чип M1 первого поколения имеет кэш L1 размером 320 КБ. 128 КБ используются под данные, а 192 КБ — под команды. Предполагаю, что этот необычно большой размер кэша L1 связан с требованиями хорошей работы Rosetta 2, но я могу и ошибаться.

Это объясняет, почему M1 быстрее, чем большой десктопный Ryzen 9. У него больше размер кэша данных и ему не так часто приходится ждать перемещения данных между кэшем и ОЗУ.

Заключение

Когда улеглась пыль, мы получили от всех оптимизаций примерно двукратный рост скорости по сравнению с первой многопоточной версией. Мне удалось достичь результата в 1 миллион частиц на телефонном CPU при частоте 60 FPS. Приличный результат, учитывая что всё это Javascript, но он не особо впечатляет. Уверен, что компилируемый язык был бы в десять раз быстрее, а если допустить, что он может использовать команды SIMD в коротких циклах, то скорость будет ещё выше.

Наверно стоит закончить на кратком сравнительном примере с использованием более традиционной методики инстансинга GPU для рендеринга вместо сомнительного собственного растеризатора. Симуляция останется на CPU, но в рендеринге будет использоваться стандартный конвейер на основе GPU.

20 миллионов частиц

Я написал простой пример, в котором для рендеринга частиц используется ThreeJS и инстансинг GPU на плоскости/четырёхугольнике. Оказалось, что его производительность чуть хуже, чем я ожидал. Инстансинг с ThreeJS требует обновления матрицы для каждой позиции частиц, а это выполняется на CPU в одном потоке. Эту работу можно распределить на GPU или по всем ядрам CPU, но она всё равно будет происходить медленно.

Это вызвано тем, что данные преобразований частиц нужно загружать в GPU в каждом кадре, а это довольно медленный процесс. Например, при симуляции четырёх миллионов частиц на чипе M1 80% времени кадра тратится на отправку данных в GPU. На моём десктопе для этого нужно всего 30% времени, но передача данных всё равно остаётся самым узким местом. Как только GPU получает все данные, отрисовка остаётся достаточно быстрой. Это значит, что с увеличением количества частиц увеличивается и объём данных, отправляемых в GPU, и эта система плохо масштабируется при количествах частиц выше нескольких миллионов. Однако можно реализовать довольно простую оптимизацию.

Я понял, что могу использовать ту же сетку количества частиц в качестве текстуры и рендерить полноэкранный четырёхугольник вместо инстансов точек. Смысл в том, что объём передаваемых в GPU данных на каждый кадр фиксирован и не зависит от размера симуляции. Использовав предыдущую сетку количества частиц, мы привяжем объём передаваемых на кадр данных к разрешению экрана. При этом в больших симуляциях будет передаваться меньше данных, но больше данных в маленьких симуляциях. Это перекос в сторону больших симуляций, который меня более чем устраивает.

Я вкратце реализовал версию на ThreeJS с собственным пиксельным шейдером, и результат меня удивил. Основному потоку на рендеринг нужно всего несколько миллисекунд, вне зависимости от размера симуляции. Это позволяет воркерам работать максимально быстро. Теперь симуляция напрямую ограничена количеством ядер CPU и при больших, и при малых масштабах симуляции. Каждый воркер примерно половину времени тратит на перемалывание чисел, а другую половину — на обновление количества частиц в сетке. Возможно, и то, и другое можно как-то ускорить ещё, но я ничего не придумал, кроме микрооптимизаций.

Эта версия может обрабатывать 20 миллионов частиц с частотой примерно 20 FPS на Mac с M1 при работе от аккумулятора. Потрясающий результат для чистого Javascript. Десктоп на той же частоте кадров успевает обрабатывать примерно 30 миллионов. Я попросил друга протестировать симуляцию на его 32-ядерном CPU и у него получилось добраться до 40 миллионов, то есть до размеров пяти 4k-дисплеев. При добавлении новых ядер симуляция достаточно хорошо масштабируется. Вы можете попробовать 20 миллионов самостоятельно. Или поэкспериментировать со своим телефоном на более скромном миллионе.

Какой же вывод здесь можно сделать?

CPU и GPU могут быстро перемалывать числа. Реально быстро. Перемещение данных происходит медленно, и ещё медленнее при произвольном доступе к данным. Если вам нужна скорость, то вам стоит знать, как работает оборудование.

Я получил огромное удовольствие от этого небольшого путешествия в мир веб-воркеров и SharedArrayBuffer. SharedArray и их функция «eventual visibility» кажутся мне магией. Когда станет чуть лучше поддержка WebGPU, я сделаю попытку писать compute-шейдеры.