Потокобезопасный кэш

[Igors]

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

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

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

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

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

[brankovic]

При (хорошей) толкотне на мутексе 4 ядра даже медленнее чем 1.

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

Знатоки ответили мне в том плане что мутекс - это медленно, и что я пытаюсь делать то что не следует 

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

Позже я перешел на OpenMP, который имеет параметр типа "время прокрутки нитки до ее усыпления". По умолчанию он 300 ms (0.3 сек). Это говорит о многом.

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

Я не спорю, разделить кэши - идея интересная.

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

[Igors]

Давайте о главном

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

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

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

[Waryable]

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

[Waryable]

Счетчик ссылок для этих данных упадет до 1, и когда первый поток их обработает, память освободится.

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

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

[Igors]

Хм. Навскидку, без поиска грабель: почему бы не держать контрольный байт-флаг для каждого сегмента в самом сегменте. Сегмент не нужен - сбрасываем флаг. Нужен - взводим. Чтение/запись флага и сегмента осуществлять за одну операцию. Флаг просто пришпиндюлить в конец/начало сегмента.

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

[Waryable]

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

[Igors]

Непонятно. Цивильный термин про статью или про цитату? 

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

[Waryable]

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

[Igors]

- менеджер кеша робит в отдельном потоке;
- потоки-обработчики обращаются к менеджеру с запросом на сегмент;

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

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

[brankovic]

За каждым пикселем лезем в кэш.

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

[Igors]

За каждым пикселем лезем в кэш.

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

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

[Igors]

Хотел было сачкануть. Время использования данных кэша у меня (как правило) ничтожно мало. Ну думаю, поставлю атомарный лок (типа 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 (холостой ход)

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

[brankovic]

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

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

[Igors]

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

Да