Dynamiczne tablice wielowymiarowe "w jednym kawałku pamięci"

2009-08-24 22:18:00

Jak wiadomo tworzenie wielu "małych" obiektów na stercie (new) może powodować znaczna fragmentacje pamięci, wiec należy tego unikać. Dla bardzo dużej ilości obiektów, potrzebującej bardzo dużej ilości operacji zwalniania i alokowania można stosować ręcznie "placement new" lub bardziej zaawansowane "upraszczacze" jak np. "FreeList". a co ze zwykła tablica? Standardowa funkcja alokująca tablice 2-wymiarowa może wyglądać tak:

template<typename T>T **alloc2d(int width,int height){ T **mem=new T*[width]; for(int x=0;x<width;++x) mem[x]=new T[height]; return mem; }

jak widać tablice mamy w pamięci 'w kawałkach' o rozmiarze odpowiadającym zmiennej height. Jak to zmienić? Trzeba zastosować "placement new". Nowa wersja wygląda tak (typ int8 odpowiada 1 bajtowi):

template<typename T>T **alloc2d(int iX,int iY){ // alokuje wszystko w jednym bloku (dane i wskazniki na dane) int8 *raw=new int8[iX*iY*sizeof(T)+iX*sizeof(T*)]; // przydziela pamiec z bloku dla wskaznikow // wskazniki sa przed danymi-stad offset o rozmiarze wskaznikow ponizej T **ret=new(raw) T*[iX]; // przydziela pamiec z bloku dla danych (znajduja sie za wskaznikami) T *data=new(&raw[iX*sizeof(T*)]) T[iX*iY]; // przypisuje do wskaznikow adresy danych for(int i=0;i<iX;++i,data+=iY) ret[i]=data; return ret; }

Co nam to daje (oprócz umiejscowienia w jednym kawałku pamięci)?

wskaźniki do danych są 'blisko' samych danych (co podobno przyspiesza dostęp do danych tablicy)
dane możemy pobrać 'w całości' - maja one adres początku, co w 'zwyklej' wersji nie jest zapewnione. Możemy np. zaalokować taką tablicę dla tekstury (dwuwymiarowa), załadować ją bezpośrednio z pliku, pozmieniać jakąś niewinna grupkę pikseli i przekazać jakiejś funkcji która ja przyjmie bez dodatkowych operacji
jest lepsza od wersji w której alokujemy tylko dane, a dostajemy sie do poszczególnej komórki przeliczając indeksy. Czemu lepsza? Z moich pomiarów wynika ze prędkość działania przy dostępie do komórek w losowej kolejności jest drastycznie większa dla tablicy ze wskaźnikami. Dla przypadku gdy czytamy tablice "po kolei" szybkość dostępu jest taka sama jak dla tablicy z "przeliczanymi indeksami".

Jak sie dostać bezpośrednio do danych takiej tablicy?. Można sie posłużyć taka prosta funkcja:

template<typename T>T *Get2d(T **iA,int iX){ // mijamy wskazniki return (T*)(((int8*)iA)+iX*sizeof(T*)); }

Na koniec trzeba usunac taka tablice:

template<typename T>void Free2d(T **iA){ int8 *ptr=(int8*)iA; delete []ptr; iA=NULL; }

jak można sie domyślić można sobie łatwo zrobić tez wersje 3,4,... wymiarowa.

Tagi: Programowanie C++

Dynamiczne tablice wielowymiarowe "w jednym kawałku pamięci"

Ustawienia

RSS