четверг, 11 декабря 2008 г.

Поддержка Mono

Сегодня мы начали работать над возобновлением поддержки Mono (http://www.mono-project.com/) платформой RunServer. Причин для этого несколько, но самая первая из них - кросс-платформенность. Три года назад такая мысль меня уже посещала и результат был неутешителен: на Mono 1.14 мы получали примерно десятикратное падение производительности по сравнению с Microsoft .Net Framework 2.0 в RunWoW. Сейчас же различные источники (например этот) сообщают, что скорость Mono вплотную приблизилась к показателям .Net.

После некоторых упражнений с напильником и бубном, RunWoW запустился, но самый первый процесс - загрузка данных из БД - занял около 10 минут против 2х минут в .Net. Вывод напрашивался сам собой, но все-же стало интеерсно, откуда такая существенная разница в скорости.


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

Дополнительные проверки показали следующее:
- реализация System.Data.SqlClient в Mono приблизительно на 40% медленнее, чем в . Net;
- время создания обьекта отличается в Mono и .Net на доли процента;
- различные коллекции (связные списки, словари, группы массивов, да и просто обычные списки) на время загрузки данных из БД не влияют, т.к. время выборки, приведения типов, да и вцелом обработки загруженных данных, на порядок больше времени, которое тратится на перебор коллекций;
- в случае, если грузится больше N элементов, выполняется не обычный select * from <..> where <..>, а просто select * from <..> и затем результат фильтруется;

Последняя особенность привлекла мое внимание. С одной стороны, все корректно - я сам писал этот код и отлаживал на различных БД, сравнивая производительность такого решения. С другой стороны оказалось, что если убрать проверку и никогда не загружать все элементы, то разрыв в скорости на Mono и .Net уменьшается до 30-40%.
Копнув чуть глубже я нашел, что сама фильтрация результатов делается не очень оптимально: есть некий массив с ID, которые должны быть в результируещем списке и для каждого элемента таблицы выполняется проверка Array.IndexOf(id) != -1.
Этот метод имеет право на жизнь, если сам IndexOf базируется на каком-нибудь оптимизированном алгоритме (хотя бы на двоичном поиске), но совершенно неприемлим в случае последовательного перебора.

Докопаться до истины стало делом принципа. Я нашел реализацию IndexOf в Mono:

public static int IndexOf (Array array, object value, int startIndex, int count)
{
if (array == null)
throw new ArgumentNullException ("array");

if (array.Rank > 1)
throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));

// re-ordered to avoid possible integer overflow
if (count < 0 || startIndex < array.GetLowerBound (0) || startIndex - 1 > array.GetUpperBound (0) - count)
throw new ArgumentOutOfRangeException ();

int max = startIndex + count;
for (int i = startIndex; i < max; i++) {
if (Object.Equals (value, array.GetValueImpl (i)))
return i;
}

return array.GetLowerBound (0) - 1;
}


Как мы видим, тут имеет место последовательный перебор. Я не стал искать реализацию этого метода в .Net, но подозреваю, что он вызывает Array.BinarySearch, что делает его в разы быстрее. Как бы там ни было, если необходимо проверить наличие записи в коллекции, самым быстрым вариантом является использование Dictionary<>, на котором я и остановился. Результат достаточно приемлим: сервер на Mono потребляет немного больше памяти и загружается на ~40% медленее. К тому же, после отказа от Array.IndexOf и .Net версия стала грузиться быстрее на пару десятков секунд.

Вывод у меня лишь один: Premature optimization is the root of all evil.

Дальше..

среда, 10 декабря 2008 г.

Баг со структурами и readonly

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


Рассмотрим такой код с вспомогательной структурой и классом.

public struct TestStruct
{
private int m_count;
private int m_value;

public int Count
{
get { return m_count; }
}

public int Value
{
get { return m_value; }
}

public TestStruct(int value)
{
m_value = value;
m_count = 0;
}

public void Increment()
{
m_count++;
}
}

public class TestClass
{
private TestStruct m_struct;

public int Value
{
get { return m_struct.Value; }
}

public int Count
{
get { return m_struct.Count; }
}

public TestClass(int value)
{
m_struct = new TestStruct(value);

for (int i = 0; i < value; i++)
Increment();
}

private void Increment()
{
m_struct.Increment();
}
}


Если создать экземпляр TestClass с каким-либо числом, то значения Value и Count будут равны этому числу. Вполне нормальное и логичное поведение.
Картина меняется, если мы добавим слово readonly:

private readonly TestStruct m_struct;


После этого изменения код

TestClass test = new TestClass(11);
Console.WriteLine("Test result: value {0}, count {1}",
test.Value, test.Count);

выдает такой результат:

Test result: value 11, count 0

Верно такое поведение или нет?
Мы знаем, что структуры являются value-type и для каждого члена структуры, вложенной в класс, память выделяется в самом классе. Потому логично предположить, что readonly распостраняется и на члены структуры. Неприятно, но компилятор нам об этом не сообщает и никак не предупреждает, что этот модификатор приведет к потере данных.
Более того, логично было бы предположить, что если метод Increment() обьявлен как private и используется только в конструкторе, то метод будет inline и на него будут распостранятся те же правила, что и для конструктора. К сожалению, это предположение не оправдывается и нам просто надо помнить, что вызов методов в конструкторе может привести к "необычным" последствиям, не говоря о том, что может быть при вызове виртуальных методов.

Дальше..

четверг, 13 ноября 2008 г.

Знание языка

Прошел тест на знание русского языка.

Я прошел "Тест на определение словарного запаса"



ВАШ СЛОВАРНЫЙ ЗАПАС - Результаты теста
Ваш словарный запас на очень высоком уровне! Превосходный результат! Вы правильно ответили на 32 вопроса из 35! Поздравляем!
Пройти "Тест на определение словарного запаса" здесь

Дальше..

пятница, 4 июля 2008 г.

SIM в Native OS X режиме


Сегодня удалось собрать SIM под qt3/mac. Понадобилось некоторое количество патчей, а также более глубокое понимание принципов работы QT приложений. Основным минусом этой версии являются проблемы с кодировками кириллицы при отправке сообщений и иногда при их приеме. Я постараюсь на днях сделать dmg образ и самодостаточное app приложение, чтобы облегчить процесс установки и тестрования. В продолжении статьи полноэкранный скриншот.

Из визуальных багов заметно небольшое смещение иконок на кнопках


Отображаение смайлов, да и вцелом интерфейс почти идентичны тому, что мы видим на других платформах, за исключением скина Aqua

Дальше..

Билд SIM для OS X

У меня получилось собрать SIM под OS X для qt3-Xfree. Это не самый лучший вариант сборки (особенно, с учетом проблем с кодировкой, переключением языка, сворачиванием в док и пр.), но все-таки он работает.

К сожалению, билд под qt3-win, т.е. нативный Carbon, все еще не работает и причина его сбоев не известна. Я постараюсь в ближайшее время выложить X-билд, дабы дать хоть какую-то возможность пользовать SIM под Macintosh, но вцелом, в планах есть пункт "запустить SIM в Carbon или Cocoa режиме".

Дальше..

Песни Петера Сьлядека


Этот мой пост не о программах и не о технологиях. Скорее, он о людях, которые их создают.
Сейчас я читаю книгу Г.Л. Олди, "Песни Петера Сьлядека".

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

Авторы хотят донести до нас что-то, что в обыденной жизни не встречается и понимается с трудом. В любом случае, это не попытка заставить читателей воображать себя героями (в пику Зыкову и подобным), это и не старания заставить нас думать о Вечном, как у неповторимых Братьев С. Скорее, "Песни", заставляют нас заново прочувствовать то, что давно стало стереотипами: мечту о вечной жизни в достатке, добром джинне-чудотворце, о даре побеждать, как мечем, так и словом, о способности знать будущее..
Мой совет - читать однозначно.


Дальше..

среда, 2 июля 2008 г.

Фикс SIM для поддержки нового протокола

