Подкачка данных переменной длины

[Igors]

Добрый день

Рассмотрим сначала простой и понятный случай. Есть имедж размером M x N, пусть например значение каждого пикселя соответствует высоте над уровнем моря. Имедж может быть велик (или имеем много имеджей), поэтому не храним его весь в памяти а подкачиваем его с диска. Псевдокод

Код

C++ (Qt)
float Image::GetPixel( int x, int y )
{
// номер страницы в файле подкачки
  int pageNo = (y / mPixelPageY) * mNumPageX + x / mPixelPageX;  
 
// загрузили страницу
  if (!mPage[pageNo].IsLoaded()) 
    LoadPage(pageNo, mBaseOffsetInFile + pageNo * mPageSizeBytes);
 
// координаты пикселя внутри страницы
  x %= mPixelPageX;
  y %= mPixelPageY;
 
// данные
  return mPage[pageNo].mData[y * mPixelPageX + x];
}
 

   

Теперь более сложный случай: каждому пикселю соответствует последовательность значений переменной длины. Для оного всего 1 значение, для другого 10, для какого-то и все 20 (пусть и редко). Как организовать подкачку в этом случае? Есть мысли?

Спасибо

[niXman]

1. т.е. Image::GetPixel() должна возвращать массив?
2. Image::GetPixel() может дергаться из нескольких потоков?
3. кол-во вызывающих ее потоков?
4. Image::GetPixel() живет в отдельном потоке?

[Igors]

1. т.е. Image::GetPixel() должна возвращать массив?

Указатель на константный

Код

C++ (Qt)
const float * Image::GetComplexPixel( int iX, int iY, int * oNumPix );
 

2. Image::GetPixel() может дергаться из нескольких потоков?

да

3. кол-во вызывающих ее потоков?

равно числу ядер процессора

4. Image::GetPixel() живет в отдельном потоке?

да

[niXman]

Указатель на константный

а как же вы узнаете размер? он же у вас разный

[Igors]

а как же вы узнаете размер? он же у вас разный

Для этого oNumPix

[niXman]

а как же вы узнаете размер? он же у вас разный

Для этого oNumPix

ааа, так вы метод изменили. не заметил.

Указатель на константный

1. если указатель - значит память для него нужно выделять динамически. но когда освобождать память? метод(код) который ее выделяет, этого знать не может. а тот кто ее получит, удалить не сможет из-за того что константный.
2. если указатель - можно возвращать адрес локального массива. но тогда никакой многопоточности.

я вижу решение таким:
нужен "некий класс"(с ссылкой на контейнер который им владеет) с перегруженным operator()(который вернет запись, и удалит себя из контейнера в котором живет), возвращающий, к примеру, std::pair<boost::uint32_t, float[32]>
boost::uint32_t - содержит размер актуальных данных.
float[32] - автоматический массив максимально возможного размера. выделение динамической памяти - дорогая операция.
для чего нужен "некий класс"? - И для того, чтоб реализовать упреждющее чтение
допустим, хранение очереди состоящей из std::pair<boost::uint32_t, float[32]> типов размером, к примеру, в 10000 единиц, будет занимать около 35кб. очень не много, но производительность вырастит ощутимо.

раз уж метод может дергаться из нескольких потоков, то наверняка нужна нешуточная производительность. потому, читать по одной записи не рационально.
еще вариант для оптимизации - не удалять из очереди "использованные" записи. а, к примеру, использовать записи типа boost::tuple<boost::uint32_t, float[32], bool>. где bool - признак состояния записи(занята/свободна). это даст ощутимый прирост производительности.

вроде правильно объяснил. остальное реализация.

[Igors]

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

Это не имеет отношения к теме, но заметим что константный указатель удалять можно (мне это всегда казалось неестественным).

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

2. если указатель - можно возвращать адрес локального массива. но тогда никакой многопоточности.

Сделать это thread-safe интересно и нужно, но пока я спрашиваю как вообще организовать подкачку для таких данных.

