Russian Qt Forum

Добрый день

Ну если просто "потокобезопасно" (звучит ужасно) - то достаточно просто поставить лок на все обращения к кэшу. Но все-таки: как сделать по уму? 

Спасибо

Зависит, наверное, от кол-ва пишущих/читающих из кеша потоков. ИМХО, сделать что-то универсальное без мьютексов врядли получится, нужно исходить из конкретного случая.
 Да и что под кешем имеешь ввиду?

Да что имею - то и введу. Значение взято из кэша и пользуется - в этот момент др. нитка вытесняет его из кэша. Что бум делать?

Как вариант - можно создать кэш нескольких уровней, каждый их которых будет содержать специфичную информацию. Таким образом, разбив по определенному признаку всю информацию, которую предполагается держать в кэше на несколько независимых частей и разместив эти части в уровнях кеша - получаем уменьшение нагрузки на кеш, и меньшую вероятность "гонки" потоков. В таком варианте нужно предусмотреть независимый метод доступа к каждому уровню кэша.

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

Hmmm... too much fantasy  :)

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

Уважаю корректный подход, давайте. Для простоты положим что имеем очень большие данные (напр  изображение, которое целиком в память не влазит). Хорошо, разбили его на части (страницы), записали на диск. Обращаемся к пикселю: находим фрагмент (страницу) в которой он сидит. Если эта страница сейчас не загружена - загружаем ее.  При этом если число страниц в памяти превышает заданное - сбрасываем наименее используемую страницу на диск (освобождаем память).

Все хорошо но как делать это с 2 и более нитками?

QSharedPointer<const ImagePart>. Сам QSharedPointer потокобезопасен (но не указываемые данные!). Когда одна нитка берет данные из кэша, то эти данные можно спокойно удалять из кэша в другой нитке. Т.о. всегда можно поддержать размер кэша не больше заданного значения, в то же время используемые данные, уже не находящиеся в кэше, автоматически уничтожатся QSharedPointer'ом как только в них не станет необходимости. Сами QSharedPointer<const ImagePart>'ы будут организованы в какой либо контейнер, доступ к которому, как говорилось выше, должен быть синхронизирован.

Если нескольким потокам нужно иметь доступ к кэшу изображения, но к разным его частям (страницам в данном случае), то можно сделать так:

Написать класс-менеджер кэша, который  будет заниматься загрузкой/выгрузкой страниц а также подсчетом их рейтинга среди потоков. Данный класс при загрузке изображения разбивает его на страницы, и сохраняет адрес каждой из них в контейнере вида:

C++ (Qt)
 QHash<Paper*,bool>

(или эквивалентном ). bool в данном случае определяет свободна данная страница, или занята. По запросу потоков менеджер будет выдавать им адреса страниц в памяти (если конкретная страница не занята другим потоком).

Выгоды данного подхода: вся работа с кэшем осуществляется в одном потоке, соответственно - ни одного мъютекса, а значит - меньше тормозов. Во вторых все потоки, которые работают с изображением работают с разными его частями, не мешая друг другу и без необходимости синхронизации работ.

Если я чего-то не понимаю - поясните, но я так вижу что кэш сам/тоже "владеет" данными. Предположим одна нитка обратилась за данными - попользовалась, освободила. Др. обращений к той же странице (покв) нет. Так что, удалить данные? Что это за кзш если он "ничего не держит"?

В реальной задаче невозможно предсказать к каким страницам будет обращение и сколько раз. Напр. вполне возможно что огромное изображение грузится но реально из него используется лишь несколько пикселей (для этого и городится огород со страницами)

А зачем это предсказывать? Потоку нужна страница - он ее запросил, сделал все, что нужно, вернул управление в кэш. Теперь кэш может раздавать ее другим потокам, или опять этому, это уже дело кэша, что с ней делать дальше.

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

Разумеется, кэш владеет данными.
Вы же указали
QSharedPointer все сделает в лучшем виде :).

Ладно, давайте я попробую набросать с QSharedPointer а Вы меня где надо поправите

C++ (Qt)
typedef QSharedPointer <unsigned char *>  TSharedPtr;
typedef QWeakPointer <unsigned char *>  TWeakPtr;
 
