Ładowanie danych z dysku do RAM - optymalizacja

0

Opis problemu:
Mam bardzo dużo danych, które chcę analizować wielokrotnie tzn. po analizie wszystkich danych będę je analizował ponownie pod innym kątem. Jest ich kilka GB! Duże ryzyko, że wszystkie nie zmieszczą mi się do RAM-u! Dane są dobrze poukładane w pliku (nie ma żadnych dziur etc.)

Pytanie:
Jak wydajnościowo najlepiej rozwiązać problem ładowania danych do pamięci?
Co byście polecili?
Czy dane lepiej trzymać w pliku czy w jakiejś bazie (ew. jakiej)?
Pod jakimi hasłami szukać podobnych problemów i ich rozwiązań w sieci?

Z problemem spotykam się pierwszy raz więc proszę o wyrozumiałość.
Głównie zależy mi na wydajności rozwiązania!

Z góry dzięki za pomoc!

0

Baza też bazuje na plikach przecież, więc myślę, że jeżeli dobrze znasz strukturę tego swojego pliku to żaden dbms nie zoptymalizuje tego tak jak Ty

1

Co byście polecili?

Jaki system? pod Windows jest memory mapped file. Mapujesz plik do przestrzeni adresowej (łatwiej o to w 64-bitowym programie bo od razu możesz zmapować całość, przy 32 bitach jest trochę ciasno) i się nie przejmujesz. Windows sobie zbuforuje tyle ile będzie mógł.

1
  1. Czy musisz je przetwarzać wszystkie naraz? Raczej mało jest takich sytuacji.

  2. Czy dane można jakoś zmniejszyć i przetwarzać w postaci skompresowanej?
    Np. zastosować "drzewo trie"? RLE? ZIP?

  3. Czy możesz podzielić dane na partycje? Np. "ludzie z nazwiskiem na literę A", na literę "B" itd

  4. Czy proces ma do wykonania dużo operacji per jeden rekord? (czyli czy więcej czasu spędza na I/O czy na CPU?)

0
Azarien napisał(a):

Co byście polecili?

Jaki system? pod Windows jest memory mapped file. Mapujesz plik do przestrzeni adresowej (łatwiej o to w 64-bitowym programie bo od razu możesz zmapować całość, przy 32 bitach jest trochę ciasno) i się nie przejmujesz. Windows sobie zbuforuje tyle ile będzie mógł.

Tak, ma to być na Windows-ie.
Dzięki @Azarien za pomoc!

0
vpiotr napisał(a):
  1. Czy musisz je przetwarzać wszystkie naraz? Raczej mało jest takich sytuacji.

  2. Czy dane można jakoś zmniejszyć i przetwarzać w postaci skompresowanej?
    Np. zastosować "drzewo trie"? RLE? ZIP?

  3. Czy możesz podzielić dane na partycje? Np. "ludzie z nazwiskiem na literę A", na literę "B" itd

  4. Czy proces ma do wykonania dużo operacji per jeden rekord? (czyli czy więcej czasu spędza na I/O czy na CPU?)

@vpiotr dzięki za ciekawe pytania! ;-)
ad 1) Założenie jest takie, że biorę jeden rekord -> wykonuję operacje -> pobieram kolejny rekord -> itd. -> kończą się dane -> wracam do początku -> pobieram znowu pierwszy rekord -> analizuję dane -> pobieram kolejny rekord itd.
Przynajmniej takiej wersji nie mogę wykluczyć. W optymistycznej wersji przetwarzam tylko część z tych danych wielokrotnie a po ich przetworzeniu przesuwam się dalej.

ad 2) Kompresja raczej nie wchodzi w grę.

ad 3) Trochę nie rozumiem pytania. Dane są poukładane wg. daty z dokładnością do 1/1000 sekundy. Czy to znaczy: tak? ;-)

ad 4) W zasadzie to odpowiedź jest dwuznaczna. Bo to zależy od rodzaju analiz. Głownie będzie tak, że na wszystkich rekordach będzie stosunkowo niewiele operacji a tylko na części będą poważniejsze obliczenia. Ale trudno mi jednoznacznie odpowiedzieć na to pytanie.
Pytanie jakie można tu zadać to ile operacji musi być wykonywanych na CPU by to się jakoś odniosło do I/O ;-). Zdaje się, że I/O jest dość "wolne" więc podejrzewam, że więcej czasu będzie spędzał na I/O.

1

Co do memory mapped file, to dodam że pod 32-bitowym programem możesz bezpiecznie zamapować do 1 gigabajta (z 2 mogą być problemy).

