Mam program operujący na dużych plikach. Im więcej wczyta do pamięci na
raz tym szybciej zadziała. Ale nie może więcej czytać bo albo pamięć się
skończy albo zacznie się używania swapa.
Odczyt ilości wolnej pamięci testowałem pod Linuksem i dawał śmiesznie
małe wartości, bo pamięć była wykorzystana niemal w całości np. przez
bufory plikowe. Niektóre rzeczy można wyrzucić, nawet niektóre programy.
Choć nie wiem, gdy jest otwarty VirtualBox.
Można też odczytać wielkość pamięci fizycznej i wykorzystać np. 70%?
(choć może być otwarty wirtualny system zajmujący 50% pamięci)
a może lepiej niech to użytkownik decyduje w Ini. Choć najlepiej było by
to automatyczne, gdy zaczyna korzystać ze swapa, zmniejszyć.

do góry

A co to jest "wielkość użytecznej wolnej pamięci" w programie, który chodzi na...
maszynie wirtualnej typu VirtualBox?

Pytasz o coś, co ma zupełnie wirtualny charakter. W dodatku na platformach, których
projektanci od dawna robią co tylko mogą, żeby Cię od tych rzeczy jak najdalej
odsunąć. Z biegiem czasu te pojęcia przestają nawet mieć fizyczny sens, więc pytanie
jest coraz bardziej bezprzedmiotowe.

Jak chcesz mieć dostęp do fizycznego sprzętu, to pisz programy bezpośrednio na ten
fizyczny sprzęt. W ramach kompromisu, być może funkcje mapujące pamięć mają jakieś
opcje, które pozwalają kontrolować stopień "nieruszalności" jakiegoś bloku albo
zakresu adresów - może się wtedy jednak okazać, że będziesz musiał tam samemu
zorganizować sobie alokację.

--
Maciej Sobczak * http://www.inspirel.com

do góry

W dniu 03.02.2017 o 13:51, Maciej Sobczak pisze:
> Jak chcesz mieć dostęp do fizycznego sprzętu, to pisz programy bezpośrednio na ten
fizyczny sprzęt. W ramach kompromisu, być może funkcje mapujące pamięć mają jakieś
opcje, które pozwalają kontrolować stopień "nieruszalności" jakiegoś bloku albo
zakresu adresów - może się wtedy jednak okazać, że będziesz musiał tam samemu
zorganizować sobie alokację.

Chodzi o to: działam na wielkich plikach, lepiej bym używał tyle pamięci
ile mogę aby było szybciej.
Przykład: sortowanie zewnętrzne 3-plikowe lub większa ilość plików. Aby
zmniejszyć zdecydowanie ilość przerzucań tym plikiem, przepuszczam przez
stóg, jak największy, tyle ile mam pamięci, Wtedy plik składa się z
dużych kawałków posortowanych.

do góry

On 2017-02-03, Borneq <b...@a...hidden.pl> wrote:
> W dniu 03.02.2017 o 13:51, Maciej Sobczak pisze:
>> Jak chcesz mieć dostęp do fizycznego sprzętu, to pisz programy bezpośrednio na ten
fizyczny sprzęt. W ramach kompromisu, być może funkcje mapujące pamięć mają jakieś
opcje, które pozwalają kontrolować stopień "nieruszalności" jakiegoś bloku albo
zakresu adresów - może się wtedy jednak okazać, że będziesz musiał tam samemu
zorganizować sobie alokację.
>
> Chodzi o to: działam na wielkich plikach, lepiej bym używał tyle pamięci
> ile mogę aby było szybciej.
> Przykład: sortowanie zewnętrzne 3-plikowe lub większa ilość plików. Aby
> zmniejszyć zdecydowanie ilość przerzucań tym plikiem, przepuszczam przez
> stóg, jak największy, tyle ile mam pamięci, Wtedy plik składa się z
> dużych kawałków posortowanych.

Robisz głupio. Do tego używa się mmap(2), a nie wykrywania ilości wolnej
pamięci. Wtedy przydzielaniem RAM-u martwi się system operacyjny.

--
Secunia non olet.
Stanislaw Klekot

do góry

W dniu 03.02.2017 o 15:15, Stachu 'Dozzie' K. pisze:
> Robisz głupio. Do tego używa się mmap(2), a nie wykrywania ilości wolnej
> pamięci. Wtedy przydzielaniem RAM-u martwi się system operacyjny.

