🚀 go-pugleaf

Lucifer wrote:

> Zastanawia mnie czy jest mozliwe cos takiego:
>
> odsmiecanie bez zadnego zliczania odniesien, popsrostu kompilator
> 'zgaduje', w ktorym miejscu programu nalezy zwolnic pamiec, albo wrzucic
> go do kolejki i wywalic po czasie kilka na raz.
>

Zwykle raczej nie robi sie zadnego zliczania odniesien, bo moze byc np. tak
ze zmienna A odnosi sie do zmiennej B, a zmienna B do A, chociaz o obu
juz chcielibysmy zapomniec.

Robi sie raczej jakies przechodzenie grafu odniesien, zeby zobaczyc, do
ktorych
obiektow mozna dojsc.

Tomek

Lucifer napisał:
> Zastanawia mnie czy jest mozliwe cos takiego:
> 
> odsmiecanie bez zadnego zliczania odniesien, popsrostu kompilator 
> 'zgaduje', w ktorym miejscu programu nalezy zwolnic pamiec, albo wrzucic 
> go do kolejki i wywalic po czasie kilka na raz.
>
> Wydaje mi sie, ze nie, ale moze jednak. Jesli nie dla wszystkich 
> alokacji to moze dla czesci, np: obiekt alokowany w bloku kodu (np: w 
> funkcji, w petli), ktory w dodatku nie jest wyprowadzany na zewnatrz 
> (nie jest zwracany przez funkcje, w petlach nie jest np: dodawany do 
> jakiejs tablicy zaalokowanej w nadrzednym bloku lub gdziekolwiek indziej).
>
> W skrocie obiekty sa usuwane z pamieci bez zliczania odniesien.

Dobrze kombinujesz :)

Zainteresuj się MLKit'em: http://www.it-c.dk/research/mlkit/

pozdrawiam,
tomek

-- 
.signature: Too many levels of symbolic links

>
> Wydaje mi sie, ze nie, ale moze jednak. Jesli nie dla wszystkich
> alokacji to moze dla czesci, np: obiekt alokowany w bloku kodu (np: w
> funkcji, w petli), ktory w dodatku nie jest wyprowadzany na zewnatrz
> (nie jest zwracany przez funkcje, w petlach nie jest np: dodawany do
> jakiejs tablicy zaalokowanej w nadrzednym bloku lub gdziekolwiek indziej).

Zwykle jak juz tworzymy obiekt, to wywolujemy jakas funkcje podajac go jej
jako parametr. No i nie wiadomo, czy ta funkcja gdzies tego obiektu nie
"schowa".

Jesli natomiast chodzi o jezyki imperatywne, to jesli tworzymy zmienna i
przekazujemy
ja tylko przez kopiowanie, to mozna rzeczywiscie przydzielic ja sobie na
stosie.

Tomek

"Lucifer" <przemek@nospam.pa55.bytom.sdi.tpnet.pl> wrote:

> Zastanawia mnie czy jest mozliwe cos takiego:
>
> odsmiecanie bez zadnego zliczania odniesien, popsrostu kompilator
> 'zgaduje', w ktorym miejscu programu nalezy zwolnic pamiec, albo
> wrzucic go do kolejki i wywalic po czasie kilka na raz.

[...]

Nie wiem, czy dobrze rozumiem, ale...


1. Nie ma zadnego zliczania odniesien (a przynajmniej ja nie slyszalem o
jakiejkolwiek zyjacej implementacji kozystajacej z tej techniki
odsmiecania [*]).

2. Tak - czasami mozna przewidziec w ktorym miejscu moze zostac zwolniona
pamiec i z miejsca wykorzystac ja ponownie. Takie cus nazywa sie "Compile
Time Garbage Collector" i poczytac o tym mozna w papierach od Mercury'ego.



[*] Paul Wilson, "Uniprocessor Garbage Collection Techniques" - do
poduszki

mp

"Tomek Czajka" <tczajka@mimuw.edu.pl> wrote:

> Jesli natomiast chodzi o jezyki imperatywne, to jesli tworzymy zmienna i
> przekazujemy
> ja tylko przez kopiowanie, to mozna rzeczywiscie przydzielic ja sobie na
> stosie.

