Dostęp do zmiennych klasy - problem z szybkością

Witam.

Mam funkcję, która kilkaset razy na sekundę przerysowuje bufor obrazka do bufora okna. Zanim obrazek zostanie przerysowany, potrzebne jest sprawdzenie jego położenia względem okna i ewentualne odcięcie tego co wystaje poza krawędzie (tzw. clipping). Początkowo robiłem to przy każdym rysowaniu, a potem uświadomiłem sobie, że przecież wystarczy to robić tylko wtedy, gdy zmienia się położenie obrazka względem okna, w innym wypadku wystarczy po prostu wykorzystywać dane z poprzedniego clippingu, co w teorii powinno dać o wiele lepszą wydajność (bo to jednak sporo mniej kalkulacji). Dorzuciłem więc do klasy obrazka dodatkowe zmienne określające ramy bufora, które należy przerysować (wcześniej były one zmiennymi lokalnymi, alokowanymi i aktualizowanymi przy każdym przerysowywaniu obrazu). Efekt? Szybkość rysowania spadła o połowę (z 600 klatek na sekundę do ok. 300)!

Ja wnioskuję, jest to różnica wynikająca z szybkości dostępu do zmiennych, bo pola klasy są przechowywanie na stercie (heap), a zmienne lokalne na stosie (stack), ale czy mogę coś w tym względzie zaradzić bez odwoływania się do pisania wstawki w ASM?

Szczerze, to BARDZO wątpię w diagnozę - że winny heap itd.
Jak ci się wydaje ten heap to gdzie jest, na Hawajach?

nawiasem mówiąc od wczoraj jest wysyp obwiniania kompilatorów, providerów (dla aplikacji webowych), fabrycznych kontenerów, KLASY itd.

Nieoficjalnie by obstawiał, że coś w kodzie jest nieoptymalne, a tego skąpisz

@AnyKtokolwiek:

Jest i kod :).

void Image::Draw(int iX, int iY)
	{
		if (iX + Data.Width < 0 || iY + Data.Height < 0 || iX >= Parent.Resolution.Render.Width || iY >= Parent.Resolution.Render.Height) return;
		else
		{
			int* In, * Out, * In_RowEnd, * In_ColumnEnd;
			int In_RowComp, Out_RowComp;

			if (iX >= 0)
			{
				if (iY >= 0)
				{
					In = Data.Bits;
					Out = &Parent.Buffer.Color[(iY * Parent.Resolution.Render.Width) + iX];
				}
				else
				{
					In = &Data.Bits[-iY * Data.Width];
					Out = &Parent.Buffer.Color[iX];
				}

				if (Data.Width + iX < Parent.Resolution.Render.Width)
				{
					In_RowEnd = In + Data.Width;
					In_RowComp = 0;
					Out_RowComp = Parent.Resolution.Render.Width - Data.Width;
				}
				else
				{
					In_RowEnd = In + (Parent.Resolution.Render.Width - iX);
					In_RowComp = Data.Width - (Parent.Resolution.Render.Width - iX);
					Out_RowComp = iX;
				}	
			}
			else
			{
				if (iY >= 0)
				{
					In = &Data.Bits[-iX];
					Out = &Parent.Buffer.Color[iY * Parent.Resolution.Render.Width];
				}
				else
				{
					In = &Data.Bits[(-iY * Data.Width) - iX];
					Out = Parent.Buffer.Color;
				}

				if (Data.Width + iX < Parent.Resolution.Render.Width)
				{
					In_RowEnd = In + (Data.Width + iX);
					In_RowComp = -iX;
					Out_RowComp = Parent.Resolution.Render.Width - (Data.Width + iX);
				}
				else
				{
					In_RowEnd = In + Parent.Resolution.Render.Width;
					In_RowComp = Data.Width - Parent.Resolution.Render.Width;
					Out_RowComp = 0;
				}
			}

			In_ColumnEnd = iY + Data.Height < Parent.Resolution.Render.Height ? &Data.Bits[Data.Size] : &Data.Bits[Data.Width * (Parent.Resolution.Render.Height - iY)];

			for (; In < In_ColumnEnd; In += In_RowComp, Out += Out_RowComp, In_RowEnd += Data.Width)
			{
				for (; In < In_RowEnd; In++, Out++) *Out = *In;
			}
		}
	}

//Data.Bits to tablica intów zawierająca piksele (bajty) obrazka
//Parent.Buffer.Color to tablica intów zawierająca piksele okna
//Data.Width, Data.Height i Data.Size to odpowiednio szerokość, wysokość obrazka, oraz ich iloczyn
//Parent.Resolution.Render.Width i Parent.Resolution.Render.Height to wysokość i szerokość okna

