Беззамочные алгоритмы: ненастойчивый кэш

(Тот факт, что русского перевода понятию «lock-free» в литературе ещё не устоялось, — нисколько меня не убеждает, что такого перевода не должно быть.)

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

BOOL IsPrime(int n)
{
 static int nLast = 1;
 static BOOL fLastIsPrime = FALSE;

 // если значение параметра не изменилось с прошлого раза,
 // воспользуемся готовым результатом
 if (n == nLast) return fLastIsPrime;

 // вычислим и запомним новый результат
 nLast = n;
 fLastIsPrime = slow_IsPrime(n);
 return fLastIsPrime;
}

Само собой, этот код потоконебезопасен: если один поток находится внутри вызова slow_IsPrime(), то другой поток, вызвавший IsPrime(), застанет значения переменных nLast и fLastIsPrime несоответствующими одно другому.

Простое решение — заключить код в критическую секцию; но простота идёт в ущерб производительности: если, скажем, nLast = 5, fLastIsPrime = TRUE, и два потока одновременно вызывают IsPrime(5), то совершенно ни к чему им выстраиваться в очередь: ничего не мешает им одновременно воспользоваться кэшированным значением.

Посмотрим, как можно реализовать наш кэш беззамочно. Воспользуемся сразу двумя трюками из прошлого поста: обновлением номера версии при каждом изменении данных, и моделью «сделай, запиши,(отчайся)» для синхронизации записи в кэш.

#define IsLocked(l) ((l) & 1)

BOOL IsPrime(int n)
{
 static int nLast = 1;
 static BOOL fLastIsPrime = FALSE;
 static LONG lCounter = 0;

 // попытаемся взять значение из кэша
 LONG lCounterStart = InterlockedReadAcquire(&lCounter, -1);
 if (!IsLocked(lCounterStart) && n == nLast) {
  BOOL fResult = fLastIsPrime;
  // никто не трогал кэш за нашей спиной?
  if (InterlockedReadRelease(&lCounter, -1) == lCounterStart)
   return fResult;
 }

 // либо чтение из кэша не удалось, либо значение не подошло:
 // вычисляем обычным способом
 BOOL fIsPrime = slow_IsPrime(n);

 // попытаемся сохранить значение в кэше
 lCounterStart = lCounter;
 if (!IsLocked(lCounterStart) &&
     InterlockedCompareExchangeAcquire(&lCounter,
              lCounterStart+1, lCounterStart) == lCounterStart) {
  nLast = n;
  fLastIsPrime = fIsPrime;
  InterlockedCompareExchangeRelease(&lCounter,
              lCounterStart+2, lCounterStart+1);
 }
 return fIsPrime;
}

Младший бит в lCounter означает, что кэш «заблокирован» на время записи; остальные биты хранят номер версии. Такая организация позволяет объединить снятие блокировки и обновление номера версии в одну простую операцию.

Функция состоит из двух частей: чтение из кэша и запись в кэш. При чтении из кэша сначала мы читаем lCounter операцией Acquire, чтобы убедиться, что прочитанные значения nLast и fLastIsPrime были записаны прежде, чем номер версии. Если, судя по прочитанному номеру, кэш не заблокирован, то мы читаем из него последние значения параметра и результата. Если результат подходит, мы берём его; но прежде нужно убедиться, что номер версии не изменился за то время, пока мы читали из кэша. Если он изменился, то, возможно, прочитанные нами значения не соответствуют друг другу, так что «подходящий» результат на самом деле недостоверен.

В обоих случаях — если закэшированный результат не подошёл, или если прочитанные данные оказались недостоверными, — просто махнём рукой на оказавшийся бесполезным кэш, и выполним вычисления полностью.

