[ZawzietyRobaczek]

#jezykc #cpp #programowanie Zawsze słyszałem żeby korzystać z jednowymiarowych tablic int* niż dwuwymiarowych int**,
porobiłem pare testów i wyszło że te dwuwymiarowe są ok. 4x lub wiecej szybsze niż 1 wymiarowe, przynamjniej kompilujac na Intelu visual studio x86, chce jeszcze sprawić na docelowej architekturze 68k.. może to wybika z tego że żeby móc traktoac 1 wymiarowa tablicę jako macierz trzeba jednac sobie obliczyć index = x + y * width - co jest dodatkową operacją.. w każdym razie w tym przypadku przyrost wydajności bardzo duży..

[Hadzik]

@ZawzietyRobaczek: lokalność danych może

[groman43]

@ZawzietyRobaczek: Podaj proszę więcej szczegółów - Jak profilowałeś kod? jak duże były tablice?
Liczenie indeksu nie powinno powodować tak drastycznego spadku wydajności. Natomiast duże skoki po tablicy mogą powodować cache missy.

[hszan]

@Hadzik: no tylko, ze tutaj lokalnosc jest po stronie 1d.
@ZawzietyRobaczek: pokaz kod, cos mi sie nie chce wierzyc. Tablica jednowymiarowa powinna byc odrobine szybsza i zajmowac troche mniej pamieci.

[Hadzik]

@hszan: zależy jakie operacje były na tablicach wykonywane i jakie były rozmiary tablic, dla dostępu sekwencyjnego po indexach lepszy wynik dla 2d ma jakiś sens

[hszan]

@Hadzik: no raczej sekwencyjny dostep to tylko 1D, 2D mialby wiekszy sens przy losowym dostepie lub bardzo specyzowanym - typu iterowanie sie przez tablice wielkosci jednego page. Tak czy siak to na bank nie bedzie kwestia 4x wydajnosci, chyba, ze mowimy o 100% missach, ale wtedy to jest skopany kod, a nie kwestia tablicy.

[zrakiep]

@ZawzietyRobaczek: jak pozostałe mirki, chciałbym zobaczyć ten kod do testowania.

Zasadniczo, takie "x + y*w" na współczesnym x86 jest zdecydowanie szybsze niż wczytanie adresu tablicy - nawet i z cache, nie mówiąc już o RAM.

[Passer93]

@ZawzietyRobaczek: w modern cpp nie korzysta się z tablic tylko z STLa, wiec nie wiem gdzie słyszałeś by korzystać z tablic jednowymiarowych xD

[Passer93]

@hszan: @Hadzik: @hszan: jaka lokalność, jak tablica 2d zajmuje taki sam ciągły blok pamięci jak 1d xD

[zrakiep]

@Passer93: no nie.

W 1d masz ciągły blok bajtów, w 2d każdy wiersz może być w zupełnie innym miejscu. Jak czytasz sekwencyjnie, wiersz po wierszu, tablica 1d super działa z cache.

STL też ma pod spodem tablice. Pytanie możesz sobie przetłumaczyć na std::array> vs std::vector>

[hszan]

@Passer93:
Ostatnio pisalem libke, zeby miec tablice na 10x page, test przy 45 milionach doubles - defragmentacja na poziomie 32%. Nie p-----l glupot xD
Wiesz o tym, ze alokujac dwie tablice obok siebie (w kodzie), jedna moze wyladowac zupelnie gdzie indziej?

[Passer93]

@zrakiep: Przeciez tablica 2d też zajmuje ciągły obszar pamięci xD

[Passer93]

@hszan: Ja nie mówiłem o alokowanych dynamicznie tablicach tylko o tych na stosie. Chyba się nie zrozumieliśmy.
Ale autor wpisu sam nie wspomniał z jakich korzysta

[zrakiep]

@Passer93: OP pisze:

dwuwymiarowych int**

taka tablica nie zajmuje ciągłego obszaru pamięci, każdy wiersz może zostać zaalokowany gdzie indziej.

[Hadzik]

@hszan: myślałem o dostępie sekwencyjnym do kolumny przy implementacji wierszowej w 1D a kolumnowej w 2D, czyli właściwie przy źle napisanym teście

[Passer93]

@zrakiep: Nie liczyłem się z tym że ktoś będzie implementował macierz alokując każdy rząd osobno xDDD Poza fragmentacją pamięci dochodzą też koszty wielokrotnej alokacji, to chyba najgorszy z możliwych sposobów.

[zrakiep]

@Passer93: za to pewnie najbardziej popularny. Toż taki std::vector> w taki sposób działa.

[Passer93]

@zrakiep: No ale jak chce zrobić macierz określonej wielkości, to powinien stowrzyć własnego wrappera nad std::array, i mieć tylko jedna alokacje ciągłego obszaru pamięci.

[zrakiep]

@Passer93: no i OP o tym wie, ale sprawdził, że mu taki int** działa 4x szybciej. Więc prawdziwe pytanie brzmi: jak to możliwe? ( ͡° ͜ʖ ͡°)

[MamCieNaHita]

@ZawzietyRobaczek: jakie flagi optymalizacyjne? na debugu to żadne porównanie

[SpinOff]

@zrakiep: Tak to możliwe, że OP nie wie co robi