// заголовок страницы - всегда в памяти
struct PageHeader {
 TSharedPtr  mData;  // данные - могут быть загружены или нет
 long long mFilePos;   // смещение в файле страниц
 
 unsigned char * LoadPage( void );  // грузит страницу с диска
 TWeakPtr GetData( void );             // возвращает (слабый) указатель на данные
};
 
TWeakPtr PageHeader::GetData( void )
{
 if (mData.isNull())    // страница не загружена?
  mData = TSharedPtr(LoadPage());  // загружаем ее, счетчик = 1
 return mData.toWeakRef();            // теперь счетчик = 2, когда слабый указатель удалится, -1
}
 

Так правильно?  :)

Не совсем. Для определенности - макс. размер кэша = 2, кол-во страниц в файле > 2 (т.е. больше размера кэша - общий случай).


Данный код далек от оптимальности по многим аспектам, но основную идею иллюстрирует.

Итак, пусть pageData() вызван одновременно из 3-х потоков для разных страниц. В последнем (третьем) вызове из кэша будут удалены самые первые данные, т.е. данные, которые в настоящий момент активно юзает первый поток. Счетчик ссылок для этих данных упадет до 1, и когда первый поток их обработает, память освободится.

Так-то оно так, но при этом в памяти могут быть 2 и более копии одной страницы, используемые разными нитками. Поэтому будет работать корректно для "только чтение".

Кроме того, досадно что при любом обращении к кэшу нитки "сталкиваются лбами" на входном мутексе, и при интенсивном обращении к кэшу это ощутимо.

:) Точно, но давайте другим поясним почему: код ниже не "потокобезопасен" и рухнет на 2 и более нитках

А вы разделите кэш на 8 частей, к каждой свой мьютекс:

struct cache_part
{
   cache c;
   mutex m;
} parts [8];

а при обращении берите % 8, и сталкиваться будут в 8 раз реже.

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

Понимаю что задача сложная и "идеального" решения, может быть, и не существует. Мне не нравится что "сразу захватили мутекс" (хотя Qt так всегда делает). Ведь частота попаданий в кэш, как правило, 80% и больше. Часто даже 100% (ну хватило памяти). Вот как бы оптимизировать "просто чтение", напр

- обращаемся к странице, атомарно увеличили ее счетчик
- если счетчик > 0, просто пользуем страницу, закончили - уменьшили счетчик
- а вот иначе (счетчик < 0) - тогда уже берем локи, это случай редкий, можно и потерпеть   

может в данной задаче лучше применить файл, проецируемый в память?

Конкретно файл не пробовал, а вот выделять больше памяти чем есть физически - проверялось не раз. Результаты: оба ОС на которых я работаю  (OSX и WinXP64) хотя и не ложатся, но проигрывают скромной "ручной" подкачке с разгромным счетом - если "только" в 5 раз медленнее - то еще и хорошо  :)

Ну и пока есть 32-bit пользователи - это решение не общее.

не изменится никак (или не понимаю, что вы называете ёмкостью)


Так ведь и в hash_map все хэши могут совпасть, но люди же пользуются. Там вопрос в аккуратном выборе хэша, здесь -- в равномерном распределении по 8-и кэшам.


конечно, а в хэш мэпе надо хэш вычислять для каждого элемента, при каждом обращении.


если успели отработать до следующего клиента, то ничего страшного. Хотя зависит от системы, если mutex::lock выходит в режим ядра, то это дороговато.


непонятно.. Правильно я догадываюсь, что вы хотите такой shared_ptr, который бы не падал в PageHeader::GetData?

Но я так понял загружать весь файл не нужно? Ведь при маппинге можно указать нужный кусок памяти.

Вариант "просто дать больше памяти" выглядит равнозначным. Все то же самое, просто "кэш достаточно велик чтобы вместить все" - никогда не происходит вытеснения. Результаты печально медленны  :)

