пятница, 28 марта 2008 г.

Многопоточность и свойства. Часть 1

В однопоточном мире есть очень многие вещи, о которых мы даже не задумываемся. Например, в онлайн-игре вполне приемлемо такое описание здоровья «живого объекта» (NPC или игрока) на C#:


public int Health
{
get { return m_health; }
set { m_health = value; }
}

Когда наносится повреждение, следующий код вполне логичен:

int damage = 100;
target.Health -= damage;

if (target.Health <= 0)
{
target.Die();
}

Т.е. мы вычитаем значение здоровья, затем сверяем, жива ли цель. Время идет, онлайн растет, процессоры дешевеют. Теперь у нас уже несколько многоядерных процессоров, тысячные онлайны, большая нагрузка. В этом свете один поток обработки выглядит архаичным и будет рано или поздно превращен в несколько конкурирующих потоков.
Если оставить указанный код без изменений в многопоточной модели, мы рано или поздно получим неприятные неожиданности. Чтобы было удобнее воспринимать, я преобразую работу со свойствами так, как делает это компилятор, но оставлю эту часть в формате C#:

int damage = 100;
int tmpHealth = target.get_Health();
target.set_Health(tmpHealth - damage);
if (target.get_Health() <= 0)
{
target.Die();
}


Расписывать, почему Health -= превратилось в такого монстрика, тут я не буду – читайте Рихтера, MSDN. Гораздо важнее то, что в этих нескольких строках кода у нас несколько проблем синхронизации. Распишу в виде таблицы несколько вариантов развития событий с двумя потоками, которые одновременно пытаются сделать такую операцию. Для удобства скажем, что значение m_health изначально было равно 150, а damage для наших потоков 100 и 200 соответственно.

Вариант 1

Поток 1Поток 2
int tmpHealth = target.get_Health();
значение tmpHealth = 150
int tmpHealth =target.get_Health();
значение tmpHealth = 150
target.set_Health(tmpHealth - damage);
значение m_health = 50
target.set_Health(tmpHealth - damage);
значение m_health = -50
if (target.get_Health() <= 0)
{
    target.Die();
}
условие истинно, т.к. m_health уже -50,
вызывается target.Die()
if (target.get_Health() <= 0)
{
    target.Die();
}
условие истинно, вызывается target.Die()


Вариант 2


Поток 1Поток 2
int tmpHealth = target.get_Health();
значение tmpHealth = 150
target.set_Health(tmpHealth - damage);
значение m_health = 50
int tmpHealth = target.get_Health();
значение tmpHealth = 50
target.set_Health(tmpHealth - damage);
значение m_health = -150
if (target.get_Health() <= 0)
{
    target.Die();
}
условие истинно, вызывается target.Die()
if (target.get_Health() <= 0)
{
    target.Die();
}
условие истинно, т.к. m_health = -150,
вызывается target.Die()


Вариант 3

Поток 1Поток 2
int tmpHealth = target.get_Health();
значение tmpHealth = 150
int tmpHealth = target.get_Health();
значение tmpHealth = 150
target.set_Health(tmpHealth - damage);
значение m_health = -50
target.set_Health(tmpHealth - damage);
значение m_health = 50
if (target.get_Health() <= 0)
{
    target.Die();
}
условие ложно, т.к. m_health = 50
if (target.get_Health() <= 0)
{
    target.Die();
}
условие ложно


Это не все возможные варианты, но некоторые из них. Вне зависимости от количества процессоров, всегда есть вероятность, что в разных потоках один и тот же код будет выполнен в неудачном для нас порядке. В случае со здоровьем NPC это может привести к многократному вызову метода Die() или к потере результата одного из вызовов. Кто-то может предложить добавить блокировку в само свойство Health:

public int Health
{
get
{
lock (m_healthLock)
return m_health;
}
set
{
lock (m_healthLock)
m_health = value;
}
}

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

if (target.Health > 0)
lock (taget.HealthLock)
if (target.Health > 0)
{
int damage = 100;
target.Health -= damage;

if (target.Health <= 0)
{
target.Die();
}
}

Такой подход дает оптимальный результат, но влечет значительные изменения кода, а также работу с CriticalSection (вместе с ThinLock в .Net 2.0 и выше) при каждом обращении.
Конечно, было бы легче, если бы мы пользовались С++, а метод для получения здоровья возвращал ссылку или указатель, но подобных стандартных механизмов в C# нет (unsafe и указатели мы пока опустим). Также было бы проще, если бы Health было не свойством (property), а полем (field). В таком случае, мы бы поступили так:

int damage = 100;
if (Interlocked.Add(ref target.Health, -damage) > 0)
{
target.Die();
}