01.07.2008 многие ICQ клиенты отключились с ошибкой, говорящей о том, что протокол неверен. В эту же категорию попал мой любимый клиент SIM (http://sim-im.org/)
Патч был сделан энтузиастами довольно быстро, но готовая версия неизвестно когда появится в общем доступе или на сайте признаного сборщика Windows билдов Noragen. Я взялся пересобрать плагин ICQ для Windows версии и выкладываю его тут.
Ссылка: http://runserver.net/icq.zip

Процесс установки довольно прост: скачиваем версию 0.9.5 с сайта Noragen (http://sim.gosign.de/setup.exe), устанавливаем и затем записываем icq.dll из архива в папку Program Files\sim\plugins, заменяя предыдущую версию.
Скорее всего, через небольшое время появятся оффициальные патчи и моя сборка не будет нужна, потому обновлять ссылку я не планирую.

P.S. Возможно, через некоторое время я попробую собрать проект на Intel Optimizing Compiler, тогда и выложу результат.

Дальше..

суббота, 3 мая 2008 г.

Кеш с гибридными ссылками

Иногда приходится задумываться о том, что выделять новые объекты каждый раз слишком дорого. Особенно это относится к байтовым и пр. буферам. В таком случае, целесообразно организовать некий пул и брать оттуда объекты, возвращая их после использования.
Госпожа Maoni Stephens (http://blogs.msdn.com/maoni/) предлагает использовать двухуровневый кеш:

use a 2-level caching mechanism:
· Maintain a strong reference for the cached items for x amount of time;
· After x amount of time is up, convert the strong references to weak references. Weak references will be considered to be kicked out of the cache before strong references are considered.

У нас нет оснований не доверять этой уважаемой даме, которая, между прочим, performance PM in the CLR department.

Реализаций одноуровневых кешей может быть достаточно много. Все они сводятся к тому, что есть некая коллекция, куда записываются объекты вместо удаления и откуда они извлекаются для работы. Чаще всего используется очередь, но иногда это бывает стек или простой список. Проблема таких пулов в уровне полезной нагрузки. Например, каждую минуту из пула считывается 1000 объектов и 1000 возвращается. Это значит, что достаточно иметь в коллекции около 1000 позиций для нормальной работы. Если происходит "всплеск" и за секунду будет запрошено 10000 объектов, будет создано 9000 новых объектов и затем они вернутся в пул. Когда нагрузка станет снова 1000 операций в секунду, в пуле будет 10000 объектов, что в 10 раз больше нужного уровня. Это пустая трата, а также не неужная фрагментация памяти.
Если у нас пул основан на очереди (модель First-In-First-Out), то все 10000 объектов будут по кругу перебираться и использоваться, что не очень оптимально. Если же в пуле задействован стек (модель First-In-Last-Out), то 9000 объектов использоваться не будут, и просто будут занимать память.
Хорошим вариантом может быть использование слабых ссылок (Weak Reference) в коллекции пула. Такие ссылки будут указывать на объекты пула до сборки мусора GC. После нее они станут не валидными. Это приемлимо, но не оптимально, потому есть смысл рассматривать гибридные варианты, о которых и говорится в цитате в начале статьи.

Если реализовывать двухуровневый кеш в таком виде, как предлагает Маони, то с некоторым интервалом нам придется пробегать эту коллекцию и проверять каждую ссылку, чтобы знать, не пора ли ей переходить из режима Strong reference в Weak reference. В подобном переборе нет ничего противозаконного, кроме того, что эта операция не потокобезопасна и должна проводиться с обязательной синхронизацией. Правильнее всего ставить блокировку на саму операцию перебора коллекции, а также на все операции по извлечению/возврату кешируемых объектов.
Как обычно, нормальных людей такой вариант вполне устроит, но членам общества Анонимных Параноиков, к которым я принадлежу, покажется, что это довольно дорого и необоснованно. :)

Долгое время я искал различные сложные решения, пытался регистрировать гибридные ссылки в отдельных коллекциях, делал копию коллекции пула перед перебором и т.п., но все это не удовлетворяло по сложности и скорости работы.
Выход сегодня был найден, причем довольно неожиданный. Ранее я упирался в поиск комплексного решения, искал подходы в чистом программировании, но найденное решение лежало на поверхности.
Оно не относится к "честным" методам: при возвращении объекта в кеш, я добавляю в пул слабую ссылку на него (WeakReference), а в отдельный список - обычную сильную ссылку. При этом, я не задумываюсь о таких тонкостях, как был ли объект ранее в этом вспомогательном списке, никогда не удаляю оттуда объекты, никогда не перебираю этот список. Единственная операция, которую я делаю с этой вспомогательной коллекцией - очищаю ее раз в несколько минут.
Это звучит несколько странно, но смысл довольно прост: я не даю объектам в пуле умереть в течение некоторого времени. Если объект извлекли из пула для работы, то на его время жизни эта коллекция никак не повлияет. Если же объект "ушел на дно", т.е. находится в хвосте стека, или в середине очереди, то мы убираем единственную сильную ссылку на него, а слабая ссылка умрет при сборке мусора.
Таким образом, через какое-то время после "всплеска" пул будет содержать только то количество объектов, которое нужно для работы, вплоть до полного очищения - отмирания всех ссылок, когда пул не используется.

Такое использование памяти кажется мне наиболее оптимальным, пусть решение и не на 100% соответствует канонам ООП.

P.S. Я рекомендую использовать для пула стек, а не очередь. Этот подход дает больше нагрузки на "ближние" объекты стека, но "дальние" почти никогда не используются и могут быть очищены сборкой мусора. Если вы не хотите сразу выделять много памяти для этого стека, можно посмотреть в сторону идей господина Justin Rogers.
P.P.S. Для обеспечения нужного времени жизни объектов в пуле есть смысл использовать более сложные методы, чем одна ссылочная колекция. Например, хранить две коллекции и в методе очистки основную заменять вспомогательной, а старую вспомогательную удалять. Таким образом любой объект гарантированно будет иметь сильную ссылку на время не меньше интервала очистки.


Дальше..

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

Собственный BitArray

Представим себе ситуацию, что у нас есть несколько сотен переменных, каким-то образом помеченных номерами. Также представим, что нам надо знать, какие из объектов изменялись, а какие нет.
Самый простой способ - держать массив булевых значений и устанавливать true или false по индексу, соответствующему номеру переменной. Чтобы было удобнее, можно наши переменные обернуть в свойства (Property) и в методе set сразу изменять состояние массива.


public int Variable10
{
get { return m_variable10; }
set
{
m_variable10 = value;
m_changed[10] = true;
}
}

Сложности начинаются если нам нужно держать счетчик измененных полей. На первый взгляд это очень просто - добавить некий m_count++ в каждый метод set..

Но что будет, если нам надо несколько раз изменить значение переменной? Просто так увеличивать счетчик в таком случае нельзя и надо делать простую проверку:

public int Variable10
{
get { return m_variable10; }
set
{
m_variable10 = value;
if (!m_changed[10])
{
m_changed[10] = true;
m_count++;
}
}
}

В отличие от предыдущего, этот код уже не безопасен в условиях многопоточности: если во время проверки m_changed[10] еще было false, а уже после нее другой поток выполнил ту же операцию, то счетчик увеличится дважды.
Вариантов решения есть несколько:

  • использовать блокировку перед проверкой, или в паре с еще одной проверкой (double-check pattern)

  • не увеличивать счетчик в момент присваивания, а перебирать массив и считать true значения, когда это необходимо

  • использовать Interlocked методы



Вариант с блокировкой довольно прост и надежен (double-check pattern):

public int Variable10
{
get { return m_variable10; }
set
{
m_variable10 = value;
if (!m_changed[10])
lock (m_syncRoot)
if (!m_changed[10])
{
m_changed[10] = true;
m_count++;
}
}
}


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

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

public int Variable10
{
get { return m_variable10; }
set
{
m_variable10 = value;
lock (m_syncRoot)
m_changed[10] = true;
}
}
...
int count = 0;
lock (m_syncRoot)
foreach(bool bvalue in m_changed)
if (bvalue)
count++;

Это довольно дорого и не очень красиво.

Вариант с Interlocked методами будет наиболее быстрым и удачным решением:

public int Variable10
{
get { return m_variable10; }
set
{
m_variable10 = value;
if (Interlocked.CompareExchange(ref m_changed[10], true, false)
== false)
Interlocked.Increment(ref m_count);
}
}

В том случае, если нам нужна максимальная производительность, и мы не дрожим над каждым байтом памяти - это вполне нормально. А что делать, если паранойя заставляет браться за калькулятор и вычислять размер нашего массива в памяти? На каждый элемент массива будет выделен один байт, что составляет 7 бит избыточности на каждую запись - значение true/false может храниться в одном бите, а хранится в 8ми! 700 бит избыточности на каждую сотню элементов, это ведь целых 88 байт! :)
В этой ситуации на помощь придет класс System.Collections.BitArray. Синтаксис его использования такой же, как обычного массива bool[]. Можно без особых проблем заменить массив на BitArray и пользоваться первыми двумя вариантами, которые мы разбирали раньше.
Возникает вполне закономерный вопрос - что же мешает Interlocked варианту работать в паре с BitArray? Рассмотрим детальнее строку

Interlocked.CompareExchange(ref m_changed[10], true, false)

Первым параметром передается ссылка на элемент, с которым будет происходить операция. Если используется массив bool[], то ref m_changed[10] честно возьмет адрес указанного элемента. В случае с BitArray, оператор [] умеет только возвращать значение или записывать его, но, ни о какой ссылке не может быть и речи.
В этой ситуации правильно вернуться к первому варианту работы со счетчиком - с двойной проверкой и блокировкой, но этот блог создан не для любителей простых путей и тривиальных решений :)
Мы реализуем собственный BitArray с возможностью установки и чтения нужных нам битов с помощью Interlocked операций.