W ogole nie rozumiem. Mozesz to jakos rozwinac ?

mp

Tomek Czajka wrote:
> Lucifer wrote:
>
>>Zastanawia mnie czy jest mozliwe cos takiego:
>>
>>odsmiecanie bez zadnego zliczania odniesien, popsrostu kompilator
>>'zgaduje', w ktorym miejscu programu nalezy zwolnic pamiec, albo wrzucic
>>go do kolejki i wywalic po czasie kilka na raz.
> 
> Zwykle raczej nie robi sie zadnego zliczania odniesien, bo moze byc np. tak
> ze zmienna A odnosi sie do zmiennej B, a zmienna B do A, chociaz o obu
> juz chcielibysmy zapomniec.
> 
> Robi sie raczej jakies przechodzenie grafu odniesien, zeby zobaczyc, do
> ktorych
> obiektow mozna dojsc.

Nie bardzo rozumiem. Co znaczy, ze A odnosi sie do B, A jest jakas 
struktura ktora zawiera B (lub na odwrot)? Jesli A i B sa ze soba w 
jakiejkolwiek relacji to zliczanie odniesien wydaje mi sie calkiem 
mozliwe, ale niezbyt efektywne.

-- 
Lucifer

Tomasz Zielonka wrote:

> Zainteresuj się MLKit'em: http://www.it-c.dk/research/mlkit/

Dzieki, poczytam.. Jakie sa wogole rodzaje odsmiecaczy, jak je mozna 
podzielic i scharakteryzowac?

-- 
Lucifer

Tomek Czajka wrote:
>>Wydaje mi sie, ze nie, ale moze jednak. Jesli nie dla wszystkich
>>alokacji to moze dla czesci, np: obiekt alokowany w bloku kodu (np: w
>>funkcji, w petli), ktory w dodatku nie jest wyprowadzany na zewnatrz
>>(nie jest zwracany przez funkcje, w petlach nie jest np: dodawany do
>>jakiejs tablicy zaalokowanej w nadrzednym bloku lub gdziekolwiek indziej).
> 
> 
> Zwykle jak juz tworzymy obiekt, to wywolujemy jakas funkcje podajac go jej
> jako parametr. No i nie wiadomo, czy ta funkcja gdzies tego obiektu nie
> "schowa".

Nie wiadomo jesli kompilator generuje bezposrednio asemblera (w 
przypadku kompilacji do natywnego kodu). Jesli np: generowalby cos 
jeszcze posredniego - cos w czym zliczalby ilosc uzyc (i skutecznie 
eliminowalby martwy, nieuzywalny kod i wogole wkladalby do takiego 
rezultatu mnostwo innych informacji) to chyba byloby to mozliwe.

> Jesli natomiast chodzi o jezyki imperatywne, to jesli tworzymy zmienna i
> przekazujemy
> ja tylko przez kopiowanie, to mozna rzeczywiscie przydzielic ja sobie na
> stosie.

To chyba niezbyt efektywnie wychodzi (duze obiekty na stosie) w 
przypadku zwracania.

-- 
Lucifer

Lucifer napisał:
> Tomek Czajka wrote:
>
>> Zwykle raczej nie robi sie zadnego zliczania odniesien, bo moze byc np. tak
>> ze zmienna A odnosi sie do zmiennej B, a zmienna B do A, chociaz o obu
>> juz chcielibysmy zapomniec.
> 
> Nie bardzo rozumiem. Co znaczy, ze A odnosi sie do B, A jest jakas 
> struktura ktora zawiera B (lub na odwrot)? Jesli A i B sa ze soba w 
> jakiejkolwiek relacji to zliczanie odniesien wydaje mi sie calkiem 
> mozliwe, ale niezbyt efektywne.

Jeśli w grafie odwołań występują cykle, samo zliczanie odniesień nie
wystarcza.

Przykład: W bibliotece Boost dla C++ są sprytne-wskaźniki zliczające
odniesienia - boost::shared_ptr<T>. Nie są one odporne na cykle:

  #include <boost/shared_ptr.hpp>
  #include <iostream>

  struct A
  {
      boost::shared_ptr<A> aptr;
      A() { std::cout << "A()" << std::endl; }
      ~A() { std::cout << "~A()" << std::endl; }
  };

  int main()
  {
      boost::shared_ptr<A> ap (new A());
      ap->aptr = ap; // Skompiluj z tą linią / bez tej linii - jest
		     // różnica?
  }

