Russian Qt Forum
Ноябрь 22, 2024, 19:16 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Russian Qt Forum > Forum > Qt > Многопоточное программирование, процессы > Потокобезопасный кэш
Страниц: 1 2 [3] 4 5   Вниз
« предыдущая тема следующая тема »
  Печать  
Автор Тема: Потокобезопасный кэш  (Прочитано 30630 раз)
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #30 : Декабрь 30, 2010, 19:01 »
Цитата: brankovic от Декабрь 30, 2010,  16:31
Цитата: Igors от Декабрь 29, 2010,  21:14
Если емкость превышена, наименее используемая страница должна быть выгружена чтобы освободить место. Если хотим иметь напр 8 кэшей, простейшее решение поделить емкость на 8. Можем конечно не делить, но тогда нам придется отслеживать чтобы общее число загруженных страниц не превысило заданное - и это надо защищать глобальной блокировкой.

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

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

Я не спорю, разделить кэши - идея интересная. Но чего мы так уж сразу (как бы) смирились с тем что "толкотня на мутексах" неизбежна? По смыслу большинство операций завязаны только на конкретную страницу, и нет необходимости блокировать весь кэш.
Записан
brankovic
Гость
« Ответ #31 : Декабрь 30, 2010, 20:01 »
Цитата: Igors от Декабрь 30, 2010,  19:01
При (хорошей) толкотне на мутексе 4 ядра даже медленнее чем 1.

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

Цитата: Igors от Декабрь 30, 2010,  19:01
Знатоки ответили мне в том плане что мутекс - это медленно, и что я пытаюсь делать то что не следует  Улыбающийся

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

Цитата: Igors от Декабрь 30, 2010,  19:01
Позже я перешел на OpenMP, который имеет параметр типа "время прокрутки нитки до ее усыпления". По умолчанию он 300 ms (0.3 сек). Это говорит о многом.

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

Цитата: Igors от Декабрь 30, 2010,  19:01
Я не спорю, разделить кэши - идея интересная.

разонравилась. Лучше просто вынести подгрузку страницы из-под лока.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #32 : Декабрь 30, 2010, 20:45 »
Давайте о главном
Цитата: brankovic от Декабрь 30, 2010,  20:01
разонравилась. Лучше просто вынести подгрузку страницы из-под лока.
Не могу с Вами согласиться. При подгрузке страницы не грех взять и глобальный лок (да, пусть все кто обращается к кэшу ждут). А вот когда запрос на чтение загруженной страницы - здесь надо сработать точно.

У меня есть кое-какие мысли - но мешает новогодняя пьянка  Улыбающийся Начну делать - отпишусь
Записан
Waryable
Гость
« Ответ #33 : Январь 04, 2011, 10:33 »
Хм. Навскидку, без поиска грабель: почему бы не держать контрольный байт-флаг для каждого сегмента в самом сегменте. Сегмент не нужен - сбрасываем флаг. Нужен - взводим. Чтение/запись флага и сегмента осуществлять за одну операцию. Флаг просто пришпиндюлить в конец/начало сегмента.
Хотя, вот дописал и, думается мне, есть в этом способе маста где собака может порыться.
Попробуйте: http://win-api.narod.ru/a2460.htm.
Сам сильно не вчитывался в эту статью. Погуглил по старой памяти. Вроде то.
Записан
Waryable
Гость
« Ответ #34 : Январь 04, 2011, 11:06 »
Цитата: Akon от Декабрь 28, 2010,  21:18
Счетчик ссылок для этих данных упадет до 1, и когда первый поток их обработает, память освободится.
Хм. Можно чуть-чуть оффтопа? Про какие ссылки идет речь?