Я опущу тут описание стандартных частей и распишу самую важную часть нового класса:

public bool this[int index]
{
get { return ((m_array[index / 0x20] & (1 << (index % 0x20))) != 0); }
set
{
if (value)
m_array[index / 0x20] |= 1 << (index % 0x20);
else
m_array[index / 0x20] &= ~(1 << (index % 0x20));
}
}

Комментировать тут особо нечего: адрес байта в массиве равен index / 32, адрес бита в байте index % 32. С таким оператором мы получим по функциональности полный аналог BitArray. Следующая задача состоит в том, чтобы записывать и считывать биты с помощью Interlocked методов. .Net это не позволяет делать, но в предыдущей статье http://blog.runserver.net/2008/04/interlockedorandexchangeadd-net.html мы получили методы InterlockedOr и InterlockedAnd.
Я не буду вдаваться в подробности и сразу приведу код для собственного BitArray, который пытается установить или снять бит и возвращает старое значение выбраного бита:

public bool TrySet(int index, bool value)
{
if (value)
{
int iValue = 1 << (index % 0x20);
return
(InterlockedOr(ref m_array[index / 0x20], iValue) & iValue) != 0;
}
else
{
int iValue = ~(1 << (index % 0x20));
return
(InterlockedAnd(ref m_array[index / 0x20], iValue) & iValue) != 0;
}
}


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