я вижу решение таким:
нужен "некий класс"(с ссылкой на контейнер который им владеет) с перегруженным operator()(который вернет запись, и удалит себя из контейнера в котором живет), возвращающий, к примеру, std::pair<boost::uint32_t, float[32]>
boost::uint32_t - содержит размер актуальных данных.

Кончайте пьянку с контейнерами и бустами, думайте самостоятельно

[niXman]

Кончайте пьянку с контейнерами и бустами

велоизобретательством занимаетесь. никакой рациональности и профф подхода.

думайте самостоятельно

зачем вы Qt используете? думайте самостоятельно. напишите свою версию

[Igors]

велоизобретательством занимаетесь. никакой рациональности и профф подхода.

В чем же по-Вашему эти рациональность и подход? Свести данные к постоянной длине, зарезервировав по максимуму? Это ход мысли начинающего "Во блин, это new потом еще надо delete... Да ну его нафиг, просто объявлю переменную массив побольше чтобы за глаза хватило". Ваше предложение float[32] - точно такое же, знание множества классов никак не меняет сути.

В STL. boost или еще где есть стандартные подходы для решения этой (или подобной) задачи? Расскажите, я с удовольствием послушаю и скажу "спасибо, я этого не знал", неважно подойдет мне это по скорости или нет. А пускать пузыри с float[32] нечего 

[niXman]

ход мысли начинающего "Во блин, это new потом еще надо delete... Да ну его нафиг, просто объявлю переменную массив побольше чтобы за глаза хватило"

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

Ваше предложение float[32]

А пускать пузыри с float[32] нечего

и это "говорит" человек, пишущий код, выделяющий 8Гб памяти?
или в статье по проектированию с использованием шаблонов, спрашивает, "кто такие команды"?
 
детский сад, да и только...

[Igors]

Ничего  "супер-сложного" не спрашивалось. Я напр. вижу такой вариант

Код

C++ (Qt)
#define VPAGE_PIX_X	32
#define VPAGE_PIX_Y	32
#define VPAGE_PIXELS	(VPAGE_PIX_X * VPAGE_PIX_Y)
 
class CVPage {
	struct CPoint {
		int	mCount;
		float	mData[1];
	};
 
	struct CData {
		const float * GetPixel( int iX, int iY, int * oNumPix ) const
		{
			int offset = mLookup[iY * VPAGE_PIX_X + iX];
			if (offset < 0) {	// empty point 
				*oNumPix = 0;
				return 0;
			}
			CPoint * pt = (CPoint *)(mBase + offset);
			*oNumPix = pt->mCount;
			return pt->mData;
		}
 
		int mLookup[VPAGE_PIXELS];
		char mBase[1];
	};
 
public:
	CVPage( void );
 
	const float * GetPixel( int iX, int iY, int * oNumPix ) const
	{
		return mData->GetPixel(iX, iY, oNumPix);
	}
 
	void * Alloc( void )
	{
		mData = (CData *) malloc(mLoadSize);
		return mData;
	}
 
	void Free( void )
	{
		if (mData) {
			free(mData);
			mData = 0;
		}	
	}		
 
private:
	long long     mFilePos;		
	unsigned int mLoadSize;
	CData *      mData;
	volatile int   mSpin;
};
 

Возможно, это "не совсем в духе С++"    Поэтому мне было бы интересно посмотреть/сравнить с др. реализациями. Также как разыгрывать mSpin - есть о чем подумать. А на флуд "нашей малышь" не стоит обращать внимания  

[niXman]

первое что на ум пришло:

Некоторые C++ программисты используют boost, некоторые о нем только слышали, некоторые - нет. Так вот, последние 2 категории - тупиковая ветвь развития (о тех, кому не позволяет железо или компилятор я не говорю), как правило, такие люди даже не доросли до стандартной библиотеки, а их стиль программирования можно назвать “Си с классами”.

отсюда: http://rakafon.blogspot.com/2009/04/boost-boost-c.html
в точности, и не первый раз, подтверждает сказанное