Autor Wątek: Brak pamięci statycznie alokowanej  (Przeczytany 1963 razy)

Offline Lerhes

  • Użytkownik

# Listopad 02, 2015, 00:48:58
Cześć,

Pytanie nie jest związane z programowaniem gier - za co przepraszam - ale odpowiedź może być przydatna dla ludzi tworzących gry na urządzenia mobilne.

Wyobraźmy sobie sprzęt dedykowany pod kontrolą systemu operacyjnego czasu rzeczywistego. Mamy na nim dostępne około 200 mb wolnej pamięci (jak sądzę RAM). W systemie tym zastosowane są dwa typowe podejścia (typowe o ile mi wiadomo):
1. Większość potrzebnej pamięci (struktury danych, tablice itp) są statycznie zaalokowane jako zmienne globalne (lub są po prostu zmiennymi globalnymi).
2. Jest możliwa dynamiczna alokacja - ale żeby ją przyspieszyć, zaimplementowany został moduł który alokuje większe fragmenty pamięci i "rozdziela" ją według potrzeb (alokacja z puli).

Wyobraźmy sobie teraz, że dostajemy do zaimplementowania pewną nową funkcjonalność. Akurat tak się składa, że wymaga ona głównie dublowania potrzebnej pamięci statycznej (jeżeli mamy tablicę stu elementową pewnych struktur danych, zmieniamy ją na tablicę dwustu elementową). Wszystko idzie spoko, do czasu, gdy okazuje się, że ta pamięć się nam skończyła (za dużo pamięci statycznej nam jest potrzebne).

Czy macie może jakieś podpowiedzi / uwagi jak sobie z tym problemem poradzić?

Oczywiście - dokupienie większej ilości pamięci nie wchodzi w grę - to system dedykowany o ustalonej architekturze i parametrach - nie można ich zmienić.
O co chodzi mi konkretnie:
1. Czy jest coś ważnego jeżeli chodzi o pamięć statycznie alokowaną (lub po po prostu pamięć gdzie umieszczane są globalne zmienne) o czym powinienem wiedzieć? Np: Czy może ulegać fragmentacji, przez co tracę dużo pamięci? (np: zmieniając ułożenie globalnych obiektów albo kolejność kompilacji coś mogę zyskać?)
2. Jeżeli odpowiedź na powyższe pytanie brzmi "to zależy" to proszę o przykład typowych rozwiązań.
3. Zdaję sobie sprawę, że ułożenie parametrów w strukturach ma znaczenie ponieważ występuje wyrównywanie parametrów (tak zwany padding) - co zresztą można kontrolować poleceniami do kompilatora - ale generalnie to chyba za mała "strata" żeby tutaj jakoś bardzo walczyć.

Wiem, że na pytanie dość trudno odpowiedzieć nie znając szczegółów, ale może ktoś mnie naprowadzi na jakiś ciekawy trop (skuteczne rozwiązanie) - bardzo chętnie przyjmę też linki z informacjami które mogą mi pomóc.

Pozdrawiam,
Lerhes
« Ostatnia zmiana: Listopad 02, 2015, 01:16:56 wysłana przez Lerhes »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

  • +2
# Listopad 02, 2015, 01:44:36
Cytuj
Wyobraźmy sobie teraz, że dostajemy do zaimplementowania pewną nową funkcjonalność. Akurat tak się składa, że wymaga ona głównie dublowania potrzebnej pamięci statycznej (jeżeli mamy tablicę stu elementową pewnych struktur danych, zmieniamy ją na tablicę dwustu elementową). Wszystko idzie spoko, do czasu, gdy okazuje się, że ta pamięć się nam skończyła (za dużo pamięci statycznej nam jest potrzebne).

Czy macie może jakieś podpowiedzi / uwagi jak sobie z tym problemem poradzić?
Podzielić, co jest potrzebne w którym momencie w zależności np. od trybu pracy i zapakować w struktury, po czym zapakować wszystko w unię. Ewentualnie, jeżeli chcemy mieć to nieco bardziej po ludzku, zarezerwować całą zamienialną pamięć w jednej tablicy, a resztę globalnych deklarować w stylu "MyStruct &foo = *(MyStruct*)&MEM[FOO_OFFSET];". Tak czy inaczej można w ten sposób uzyskać dowolny statyczny podział pamięci z reusowaniem czego się chce.