public int Variable10
{
get { return m_variable10; }
set
{
m_variable10 = value;
if (m_changed.TrySet(10, true) == false)
Interlocked.Increment(ref m_count);
}
}


Таким образом мы получили оптимальный по производительности и использованию памяти способ отслеживания изменений переменных, имеющих некие индексы.
Вы можете спросить, зачем вообще это нужно, на что я приведу два простых примера:
1. У нас есть объект, считанный из БД с большим количеством полей и мы хотим для каждой записи в базу записывать в UPDATE не все эти поля, а только изменившиеся.
2. Необходимо передать по сети изменения некого большого объекта. В таком случае удобно послать в одном пакете количество изменившихся полей, битовую маску изменений (внутренность нашего BitArray) и сами изменения.

Второй пример не придуман, а используется в некоторых современных MMOG, в том числе и в World Of Warcraft и в эмуляторе RunWoW.

Дальше..

среда, 9 апреля 2008 г.

InterlockedOr/And/ExchangeAdd в .Net

Программистам C++ через WinAPI доступно много различных Interlocked функций на все случаи жизни. Выбор этих функций в .Net невелик: Increment, Decrement, Add, Exchange, CompareExchange и почти бесполезный Read. В большей части случаев этих методов вполне достаточно, да и более 80% программистов вообще не знают об атомарных функциях и не используют их. Не так давно я столкнулся с задачей, в которой нужны были атомарные бинарные операции InterlockedOr и InterlockedAnd. О самой этой задаче я расскажу в другой статье, а в этой рассмотрим, как можно получить в C# доступ к этим функциям, а также к экзотической функции InterlockedExchangeAdd


Логично предположить, что нужные нам функции скрываются в модуле kernel32.dll, как и другие Interlocked*. Как культурные люди мы не лезем в этот файл через Far/Total Commander (хотя и делаем так зачастую :)), а изучим его через Dependency Walker из комплекта Visual Studio (Common7\Tools\Bin\Depends.Exe).

Результат выглядит приблизительно так:



Возможно, на других системах вид будет немного другой, но на моей Windows 2008 RC 2 в списке наблюдаются только основные Interlocked функции. Забегу немного вперед и скажу, что в kernel32.dll для платформы x64 они вообще отсутствуют. Если же мы посмотрим в kernel32.lib от Microsoft Platform SDK (в этот раз обычным текстовым или бинарным редактором), то увидим, что InterlockedOr нет и там.

Ответ можно найти в файле WinBase.h:

#if !defined (InterlockedOr)

#define InterlockedOr InterlockedOr_Inline