------------------------
Нашел сам.  Непонимающий Извиняюсь за невнимательность.
« Последнее редактирование: Январь 04, 2011, 11:10 от Waryable » Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #35 : Январь 05, 2011, 12:25 »
Цитата: Waryable от Январь 04, 2011,  10:33
Хм. Навскидку, без поиска грабель: почему бы не держать контрольный байт-флаг для каждого сегмента в самом сегменте. Сегмент не нужен - сбрасываем флаг. Нужен - взводим. Чтение/запись флага и сегмента осуществлять за одну операцию. Флаг просто пришпиндюлить в конец/начало сегмента.
В цивильных терминах это значит: каждая страница имеет свой (Q)ReadWriteLock  Улыбающийся
Это делать придется, но на этом приключения не кончаются. Ну захватили страницу по чтению, а она еще не загружена, дальше что?
Записан
Waryable
Гость
« Ответ #36 : Январь 05, 2011, 15:44 »
Непонятно. Цивильный термин про статью или про цитату?  Улыбающийся
Если про цитату, то это мой велосипед марки QSharedPointer... С восьмеркой на переднем колесе - колбасит.   Веселый
А если про статью, то я не очень понял когда такая ситуация может случиться. Если только вы не хотите сделать кеш настолько интеллигентным, что он будет знать что вам потребуется, скажем, на секунду вперед? Если так, то надо понимать характер работы потоков с сегментами и на основе этих знаний делать модель прогнозов. Я почему-то думаю, что это не слишком сложно.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #37 : Январь 05, 2011, 16:18 »
Цитата: Waryable от Январь 05, 2011,  15:44
Непонятно. Цивильный термин про статью или про цитату?  Улыбающийся
Про то что Вы пишете  Улыбающийся Если напр страница читается/используется 2-мя нитками, то счетчик использования этой страницы должен быть = 2, и нельзя захватить ее по записи пока счетчик не станет = 0. Ну вот и пришли к ReadWriteLock  Улыбающийся
Записан
Waryable
Гость
« Ответ #38 : Январь 05, 2011, 18:28 »
Ну а если так:
- менеджер кеша робит в отдельном потоке;
- потоки-обработчики обращаются к менеджеру с запросом на сегмент;
- менеджер проверяет флаг-счетчик лока:
        - сегмент уже загружен: наращивает счетчик обращений к сегменту, возвращает флаг "ОК", и указатель на сегмент;
        - сегмент не загружен: загружает счетчик, возвращает флаг "ОК", и указатель на сегмент;
- поток-обработчик после обработки сегмента обращается к менеджеру с функцией, уменьшающей соответствующий счетчик;
- если счетчик сегмента достиг значение = 0, то тут либо ничего не делаем, либо опять же строим прогноз погоды;
- счетчики лежат в массиве(отдельно от сегментов);
- лочить надо только массив счетчиков. Сделать их атомарными и там, если я чего-то не упустил, получатся уже "честные" гонки.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #39 : Январь 06, 2011, 07:54 »
Цитата: Waryable от Январь 05, 2011,  18:28
- менеджер кеша робит в отдельном потоке;
- потоки-обработчики обращаются к менеджеру с запросом на сегмент;
Обращаться из др. нитки к кэшу - удовольствие дорогое. Нужно положить запрос в очередь, разбудить менеджера, дождаться от него ответа - какая уж тут скорость?

Практический пример использования кэша: ф-ция складывает/осредняет некоторое число пикселей N которое по умолчанию 25 (но может быть и больше). За каждым пикселем лезем в кэш. Кратность вызова такой ф-ции - миллионы.
Записан
brankovic
Гость
« Ответ #40 : Январь 06, 2011, 19:42 »
Цитата: Igors от Январь 06, 2011,  07:54
За каждым пикселем лезем в кэш.

Я вижу функциональность кэша всё расширяется, этак вы скоро отдельные биты начнёте кэшировать..
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #41 : Январь 07, 2011, 09:30 »
Цитата: brankovic от Январь 06, 2011,  19:42
Цитата: Igors от Январь 06, 2011,  07:54
За каждым пикселем лезем в кэш.

Я вижу функциональность кэша всё расширяется, этак вы скоро отдельные биты начнёте кэшировать..
С интересом послушаю др. решения  Улыбающийся
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #42 : Январь 11, 2011, 11:59 »
Хотел было сачкануть. Время использования данных кэша у меня (как правило) ничтожно мало. Ну думаю, поставлю атомарный лок (типа 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
Гость
« Ответ #43 : Январь 11, 2011, 12:57 »
Цитата: Igors от Январь 11, 2011,  11:59
4 cores          7min 38 secs
8 cores          8min 6 secs
8 cores          4min 9 secs (холостой ход)

Это что, спинлок?
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #44 : Январь 11, 2011, 13:02 »
Цитата: brankovic от Январь 11, 2011,  12:57
Это что, спинлок?
Да
Записан
Страниц: 1 2 [3] 4 5   Вверх
  Печать  
« предыдущая тема следующая тема »
 
Перейти в:  


Страница сгенерирована за 0.058 секунд. Запросов: 22.