Pull to refresh

Танчики на node.js — оптимизация

Game development
Спасибо всем, кто пытался поиграть в первый раз. Очень жаль, что я разочаровал столько людей жуткими тормозами игры. Но я мог бы и не догадаться до их причины, если бы не вы. Сейчас сервер порядком оптимизирован, но количество одновременных игр увеличено всего до пяти. Это незначительно, но дело уже не в производительности сервера, а в том, что в худшие вечерние часы скорость моего интернета не позволит больше. Заманухи ради появилась возможность выбрать уровень перед стартом игры. А также в ответ на «обидный» комментарий, появилась возможность поиграть 2 на 2. Итак — демка, альтернативный сервер, еще сервер. Сейчас остается надеяться, что я не сильно поспешил, и сервер не подведет. Под катом я расскажу, каких глупостей наделал в первой версии.

Профилирование


Итак, чтобы начать что-то оптимизировать, нужно найти узкие места. В случае node.js я поступил следующим образом: запускаем игру с ключом --prof

node --prof src/server

По завершении скрипта в текущей папке появится файл v8.log. Чтобы его превратить во что-то удобоваримое, я воспользовался утилитой linux-tick-processor из исходников v8. Не вдавался в подробности работы linux-tick-processor, но, чтобы получить её себе и заставить работать, пришлось выполнить несколько команд:

svn co http://v8.googlecode.com/svn/branches/bleeding_edge/ v8
cd v8
svn co http://gyp.googlecode.com/svn/trunk build/gyp
make native

После make native в текущей папке появится папка out с бинарниками, которыми пользуется linux-tick-processor. Чтобы обработать v8.log, в папке v8 выполняем:

tools/linux-tick-processor /full/path/to/v8.log > /full/path/to/v8.out

В получившемся v8.out смотрим результаты. Инфа о профилировании взята отсюда. Если я делаю это слишком сложно и кто-то знает способ лучше, буду рад узнать.

Имитируем нагрузку


Второй раз испытывать судьбу и рушить надежды сотен хабралюдей поиграть в танчики мне не захотелось. И я решил имитировать нагрузку на сервер своими силами. Для этого неплохо подходит Selenium, a точнее Selenium Server. Если кто-то не знаком, Selenium Server — это java приложение, способное запускать практически любой браузер, и выполнять разнообразные команды: кликать по ссылкам, нажимать кнопки, проверять наличие или отсутствие определенного текста на странице, и многое другое. Так же реализованы клиенты для многих языков программирования.
Для своих целей я написал небольшой php-скрипт, который открывает страницу, авторизуется, запускает игру и ждет 30 секунд. Запустив этот скрипт на выполнения в нескольких консолях:

phpunit --repeat=10 test.php

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

Оптимизация 1 — замыкания


Запускаем node с профайлером, обрабатываем лог, и смотрим v8.out. В файле v8.out функции отсортированы по убыванию времени исполнения. Первой в логе идет функция Array.forEach:

ticks  total  nonlib   name
1514    2.3%   14.9%  LazyCompile: *forEach native array.js:1019

Тут я не сразу понял в чем дело. Я решил, что это из-за того, что в некоторых местах я использую конструкцию:

someArray.forEach(function(item){
    ...
}, this);

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

Class.prototype.handler = function(item)
{
   ...
}

Class.prototype.func = function()
{
    someArray.forEach(this.handler, this);
}

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

Оптимизация 2 — поиск пересечений


Запускаем профайлер, запускаем selenium тесты и смотрим дальше:

   ticks  total  nonlib   name
  31043    3.8%   16.5%  LazyCompile: MapArrayed.intersects src/utils/map_arrayed.js:45
  26763    3.3%   14.3%  Stub: CEntryStub
  22800    2.8%   12.1%  LazyCompile: *forEach native array.js:1019
  16323    2.0%    8.7%  LazyCompile: IN native runtime.js:353
  13800    1.7%    7.4%  Stub: KeyedLoadElementStub
   6911    0.9%    3.7%  LazyCompile: *MapArrayed.forEach src/utils/map_arrayed.js:59

Что ж, не удивительно. Поиск пересечений занимает слишком много времени, нужно переписать карту. Я описывал три способа в прошлой статье: трехмерный массив с индексами-координатами, список прямоугольников и дерево вложенных прямоугольников. Поигравшись с деревом я пришел к выводу, что при 1000 объектов на карте большого выигрыша в производительности не получается. Идея трехмерного массива с индексами-координатам мне не нравится в принципе. Я остановился на следующем способе: в основе его так же остались объекты заданные прямоугольниками, но чтобы каждый раз не пробегать по всем объектам карты, объекты сгруппированы по небольшим ячейкам. То есть получаем тот же трехмерный массив, но с другим смыслом. Первые две размерности — это индексы ячеек, по сути это те же координаты, только с грубым приближением. Третья размерность — список объектов-прямоугольников пересекающихся с данной ячейкой. Отличия от предложения Oblitus в том, что такой способ не накладывает никаких ограничений на минимальный шаг перемещения для объектов и зернистость такого массива можно безболезненно варьировать по своему усмотрению. Вполне возможно, что это все еще не оптимальный вариант.

