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