Атомарная операция Interlocked.Add обеспечит нам выполнение вычитания без вмешательства других потоков, а также вернет старое новое значение переменной. Таким образом, мы без проблем сможем узнать, было ли именно это повреждение смертельным.
Мы отошли от принципов «красивого программирования» ради дополнительной производительности. В большей части случаев такой вариант приемлем, но у свойств есть еще одно полезное свойство – они могут быть виртуальными.
Например, в базовой реализации «живого объекта» мы имеем всю ту же работу с переменной:

public virtual int Health
{
get { return m_health; }
set { m_health = value; }
}

А в наследнике, реализующем игрока, запись уже идет в объект БД:

public override int Health
{
get { return m_dbCharacter.Health; }
set { m_dbCharacter.Health = value; }
}

Перейти к Interlocked методам в этом случае будет проблематично, потому самым разумным вариантом будет в таком случае перестать пользоваться свойством set напрямую (например, объявить его как protected в .Net 3.5) и сделать отдельный метод для изменения здоровья объекта:

void ModifyHealth(int value)
{
if (Health > 0)
lock (m_healthLock)
if (Health > 0)
{
Health += value;

if (Health <= 0)
{
Die();
}
}
}

Хотелось бы использовать атомарные методы и в этой ситуации, но это уже проблематично, т.к. m_dbCharacter.Health в свою очередь вполне может быть свойством.
Наиболее производительным решением будет отказаться от виртуальности в таких свойствах, а объект БД обновлять в ключевых точках (при выходе из игры, при смерти и т.п.). Наиболее правильным решением будет отказ от использования публичных сеттеров для свойств, которые могут быть использованы в разных потоках. Разумным людям я советую остановиться на одном из этих вариантов. Остальным же (любителям нестандартных решений и «крестовых походов») я предложу несколько своих вариантов решения в следующих статьях на эту тему.


Update 03.04.08: Interlocked.Increment/Interlocked.Decrement не имеют второго параметра. Правильно пользоваться Interlocked.Add. Если кого сбил с толку - извиняюсь, самого бес попутал

Update 04.04.08: В ходе испытаний оказалось, что Interlocked.Add возвращает не старое, а новое значение. Это я проворонил, каюсь.


Дальше..

вторник, 25 марта 2008 г.

Двумерные массивы и foreach

Известно, что если сделать список List<TestObject> list и перебирать его через foreach:


foreach(TestObject obj in list)
{
..
}

скорость будет меньше, чем если бы у нас был массив TestObject [] array и мы перебирали его поэлементно или тем же foreach:

foreach(TestObject obj in array)
{
..
}

Разница в скорости примерно в 2-3 раза, но зачастую это не критично, т.к. сами операции над объектами занимают такое время, что на их фоне перебор коллекции лишь песчинка в песочных часах.

Причина скорости работы с массивами в том, что компилятор и JIT отслеживают такие операции и машинный код перебора массива уже сравним с тем, что был бы в чистом С - наращивание указателя на элемент массива с каждым шагом. В случае же с List<> создается енумератор, выполняется каждый раз вызов MoveNext и прочие действия.

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

for(int x=0; x<max_x; x++)
for(int y=0; y<max_y; y++)
{
   TestObject obj = array[x,y];
..
}


Через какое-то время коллекцию пришлось вынести в другое место, а массив получать как TestObject[,]. Тогда же и появилась идея написать перебор в один цикл с стандартным foreach:

TestObject [,] array = getArray();
foreach(TestObject obj in array)
{
..
}

Компилятор остался недоволен такой конструкцией, потому массив был приведен к Array и следующий пример без проблем компилировался и работал:

Array array = (Array)getArray();
foreach(TestObject obj in array)
{
..
}


Через несколько дней я заметил, что нагрузка на процессор после этой "оптимизации" заметно возросла. Детальное изучение показало, что после приведения к Array перебор коллекции перестал оптимизироваться и свелся к работе с Array.GetEnumerator(), оптимальность которого, мягко говоря, невысокая.

Был вариант вернуться к двойному перебору массива, но в результате был выбран более простой путь - отказаться от двумерных массивов. Действительно, с zero-based индексами мы совершенно спокойно можем заменить обращение array[x,y] на array[x + y*max_x], а для перебора коллекции получать просто массив TestObject[] и работать с ним как с foreach/for/while, положившись на оптимизацию компилятора и JIT.