Оптимизация 3 — forEach


Опять смотрим результаты профилирования. Тут получается странная картина, если я поиграл только в одну игру, то имеем:

  ticks  total  nonlib   name
    51    0.1%   11.6%  LazyCompile: *Loggable.log battlecity/src/server/loggable.js:32
    12    0.0%    2.7%  LazyCompile: MapTiled.intersects battlecity/src/utils/map_tiled.js:106
     8    0.0%    1.8%  Stub: CEntryStub
     6    0.0%    1.4%  LazyCompile: *forEach native array.js:1019
     4    0.0%    0.9%  Stub: StringAddStub
     4    0.0%    0.9%  Stub: ArgumentsAccessStub_NewNonStrictFast

Если я запустил selenium и сервер проиграл несколько десятков игр:

   ticks  total  nonlib   name
   4108    2.0%   16.1%  LazyCompile: *forEach native array.js:1019
   3626    1.8%   14.3%  Stub: CEntryStub
   2176    1.1%    8.6%  LazyCompile: *MapTiled.forEach battlecity/src/utils/map_tiled.js:139
   2048    1.0%    8.0%  LazyCompile: IN native runtime.js:353
   1755    0.9%    6.9%  Stub: KeyedLoadElementStub {1}
   1475    0.7%    5.8%  LazyCompile: *Loggable.log battlecity/src/server/loggable.js:32
    337    0.2%    1.3%  LazyCompile: MapTiled.intersects battlecity/src/utils/map_tiled.js:106
    336    0.2%    1.3%  Stub: ToBooleanStub_Bool

Странная вещь, со временем forEach() жрет все больше и больше времени. Скажу, что каждый объект на карте имеет свой уникальный id, и этот id глобальный, то есть со временем он только увеличивается. Но кол-во объектов-то на карте не меняется от парии к парии. Это не очень удачный прием, можно сделать id объекта локальным для каждого игрового поля, чтобы id не увеличивался бесконечно, но ведь в javascript массивы хранятся не как в C++. В javascript это должно быть что-то типа хеш-таблицы, так почему же время forEach все больше и больше? В этом месте я долго бился головой об стену, пока не догадался провести такой эксперимент:

a=[1];
a[1000000]=1;
console.time('qwe');
a.forEach(function(i){console.log(i);})
console.timeEnd('qwe');
console.time('asd');
for (var i in a) console.log(a[i]);
console.timeEnd('asd');

В результате получаем неутешительные результаты.

FF:
qwe: 163ms
asd: 2ms

Chrome:
qwe: 254ms
asd: 1ms

ну и Opera для общей картины:
qwe: 0ms (188µsec)
asd: 0ms (87µsec)

Как видим в Опере forEach() и for(var i in ...) принципиально не отличаются по времени выполнения, но Chrome и Firefox очень сильно меня расстроили, именно по этому сервер (да и клиент) начинал сильно тормозить через несколько игр. Делать нечего, переписываем forEach() на for(var i in ...). И, о, чудо! Тормоза, которые я списывал на утечки памяти, пропадают!

Оставляем node на пару часов запустив в нескольких консолях «phpunit --repeat=100 test.php» и видим:

   ticks  total  nonlib   name
    746    0.2%   16.1%  LazyCompile: *Loggable.log battlecity/src/server/loggable.js:28
    128    0.0%    2.8%  LazyCompile: *Game._stepItem battlecity/src/core/game.js:77
    101    0.0%    2.2%  LazyCompile: MapTiled.intersects battlecity/src/utils/map_tiled.js:102
     61    0.0%    1.3%  Stub: CEntryStub
     52    0.0%    1.1%  Function: EventEmitter.emit events.js:38
     50    0.0%    1.1%  Stub: SubStringStub
     46    0.0%    1.0%  LazyCompile: *MapTiled.add battlecity/src/utils/map_tiled.js:24
     45    0.0%    1.0%  LazyCompile: FILTER_KEY native runtime.js:398

Наконец-то в результатах профилирования появляются вещи, о которых я предполагал, а не непонятно откуда взявшиеся forEach().

Оптимизация 4 — трафик