Cytuj
Czy może ulegać fragmentacji, przez co tracę dużo pamięci?
Co najwyżej przez alignment danych, przez co wiele nie stracisz.

Cytuj
3. Zdaję sobie sprawę, że ułożenie parametrów w strukturach ma znaczenie ponieważ występuje wyrównywanie parametrów (tak zwany padding) - co zresztą można kontrolować poleceniami do kompilatora - ale generalnie to chyba za mała "strata" żeby tutaj jakoś bardzo walczyć.
Zależy ile tych struktur potem będzie. Jeżeli w strukturze siedzi bajt z intem, to 3/8 pamięci to padding i taką samą proporcję nieużytków będzie miała też dowolnego rozmiaru tablica tych struktur.

Offline hashedone

  • Użytkownik

  • +1
# Listopad 02, 2015, 10:58:10
Oprócz tego o czym mówi Krzysiek K, zależy jakie dane są trzymane i jak wykorzystywane. Jeśli dane się dobrze kompresują (lub nie ma znaczenia ich dokładna wartość - kompresja stratna może dać jeszcze lepsze wyniki) a w danym momencie zawsze wykorzystywana jest część danych (a nieużywanych danych nie można trzymać np. na dysku bo dysku nie ma), można próbować z kompresją (przecież nie od dzisiaj karty graficzne trzymają w pamięci skompresowane tekstury więc rozwiązanie nie jest takie abstrakcyjne). Trzeba tylko pamiętać że dekompresja może niekiedy potrzebować dodatkowej pamięci, a więc jeśli zysk miałby być bardzo mały to to rozwiązanie niewiele pomoże.
« Ostatnia zmiana: Listopad 02, 2015, 12:52:12 wysłana przez hashedone »

Offline sebas86

  • Użytkownik

  • +1
# Listopad 02, 2015, 21:50:29
Jeśli chodzi o padding straty mogą być większe niż się wydaje ale to zależy od architektury a nawet używanych operacji i typów danych. Nierzadkim przypadkiem jest wyrównywanie np. liczby zmiennoprzecinkowych do 4, 32 lub więcej bajtów. W procesorach CISC zazwyczaj są instrukcje, które pozwalają mniej wydajniej ale jednak ładować takie dane, w RISC może być z tym problem. Zawsze warto rzucić okiem na rozmiar całej struktury, powinien uwzględniać wyrównanie.

Pierwsza rzecz, która przyszła mi do głowy to modele pamięci. Coś czego nie widziałem od czasów pierwszych zabaw z kompilatorami pod DOS-em. Krótko mówiąc kompilator miał do wyboru z góry kilka predefiniowanych modeli, które różniły się ilością pamięci jaka była do dyspozycji w aplikacji. Możliwe, że kompilator dla tej platformy stosuje coś podobnego aby ułatwić sobie zarządzanie, warto byłoby przejrzeć dobrze dokumentację.

Możliwe też, że na tej cudacznej platformie da się jednak wycisnąć trochę ekstra wolnej pamięci. Często dla redukcji kosztów pamięć jest tylko jedna  i dzielona między różne peryferia, czasami np. GPU mobilne mają na stałe zablokowany pewien obszar pamięci i jego wielkość da się skonfigurować podczas rozruchu.

Offline Xender

  • Użytkownik

  • +1
# Listopad 03, 2015, 08:35:07
Nierzadkim przypadkiem jest wyrównywanie np. liczby zmiennoprzecinkowych do 4,
Brzmi normalnie, KK. już o tym wspomniał.
Nawet na x86 się tak wyrównuje.

32 lub więcej bajtów.
Nie brzmi wiarygodnie. Źródło?

Do >=32 bajtów to np. się wyrównuje całe vertexy na GPU, nie pojedyncze zmienne.
Na to IIRC nie ma reguły (co GPU to inaczej), a sprawa też dotyczyła PC, nie wiem jak konsol.
« Ostatnia zmiana: Listopad 03, 2015, 08:37:14 wysłana przez Xender »

Offline hashedone

  • Użytkownik

  • +2