Właściwie nie znam żadnej poważnej implementacji języka funkcyjnego,
która używałaby zliczania odniesień jako podstawowej metody odśmiecania.

Chyba, że mówimy od gwarantowaniu na poziomie systemu typów, że dla
pewnych obiektów ilość odniesień wynosi co najwyżej 1 - wtedy kłania się
Clean (i chyba Mercury?).

pozdrawiam,
tomek

-- 
.signature: Too many levels of symbolic links

Michal Przybylek wrote:
> "Lucifer" <przemek@nospam.pa55.bytom.sdi.tpnet.pl> wrote:
> 
> 
>>Zastanawia mnie czy jest mozliwe cos takiego:
>>
>>odsmiecanie bez zadnego zliczania odniesien, popsrostu kompilator
>>'zgaduje', w ktorym miejscu programu nalezy zwolnic pamiec, albo
>>wrzucic go do kolejki i wywalic po czasie kilka na raz.
> 
> 
> [...]
> 
> Nie wiem, czy dobrze rozumiem, ale...
> 
> 
> 1. Nie ma zadnego zliczania odniesien (a przynajmniej ja nie slyszalem o
> jakiejkolwiek zyjacej implementacji kozystajacej z tej techniki
> odsmiecania [*]).

O zliczaniu odniesien wiem z pewnych zrodel w C, jak to jest 
zorganizowane w normalnych jezykach nie mam pojecia. Myslalem ze podobnie.

> 2. Tak - czasami mozna przewidziec w ktorym miejscu moze zostac zwolniona
> pamiec i z miejsca wykorzystac ja ponownie. Takie cus nazywa sie "Compile
> Time Garbage Collector" i poczytac o tym mozna w papierach od Mercury'ego.

Ok, dzieki.

-- 
Lucifer

Lucifer wrote:

> Zastanawia mnie czy jest mozliwe cos takiego:
>
> odsmiecanie bez zadnego zliczania odniesien, popsrostu kompilator
> 'zgaduje', w ktorym miejscu programu nalezy zwolnic pamiec, albo 
> wrzucic go do kolejki i wywalic po czasie kilka na raz.

Jeśli chodzi o automatyczne zarządzanie pamięcią, ale całkowicie 
pozbawione ciężkich mechanizmów czasu wykonania programu, takich jak 
liczniki referencji, czy odśmiecacze śledzące dowiązania (tracing 
garbage collectors), to w ogólnym przypadku, dla dowolnego języka, 
zapewniające brak wycieków pamięci - nie, nie jest znane takie rozwiązanie.

Niestety bardzo długo języki wysokopoziomowe (czyli te, które m.in. 
zwalniają programistę z konieczności "ręcznego" zwalniania pamięci) nie 
wzbudzały żadnego zainteresowania przemysłu. Być może dlatego (albo 
dlatego że to trudny problem) na temat automatycznej gospodarki pamięcią 
(w ogole) powiedziano stosunkowo niewiele. Pojedynczy człowiek jest w 
stanie w ciągu kilkudziesięciu długich wieczorów przeczytać i zrozumieć 
wszystkie publikacje poruszające ten temat. Tych wnoszących do tematu 
coś rzeczywiście istotnego jest może ze dwadzieścia... O odśmiecaniu 
czasu kompilacji (compile-time gargabe collection) wiadomo bardzo niewiele.