Тут я решил немного отступить от профайлера. Дело в том, что в поисках предыдущей оптимизации я посчитал трафик между клиентом и сервером. Оказалось в разгар игры клиенту может отправляться до 30кб/c. Очевидно, для такой игры, как танчики — это запредельная цифра. Но на это есть несколько причин. Во-первых, при изменения всего одного свойства, объект отправляется клиенту целиком. Во-вторых, объекты отправляются в JSON, что также значительно увеличивает размер передаваемых данных. Первоначально объекты отправлялись примерно так:
Bullet.prototype.serialize = function()
{
    return {
        type: 'Bullet',
        id: this.id,
        x: this.x,
        y: this.y,
        z: this.z,
        speedX: this.speedX,
        speedY: this.speedY,
        finalX: this.finalX,
        finalY: this.finalY
    };
};

что вело к передаче строки {«type»:«Bullet»,«id»:777,«x»:123,«y»:456,«z»:1,«speedX»:2,«speedY»:0,«finalX»:123,«finalY»:456} длинной около 100 байт. Немного подумав, переделал сериализацию объектов так, чтобы получался не объект, а массив:
Bullet.prototype.serialize = function()
{
    return [
        battleCityTypesSerialize['Bullet'], // 0
        this.id, // 1
        this.x, // 2
        this.y, // 3
        this.speedX, // 4
        this.speedY, // 5
        this.finalX, // 6 todo remove
        this.finalY // 7 todo remove
    ];
};

в результате получаем около 25 байт [0,777,123,456,2,0,123,456]. Трафик снизился примерно до 7-8кб/c в разгар игры. Его можно снизить еще в несколько раз, передавая только измененные свойства и передавая только управляющие команды, но эту переделку я оставил на будущее.

Оптимизация 5 — синхронизация с клиентом


Алгоритм синхронизации из прошлой статьи оказался неудачным. Единственная причина именно такого выбора, а не мгновенная рассылка изменений всем клиентам, которые в них заинтересованы, была в том, что вновь подключившийся клиент может получить все изменения в прошлом точно таким же способом, что и текущие данные. Так же во время реализации этого способа я пришел к идее сгруппировать объекты в коллекции, и обращаться за обновлениями не к самим объектам, а к коллекциям объектов. Такими коллекциями стали «все пользователи», «сообщения в общем чате», «список игр», «пользователи в текущей игре», «сообщения в текущей игре» и «объекты на карте текущей игры».
Новым способом синхронизации стала немедленная рассылка изменений по объектам User, где они накапливаются. А объект User по прежнему отправляет данные браузеру пакетами, раз в 50мс. Остается вопрос когда и как синхронизировать первоначальные данные? Я решил добавить объекту User 2 метода: watchCollection() и unwatсhCollection() и в момент подключения к группе объектов, User отправляет клиенту все объекты, как вновь созданные:

/**
 * @param collection
 * @param syncKey ключ, по которому клиент узнает к какой группе относятся объекты
 */
ServerUser.prototype.watchCollection = function(collection, syncKey)
{
    this.unwatchCollection(syncKey);
    // сюда будут складываться обновления объектов
    this.updateCollector[syncKey] = [];
    var user = this;
    var cb = function(item, type) {
        user.onCollectionUpdate(syncKey, item, type);
    };
    // подписываемся на обновления
    collection.on('update', cb);
    // запоминаем callback, чтобы при отключении от группы, можно было удалить обработчик
    this.collections[syncKey] = {'callback': cb, 'collection': collection};
    // отправляем клиенту все объекты группы, как вновь созданные
    collection.traversal(function(item){
        this.onCollectionUpdate(syncKey, item, 'add');
    }, this);
};

ServerUser.prototype.unwatchCollection = function(syncKey)
{
    if (this.collections[syncKey]) {
        // удаляем обработчик
        this.collections[syncKey].collection.removeListener('update', this.collections[syncKey].callback);
        // сообщаем клиенту, чтобы он удалил у себя эту группу
        this.clientMessage('clearCollection', syncKey);
        delete this.collections[syncKey];
        delete this.updateCollector[syncKey];
    }
};

Таким образом сразу после авторизации пользователя на сервере, объект User подключается к трем группам объектов (коллекциям):
user.watchCollection(registry.users, 'users');
user.watchCollection(registry.premades, 'premades');
user.watchCollection(registry.messages, 'messages');

А во время входа в игру и выхода из игры, пользователь соответственно подключается и отключается от других интересующих его коллекций:

Premade.prototype.join = function(user, clanId)
{
    // ...
    user.watchCollection(this.users, 'premade.users');
    user.watchCollection(this.messages, 'premade.messages');
    // ...
};

