Russian Qt Forum

Добрый день

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

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

Спасибо

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

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

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

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

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

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

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

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

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

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

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

Да, через CAS

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Так от счетчика "текущего использования" толку еще меньше. Напр работают 4 нитки, имеем значения от 0 до 3 - и что с того?

А так все элементы быстро станут резидентами, ведь счетчики непрерывно растут. Кстати в int они не влазят, поэтому константа 99 вызывает "сардоническую улыбку"  :)

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

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

Нет? Я может быть неадекватно понимаю ситуацию? :)

Кол-во ниток использующих (сейчас) данный элемент можно получить из самого локера, технически это не проблема. Но это просто "фотография" т.е. расклад в данный момент времени - и все. Ну напр обнаружили что вот сейчас элемент затребован всеми 4 нитками - и что, уже маркировать его резидентом? А если 3-мя или 2-мя? Выглядит как-то несолидно/неустойчиво

Цифра четыре условно взята за пик, прохождение которого в соответствующую сторону (вверх/вниз) знаменует смену флага резидентности. Да, тут получается к чему-то нужно привязаться, может быть даже высчитывать процент текущих ниток, работающих с элементом, от всех имеющихся ниток. Впрочем, это ничем не лучше константы. Тогда надо думать, раз такое не подходит.

Может отталкиваться от алгоритма который обрабатывает изображение, или это секретные разработки? =)

Обработка довольно однообразна

- на основании др данных вычисляются координаты пикселя и некоторый радиус (также в пикселях)
- в получившемся круге выбирается заданное кол-во пикселей (default 25) и вычисляется их среднее значение в виде float rgb(a)

Эта утилитарная операция повторяется много раз и может быть вызвана любой ниткой во многих вариантах.

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

Это не тот случай. Простой пример: имедж отмаплен сферой. Тогда расчет какие части имеджа (элементы) потребуются вероятно обойдется дороже самого осреднения.

Ну и почему мы сразу сочли что общее/регулярное решение невозможно или слишком сложно, поэтому надо искать частное решение используя специфику задачи? Как насчет подумать (вместо воспоминаний как использовать готовое)? Ну напр

- после 1 миллиона обращений проходимся по всем элементам и (пере)назначаем резидентов (возможно обнуляя счетчики)

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

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