Było trochę na ten temat (CTGC) w związku z badaniami nad wydajnością 
Javy. Możesz się czuć dumny bo w zasadzie doszedłeś do tego jak to może 
być zrealizowane :) - za pomocą prostej, syntaktycznej analizy kodu 
programu. Było trochę przy okazji zastosowań różnych form analizy 
przepływu danych i sterowania - jest np. jeden papier na temat analizy 
reprezentacji danych w kompilatorze Bigloo ("Storage Usage Analysis and 
its Applications" Manuel Serrano, Mark Feeley). Było też trochę na temat 
zastosowania systemu typów i mechanizmów rekonstrukcji typów do tego 
celu w związku z kompilatorem MLKit (link podał Tomek).

Lucifer wrote:

> Dzieki, poczytam.. Jakie sa wogole rodzaje odsmiecaczy, jak je mozna
> podzielic i scharakteryzowac?

Np. podział ze względu na mechanizm znajdowania śmieci:

liczniki odniesień (reference counting) vs odśmiecacze śledzące (tracing 
garbage collectors).

zalety liczników odniesień:

* łatwo zaimplementować
* przy leniwym niszczeniu obiektów zapewniają minimalne przerwy w 
działaniu programu
* pozwalają szybko odzyskiwać pamięć (już w momencie, gdy obiekt traci 
ostatnie dowiązanie)

wady:

* nie są w stanie zwolnić struktur cyklicznych (problem wyjaśnił Tomek)
* wykonują zawsze pracę proporcjonalną do pracy wykonywanej przez 
program, a nie do tempa alokacji obiektów, czy też tempa tworzenia śmieci
* są zazwyczaj zbudowane w oparciu o normalny malloco-podobny alokator 
ogólnego przeznaczenią, więc posiadają te same co on wady - fragmentują 
pamięć, duży średni koszt alokacji/dealokacji pojedynczego obiektu

W praktyce nie używa się ich...

Odśmiecacze śledzące:

najprostszy, naiwny odśmiecacz typu mark-and-sweep działa następująco:

* mamy sterte o określonym rozmiarze, np. 100 kilo.
* gdy jest na niej za mało wolnego miejsca, by zrealizować aktualne 
żądanie akokacji pamięci zatrzymujemy działanie programu.
* zaczynając od obiektów statycznie zaalokowanych, oraz mających 
dowiązania w rejestrach i na stosie śledzimy graf dowiązań
* wszystkie obiekty, do których trafiamy zaznaczamy jako "żywe" (np. 
korzystając ze specjalnego pola bitowego w nagłówku obiektu).
* po przejrzeniu całego grafu przeglądamy liniowo stertę i "usuwamy" 
wszystkie obiekty, które nie są "żywe", pozostałe "odznaczamy".

zalety:
* wykonuje zawsze pracę proporcjonalną do tempa alokacji obiektów
* zależne od typu, implementacji i zastosowania

wady:
* zależne od typu, implementacji i zastosowania

Same śledzące można podzielić na:

kopiujące i typu mark-and-sweep

albo na:

generacyjne i niegeneracyjne

albo na:

typu stop-and-collect, inkrementalne, współbieżne i równoległe

albo na:

konserwatywne i precyzyjne.



Najlepszym źródłem wiedzy na ten temat jest wspomniany przez Michała 
papier Wilsona...

>
> > Jesli natomiast chodzi o jezyki imperatywne, to jesli tworzymy zmienna i
> > przekazujemy
> > ja tylko przez kopiowanie, to mozna rzeczywiscie przydzielic ja sobie na
> > stosie.
>
> W ogole nie rozumiem. Mozesz to jakos rozwinac ?

Chodzilo mi po prostu o to, ze sa takie czeste proste przypadki, kiedy widac
kiedy obiekt nalezy przydzielic a kiedy zwolnic, np. gdy w bloku kodu
tworzymy
sobie lokalna zmienna typu Integer i nie dajemy nikomu wskaznika do niej -
wtedy dokladnie wiadomo, ze na taka zmienna mozemy przydzielic pamiec (na
stosie)
przy wejsciu do tego bloku kodu i zwolnic przy wyjsciu.

Tomek

On Thu, 12 Dec 2002, Tomek Czajka wrote:

> Chodzilo mi po prostu o to, ze sa takie czeste proste przypadki, kiedy widac
> kiedy obiekt nalezy przydzielic a kiedy zwolnic, np. gdy w bloku kodu
> tworzymy
> sobie lokalna zmienna typu Integer

Integer mieści się zazwyczaj w pojedynczym słowie maszynowym więc w
ogole nie ma sensu na niego alokować pamięci ;)

