Nie wiem, w której kategorii umieścić to pytanie, które jest związane z językiem C+ (opartym na C), algorytmami, ale ta kategoria wydała się najodpowiedniejsza.
Powiedzmy, że mamy program proceduralny bliski programowaniu funkcyjnemu. Program przetwarza jakieś dane określonym algorytmem.
Jeśli te dane przychodzą z zewnątrz i wracają na zewnątrz (jak to się dzieje np. w programach sieciowych), to można regulować rozmiar buforu danych przychodzących i wychodzących. Jeśli natomiast algorytm operuje na jakichś danych wewnątrz (jak to się dzieje np. w kompilatorach), to wtedy generalnie dane są zapisywane w narastającym rozmiarze w pamięci operacyjnej (aż do czasu wygenerowania pliku pośredniego w przypadku kompilacji).
Czy istnieje jakieś ogólne podejście do regulowania rozmiaru tych danych wewnętrznych, tak by nie zmierzało się do nieskończonego rozmiaru pamięci operacyjnej wymaganego do wykonania algorytmu?
Pamięć może być wymiatana na dysk do pliku wymiany, ale z praktycznych doświadczeń wiem, że takie rozwiązanie jest wolne, nieoptymalne. Można też napisać menedżera zarządzającego pamięcią specyficznie do posiadanych urządzeń (hardware). Ale czy istnieje coś w rodzaju automatycznej regulacji? Jakimi kryteriami się kierować, by nie uzależniać się od sprzętu a algorytm dostosował się do bieżącego stanu systemu?
Można założyć, że jest jakiś minimalny rozmiar pamięci operacyjnej wymagany do uruchomienia danego algorytmu, ale przecież nie wszystko musi przechowywać w pamięci operacyjnej, może część składować w plikach w pamięci nieulotnej albo też może odtwarzać część danych kosztem czasu. I oczywiście mam na myśli pamięć, z której nadal korzysta wewnętrznie, a nie generuje tylko strumień danych.
Poruszam to zagadnienie, ponieważ przygotowałem mechanizm w postaci zmiennych plikowych i chciałbym go stosować w optymalny sposób, by nie tworzyć zależności od starego sprzętu w przyszłości.
overcq napisał(a):
Powiedzmy, że mamy program proceduralny bliski programowaniu funkcyjnemu. Program przetwarza jakieś dane określonym algorytmem.
Chyba mylisz pojęcia. Zazwyczaj (błędnie) za programowanie proceduralne uznaje się programowanie impeartywne a to jest całkowitym zaprzeczeniem programowania funkcyjnego. Programowanie funkcyjne to taki paradygmat, gdzie nie masz zmiennych i poleceń tylko funkcje takie jak w matematyce, które zamieniają wejście na wyjście
Czy istnieje jakieś ogólne podejście do regulowania rozmiaru tych danych wewnętrznych, tak by nie zmierzało się do nieskończonego rozmiaru pamięci operacyjnej wymaganego do wykonania algorytmu?
Nie. Wszystko zależy od algorytmu. Jak ta dodatkowa pamięc to jakiś cache to możesz zaimplementować w tym cachu, że jak przekroczysz limit to dane znikają i trzeba je zaczytać. Jeśli dane są konieczne to oczywiście nic nie zrobisz poza zmianą w algorytmie
Ten przypadek z artykułu jest dziwny. Po co czytać cały plik? Zazwyczaj czyta się plik strumieniowo, bo wtedy nie jesteś uzależniony od rozmiaru pliku wejściowego. Z drugiej strony takie czytanie danych/metadanych z pliku zazwyczaj jest dobrze cachowane przez system operacyjny. Tak czy owak: twój algorytm potrzebuje jakiegoś cacha (skoro nie potrzebuje tych danych cały czas). Bez informacji na temat jego działa jest ciężko powiedzieć co Ci potrzeba
Czy istnieje jakieś ogólne podejście do regulowania rozmiaru tych danych wewnętrznych, tak by nie zmierzało się do nieskończonego rozmiaru pamięci operacyjnej wymaganego do wykonania algorytmu?
poruszasz bardzo szeroki temat i w sumie nie wiadomo, co masz konkretnie na myśli.
np.
to wtedy generalnie dane są zapisywane w narastającym rozmiarze w pamięci operacyjnej (aż do czasu wygenerowania pliku pośredniego w przypadku kompilacji).
rozwiązaniem na powyższy problem może być garbage collector, ale z drugiej strony nie wszystkie języki mają garbage collector, poza tym twoje założenie dane są zapisywane w narastającym rozmiarze w pamięci operacyjnej może być czasem prawdziwe, a czasem nie. No chyba, że mówisz o jakimś konkretnym algorytmie, który faktycznie żre pamięć jak cholera i nigdy jej nie zwalnia.
@slsy:
Miałem na myśli programowanie proceduralne tylko kierujące się ku funkcyjnemu. Tak jak było określone w rozdziale książki Język C++ (nie pamiętam autora).
Dzięki za uwagę o cache. Właśnie w menedżerze plików mam taki mechanizm ładowania stronami pamięci. Tylko kwestia zrozumienia, jak to zrobić optymalnie. Ale zależnie od algorytmu…
Co do artykułu, to tam nie ma czytania i pisania całego pliku, lecz swobodny dostęp do danych w tablicy składowanej w pliku. I właśnie nasunęło mi się, że dane można odpowiednio układać blisko siebie (co jest oczywiście znane… i rzadko stosowane?) w zależności od wspólnego użycia, by opłacało się je zapisywać do pliku.
@LukeJL:
Problemem jest pamięć, która jest nadal używana, np. podczas kompilacji (optymalizacji), i brak jej zwolnienia nie wynika z jej porzucania bez zwalniania. Chociaż kto wie, czy nie mogłaby być szybciej zwolniona.
Pamięcią zarządzać może: aplikacja (jeśli implementujesz własne zarządzanie zaalokowanego na starcie obszaru), biblioteka C, inne biblioteki, system operacyjny. Czasem osobno, czasem razem z innymi fragmentami. Nie ma uniwersalnej metody przenośnej na każdą platformę sprzętową czy programową która ci zagwarantuje takie samo działanie wszędzie. Nawet ten sam system operacyjny może z czasem zmienic podejście do zarządzania pamięcią w przyszłych wersjach.
W tym temacie pisałem wyłącznie o zarządzaniu pamięcią u źródła czyli w aplikacji. Zanim system operacyjny zablokuje możliwość wykonywania programu lub innych programów.
Zastanawiałem się, czy możliwe jest efektywne wykonywanie programu, który alokuje dużo pamięci podczas działania, nie w strumieniu danych (który można przesyłać dalej), np. kompilator. Nie zrobiłem jeszcze prototypu takiego programu, ale przygotowałem procedury plikowe do takiego użycia, zapisu danych na dysk. Dlatego pytałem o najoptymalniejsze zarządzanie takimi danymi przechowywanymi poza pamięcią operacyjną.
Jak widać mały odzew, ale zagadnienie też niepopularne w dzisiejszych urządzeniach, którym raczej dokłada się nową pamięć, i losowo usuwa procesy w przypadku jej braku.
Jeśli masz na mysli: start programu -> program prosi o blok pamięci -> system (albo bezpośrednio kernel lub pośrednio przez biblioteki) obsługuje i przydziela -> program dostał przydział -> program implementuje obsługę zarządzania blokiem i nie komunikuje się w tej sprawie z nikim aż do końca działania. To odpowiedź brzmi – jeszcze jak. Tak działają niektóre demony usług, silniki gier czy inne wysoko wydajne aplikacje. Przeskakuje się w ten sposób konieczność czekania na obsłużenie odwołań do bibliotek i wywołań systemowych i zapewnia gwarancję że z góry założona ilość pamięci będzie zawsze zapewniona w czasie działania programu.
Inne rozwiązania oznaczają, że to nie program zarządza pamięcią. Wywołania np. malloc(3), free(3) itp nie znacza, że program ma cokolwiek do powiedzenia w temacie zarządzania pamięcią. On tylko grzecznie prosi zewnętrznego zarządcę pamięci o przydział a potem zgłasza, że już danego przydziału nie potrzebuje.
Czy i kiedy (jeśli w ogóle) zewnetrzny w stosunku do niego zarządca udostępni ten obszar dalej (lub ponownie temu samemu programowi) to już jego słodka tajemnica o której program nie ma pojecia.
Na czym jest pamięć jaką system przydzieli aplikacji - zależy od systemu. Możesz sobie tworzyć dodatkowe obszary leżące poza tym co system traktuje jako pulę do przydziału. Możesz sobie zaimplementować własną pamięć wirtualną w programie która będzie warstwą kleju między pamiecią wirtualną systemu operacyjnego (którą zazwyczaj tworzą RAM i obszar wymiany na dysku na desktopach, w urządzeniach embeded mogą tam dochodzić jakieś banki pamięci czy kości FLASH) i czymkolwiek chcesz co potrafi przechowywać na stałe lub ulotnie bity informacji - pliki, urzędzania znakowe i blokowe i inne wynalazki jakie obsługuje system operacyjny lub do jakich potrafi wyłać jakkolwiek dane. Może tutaj wchodzić nawet zdalny serwer.
Co do wydajności, szybkości itd. to już zależy jaki to sprzęt i jakie są czasy dostępu i jakie zastosujesz algorytmy. Nie ma jednego genialnego najlepszego na świecie algorytmu zarządzania. Jedne będa gorsze inne lepsze zależnie od sprzętu na którym mają działać, typowego obszaru alokacji, częstotliwości wywołań itd.
Jeśli coś pominąłem, niezrozumiałem lub masz dalsze pytania - to mogę rozwinąć jeśli będę w stanie. Piszę tyle na raz bo czytając twój post niestety nie mam zielonego pojęcia co masz na myśli. To znaczy mogę potencjalnie mieć, ale by to wymagało założenia, że chcesz zaimplementować coś zakrawającego o zautomatyzowane przewidywanie z góry przez system operacyjny ile będzie potrzebne pamięci na wykonanie alorytmu. Jeśli tak - to musisz uściślić realia w jakich ma to działać i przyjete limity lub ich brak. Wtedy bedzie jakieś pole do dalszej dyskusji.