Tworzysz mapping za pomocą CreateFileMapping, a potem 1-gigowe okienko do tego pliku za pomocą MapViewOfFile.
Przy czym wcale nie oznacza to, że tylko 1 gigabajt pliku może być załadowany do pamięci, a tylko tyle że w danym momencie możesz posiadać wskaźnik do jednego gigabajta zawartości. Jeśli masz np. 8 giga RAM-u to system będzie zarządzał całymi 8 gigami, a ty masz 1-gigowe „okienko” które sobie przesuwasz po pliku.

W programie 64-bitowym MapViewOfFile może objąć cały plik na raz ileby tych gigabajtów nie było, bo przestrzeń adresowa jest wielka.

1

To czytaj sekwencyjnie po x rekordów i je przetwarzaj.

Rozwiązanie 1
Czytaj w osobnym wątku i przetwarzaj to co przeczytałeś - aż do końca pliku (wielowątkowość).

Rozwiązanie 2
Czytaj np. po 1000 rekordów i przetwarzaj je równolegle (np. przy pomocy OpenMP - łatwiejsza wielowątkowość).
Wprowadzenie: http://bisqwit.iki.fi/story/howto/openmp/

Jeśli czas obliczeń na rekordzie przekracza jego średni czas odczytu (po uśrednieniu po całym pliku) to rozwiązanie nr 2 będzie lepsze.
Jeśli czas obliczeń jest <= od czasu wczytania to lepsze będzie rozwiązanie 1.
Docelowo można pewnie je połączyć.

Memory Mapped Files (rozwiązanie 0 - od niego bym zaczął) można wykorzystać na Windows i Linux, bezpośrednio lub przez Boost.

0

Jeszcze raz bardzo wam dziękuję za pomoc!
Jak zacznę się w to wdrażać to najwyżej będę dopytywał o szczegóły ;-)
pozdrawiam!

0

Witam ponownie.
Poczytałem już trochę o tym memory mapped file i zastanawia mnie taka kwestia: jeśli mam dysk SSD na którym mam system operacyjny (Win7) oraz dysk HDD, na którym znajduje się plik z danymi to czy mapując go system utworzy jego "kopię"/przestrzeń virtualną:
a) na dysku na którym jest postawiony system (SSD)
b) na dysku na którym jest plik z danymi (HDD)
c) na dysku na którym jest odpalony program, który mapuje plik?

Z góry dziękuję za pomoc.

2

OS nie będzie tworzył kopii pliku, tylko korzystał z istniejącego. Memory mapped file to powiedzmy taki rodzaj swapa, gdzie wybrany plik jest używany jako plik wymiany.

Jeśli plik czytasz małymi porcjami z losowych miejsc to rób to wielowątkowo. Dzięki temu pozwolisz działać mechanizmowi http://en.wikipedia.org/wiki/Native_Command_Queuing Czy przyniesie on poprawę wydajności zależy pewnie od sprzętu, systemu i sposobu odczytywania pliku.

0
Wibowit napisał(a):

OS nie będzie tworzył kopii pliku, tylko korzystał z istniejącego. Memory mapped file to powiedzmy taki rodzaj swapa, gdzie wybrany plik jest używany jako plik wymiany.

Ok, chyba rozumiem ;-). Dzięki!

0
Wibowit napisał(a):

Jeśli plik czytasz małymi porcjami z losowych miejsc to rób to wielowątkowo. Dzięki temu pozwolisz działać mechanizmowi http://en.wikipedia.org/wiki/Native_Command_Queuing Czy przyniesie on poprawę wydajności zależy pewnie od sprzętu, systemu i sposobu odczytywania pliku.

Raczej będę czytał sekwencyjnie. Poza tym i tak zamierzam korzystać ze wszystkich wątków przy analizach (obliczeniach).
A tak w ogóle to chyba lepiej czytać dużymi porcjami (ale wielokrotnością ziarnistości alokacji (?) czyli 64kb), co nie?
I jeszcze dopytam ;-)

Wibowit napisał(a):

gdzie wybrany plik jest używany jako plik wymiany.

Jako plik wymiany między tym co jest w pliku na dysku twardym a pamięcią RAM - dobrze rozumuję?

2

Raczej będę czytał sekwencyjnie. Poza tym i tak zamierzam korzystać ze wszystkich wątków przy analizach (obliczeniach).
A tak w ogóle to chyba lepiej czytać dużymi porcjami (ale wielokrotnością ziarnistości alokacji (?) czyli 64kb), co nie?