При записи в кэш мы не только проверяем, что кэш не заблокирован, но одновременно с этим ещё и блокируем его сами, устанавливая младший бит. (Если окажется, что кэш был заблокирован, — тоже не страшно: никто не будет в обиде, если не станем записывать в него вычисленный результат. Цель ведь сэкономить время, а не любой ценой избежать повторного вычисления.) Заблокировав кэш, мы обновляем в нём данные, и затем одной операцией InterlockedCompareExchangeRelease снимаем блокировку и увеличиваем номер версии. Операция должна быть Release, чтобы изменения данных записались в память раньше снятия блокировки.

Мы пользуемся тем, что успех операций над кэшем необязателен: и при чтении, и при записи, если кэш окажется заблокирован, то, по идее, лучше отказаться от преимуществ кэширования — «К чёрту всё! Сделаю всё сам!» — чем выстраиваться в очередь за право доступа к кэшу. Ценой избыточных вычислений мы избегаем проблем навроде инверсии приоритетов (когда высокоприоритетный поток ожидает освобождения замка, занятого низкоприоритетным потоком).

Важно обратить внимание, что получившаяся система не вполне беззамочна: используя беззамочные алгоритмы, мы фактически реализовали эффективный замок. Если «застрянет» поток, заблокировавший кэш для записи, — все прочие потоки, хотя и продолжат выполняться, кэшем пользоваться уже не смогут.

Аналогичную систему можно реализовать и при помощи TryEnterCriticalSection:

BOOL IsPrime(int n)
{
 static int nLast = 1;
 static BOOL fLastIsPrime = FALSE;
 BOOL fHaveAnswer = FALSE;
 BOOL fIsPrime;

 // попытаемся взять значение из кэша
 if (TryEnterCriticalSection(&g_cs)) {
  if (n == nLast) {
   fHaveAnswer = TRUE;
   fIsPrime = fLastIsPrime;
  }
  LeaveCriticalSection(&g_cs);
 }
 if (fHaveAnswer) return fIsPrime;

 // либо критическая секция занята, либо значение не подошло:
 // вычисляем обычным способом
 fIsPrime = slow_IsPrime(n);

 // попытаемся сохранить значение в кэше
 if (TryEnterCriticalSection(&g_cs)) {
  nLast = n;
  fLastIsPrime = fIsPrime;
  LeaveCriticalSection(&g_cs);
 }
 return fIsPrime;
}

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

Начиная с Windows 7, мы можем также задействовать slim reader-writer locks:

BOOL IsPrime(int n)
{
 static int nLast = 1;
 static BOOL fLastIsPrime = FALSE;
 BOOL fHaveAnswer = FALSE;
 BOOL fIsPrime;

 // попытаемся взять значение из кэша
 if (TryAcquireSRWLockShared(&g_lock)) {
  if (n == nLast) {
   fHaveAnswer = TRUE;
   fIsPrime = fLastIsPrime;
  }
  ReleaseSRWLockShared(&g_lock);
 }
 if (fHaveAnswer) return fIsPrime;

 // либо кэш заблокирован для записи, либо значение не подошло:
 // вычисляем обычным способом
 fIsPrime = slow_IsPrime(n);

 // попытаемся сохранить значение в кэше
 if (TryAcquireSRWLockExclusive(&g_lock)) {
  nLast = n;
  fLastIsPrime = fIsPrime;
  LeaveSRWLockExclusive(&g_lock);
 }
 return fIsPrime;
}

Но и в этой реализации потоки, читающие из кэша, могут помешать записи в кэш; тогда как в нашей первой «беззамочной по духу» реализации только одновременные попытки записи приводят к конфликту. Если IsPrime() вызывается несколько раз с одним значением (например, 13), и затем много раз подряд с другим значением (например, 17) — то напор потоков, проверяющих, не закэширован ли результат для 17, просто не пропустит ни один поток действительно закэшировать результат для 17! Получается, если нагрузка на кэш очень высокая (а собственно, именно поэтому мы его идобавили!) — тогда реализация на основе slim reader-writer locks превращает кэш в почти бесполезный.