W zasadzie wystarczy zmienne z linii 6 i 7 przenieść do pól klasy, by ilość klatek spadła o połowę (mimo, że reszta kodu zostaje bez zmian).

pola klasy są przechowywanie na stercie (heap), a zmienne lokalne na stosie (stack)

Tylko jeśli sam obiekt klasy siedzi w heapie (albo tak zaprojektujesz klasę). Ogólnie przydałoby się, żebyś pokazał(a) cały kod, oraz takie rzeczy jak metodę benchmarkowania.

Crow napisał(a):

@AnyKtokolwiek:

Jest i kod :).

W zasadzie wystarczy zmienne z linii 6 i 7 przenieść do pól klasy, by ilość klatek spadła o połowę (mimo, że reszta kodu zostaje bez zmian).

Oryginalne stwierdzenie.
Rozwinięcie maszynowe nie różni się więcej niż o nanosekundy (inny rejestr bazowy pracuje).

Crow napisał(a):

Mam funkcję, która kilkaset razy na sekundę przerysowuje bufor obrazka do bufora okna...

Po kiego tak często?
Telewizja 4k ma tylko 100Hz = 100 klatek na sekundę.

@enedil:

class Image
{
private:
	struct BitmapData //To jest przerobiona wersja windowsowego structa BITMAP, którego trzeba do GetObject() - dodałem 2 ostatnie wiersze
	{
		long Type;
		long Width;
		long Height;
		long BytesPerScanLine;
		long Planes;
		long BitsPerPixel;
		int* Bits = nullptr;
		int Size;
	};
	Display& Parent; //Display to referencja do klasy okna, z której uzyskuję wymiary, dostęp do bufora itd.
	BitmapData Data = { 0 };
	int* In, * Out, * In_RowEnd, * In_ColumnEnd; //to właśnie te testowane pola klasy
	int In_RowComp, Out_RowComp; //to właśnie te testowane pola klasy
public:
	Image(Display& cDisplay);
	void Draw(int iX, int iY);
	void LoadFromFile(LPCWSTR lpcwstrFilePath);
	virtual ~Image();
};

Image::Image(Display& cDisplay) : Parent(cDisplay){}

void Image::LoadFromFile(LPCWSTR lpcwstrFilePath)
{
	if (HBITMAP Source = static_cast<HBITMAP>(LoadImageW(NULL, lpcwstrFilePath, IMAGE_BITMAP, 0, 0, LR_LOADFROMFILE)))
	{
		GetObject(Source, sizeof(BITMAP), &Data);
		Data.Size = Data.Width * Data.Height;

		BITMAPINFO BitmapInfo;
		BitmapInfo.bmiHeader.biSize = sizeof(BITMAPINFOHEADER);
		BitmapInfo.bmiHeader.biWidth = Data.Width;
		BitmapInfo.bmiHeader.biHeight = -Data.Height;
		BitmapInfo.bmiHeader.biPlanes = 1;
		BitmapInfo.bmiHeader.biBitCount = 32;
		BitmapInfo.bmiHeader.biCompression = BI_RGB;

		Data.Bits = new int[Data.Size];
		if (!GetDIBits(Parent.WindowDC, Source, 0, Data.Height, Data.Bits, &BitmapInfo, DIB_RGB_COLORS))
		{
			delete[] Data.Bits;
			std::cout << "ERROR! Could not read bits" << std::endl;
		}

		DeleteObject(Source);
	}
	else std::cout << "ERROR! Could not load bitmap" << std::endl;
}

Draw() już było.
 
A metoda benchmarkowania wygląda tak:

int FPS;
std::chrono::steady_clock::time_point Second = std::chrono::steady_clock::now();
std::chrono::steady_clock::time_point Before = Second;
std::chrono::steady_clock::time_point After;
std::wstring Caption;

while (!Terminated) //to obsługuje osobny wątek
{
	After = std::chrono::steady_clock::now();
	Before = After;

	//Tutaj kod robiący różne rzeczy w ramach renderowania klatki, odświeżania logiki itd.

	if ((std::chrono::duration_cast<std::chrono::seconds> (After - Second)).count())
	{
		Second = After;
		Caption = Display.Caption + L" | FPS: " + std::to_wstring((FPS)); //Liczba FPS wyświetlana na belce okna
		SetWindowTextW(Display.Handle, Caption.c_str()); //Display.Handle to windowsowy uchwyt okna
		FPS = 1;
	}
	else FPS++;
}