LONG
FORCEINLINE
InterlockedOr_Inline (
__inout LONG volatile *Target,
__in LONG Set
)
{
LONG i;
LONG j;

j = *Target;
do {
i = j;
j = InterlockedCompareExchange(Target,
i | Set,
i);

} while (i != j);

return j;
}

#endif


Как видим, битовые атомарные операции реализованы в виде цикла с InterlockedCompareExchange и ничего не мешает нам сделать то же самое в C#. Вот пример реализации InterlockedOr с сохранением оригинального синтаксиса:


public static int InterlockedOr(ref int Target, int Set)
{
int i;
int j = Target;
do
{
i = j;
j = Interlocked.CompareExchange(ref Target, i | Set, i);
}
while (i != j);

return j;
}


Точно так же реализуется и InterlockedAnd с заменой i | Set на i & Set. Как именно работает этот код я тут объяснять не буду, отослав вопрошающих к первоисточникам, литературе, или к дзен-поиску (http://dzen.yandex.ru/).

А мы же вернемся к экзотической функции InterlockedExchangeAdd. Эта функция добавляет указанное значение к переменной и возвращает ее старое значение. Отличие от InterlockedAdd минимально, а если взглянуть на .Net Framework через призму декомпилятора, то мы увидим, что сам Interlocked.Add реализован именно через ExchangeAdd добавлением слагаемого:

public static int Add(ref int location1, int value)
{
return (ExchangeAdd(ref location1, value) + value);
}


Это утверждение верно и в обратную сторону: мы можем вычесть из результата Interlocked.Add слагаемое и получить такой же результат, как при вызове InterlockedExchangeAdd. Этот метод универсален и для повседневного использования я рекомендую именно его (например, при портировании кода с С++ с сохранением синтаксиса и имен используемых методов).
Тут бы и время закончить статью, но в ходе подготовки материалов для второй части статьи "Многопоточность и свойства" (первая часть: http://blog.runserver.net/2008/03/blog-post_28.html) я столкнулся с задачей, в которой нужно атомарной функцией добавить некое значение к переменной, передающейся по указателю int * (или же IntPtr), а не по ссылке ref int. Нормального метода преобразования указателя в ссылку в C# не существует, потому пришлось обратиться к P/Invoke. Сайт http://pinvoke.net предлагает нам следующее описание:

[DllImport("kernel32.dll")]
static extern int
InterlockedExchangeAdd(ref int Addend, int Value);


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

[DllImport("kernel32.dll")]
static extern int
InterlockedExchangeAdd(int* Addend, int Value);


Метод пригоден к использованию, все с ним хорошо, кроме одной "мелочи": в x64 режиме мы получаем System.EntryPointNotFoundException, сообщающий, что точка входа с таким именем не найдена в kernel32.dll. Ранее я уже упоминал, что Interlocked методы в x64 версии kernel32.dll попросту отсутствуют. Снова обратившись к WinBase.h мы видим, что в этот раз методы не прячутся под inline реализации, а переадресованы на intrinsic функции (http://msdn2.microsoft.com/en-us/library/191ca0sk.aspx). Где именно находится их реализация, я не нашел. Это ни .lib файлы от Platform SDK, ни системные библиотеки. Будем считать, что их реализация вшита в компилятор, или куда-либо еще. Единственный вариант, который я нашел, это создание собственной DLL, которая экспортирует функцию-враппер:

extern "C" __declspec(dllexport) LONG
interlockedExchangeAdd(LONG volatile * target, LONG value)
{
return InterlockedExchangeAdd(target, value);
}


Сложность еще заключается в том, что необходимо будет держать две разные библиотеки: для x86 и x64 режима. Я обошел это ограничение таким образом:

[DllImport("kernel32.dll",
EntryPoint = "InterlockedExchangeAdd")]
private static extern int
NativeInterlockedExchangeAdd(int * target, int value);

[DllImport("InterlockedWrapper_x64.dll",
EntryPoint = "interlockedExchangeAdd")]
private static extern int
CustomInterlockedExchangeAdd(int * target, int value);

public static int
InterlockedExchangeAdd(int* target, int value)
{
if (IntPtr.Size == 4) // x86
return NativeInterlockedExchangeAdd(target, value);
else
return CustomInterlockedExchangeAdd(target, value);
}


Таким образом, в x86 режиме используется kernel32.dll, а в x64 - наша собственная библиотека-враппер.

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

Дальше..

пятница, 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.
Дальше..