В качестве вывода я процитирую Mike Stall (http://blogs.msdn.com/jmstall/):


Optimizing for the wrong scenario can kill performance



Дальше..

понедельник, 24 марта 2008 г.

.Net Thread Pool и IOCP

В программировании часто перед нами встает задача выполнить какое-то действие "параллельно" с текущим. Методов решения может быть море: использование дополнительных потоков, откладывание задачи "на потом" (вручную или с помощью APC), использование каких-либо очередей задач и другие варианты асинхронного выполнения.
Нас же интересует именно Thread Pool в .Net. Его использование зачастую считается хорошим тоном, а некоторые методы CLR используют его неявно для своих целей (в т.ч. System.Net.Sockets и делегаты в асинхронных вызовах). Недостаток у него я усматриваю лишь один: универсальность. Все люди разные, но на заводах шьют одежду по общим меркам и размерам. Каждая книга уникальна, но для нее определяют категорию и ставят на полку с другими, похожими..

Так и наш Thread Pool пытается решать все задачи единым подходом: задача поступает в очередь и через какое-то время выбирается один из свободных потоков для ее выполнения. Если свободных потоков нет, то с некоторой периодичностью создаются новые.
Проблема в том, что нас не всегда может устроить тот факт, что все задачи равноправны и все выполнятся "как можно быстрее". Нас изредка волнует, насколько затормозят работу БД 25 задач извлечения данных, выполненных одновременно, нам хочется указать, что такая-то задача может быть выполнена после всех остальных. Конечно, в 95% случаев это не имеет значения, но когда мы говорим о time-critical приложениях, таких как сервера онлайн-игр, это надо учитывать. Те же 25 обращений к БД эффективны лишь в том случае, если на сервере БД есть 25 процессоров, способных выполнить эти запросы, иначе задачи либо поступят там в очередь выполнения, либо будут выполняться в 25 разных потоках, что может привести к увеличению накладных расходов на блокировки, совместное использование жесткого диска и пр. Практика показывает, что 25 таких задач почти всегда быстрее выполнятся последовательно, чем параллельно.

Посмотрим в сторону кастомизабельности Thread Pool. Он позволяет указывать количество потоков (SetMaxThreads/SetMinThreads), а также сам рассчитывает нужное кол-во потоков исходя из количества процессоров:

There is one thread pool per process. The thread pool has a default size of 25 worker threads per available processor, and 1000 I/O completion thread.


Количество потоков дет нам возможность управления над выполнением: совсем "тяжелые" задачи есть смысл выполнять в 2-3 потока, не критичные по времени - в одном потоке, а "легкие", в которых точно нет блокировок, правильно выполнять в таком же количестве потоков, сколько и процессоров в системе. К сожалению, это все было бы возможно, если бы можно было использовать несколько пулов с разными параметрами. Самое начало цитаты не оставляет нам выбора - надо придумывать что-то собственное.
Тут есть смысл посмотреть в сторону приятнейшей технологии IOCP: Input Output Completion Ports. Как видно из названия, разрабатывалась она для облегчения асинхронного выполнения операций ввода/вывода. Нам же важно, что технология эта позволяет ставить задачи в очередь и выполнять их с помощью указанного количества потоков. А именно, мы сами создаем потоки для IOCP и вызываем в них метод GetQueuedCompletionStatus. На этом выполнение потока блокируется и дальнейшую судьбу его решит уже ядро системы. Ожидающие потоки ставятся в LIFO (Last In First Out) очередь и возобновляются тогда, когда для них есть задачи. Использование именно LIFO позволяет использовать одни потоки чаще, чем остальные, что уменьшает расходы на переключение между ними.

Реализация собственного Thread Pool с IOCP довольно проста. Для операций надо будет извлечь с помощью P/Invoke четыре функции из kernel32.dll:
  • CreateIoCompletionPort
  • CloseHandle
  • GetQueuedCompletionStatus
  • PostQueuedCompletionStatus
При создании собственного пула надо инициализировать объект IOCP через вызов метода CreateIoCompletionPort, потом создать кужное количество потоков, в которых в цикле будет вызываться GetQueuedCompletionStatus и затем использовать PostQueuedCompletionStatus для постановки задачи в очередь. Саму задачу можно передать в виде ссылки на делегат. Делается это без особых сложностей самой CLR (если при описании P/Invoke указать делегат как параметр к PostQueuedCompletionStatus), либо вручную через класс Marshal, или же через GCHandle. ToIntPtr/GCHandle. FromIntPtr.
После окончания использования IOCP надо закрыть методом CloseHandle.

Такой подход дает нам возможность использовать любое количество собственных Thread Pool с любым количеством потоков.

Дальше..

Создание блога

Запущен блог, в котором будут освещаться вопросы, возникающие в ходе разработки RunServer, а также вопросы сетевого программирования и создания игр вцелом.
Я не могу назвать себя опытным разработчиком игровых проектов, но некоторый опыт имеется, в том числе и проект учебного эмулятора World of Warcraft - RunWoW, который на данный момент в кластерном режиме поддерживает 2500 пользователей онлайн (http://wow.wnet.ua/).
Также я участвую в проекте Syndicate Online (http://www.syndicate-online.com/), сервер которого построен на платформе RunServer.
Дальше..