Давайте я сначала отвечу на первое
Емкость кзша - это число страниц которые могут быть в памяти. Если емкость превышена, наименее используемая страница должна быть выгружена чтобы освободить место. Если хотим иметь напр 8 кэшей, простейшее решение поделить емкость на 8. Можем конечно не делить, но тогда нам придется отслеживать чтобы общее число загруженных страниц не превысило заданное - и это надо защищать глобальной блокировкой. Кроме того, каждый кэш может вытеснять только "свои" страницы. И что делать если у кэша НЕТ загруженных станиц, но их общее число превысило предел (др кэши загрузили) ? Кого вытеснять?  :)  А даже если и есть кого, заметим: это будет страница наименее пользуемая "в данном кэше", значит число подкачек растет.

В общем "чем красивше выглядит решение - тем сложнее его реализовать"  :)

Если все заголовки страниц держать в памяти - то почему бы просто не вписать в каждый заголовок номер кэша? Так что, может быть, насчет переделок структур данных я был неправ  :)

Я хочу чтобы наиболее популярная операция - чтение уже загруженной страницы - проходила "сквозняком" на атомарных операциях со счетчиком этой страницы.

"дороговато" - то очень мягко сказано. При интенсивной конкуренции мутекс убивает скорость в ноль.

QReadLocker не оно? или просто использовать несколько QSharedMemory

Да, это я проглядел. Но проблема непринципиальная. Можно обойтись и без 9-го мьютекса, только атомарными операциями. Можно с 9-м мьютексом. Можно и на восемь ёмкость разделить в конце концов.

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


"Чтение" у вас, как я понял, это
1 поиск в кэше
2 копирование shared_ptr <Page>
3 сохранение отметки о недавнем использовании этой страницы

то есть даже в чтении присутствует пара записей, а ведь есть же ещё ветка, когда страница не найдётся. Слишком сложные операции, простого lockfree решения тут нет.


Я не о конкуренции, я о замедлении, которое даёт вызов lock для незалоченного мьютекса. В виндовой реализации QMutex, нагорожен целый огород, только чтобы в режим ядра не попасть. В результате на пару lock/unlock приходится 1 системный вызов если всё хорошо, и 2, если мьютекс таки был занят.

К чему это всё. Если у вас программа работает со страницами, то полезная работа обычно занимает на порядки больше времени, чем поиск в кэше. Поэтому реального толкания не возникает: тред захватывает мьютекс, мухой ищет в кэше, отдаёт мьютекс и идёт делать 99% работы. Очень редко, условно в 1% случаев он засыпает посреди чтения мьютекса, или треды случайно сталкиваются. Но эту заминку надо умножать 1%, поскольку в 99% случаев её просто нет.

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

В общем я за решение от Akon, с поправкой на прошлый абзац.

Вообще-то именно трений среди читающих Igors и хотел избежать. Совсем в чистом виде использовать нельзя -- каждый читающий хочет оставить метку о недавнем использовании страницы, а это запись. Но можно ввести доп. мьютекс. Тут надо пробовать и замерять время, теоретически может быть выигрыш.


или сразу особую уличную магию!

зачем мютекс для такой мелочи? QAtomicInt достатотчно

Так и хочу - но тогда не получается использовать готовые классы (QReadWriteLock и др). Не беда, все равно от них здесь толку мало

Я писал тесты (они даже где-то на этом форуме). Не знаю как на Вындоуз. но на моем основном OC (OSX) - совсем мрачно. При (хорошей) толкотне на мутексе 4 ядра даже медленнее чем 1. Знатоки ответили мне в том плане что мутекс - это медленно, и что я пытаюсь делать то что не следует  :)  Позже я перешел на OpenMP, который имеет параметр типа "время прокрутки нитки до ее усыпления". По умолчанию он 300 ms (0.3 сек). Это говорит о многом.

Я не спорю, разделить кэши - идея интересная. Но чего мы так уж сразу (как бы) смирились с тем что "толкотня на мутексах" неизбежна? По смыслу большинство операций завязаны только на конкретную страницу, и нет необходимости блокировать весь кэш.

не очень верится. То есть в теоретическом пределе да, но на реальной задаче вряд ли.


У знатоков просто был тяжёлый день..


мне не говорит. Разве openMP имеет какое-то влияние на ОС? Разве нельзя написать вручную тоже самое, что и с помощью openMP? Я так думал, что openMP это навроде библиотеки, только в форме расширения языка.


