Представим себе ситуацию, что у нас есть несколько сотен переменных, каким-то образом помеченных номерами. Также представим, что нам надо знать, какие из объектов изменялись, а какие нет.
Самый простой способ - держать массив булевых значений и устанавливать 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.
0 коммент.:
Отправить комментарий