GetPixel thread-safe

[Igors]

Добрый день

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

Код:

void Image::GetPixel( int iX, int iY, float oColor[4] )
{
// находим в какой странице находится нужный пиксель
// переводим iX, iY в координаты страницы
  ImgPage * thePage = this->GetPage(&iX, &iY);

// если страница не загружена - загружаем ее
  if (!thePage->mData)
    LoadPageFromDisk(thePage);

// получаем указатель на нужный пиксель
  unsigned char * pixel = (unsigned char *) thePage->mData + iY * mPageWidthBytes + iX * mPixelSize;

// получаем из пикселя 4-х байтные float
  switch (mDataFormat) {
    case ARGB8:
     oColor[0] = pixel[0] / 255.0f; 
     oColor[1] = pixel[1] / 255.0f; 
     oColor[2] = pixel[2] / 255.0f; 
     oColor[3] = pixel[3] / 255.0f; 
     break;
     
    case ARGB16:
     ...
     break;
    ...
  }
}

Вопрос: как мне сделать эту функцию thread-safe? Понятно что я могу поставить MutexLock на входе и Unlock на выходе. Но не хотелось бы - GetPixel вызывается очень часто, значит я реально буду использовать 1 процессор (да еще и за мутекс с меня что-то возьмут). А по-другому дело упирается в загрузку страницы. Если данных много, то для того чтобы загрузить страницу, надо сначала другую, наименее используемую вытолкнуть на диск. Если эта выталкиваемая страница используется функцией GetPixel из другой нитки - я получу неверные расчеты (crash не произойдет, но это еще хуже). Как правило подгрузка/выгрузка страниц - выполняется относительно редко, примерно 1 раз нв 10000 вызовов GetPixel

Что бы Вы могли посоветовать?
Спасибо

[BRE]

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

[Igors]

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

Нитка 1:

Код:

void GetPixel( ... )
{
  ....                                // <---  сейчас 1-й процессор выполняет команду здесь, mUsage еще = 0
  ++thePage->mUsage;
  ...                                // read pixel
 --thePage->mUsage;
}

Нитка 2:

Код:

void LoadPageFromDisk( ... )
{
  ....                               
  if (!theLastPage->mUsage) {     // <---  сейчас 2-й процессор выполняет команду здесь, mUsage еще = 0
   ...
   theLastPage->mData = 0;       // mark page as swapped
   ....                                
  }
  ...
}

Хммм... наверное я был не прав - crash я все-таки получу 

[BRE]

А ты сделай GetPage атомарной:

Код

C++ (Qt)
void GetPixel( ... )
{
	ImgPage page = GetPage(...);	// Вернули страницу (если надо загрузили страницу)
	...
}	// при выходе из функции объект page разрушается и в деструктор уменьшает счетчик
 

Вся работа со счетчиками защищается мьютексами.

[Igors]

А ты сделай GetPage атомарной:

Код

C++ (Qt)
void GetPixel( ... )
{
	ImgPage page = GetPage(...);	// Вернули страницу (если надо загрузили страницу)
	...
}	// при выходе из функции объект page разрушается и в деструктор уменьшает счетчик
 

Вся работа со счетчиками защищается мьютексами.

Возврат объекта по значению, вызов конструктора/деструктора, вызов new/delete (упаси боже) - все эти радости жизни мне (в данной конкретной задаче) недоступны. Слишком много вычислений, слишком критична скорость. Если интересно почему - могу рассказать, или просто скажем - нужны максимально быстрые, низкоуровневые решения. Каждый патрон на счету 

[BRE]

Сделал набросок:

Код

C++ (Qt)
class Page
{
public:
	Page() : m_cntUsed( 0 ) {}
 
	void	incCntUsed()
	{
		QMutexLocker lock( m_mutex );
		++m_mutex;
	}
 
	void	decCntUsed()
	{
		QMutexLocker lock( m_mutex );
		--m_mutex;
	}
 
	quint32	cntUsed() const
	{
		QMutexLocker lock( m_mutex );
		return m_mutex;
	}
 
private:
	QByteArray		m_data;
 
	quint32		m_cntUsed;
	mutable QMutex	m_mutex;
};
 
class ImgPageCache
{
public:
	Page	*getPage( int x );
 
private:
	QMap<int, Page*>	m_cache;
	mutable QMutex		m_mutex;
};
 
Page *ImgPageCache::getPage( int x )
{
	Page *page = 0;
	QMutexLocker lock( m_mutex );
	if( m_cache.contains( x ) )
	{
		// Страница в кеше
		page = m_cache[ x ];
		page->incCntUsed();
		return page;
	}
	lock.unlock();
 
	// Страницы нет в кеше, загружаем...
	page = LoadPage( ... );
 
	lock.relock();
	m_cache.insert( x, page );
	page->incCntUsed();
	return page;
}
 