Z tego co widzę w strasznej pętli przepisujesz pixel po pixel'u.
Doprawdy myślisz że jesteś w stanie konkurować z producentami kart graficznych?
Rysowanie jednego obrazku na drugim pozostaw systemowi, ewentualnie użyj CUDA i zmuś do tego kartę graficzną (ale i tak nie osiągniesz prędkości karty graficznej).

Skoro i tak używasz windowsowych poleceń to użyj tego:
https://docs.microsoft.com/en-us/windows/win32/api/wingdi/nf-wingdi-bitblt

Crow napisał(a):

Ja wnioskuję, jest to różnica wynikająca z szybkości dostępu do zmiennych, bo pola klasy są przechowywanie na stercie (heap), a zmienne lokalne na stosie (stack), ale czy mogę coś w tym względzie zaradzić bez odwoływania się do pisania wstawki w ASM?

(...)

Crow napisał(a):

W zasadzie wystarczy zmienne z linii 6 i 7 przenieść do pól klasy, by ilość klatek spadła o połowę (mimo, że reszta kodu zostaje bez zmian).

Moim zdaniem różnica nie wynika z położenia sterta vs stos, a raczej zmienne lokalne vs obiekt. Możesz to zweryfikować alokując obiekt na stosie gdzieś na początku programu i posługując się cały czas wskaźnikiem do niego.

Kompilator C/ C++ musi przestrzegać reguł aliasowania wskaźników. Reguły te można wyłączyć słowem kluczowym restrict:
https://en.wikipedia.org/wiki/Restrict
https://en.cppreference.com/w/c/language/restrict

Moje rozumowanie jest takie:

• zmienne lokalne są tworzone w ramce stosu przeznaczonej dla obecnego wywołania obecnie wykonywanej funkcji i kończą żywot wraz z wyjściem z funkcji
  • z tego powodu nikt nie mógł przed aktualnym wywołaniem funkcji pobrać w legalny sposób adresu tych zmiennych
  • jeżeli w samej funkcji też nie ma adresowania tych zmiennych lokalnych to można założyć, że nie ma do nich wskaźników w ogóle
  • skoro wiadomo, że nie ma do nich legalnych wskaźników to można je traktować tak jak pamięć adresowaną wskaźnikami z restrict
• w przypadku wrzucenia zmiennych do obiektu możemy mieć taką sytuację, że któryś ze wskaźników int* In, * Out, * In_RowEnd, * In_ColumnEnd; może wskazywać na któreś pole obiektu int In_RowComp, Out_RowComp;
  • kompilator nie może zastosować optymalizacji, które wpłynęłyby na semantykę takiego przypadku i dlatego ma związane ręce
  • ma związane ręce to znaczy, że musi ciągle zapisywać zmiany w polach obiektu i nie może zmieniać kolejności ładowania, modyfikacji i zapisu danych (patrz: przykłady np w wikipedii dotyczące słówka restrict)
• prawdopodobnie wskaźnik this nie jest restrict, więc spróbuj zamienić metodę void Image::Draw(int iX, int iY) na statyczną, a jako pierwszy parametr dać wskaźnik (z modyfikatorem restrict) do obiektu typu Image
  • ponadto wskaźniki w obiekcie Image też mają mieć modyfikator restrict

Nie polecam zabawy w restrict bo nadużywając można strzelić sobie w stopę jeszcze łatwiej niż bez niego. Zamiast tego polecam skopiować pola obiektu do zmiennych lokalnych na wejściu do metody void Image::Draw(int iX, int iY), a przed wyjściem skopiować je z powrotem ze zmiennych lokalnych do obiektu.

Generalnie do analizy takich problemów używa się narzędzi do profilowania, np. intelowego VTune'a, ktory z tego co wiem jest darmowy. Bez tego to jest zgadywanie.

Crow napisał(a):

Witam.

Efekt? Szybkość rysowania spadła o połowę (z 600 klatek na sekundę do ok. 300)!

Literówka, czy masz super szybki monitor?

@Crow moja rada to zacząć od profilera a nie od prób optymalizacji na ślepo. Bo pomijając kwestie optymalizacji kompilatora które twoje zmiany mogą popsuć, albo np. problemów z obiektami które są większe niż linia cache, to może być tak że optymalizujesz kawałek kodu który zabiera 1% czasu zamiast skupić się na tym co zabiera go 99%.

Widzę, ze dużo szczegółów padło