разонравилась. Лучше просто вынести подгрузку страницы из-под лока.

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

У меня есть кое-какие мысли - но мешает новогодняя пьянка  :) Начну делать - отпишусь

Хм. Навскидку, без поиска грабель: почему бы не держать контрольный байт-флаг для каждого сегмента в самом сегменте. Сегмент не нужен - сбрасываем флаг. Нужен - взводим. Чтение/запись флага и сегмента осуществлять за одну операцию. Флаг просто пришпиндюлить в конец/начало сегмента.
Хотя, вот дописал и, думается мне, есть в этом способе маста где собака может порыться.
Попробуйте: http://win-api.narod.ru/a2460.htm.
Сам сильно не вчитывался в эту статью. Погуглил по старой памяти. Вроде то.

Хм. Можно чуть-чуть оффтопа? Про какие ссылки идет речь?

------------------------
Нашел сам.  ??? Извиняюсь за невнимательность.

В цивильных терминах это значит: каждая страница имеет свой (Q)ReadWriteLock  :)
Это делать придется, но на этом приключения не кончаются. Ну захватили страницу по чтению, а она еще не загружена, дальше что?

Непонятно. Цивильный термин про статью или про цитату?  :)
Если про цитату, то это мой велосипед марки QSharedPointer... С восьмеркой на переднем колесе - колбасит.   :D
А если про статью, то я не очень понял когда такая ситуация может случиться. Если только вы не хотите сделать кеш настолько интеллигентным, что он будет знать что вам потребуется, скажем, на секунду вперед? Если так, то надо понимать характер работы потоков с сегментами и на основе этих знаний делать модель прогнозов. Я почему-то думаю, что это не слишком сложно.

Про то что Вы пишете  :) Если напр страница читается/используется 2-мя нитками, то счетчик использования этой страницы должен быть = 2, и нельзя захватить ее по записи пока счетчик не станет = 0. Ну вот и пришли к ReadWriteLock  :)

Ну а если так:
- менеджер кеша робит в отдельном потоке;
- потоки-обработчики обращаются к менеджеру с запросом на сегмент;
- менеджер проверяет флаг-счетчик лока:
        - сегмент уже загружен: наращивает счетчик обращений к сегменту, возвращает флаг "ОК", и указатель на сегмент;
        - сегмент не загружен: загружает счетчик, возвращает флаг "ОК", и указатель на сегмент;
- поток-обработчик после обработки сегмента обращается к менеджеру с функцией, уменьшающей соответствующий счетчик;
- если счетчик сегмента достиг значение = 0, то тут либо ничего не делаем, либо опять же строим прогноз погоды;
- счетчики лежат в массиве(отдельно от сегментов);
- лочить надо только массив счетчиков. Сделать их атомарными и там, если я чего-то не упустил, получатся уже "честные" гонки.

Обращаться из др. нитки к кэшу - удовольствие дорогое. Нужно положить запрос в очередь, разбудить менеджера, дождаться от него ответа - какая уж тут скорость?

Практический пример использования кэша: ф-ция складывает/осредняет некоторое число пикселей N которое по умолчанию 25 (но может быть и больше). За каждым пикселем лезем в кэш. Кратность вызова такой ф-ции - миллионы.

Я вижу функциональность кэша всё расширяется, этак вы скоро отдельные биты начнёте кэшировать..

С интересом послушаю др. решения  :)