Najlepiej czytać sekwencyjnie i w miarę dużymi porcjami (zbyt duże też są złe, bo na dużą porcję musisz długo czekać - lepiej odczytać średnią, zacząć obliczenia i jednocześnie zacząć czytać drugą). Ale jeżeli musisz czytać (pseudo)losowo i małymi porcjami (powiedzmy, mniej niż megabajt) to warto rozważyć czytanie wielowątkowe.

Zobacz sobie tutaj: http://pclab.pl/art58237-73.html jak Queue Depth (QD) wpływa na szybkość odczytu. Test jest sztuczny, więc w programach użytkowych wyniki mogą być inne, np niewarte zachodu.

Jako plik wymiany między tym co jest w pliku na dysku twardym a pamięcią RAM - dobrze rozumuję?

Tak. Jeśli odpalisz mapowanie pliku do RAMu to wtedy plik będzie obszarem pamięci, ale w RAMie będzie załadowana jego część (potencjalnie całość), bo RAM będzie służył jako bufor (zarówno odczytu jak i zapisu).

Podobnie jak przy swapie, możesz mieć dużo większy mapowany plik niż rozmiar RAMu. Np mając 256 MiB RAMu możesz mieć 1 GiB swapa lub alternatywnie możesz zmapować sobie 1 GiB plik do przestrzeni adresowej.

0
Wibowit napisał(a):

Najlepiej czytać sekwencyjnie i w miarę dużymi porcjami (zbyt duże też są złe, bo na dużą porcję musisz długo czekać - lepiej odczytać średnią, zacząć obliczenia i jednocześnie zacząć czytać drugą). Ale jeżeli musisz czytać (pseudo)losowo i małymi porcjami (powiedzmy, mniej niż megabajt) to warto rozważyć czytanie wielowątkowe.

Ahh, jeszcze muszę dopytać dla wewnętrznego spokoju - sorka ;-).

A jeśli to będzie w programie na 64 bit-ach to rozumiem, że mapuję cały plik i system sam będzie sobie dobierał optymalną wielkość porcji? ;-)

Natomiast jeśli mam dużo więcej RAMu niż wielkość pliku (np. plik ma 4GB a ja mam 8GB) to po zmapowaniu wszystko wyląduje w RAM-ie i będzie chodzić tak samo jak gdybym wczytał to tradycyjną metodą (nie będzie żadnych ograniczeń / dodatkowych narzutów wynikających z mappowania)?

Z góry jeszcze raz dziękuję i przepraszam za tyle pytań.

2

Zmapowanie pliku nie daje gwarancji, że cokolwiek pojawi się w RAMie. Dopiero dobranie się do konkretnego zmapowanego adresu w RAMie da gwarancję, że kawałek pliku odpowiadający temu adresowi zostanie załadowany (w końcu musi, inaczej cała zabawa nie miałaby sensu). Jeżeli w RAMie będzie brak odpowiedniej strony z danymi, to procesor wywoła przerwanie które zostanie obsłużone przez OS, który załaduje dane do strony w pamięci i przekaże sterowanie z powrotem do programu. Ziarnistość odczytu to rozmiar jednej strony RAMu, czyli przy x86 to zwykle 4 KiB. System jednak może sobie ładować pamięć z wyprzedzeniem tak jak sobie zdecyduje i chyba ciężko tym sterować. System może sobie w dowolnym momencie zrzucić dowolną stronę na dysk albo ją załadować, ale w ogólności, jeżeli plik nie jest jakoś podwójnie mapowany albo np mapowany i czytany/ zapisywany tradycyjnie, to efekty tych odczytów i zapisów stron pamięci są takie, że dostajesz dokładnie te dane co są w pliku i jednocześnie w pliku są zapisywane (przy zrzucie strony na dysk) wszystkie zmiany, których dokonałeś w zmapowanej przestrzeni adresowej.

Jako ciekawostkę dodam, że mechanizm mapowania plików do pamięci jest wykorzystywany przy odpalaniu plików wykonywalnych. Nawet jeśli twój EXEk jest 2-gigabajtowym Hello Worldem, gdzie 99.9% objętości pliku jest zwykle nieużywane, to odpali się w ułamku sekundy, bo kawałek EXEka wyświetlający Hello Worlda zajmuje np 50 KiB, a wczytanie tego kawałka do RAMu to betka.
Różnica jest chyba (strzelam) tylko taka, że zmiany w RAMie nie są zapisywane z powrotem do EXEka.

1 użytkowników online, w tym zalogowanych: 0, gości: 1