• co może i prawdopodobnie będzie zoptymalizowane
• żeby nie używać "ręcznego" kodu
• profilowanie, a nie domysły

Dodam, do gorącej herbaty, że nie ma zamienności zmiennych w klasie i zmiennych lokalnych w metodzie. Powiem jeszcze bardziej, nie ma zmiennych w klasie, a są pola.

To trzeba sobie mocno w głowie oddzielić. Pola są informacją o wiele bardziej trwałą, niż doraźne zmienne.
Po rozdzieleniu w głowie j/w drugi temat: nazwy. O ile ix jest dla mnie 'spoko' nazwą zmiennej lokalnej o zakresie 3 linii, to fatalną nazwą pola (czy zmiennej o dużym zakresie).
Źle użyta nazwa ma razić, nie dać spać itd i nakłonić do refaktoringu.

Tak się składa, że w 95% przypadków dążenie do czytelnego, stylowego kodu polepsza optymalizację (pozostałe 5% to dodanie poziomu abstrakcji, może nieco osłabić szybkosć).
Na gruncie tego wątku: najbardziej lokalny charakter zmiennych, jaki jest możliwy, jest czynnością ku dobremu stylowi, i daje kompilatorowi okazję optymalizacji. Współczesny CPU ma więcej rejestrów niż dawniej, ale dalej to skończona ilość, niech tam pracują zmienne najbardziej lokalne.

Dodam, że arytmetyka wskaźnikowa to przypuszczalnie była szybsza od indeksowej (tablicowej), ale to było trzydzieści lat temu.

for (; In < In_RowEnd; In++, Out++) *Out = *In;

to nie tylko można zastąpić funkcją z karty graficznej, ale memcpy czy czymś, co się zinlinuje.
Po (drugie??? chyba już siedemnasta myśl), wątpię, by porównanie końca zakresu na wskaźnikach było szybsze niż na integerach integerze (jednym), chętnie o mniejszym zakresie (i zmienne silnie lokalne).
Dwa długie inkrementy, zamiast jednego (krótkiego) itd Ten zapis ma jeden cel: czuć się jak hacker.
Gdybym miał pisac ręcznie, bym dał:

for(short i=0; i< row_length; i++) a[i] = b[i];

Z drobiazgów, które są pro-stylowe, a dają kompilatorowi szanse do wykazania się, są const i constexpr

@Wibowit wolał bym, zebyś wycofał się z porady

prawdopodobnie wskaźnik this nie jest restrict, więc spróbuj zamienić metodę void Image::Draw(int iX, int iY) na statyczną,

Ta klasa ma przed sobą DUŻY zakres analizy, co jest polem, jakim jest polem itd, niech to najpierw się stanie. W sumie, to nie ma pewności czy klasa to naprawdę Image, czy coś innego (ImageBuffer ?) a metoda to Draw. Na pewno w obecnym kształcie nie jest to klasa, która da się użyć w grze, poza testem wydajnościowym - tu jeszcze wiele będzie się działo

A ja powiem tak:
Analizowanie przyczyn spadku wydajności jedynie na podstawie kodu (gdy złożoność się nie zmieniła), jest trudne i wymaga ogromnej ilości doświadczenia. Uzyskanie informacji na forum internetowym lub SO graniczy z cudem (z powodu trudności przekazania wszystkich ważnych informacji i trudności ich interpretowania).
Rozważanie wstawek assemblerowych nie ma sensu, bo kompilator potrafi cuda (polecam dowolne filmami z Matt Godbolt, np to).

Fajnie, że robisz jakieś pomiary, ale początkujący często robią błędy, które są trudne do zauważenia, a zakłócające wyniki:

• uruchamiania testów na build debug (brak optymalizacji kompilatora). Jak pisałem wcześniej, kompilator potrafi cuda, brak właściwych ustawień kompilatora będzie dawał dramatycznie inne wyniki. Przypuszczam, że to jest twój przypadek, bo: nie wspominałeś słowem (jakie masz ustawiania), a opisywany przez ciebie objaw (dwukrotny spadek wydajności, bo zmienne zostały przeniesione, z lokalnych do klasy), jest typowy dla braku optymalizacji i to jest najlepsze wyjaśnienie tego co obserwujesz
• pomiary wykonywane zegarem o słabej rozdzielczości (raczej to nie jest problem)
• kod testowy mierzący wydajność jest źle zbudowany i optymalizator usunął to co najistotniejsze.