Хотел было сачкануть. Время использования данных кэша у меня (как правило) ничтожно мало. Ну думаю, поставлю атомарный лок (типа QAtomicInt::testAndSetAcquire) на все  обращения к кэшу - и все дела. То есть каждая нитка захватила кэш, попользовалась, освободила. На 4 ядрах (моя машина) это проходит. Но на 8 становится мрачно :-(

Страниц: 5, 135
Число обращений к кэшу на 4 ядрах: 94, 945, 787

4 cores          7min 38 secs
8 cores          8min 6 secs
8 cores          4min 9 secs (холостой ход)

Пробовал различные реализации локов, это конечно как-то меняет статистику но принципиально ничего нового не вносит.  Мда... придется делать

Это что, спинлок?

Да

А для мьютекса замер?

Если имеется ввиду реализация на pthread_cond_wait (как в Qt) - то незачем терять время на ее проверку

Имеется ввиду QMutex, который контролирует доступ к кэшу. И времени для замены спинлока на мьютекс нужно немного. Но если незачем то тогда ладно.

Вот уж и не знаю как быть: вижу что это никому не интересно и не хочу навязываться. Но я обещал отписаться когда сделаю, поэтому вот псевдокод

C++ (Qt)
struct CPageHead {
 CPageData * AcquireRead( void );
 void * ReleaseRead( void )  { mMutex.unlock(); }
 
 CPageData * mData;
 atomic <UInt32> mAccessCount;
 spin_rw_mutex mMutex;
 
 static atomic <UInt32> mAccessTotal;
 static spin_mutex mLoadMutex;
};
 
CPageData * CPageHead::AcquireRead( void )
{
 mMutex.lock_read();    
 
// здесь mData может быть загружена или нет, но не может быть выгружена
 
  if (!mData) {                                                     // не загружена
   spin_mutex::scoped_lock theLock(mLoadMutex);    // берем лок
   if (!mData) {                         // др. нитка успела подгрузить?
//    UInt32_64 * dummy = (UInt32_64 *) &mMutex;  // неверно! (предыдущий вариант)
       atomic <UInt32_64> * dummy = (atomic <UInt32_64> *) &mMutex;  
       *dummy += WRITE_PENDING;             // блокируем доступ по чтению во время LoadPage           
       LoadPage();                      // грузим апельсины бочками
       *dummy -= WRITE_PENDING;     // mData готово, можно читать
    }
  }
 
// обновляем статистику
  mAccessCount = ++mAccessTotal;
  return mData;
}
 

LoadPage сводится к нахождению кандидата на вытеснение, захвату его "по записи", сбросу его на диск и перелинковке списка. Ищу линейным поиском по списку, беру первый элемент для которого выполняется условие mAccessCount < mAccessTotal / 4. Прикидывал более оптимальный поиск но ничего путного не придумал.

Отнюдь, как время будет почитаю с интересом. Хорошо, что отписались -- обещания надо выполнять ;)

Отнють. Очень интересно. Но мне для нормального прочтения этого псевдокода надо подтянуть свои знания. ??? Как смогу, так и оценю.  :)

Igors, нельзя ли кратко пояснить магию WRITE_PENDING? Почему не mMutes.write_lock ()?

Для LoadPage нам нужно захватить страницу "по записи" (т.е. exclusive) но mMutes.write_lock здесь ведет к deadlock - ведь мы уже захватили ее "по чтению" (shared)

Кажется понял: если бы у spin_rw_mutex была операция upgrade_read_lock_to_write_lock (), то её вызов потенциально может привести к дэдлоку (поправьте, если неверно).

Под *dumy |= WRITE_PENDING подразумевается атомарная операция, правильно я понимаю? Потому что иначе не будет работать.

Кода про вытеснение страницы вообще нет, а он тут важен. Собственно от его реализации зависит, насколько верен этот код.

Как осуществляется поиск "самой старой страницы" при вытеснении, перебором по всем страницам?

В принципе верно. Как только LoadPage поставит ненулевое mData, др. нитка может ее "подхватить" (и рухнуть).

Необязательно. Пока LoadPage страницу не загрузила - мы защищены

Там нiчого особливого. Поиск линейным проходом по списку, выбирается первая страница у которой

mAccessCount <= mAccessTotal / 4;

Она захватывается "по записи". Загружаемая перемещается в голову списка (как обычно в LRU). Во время выгрузки/подгрузки чтение др. страниц не блокируется (чем я весьма доволен).

Я конечно понимаю, что это псевдокод, но всё-таки тут неясный момент. spinlock_mutex это обёртка вокруг atomic_int? В таком случае операция |= попортит всю атомарность. Можно в общих чертах схему работы spinlock_mutex?

Это read/write locker . Член данных один (4/8 байт в 32/64). Флаги