Mariusz K. Grzeca napisał:
> On Thu, 12 Dec 2002, Tomek Czajka wrote:
> 
> Integer mieści się zazwyczaj w pojedynczym słowie maszynowym więc w
> ogole nie ma sensu na niego alokować pamięci ;)

Ze znanych mi języków chyba tylko Haskell ma typ, który nazywa się
_dokłanie_ Integer (nieograniczone liczby całkowite) i on się raczej nie
mieści w pojedynczym słowie maszynowym :)

pozdr
tomek

-- 
.signature: Too many levels of symbolic links

On Thu, 12 Dec 2002, Tomasz Zielonka wrote:

> Ze znanych mi języków chyba tylko Haskell ma typ, który nazywa się
> _dokłanie_ Integer (nieograniczone liczby całkowite) i on się raczej nie
> mieści w pojedynczym słowie maszynowym :)

Ej, to ja tu jestem od czepiania się słówek ;P

"Tomasz Zielonka" <t.zielonka@students.mimuw.edu.pl> wrote:

> Ze znanych mi języków chyba tylko Haskell ma typ, który nazywa się
> _dokłanie_ Integer (nieograniczone liczby całkowite) i on się raczej nie
> mieści w pojedynczym słowie maszynowym :)

Chociazby Eiffel (i miesci sie w pojedynczym slowie maszynowym).
:-P

mp

"Mariusz K. Grzeca" <mgrzeca@sokrates.mimuw.edu.pl> wrote:

> Integer mieści się zazwyczaj w pojedynczym słowie maszynowym więc w
> ogole nie ma sensu na niego alokować pamięci ;)

Nie w jezykach z dynamicznymi typami :-P

Zdaje sie, ze w ten sposob postepuja Allegro i CMUCL przy odpowiednich
deklaracjach dla obiektow liczbopodobnych. Glowy jednak nie dam.


mp

"Tomek Czajka" <tczajka@mimuw.edu.pl> wrote:

> Chodzilo mi po prostu o to, ze sa takie czeste proste przypadki, kiedy
> widac kiedy obiekt nalezy przydzielic a kiedy zwolnic, np. gdy w bloku
> kodu tworzymy sobie lokalna zmienna typu Integer i nie dajemy nikomu
> wskaznika do niej - wtedy dokladnie wiadomo, ze na taka zmienna
> mozemy przydzielic pamiec (na stosie)
> przy wejsciu do tego bloku kodu i zwolnic przy wyjsciu.

Ok, rozumiem.

[BTW: nie dokladnie wiadomo - a przynajmniej nie zawsze (np. przy
uniwersalnym srodowisku najczesciej nie mozemy byc pewni niczego)]

mp

> Ze znanych mi jêzyków chyba tylko Haskell ma typ, który nazywa siê
> _dok³anie_ Integer (nieograniczone liczby ca³kowite) i on siê raczej nie
> mie¶ci w pojedynczym s³owie maszynowym :)

Ja znam jeszcze Integer z Pascala - we FreePascalu miesci sie on w polowie
slowa maszynowego :-)

Tomek

> Integer mie¶ci siê zazwyczaj w pojedynczym s³owie maszynowym wiêc w
> ogole nie ma sensu na niego alokowaæ pamiêci ;)

No jak to nie - trzeba chocby to jedno slowo maszynowe zaalokowac.

Tomek

On Thu, 12 Dec 2002, Michal Przybylek wrote:

> Nie w jezykach z dynamicznymi typami :-P

Dlaczego nie? Wiekszość mi znanych używa unboxowanych, otagowanych
intów. Boxowanie inta nie ma sensu...

On Fri, 13 Dec 2002, Tomek Czajka wrote:

> > Integer mieści się zazwyczaj w pojedynczym słowie maszynowym więc w
> > ogole nie ma sensu na niego alokować pamięci ;)
> 
> No jak to nie - trzeba chocby to jedno slowo maszynowe zaalokowac.

Nie, ponieważ mieści się w rejestrze, w pojedynczym słowie na stosie i
jest unboxowany (ale być może otagowany) w innych strukturach. intów
się raczej nie boxuje, tym samym nie alokuję sie pamięci specjalnie
dla nich.

"Mariusz K. Grzeca" <mgrzeca@sokrates.mimuw.edu.pl> wrote:

> > Nie w jezykach z dynamicznymi typami :-P
>
> Dlaczego nie? Wiekszość mi znanych używa unboxowanych,
> otagowanych intów. Boxowanie inta nie ma sensu...

Wlasnie dlatego, ze to nie jest normalny "int".

Problemy sa dwa - drozsze operacje (bez jaj - przeciez to ma podchodzic pod
optymalizowane C ;-)) i niezadko bardzo mala dlugosc liczby (np. nieboxowany
fixnum pod LispWorks'em jest <= 8388607, pod CL'em <= 2^24-1 [standard
gwarantuje 2^15-1]). Jeszcze gorzej jest z nieboxowanymi floatami (w
praktyce gdzies ok. 20 bitow). Wartosci te sa dla wielu zastosowaniach na
tyle smieszne, ze dobre kompilatory musza pozwalac na uzywanie nieboxowanych
i nietagowanych liczb.


mp

"Mariusz K. Grzeca" <mgrzeca@sokrates.mimuw.edu.pl> wrote

> > Nie w jezykach z dynamicznymi typami :-P
>
> Dlaczego nie?

A... juz widze.

Mowiac:

"Zdaje sie, ze w ten sposob postepuja..."

mailalem na mysli trzymanie pelnego integera na stosie.


mp

Tomek Czajka <tczajka@mimuw.edu.pl> wrote:
>> Ze znanych mi j?zyków chyba tylko Haskell ma typ, który nazywa si?
>> _dok?anie_ Integer (nieograniczone liczby ca?kowite) i on si? raczej nie
>> mie?ci w pojedynczym s?owie maszynowym :)

> Ja znam jeszcze Integer z Pascala - we FreePascalu miesci sie on w polowie
> slowa maszynowego :-)
	... no jeszcze kilka innych jezykow ma takie dlugie int'y;-)
Patrz lisp, Python itp. Z powazaniem
								Adam Przybyla

Użytkownik "Mariusz K. Grzeca" <mgrzeca@sokrates.mimuw.edu.pl> napisał w
wiadomości
news:Pine.LNX.4.44L.0212130256590.2284-100000@sokrates.mimuw.edu.pl...
> > Nie w jezykach z dynamicznymi typami :-P
>
> Dlaczego nie? Wiekszość mi znanych używa unboxowanych, otagowanych
> intów. Boxowanie inta nie ma sensu...
>
Prosze o wyjasnienie terminow:
boxowany
otagowany
Z gory dziekuje za pomoc.
Pozdrawiam,
soovack

>
> > > Integer mie¶ci siê zazwyczaj w pojedynczym s³owie maszynowym wiêc w
> > > ogole nie ma sensu na niego alokowaæ pamiêci ;)
> >
> > No jak to nie - trzeba chocby to jedno slowo maszynowe zaalokowac.
>
> Nie, poniewa¿ mie¶ci siê w rejestrze, w pojedynczym s³owie na stosie i
> jest unboxowany (ale byæ mo¿e otagowany) w innych strukturach. intów
> siê raczej nie boxuje, tym samym nie alokujê sie pamiêci specjalnie
> dla nich.

No chyba alokacje w rejestrze albo na stosie tez sie nazywa alokacja.
Zreszta
w rejestrach to zbyt duzo tych zmiennych sie nie pomiesci (szczegolnie dla

funkcji rekurencyjnych).

Tomek

Tomek Czajka wrote:

> No chyba alokacje w rejestrze albo na stosie tez sie nazywa alokacja.

Ale to co innego...

Użytkownik "soovack" <soovack@gazeta.pl> napisał w wiadomości
news:atdcqn$bin$2@news.tpi.pl...
> Prosze o wyjasnienie terminow:
> boxowany
> otagowany
>
Juz sam znalazlem odpowiedz.
Przepraszam za banalne pytanie - nastepnym razem
zapuszcze sobie googla zanim publicznie popisze sie
swoja niewiedza.
soovack

ps.
Dla takich lamerow jak ja ktorzy byc moze beda zainteresowani
tym tematem podaje linka do ciekawej strony o zarzadzaniu
pamiecia - www.memorymanagement.org - tu jest chyba
wszystko co wypada wiedziec.