# Listopad 03, 2015, 10:50:48
Do >=32 bajtów to np. się wyrównuje całe vertexy na GPU, nie pojedyncze zmienne.
Tam gdzie pamięci brakuje (np. embeded), tam nawet vertexów się nie wyrównuje - jedynie całe tablice vertexów. Nawet na potrzeby instrukcji sse wyrównanie to max jakieś 16 bajtów (4 słowa po 4 bajty - chociaż mogę sobie wyobrazić na maszynie 64-bitowej wyrównanie do 4 słów po 8 bajtów właśnie dla operacji sse - i krótki research to potwierdza, Intel dopiero w 2010 roku udostępnił w swoich procesorach 256 bitowe rejestry na potrzeby sse - a więc powiedzmy że może wtedy opłacało by się cokolwiek wyrównać do tych 32 bajtów, ale tak na prawdę w środku siedzą cztery zmienne, każda wyrównana najpewniej do 8).

=== EDIT ===

Pytanie nie dawało mi spokoju - zrobiłem research mały jak to jest ze zmiennymi zmiennoprzecinkowymi. No i znalazłem to: http://stackoverflow.com/questions/12938828/what-is-the-required-alignment-of-long-double-in-64-bit-linux-mac-and-others. Z tego wynika, że na 64 bitowej maszynie, faktycznie wyrównanie jednego typu zmiennoprzecinkowego jest spore - mianowicie long double jest wyrównany do 16 bajtów. Ale long double to bodajże 80-bitowa zmienna na tej platformie, a więc wyrównanie 10 bajtowych danych do 16 bajtów brzmi całkiem racjonalnie. Pytanie tylko: kto używa long double gdziekolwiek? Naukowcy? Bo mi to się wydaje że jak brakuje pamięci to się używa tylko floatów - a te są już wszędzie wyrównane do 32, ale BITów (a więc 4 bajtów) - nie znalałem żadnego źródła które by inaczej traktowało, próbowałem :(
« Ostatnia zmiana: Listopad 03, 2015, 11:39:41 wysłana przez hashedone »

Offline sebas86

  • Użytkownik

  • +1
# Listopad 04, 2015, 01:09:11
Niestety nic nie wiadomo na temat struktur jakie używa autor pytania ani o architekturze, więc ciężko oszacować potencjalny wpływ. Zakładałbym najgorsze i pod tym kontem przeszukiwał dokumentacje.

Offline Dab

  • Redaktor
    • blog

  • +2
# Listopad 04, 2015, 02:29:13
Cytuj
Intel dopiero w 2010 roku udostępnił w swoich procesorach 256 bitowe rejestry na potrzeby sse - a więc powiedzmy że może wtedy opłacało by się cokolwiek wyrównać do tych 32 bajtów, ale tak na prawdę w środku siedzą cztery zmienne, każda wyrównana najpewniej do 8).

Są instrukcje które wymagają wyrównania do 32 bajtów. Np. VMOVAPS:
Cytuj
When the source or destination operand is a memory operand, the operand must be aligned on a 16-byte (128-bit version) or 32-byte (VEX.256 encoded version) boundary or a general-protection exception (#GP) will be generated.

Offline Xender

  • Użytkownik

  • +1
# Listopad 04, 2015, 09:49:41
@Dab - O, dobrze wiedzieć. Chociaż same rejestry też są 128 lub 256-bitowe, czyli odpowiednio 16 lub 32-bajtowe.

Czyli generalna reguła, że zmienną przeważnie wyrównuje się do tylu bajtów, ile ona sama ma, sprawdza się i tutaj.

Offline Lerhes

  • Użytkownik

# Listopad 04, 2015, 13:45:23
Dziękuję za wszystkie uwagi i pomysły.

Na razie udało mi się zrobić jeden eksperyment: Zmieniłem domyślny padding z 4 bajtów na 1 bajt, i "zyskałem" 26 mb pamięci. Nie jest źle, aczkolwiek szału nie ma.
Jeżeli chodzi o inne opcje kompilacji, czy możliwości samego systemu czasu rzeczywistego - w te aspekty jeszcze się nie zagłębiłem.

Oczywiście, zawsze pozostaje pytanie, czy te wszystkie globalne struktury są mi potrzebne i czy nie dało by się przeprojektować kodu tak, żeby ograniczyć ich liczbę - tutaj mam już pewne sukcesy, ale nadal czeka mnie sporo pracy.

Dziękuję jeszcze raz za pomoc.
Lerhes