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

Иногда приходится задумываться о том, что выделять новые объекты каждый раз слишком дорого. Особенно это относится к байтовым и пр. буферам. В таком случае, целесообразно организовать некий пул и брать оттуда объекты, возвращая их после использования.
Госпожа 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. Для обеспечения нужного времени жизни объектов в пуле есть смысл использовать более сложные методы, чем одна ссылочная колекция. Например, хранить две коллекции и в методе очистки основную заменять вспомогательной, а старую вспомогательную удалять. Таким образом любой объект гарантированно будет иметь сильную ссылку на время не меньше интервала очистки.


Дальше..

Собственный 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.

Дальше..