бит 0 - WRITE (locker захвачен exclusive - "по записи")
бит 1 - PENDING (блокирует новый захват по чтению, хотя еще могут быть читающие)
биты 2..32(64) - число читающих

Locker "спиновый", т.е. усыпления нитки не происходит а крутится холостой ход (со многими финтами). Операция |= в данном случае может и не быть атомарной, т.к. никто больше не может захватывать именно эту страницу "по записи", необходимо только блокировать захваты по чтению.

Попробую набросать сценарий, вы меня поправьте если что. Пусть имеется 2 треда, А и Б, и пусть события происходят в таком порядке:

1. тред А захватил mMutex на чтение, mMutex == {false, false, 1}
2. тред А проверил, что mData == NULL, выполнил mLoadMutex.lock (), ещё раз проверил mData (всё ещё NULL)
3. тред А собирается сделать mMutex.pending = true и для этого читает mMutex в регистр AR, теперь AR == {false, false, 1}
4. тред А засыпает
5. тред Б захватывает mMutex на чтение, теперь mMutex == {false, false, 2}
6. тред Б засыпает
7. тред А просыпается и делает AR.pending = true, теперь AR == {false, true, 1}, mMutex == {false, false, 2}
8. тред А записывает AR в mMutex, теперь mMutex == {false, true, 1}
9. тред А загружает страницу и снимает write_pending, mMutex == {false, false, 1}
10. тред А отпускает mLoadMutex, и выходит из aquire_read, делает свою полезную работу и вызывает release_read, теперь mMutex == {false, false, 0}

Состояние после пункта 10 таково: мьютекс mMutex не захвачен ни на чтение ни на запись, но Б считает, что захватил мьютекс. Когда Б проснётся, он станет работать со страницей не имея рид-лока. Насколько я понимаю, это вовсе не то, чего хотелось. Правильно я рассуждаю?

Нечего поправлять, Вы правы, прямая ошибка и, мне кажется это можно показать даже проще

C++ (Qt)
*dummy |= WRITE_PENDING;
 

Это НЕ атомарно и выполняется так

- содержимое *dummy принимается на регистр
- выполняется OR на регистре
- содержимое регистра записывается по адресу dummy

Заметим что объявление volatile (так кстати и было) в данном случае ничего не меняет. Ошибка в том что пока выполняется OR на регистре, ОС может забрать у нитки управление на любое время, в течение которого др. нитка может обновить dummy. Когда  управление вернулось и регистр пишется в память, эти изменения будут утеряны. В общем, классические грабли.

Исправил, спасибо

Собственно такие ошибки сразу видно, нельзя мешать атомарный доступ с обычным. Но это так, придирки, гораздо интереснее вот что: зачем вообще нужно WRITE_PENDING? Почему нельзя так:

C++ (Qt)
Data *acquire ()
{
   m_mutex.lock_read ();
 
   if (!m_data)
   {
      scoped_lock sl (m_load_mutex);
      if (!m_data)
      {
         Data *tmp = LoadPage (); //first load
         m_data = tmp;           //tmp is ready, assign m_data to it
      }
   }
 
   return m_data;
}
 

А разве это присваивание атомарно?  :) (возможно и да, но это не обещается). А вообще конечно можно, но получается очень неудобно: текста в LoadPage довольно много и все время нужно помнить что mData надо держать = 0. 

Конечно запись слова атомарна. Но даже если нет, проще сделать атомарное m_data += tmp, чем городить огород с WRITE_PENDING. Хотя бы потому, что здесь одна операция вместо 2х. Атомарные операции довольно дорогая штука. Итого, WRITE_PENDING не нужен.

Дорогие по сравнению с записью/чтением на диск?  :) Ладно - непринципиально. А вот поиск кандидата на вытеснение - не мешало бы улучшить. А то линейный проход, пусть и быстрый, но по тысячам страниц - никак не гуд  Я даже др. тему завел http://www.prog.org.ru/index.php?topic=16335.msg108525#msg108525 (http://www.prog.org.ru/index.php?topic=16335.msg108525#msg108525)

Но энтузиазма не наблюдается (как обычно когда этого нет в Асыстенте)