Системное программирование / [Перевод] Беззамочные алгоритмы: ненастойчивый кэш

(Тот факт, что русского перевода понятию «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), то совершенно ни к чему им выстраиваться в очередь: ничего не мешает им одновременно воспользоваться кэшированным значением.

Посмотрим, как можно реализовать наш кэш беззамочно.

Рубрика: Habr