Premade.prototype.unjoin = function(user)
{
    // ...
    user.unwatchCollection('premade.users');
    user.unwatchCollection('premade.messages');
    user.unwatchCollection('f');
    user.unwatchCollection('game.botStack');
    // ...
};

Premade.prototype.startGame = function()
{
    // ...
    this.users.traversal(function(user){
        // ...
        user.watchCollection(this.game.field, 'f');
        user.watchCollection(user.clan.enemiesClan.botStack, 'game.botStack');
        // ...
    }, this);
    // ...
}

Жаль, что сразу не приходят в голову простые и правильные мысли.
В результате имеем:
    ticks  total  nonlib   name
   2074    0.5%    9.9%  LazyCompile: *Game._stepItem battlecity/src/core/game.js:29
    751    0.2%    3.6%  LazyCompile: MapTiled.intersects battlecity/src/utils/map_tiled.js:102
    489    0.1%    2.3%  LazyCompile: MapTiled.traversal battlecity/src/utils/map_tiled.js:132
    376    0.1%    1.8%  LazyCompile: FILTER_KEY native runtime.js:398

Судя по тому, что Game._stepItem вышел на первое место, и стал выполняться 9.9% времени, а не 2.8%, как раньше, считаем переделку успешной. На этот момент, сервер загружен примерно на 50% при 10 одновременных играх. Поставить 20 игр одновременно в демке я не рискнул, из-за того, что в худшие вечерние часы, скорость моего интернета падает до 200кБайт/с и ниже.

Оптимизация 6 — обход игровых объектов


Первоначально я не задумывался об этом, и для каждого объекта на поле в цикле вызывал функцию _stepItem():

Game.prototype._stepItem = function(item)
{
    // tanks and Base processing within Clan.step
    if (item.step && !(item instanceof Tank) && !(item instanceof Base)) { // todo
        item.step();
    }
};

Game.prototype.step = function()
{
    this.field.traversal(this._stepItem, this);
    this.premade.clans[0].step();
    this.premade.clans[1].step();
};


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

Game = function Game(level, premade)
{
    // ...
    this.stepableItems = [];
    this.field.on('add', this.onAddObject.bind(this));
    this.field.on('remove', this.onRemoveObject.bind(this));
    // ...
};

Game.prototype.onAddObject = function(object) {
    if (object.step && !(object instanceof Tank) && !(object instanceof Base)) {
        this.stepableItems[object.id] = object;
    }
};

Game.prototype.onRemoveObject = function(object) {
    delete this.stepableItems[object.id];
};

Game.prototype.step = function()
{
    for (var i in this.stepableItems) {
        this.stepableItems[i].step();
    }
    // ...
};


В результате я вернулся опять к пересечению объектов, но уже на совсем другом уровне:

   ticks  total  nonlib   name
    129    0.0%    2.4%  LazyCompile: MapTiled.intersects battlecity/src/utils/map_tiled.js:102
     66    0.0%    1.2%  Stub: SubStringStub
     54    0.0%    1.0%  Stub: CEntryStub
     47    0.0%    0.9%  Function: EventEmitter.emit events.js:38
     39    0.0%    0.7%  LazyCompile: MapTiled.add battlecity/src/utils/map_tiled.js:24
     30    0.0%    0.6%  Function: Socket._writeOut net.js:389


Теперь 5 игр одновременно занимают 15-16% процессорного времени. То есть мой старенький сервер должен потянуть около 30 игр в одном потоке.

Бага с наследованием


Пришлось побороться с одной багой, причины которой заслуживают внимания. При наследовании я забыл вызвать родительский «конструктор»:
function Parent()
{
    this.property = [];
}

function Child()
{
    // Parent.apply(this, argiments); - забыл
};

Child.prototype = new Parent();
Child.prototype.constructor = Child;

В результате массив property оказался только в prototype, а не в this. То есть расшарен между всеми экземплярами Child, что не вызвало никаких ошибок во время выполнения, но привело к труднообнаружимому багу. Все таки с javascript ничего не стоит прострелить себе ногу.

Планы на будущее


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

Первая часть
Tags:танчикиnode.jsjavascriptwebsockets
Hubs: Game development
Total votes 87: ↑80 and ↓7 +73
Views10.2K

Popular right now

Senior Javascript/Node.JS Разработчик
from 2,500 to 3,300 $MakeomaticRemote job
Node.js разработчик
from 40,000 to 60,000 ₽Onlinetours.ruRemote job
JavaScript Software Engineer
from 3,000 to 5,500 $XpowerОдессаRemote job
Backend developer (node.js)
from 2,000 $MessappsRemote job
Fullstack Developer (Node.js)
from 3,000 to 4,500 $IntentoRemote job