[Igors]

Код

C++ (Qt)
Page *ImgPageCache::getPage( int x )
{
	Page *page = 0;
	QMutexLocker lock( m_mutex );
	if( m_cache.contains( x ) )
	{
 

Только вызов contains весит дороже чем весь GetPixel. И если я на каждом вызове использую QMutexLocker lock( m_mutex ) - то проще и лучше поставить его первой строкой в GetPixel - и вся любовь.

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

[BRE]

Только вызов contains весит дороже чем весь GetPixel.

А кто заставляет его использовать, это только для примера.

И если я на каждом вызове использую QMutexLocker lock( m_mutex ) - то проще и лучше поставить его первой строкой в GetPixel - и вся любовь.

И что получиться? В один момент времени получать пиксель сможет один поток.

Я бы хотел вот что: если страница в памяти (а это 99% всех случаев) - все проходит без всяких мутексов.

А как ты себе это представляешь? 

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

[Igors]

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

"Доставание" получается дороже чем сам GetPixel 

Хорошо, а если по-другому покрутить? Вот пример как используется GetPixel

Код:

void Image::Sample( int iX, int iY, int sample, FColor & color )
{
  int i, j, num = 0;
  FColor temp;
  oColor = 0.0f;
  for (j = iY - sample; j <= iY + sample; ++j)
    for (i = iX - sample; i <= iX + sample; ++i) {
      if (CheckPixel(i, j) {
       GetPixel(i, j, temp);
       oColor += temp;
       ++num;
      }
    } 
    if (num) 
     oColor /= num;
}  

Допустим мы "зажали" пока свап на диск, да, какие-то пиксели не смогут просчитаться, пусть GetPixel вернет для них false. Таких случаев будет мало, вполне возможно все имеджи в памяти. Хммм... вернуться и "досчитать все теперь уже с мутексами"? (просто мысли вслух  )

[BRE]

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

[Igors]

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

Нет, этого не получить. Ладно, поставлю пока просто мутекс на входе и потестирую скорость/загрузку. А дальше видно будет

[SABROG]

"Доставание" получается дороже чем сам GetPixel 

Вопрос: как мне сделать эту функцию thread-safe?

Но не хотелось бы - GetPixel вызывается очень часто, значит я реально буду использовать 1 процессор

Я вот чего понять не могу, как количество потоков может повлиять на скорость получения пикселя? Винчестер наверняка один, файл с тайлами тоже один. Количество ядер процессора никак не влияет на скорость чтения с диска. Значит в потоке выполняются и другие вычисления. Говоря о том, что contains() будет дороже чем GetPixel, реально ты ошибочно сравниваешь стоимость всего потока, в котором наверняка не только GetPixel, иначе это сравнение ошибочно, т.к. время доступа к пикселю будет константным из-за того, что количество потоков никак не влияют на скорость чтения информации с носителя.

Нет, этого не получить.

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

[Igors]

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

Никакой суперкрутой программы, задача очень банальна: рендер полигонных 3D объектов. Допустим выходной имедж 640х480 (это очень скромно, может быть 4Кх3К). Каждый пиксель разбивается на суб-пиксели. Минимальная матрица 4х4, максимальная 64х64. Каждый суб-пиксель проецируется на 3D объект который может быть покрыт текстурами При вычисления аттрибутов суб-пикселя каждая текстура должна "самплиться", т.е. N точек исходного имеджа должны быть осреднены. Детали организации/хранения имеджей см. выше

Я вот чего понять не могу, как количество потоков может повлиять на скорость получения пикселя? Винчестер наверняка один, файл с тайлами тоже один. Количество ядер процессора никак не влияет на скорость чтения с диска. Значит в потоке выполняются и другие вычисления. Говоря о том, что contains() будет дороже чем GetPixel, реально ты ошибочно сравниваешь стоимость всего потока, в котором наверняка не только GetPixel, иначе это сравнение ошибочно, т.к. время доступа к пикселю будет константным из-за того, что количество потоков никак не влияют на скорость чтения информации с носителя.

Как видно из обсуждения здесь, я вынужден ставить мутекс-блокировку на каждый GetPixel. Как показали эксперименты (см. топик "Проблемы с QMutex") это далеко не безобидная операция которая может сделать 4 процессора в несколько раз медленнее чем 1. Мне бы ОЧЕНЬ хотелось ставить мутекс только там где происходит обращение к диску, но такого решения я пока не нашел.