Czyli mapuję cały plik i sortuję go "w pamięci"? Ale były algorytmy
zewnętrzne minimalizujące ilość odwołań do dysku. Chyba nie warto
zamapować całego pliku a potem robić quickSorta przemieszczającego
elementy z jednego końca pliku na inny.

do góry

On 2017-02-03, Borneq <b...@a...hidden.pl> wrote:
> W dniu 03.02.2017 o 15:15, Stachu 'Dozzie' K. pisze:
>> Robisz głupio. Do tego używa się mmap(2), a nie wykrywania ilości wolnej
>> pamięci. Wtedy przydzielaniem RAM-u martwi się system operacyjny.
>
> Czyli mapuję cały plik i sortuję go "w pamięci"? Ale były algorytmy
> zewnętrzne minimalizujące ilość odwołań do dysku. Chyba nie warto
> zamapować całego pliku a potem robić quickSorta przemieszczającego
> elementy z jednego końca pliku na inny.

A te algorytmy to wymagają deskryptora pliku, inaczej w magiczny sposób
nie działają?

--
Secunia non olet.
Stanislaw Klekot

do góry

On 03.02.2017 15:15, Stachu 'Dozzie' K. wrote:
> On 2017-02-03, Borneq <b...@a...hidden.pl> wrote:
>> W dniu 03.02.2017 o 13:51, Maciej Sobczak pisze:
>>> Jak chcesz mieć dostęp do fizycznego sprzętu, to pisz programy bezpośrednio na
ten fizyczny sprzęt. W ramach kompromisu, być może funkcje mapujące pamięć mają
jakieś opcje, które pozwalają kontrolować stopień "nieruszalności" jakiegoś bloku
albo zakresu adresów - może się wtedy jednak okazać, że będziesz musiał tam samemu
zorganizować sobie alokację.
>>
>> Chodzi o to: działam na wielkich plikach, lepiej bym używał tyle pamięci
>> ile mogę aby było szybciej.
>> Przykład: sortowanie zewnętrzne 3-plikowe lub większa ilość plików. Aby
>> zmniejszyć zdecydowanie ilość przerzucań tym plikiem, przepuszczam przez
>> stóg, jak największy, tyle ile mam pamięci, Wtedy plik składa się z
>> dużych kawałków posortowanych.
>
> Robisz głupio. Do tego używa się mmap(2), a nie wykrywania ilości wolnej
> pamięci. Wtedy przydzielaniem RAM-u martwi się system operacyjny.

Nie bardzo rozumiem, co mu zmapowanie plików do pamięci pomoże.
Jeśli odpali na tym qsorta najlepszy system operacyjny mu nie
pomoże ;-)

Pewnie chciałby posortować małe porcje, a potem mergesort
na plikach. Ta drugą cześć bez problemu można robić jak
sgerujesz, ale przy pierwszej, wypadałoby wiedzieć, ile się zmieści.
Jeśli zmieści się dwa razy więcej, będzie jeden przebieg mniej.

OK, co prawda mergesort puszczony naiwnie spowoduje pełne
log_2 (N) odczytów z dysku, to mergesort zrobiony w kolejnośćipostorder

sortuj( a,b ){
mid = a+(b-a)/2;
sortuj (a,mid);
sortuj (mid,b);
scal(a,mid,b)
}

przy dobrym automatycznym zarzadzaniu pamięcią (a nawety głupim
'wywalaj wg kolejności użycia') da wynik przyzwoity.

Ale nie idaealny, bo muszę mieć zmapowane w p[amięci wejscie i wyjscie,
trace wiec jeden przebieg.


Z drugiej strony to problem istotny tylko przy słąbych algorytmach.
Jeśli skorzystać z 256 plików, to 65 terabajtów posortuję za pomocą
gigabajta w trzech seriach odczyt/zapis ;-)

pzdr
bartekltg

do góry

W dniu 03.02.2017 o 18:59, bartekltg pisze:
> Z drugiej strony to problem istotny tylko przy słąbych algorytmach.
> Jeśli skorzystać z 256 plików, to 65 terabajtów posortuję za pomocą
> gigabajta w trzech seriach odczyt/zapis ;-)

A tego nie znałem. Stosowałem
http://zofia.kruczkiewicz.staff.iiar.pwr.wroc.pl/wyk
lady/ALG/Algusm5_1.pdf
http://zofia.kruczkiewicz.staff.iiar.pwr.wroc.pl/wyk
lady/ALG/Algusm5_2.pdf
http://zofia.kruczkiewicz.staff.iiar.pwr.wroc.pl/wyk
lady/ALG/Algusm5_3.pdf