Dziękuję wszystkim za bardzo sensowne porady!
Troszkę przerobiłem kod i obecnie wygląda tak (póki co trzymam się clippingu przy każdym rysowaniu bo nie wydaje się mieć specjalnego wpływu na wydajność, przynajmniej w porównaniu do kopiowania danych na wejściu):

void Image::Draw(int iX, int iY)
{
	if (iX + Data.Width < 0 || iY + Data.Height < 0 || iX >= Parent.Resolution.Render.Width || iY >= Parent.Resolution.Render.Height) return;
	else
	{
		int* In, * Out, * In_ColumnEnd;
		int Width;

		if (iX >= 0)
		{
			if (iY >= 0)
			{
				In = Data.Bits;
				Out = &Parent.Buffer.Color[(iY * Parent.Resolution.Render.Width) + iX];
			}
			else
			{
				In = &Data.Bits[-iY * Data.Width];
				Out = &Parent.Buffer.Color[iX];
			}

			Width = (Data.Width + iX < Parent.Resolution.Render.Width) ? Data.Width * sizeof(*In) : (Parent.Resolution.Render.Width - iX) * sizeof(*In);
		}
		else
		{
			if (iY >= 0)
			{
				In = &Data.Bits[-iX];
				Out = &Parent.Buffer.Color[iY * Parent.Resolution.Render.Width];
			}
			else
			{
				In = &Data.Bits[(-iY * Data.Width) - iX];
				Out = Parent.Buffer.Color;
			}

			Width = (Data.Width + iX < Parent.Resolution.Render.Width) ? (Data.Width + iX) * sizeof(*In) : Parent.Resolution.Render.Width * sizeof(*In);
		}

		In_ColumnEnd = iY + Data.Height < Parent.Resolution.Render.Height ? &Data.Bits[Data.Size] : &Data.Bits[Data.Width * (Parent.Resolution.Render.Height - iY)];

		for (; In < In_ColumnEnd; In += Data.Width, Out += Parent.Resolution.Render.Width) std::memcpy(Out, In, Width);
	}
}

Czyli zamieniłem iterowanie po jednym int, na kopiowanie całych wierszy przy użyciu memcpy. Uzyskałem dzięki temu przyrost klatek z 600 do ok. 850 czyli w zasadzie sukces. Wczoraj jednak @enedil zasugerował użycie std::copy, które ponoć ma jakiś "wbudowany" sposób na odpowiedni aligment danych, przez co mógłbym kopiować jeszcze wydajniej niż wiersz po wierszu. Przepatrzyłem jednak dokumentację std::copy i niczego takiego nie znalazłem, ktoś coś może podpowiedzieć? :).

Wczoraj jednak @enedil zasugerował użycie std::copy, które ponoć ma jakiś "wbudowany" sposób na odpowiedni aligment danych, przez co mógłbym kopiować jeszcze wydajniej niż wiersz po wierszu. Przepatrzyłem jednak dokumentację std::copy i niczego takiego nie znalazłem, ktoś coś może podpowiedzieć? :).

Nie chodzi o kopiowanie wydajniej niż wiersz po wierszu (bo do tego chyba nie ma gotowca w bibliotece standardowej), a o ten alignment, czyli wyrównanie wskaźników. Nie wiem na ile to wyrównanie wskaźników miałoby na coś wpłynąć (to i tak trzeba sprawdzić zarówno w memcpy jak i std::copy, nie widzę jakiegoś wymogu by wskaźniki przekazywane do std::copy miały być wyrównane). memcpy raczej ma wyifowane wszystko co trzeba, co najwyżej std::copy wymaga mniej ifów w implementacji. Popatrz jakie memcpy może być zakręcone: https://github.com/bminor/glibc/blob/master/sysdeps/x86_64/multiarch/memcpy-ssse3.S

W zasadzie wystarczy zmienne z linii 6 i 7 przenieść do pól klasy, by ilość klatek spadła o połowę (mimo, że reszta kodu zostaje bez zmian).

@Crow No i co w tym dziwnego? Metody mają zewnętrzny storage (w sensie inny niż pola klasy/struktury), więc jeśli odwołujesz się do pól odwołujesz się do innego miejsca w pamięci, którego najprawdopodobniej nie ma w cache. To i tak nieźle, że spadło Ci tylko o połowę. Przekazanie wskaźników jako argumenty powinno być tak samo szybkie jak typowo lokalne, ale nie czytałem Twojego kodu więc gwarancji nie daje.

Jeśli chcesz się czegoś nauczyć w tym temacie to szukaj materiałów związanych z Data Oriented Design.