Ограничить ReadWriteLock

[Igors]

Добрый день

Есть список, каждый элемент имеет собственный ReadWriteLock. Все работает, но иногда наступает заметное замедление. Профайлер показывает что тормозит захват элемента по чтению - ну получается так что всем ниткам нужно какое-то небольшое число элементов, к которым все они щемятся по чтению - вот и получается интенсивная конкуренция на локе. Заранее неизвестно какие это элементы и будет ли такая ситуация вообще. Также в процессе работы те или иные элементы могут оказаться "часто востребованными". Напр на первой минуте это элемент 2, потом уже элемент 10 и.т.п. Расходы "по записи" малы, иногда запись не происходит никогда - просто с ней надо считаться.

Как это порешать ?   

Спасибо

[Авварон]

Версия кутехи какая?

[Igors]

Версия кутехи какая?

Никакая, используется tbb::spin_rw_mutex но даже он притормаживает. Вообще как реализован ReadWriteLock здесь без разницы

[V1KT0P]

Как это порешать ?   

Если чтение не меняет данные, то сделай чтоб мьютекс блокировался только на момент записи. Тогда тормоза будут когда все нитки начнут чтение в момент записи. А если есть возможность реализовать запись из одной нитки, размер данных позволяет без проблем делать копию и по условию задачи можно на время записи отдавать старые данные, то можно вообще без мьютексов обойтись. Чтение производить без мьютексов, данные засунуть в умный указатель. При записи делать копию и менять умный указатель. Если кто-то читал старые данные то после завершения старые данные самоуничтожатся, а последующие уже будут вытягивать новые данные.

[Авварон]

Igors
Вообще-то имеет, но, я так подозреваю спинлок реализован через атомики и быстрее его не сделать.

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

[Igors]

Избегаю цитирования чтобы покороче

Задача банальна: работа с большими картинками (или большим их числом) которые все в память не влазят. Поэтому они разбиты на фрагменты (tiles). Если затребованный пиксель находится в выгруженном фрагменте - он подгружается. При этом возможно др фрагмент вытесняется на диск (простой LRU).

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

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

[Авварон]

Я не про атомарность лока, а про то, реализован он через атомик инты (test&set) или нет. Ну да не суть.

Можно ли в треде кешировать элемент, к которому обращались в последний раз?

[Igors]

Я не про атомарность лока, а про то, реализован он через атомик инты (test&set) или нет. Ну да не суть.

Да, через CAS

Можно ли в треде кешировать элемент, к которому обращались в последний раз?

Можно, захватив его по чтению мы можем скопировать. Но нитка делает множество обращений к разным имеджам и/или разным частям одного имеджа. Поэтому сначала надо как-то собрать статистику, а где ее хранить и как обновлять?  Также перезапись 64к в местный буфер выглядит глуповато учитывая что один элемент может интенсивно использоваться всеми нитками. Также 1 элемент в локальном кэше - мало, а больше - растут расходы на проверку. Ведь время обращения к пикселю мало

[alexis031182]

Возможно ли перевести поток на работу с другим фрагментом изображения (или может быть пикселем), если превышен заранее определённый лимит обращений к этому фрагменту? То есть ввести счётчик заблокированных потоков у каждого пикселя. Если обращения потоков идут к рядом стоящим пикселям, то, возможно, счётчики блокировок можно было бы вести для групп пикселей. Это по идее снизит накладные расходы. Как-то так...

[Igors]

Возможно ли перевести поток на работу с другим фрагментом изображения (или может быть пикселем), если превышен заранее определённый лимит обращений к этому фрагменту? То есть ввести счётчик заблокированных потоков у каждого пикселя. Если обращения потоков идут к рядом стоящим пикселям, то, возможно, счётчики блокировок можно было бы вести для групп пикселей. Это по идее снизит накладные расходы. Как-то так...

Что-то не очень ясно "как" Практически любое приложение обращается к ф-циям типа GetPixel на самом низком уровне. С точки зрения вызывающего делать какие-то движения в зависимости от куда попало GetPixel нереально - это может быть только вшито в саму GetPixel и быть "opaque" для вызывающего.

Ладно, допустим (пока) как-то резидентные элементы назначены. Тогда смотрится совсем неплохо. Псевдокод

Код

C++ (Qt)
if (!element->mResidentFlag)   // если элемент нерезидентный (выгружаемый)
 element->AcquireRead();      // захватываем по чтению
 
AtomicInc(element->mNumAccess);    // увеличиваем число обращений к элементу
AtomicInc(theTotalAccess);   // увеличиваем общее обращений ко всем элементам
 

Теперь надо как-то лихо ставить/убирать mResidentFlag в зависимости от счетчиков

[alexis031182]

Что-то не очень ясно "как" Практически любое приложение обращается к ф-циям типа GetPixel на самом низком уровне. С точки зрения вызывающего делать какие-то движения в зависимости от куда попало GetPixel нереально - это может быть только вшито в саму GetPixel и быть "opaque" для вызывающего.

То есть на уровне вызывающего потока координаты пиксела не известны?

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

Объясните, пожалуйста, а для чего задумана "резидентность" элементов? Для чего часть элементов делать невыгружаемыми?

[Igors]

То есть на уровне вызывающего потока координаты пиксела не известны?

Конечно известны, но использовать их для чего-либо (кроме получения цвета/значения пикселя) мягко говоря "неудобно"

Объясните, пожалуйста, а для чего задумана "резидентность" элементов? Для чего часть элементов делать невыгружаемыми?

Чтобы избежать потерь на локе (см первый пост темы)

[alexis031182]

Понял... значит задача, получается, сводится к тому, как снять флаг "частой востребованности" с элемента, верно? Если установить его с помощью счётчика обращений не проблема, то убрать...

А в конце работы с данными пиксела не создаётся никакого события, чтобы его можно было прикрутить к декрементации счётчика обращений?

[Igors]

Понял... значит задача, получается, сводится к тому, как снять флаг "частой востребованности" с элемента, верно? Если установить его с помощью счётчика обращений не проблема, то убрать...

Верно, но пока я не знаю даже как установить

А в конце работы с данными пиксела не создаётся никакого события, чтобы его можно было прикрутить к декрементации счётчика обращений?

После того как пиксель использован его надо освободить (был захвачен по чтению). Счетчик обращений накапливает общее число обращений (а не текущее использование)

[alexis031182]

Понял... значит задача, получается, сводится к тому, как снять флаг "частой востребованности" с элемента, верно? Если установить его с помощью счётчика обращений не проблема, то убрать...

Верно, но пока я не знаю даже как установить

Почему нельзя хотя бы для начала просто привязаться к какой-нибудь константе? Например

Код:

if(element->mNumAccess > 99) element->setResidentFlag(true);

После того как пиксель использован его надо освободить (был захвачен по чтению). Счетчик обращений накапливает общее число обращений (а не текущее использование)

Желательно наверное всё-таки использование. Для чего инкрементацию счётчика нужно поместить до

Код:

element->AcquireRead();

Иначе от счётчика мало толку, получается