pliki o rozmiarach wynikających z ciągu Fibonacciego któregoś rzędu.
Przy czym te pliki zachowywały się jak kolejka, nie można było usunąć z
początku (przydałyby się dziury plikowe) to wzrastały do co najmiej
wielkości sortowanego pliku. Więc metoda 3 plikowa wymaga 3 krotnie
więcej dysku niż ten plik, 5 - plikowa mniej przebiegów ale więcej dysku.
Co zrobić aby te 256 plików nie zajmowało 256*65 TB = 17 Petabajtów dysku?

do góry

W dniu 03.02.2017 o 19:35, Borneq pisze:
> więcej dysku niż ten plik, 5 - plikowa mniej przebiegów ale więcej dysku.
> Co zrobić aby te 256 plików nie zajmowało 256*65 TB = 17 Petabajtów dysku?

Co prawda, teoretycznie to 65 TB rozłoży się na 256 plików po 256 GB ale
będą dopisywać na koniec a wskaźnik początku będzie się przesuwał,
Trochę przesadziłem, tak jest dla 3 czy 5 plików, gdzie jest więcej
przebiegów, może te 256 plików nie zdąży być tak wielkie jak wynikowy.
Choć jeden z tych 256 osiągnie pełną wielkość, inne będą mniejsze
jedynie o czynnik fibonacciego któregoś rzędu

do góry

On 03.02.2017 19:35, Borneq wrote:
> W dniu 03.02.2017 o 18:59, bartekltg pisze:
>> Z drugiej strony to problem istotny tylko przy słąbych algorytmach.
>> Jeśli skorzystać z 256 plików, to 65 terabajtów posortuję za pomocą
>> gigabajta w trzech seriach odczyt/zapis ;-)
>
> A tego nie znałem. Stosowałem
> http://zofia.kruczkiewicz.staff.iiar.pwr.wroc.pl/wyk
lady/ALG/Algusm5_1.pdf
> http://zofia.kruczkiewicz.staff.iiar.pwr.wroc.pl/wyk
lady/ALG/Algusm5_2.pdf
> http://zofia.kruczkiewicz.staff.iiar.pwr.wroc.pl/wyk
lady/ALG/Algusm5_3.pdf

Mistrzostwo dydaktyki to nie jest.

> pliki o rozmiarach wynikających z ciągu Fibonacciego któregoś rzędu.
> Przy czym te pliki zachowywały się jak kolejka, nie można było usunąć z
> początku (przydałyby się dziury plikowe) to wzrastały do co najmiej
> wielkości sortowanego pliku.

A to w jakimkolwiek pliku (systemie operacyjnym) można przesunąć
poczatek pliku?


> Więc metoda 3 plikowa wymaga 3 krotnie
> więcej dysku niż ten plik, 5 - plikowa mniej przebiegów ale więcej dysku.
> Co zrobić aby te 256 plików nie zajmowało 256*65 TB = 17 Petabajtów dysku?

Masz dwa razy więcej dysku.

Wczytujesz umówiony gigabajt do pamięci, sortujesz, zapisujesz do nowego
pliku.
Masz (rozmiar / 1GB) plików po 1GB.
Kasujesz oryginały.
Robisz merge na 256 plikach na raz.
Masz więc w kolejnych fazach
(rozmiar / 1GB)/265
(rozmiar / 1GB)/256^2
...
pliów.


Jak robisz merge na raz więcej niż jednemu plikowi?

Trzymasz parę(wartość, indeks)
indeks to numer pliku z którego pochodzi wartość.
Na start wypełniasz je jednym elementem z każdego pliku.

Zabierasz parę z wierzchołka kopca, wartosć do pliku wyjściowego,
z pliku indeks wsadzasz do kopca jeden element.



Oczywiście, nie czytasz pliów po elementcuie, tylko je sobie buforujesz
w pamięci. Bufory nie muszą być wcale duże, byle się wygodnie czytało
z dysku.

256 plików wynika raczej z ograniczenia pamięci (przy naszych
załozeniach mamy po 4MB na plik) niż z tego, że kopiec by słabo
działał dla większej liczby.


Tu widzę jakieś wariacje na temat:
http://www.csbio.unc.edu/mcmillan/Media/Comp521F10Le
cture17.pdf
Ładnie, kolorowo, bez traści kodu z którego i tak nie skorzystamy ;-)


pzdr
bartekltg

PS: z drugiego postu nic nie rozumiem.
Chyba jednak mówimy o czym innym ;-)

do góry