C++ için Garbage Collector yazmak



Yaklaşık üç satırı geçen tüm programlar çeşitli nedenlerle derleme anında (compile time) belirlenemeyen miktarda hafızaya ihtiyaç duyarlar. Bu programın çalışma anında (runtime) dinamik hafızayı (dynamic memory) kullanmasını zorunlu kılar.

Dinamik hafızanın yönetimi için iki temel yaklaşımdan söz edebiliriz.

• Manuel: Hafızayı alırsınız, kullanirsınız ve ne zaman isterseniz bırakırsınız. C++ bu yaklaşımı tercih eder. Bırakma zamanına ve sırasına biz karar verdiğimiz için tam olarak ne zaman destructor’larin çağırılacağını, hangi sıra ile çağırılacaklarına karar verebiliriz. Eğer bırakmayi unutursanız memory leak’ler en iyi ihtimalle sadece performansinizi düşürür, en kötü ihtimalle...

• Garbage Collection: Hafızayı alırsınız ve kullanırsınız. Bilinmeyen bir zamanda GC hafızayı birakir, bırakacağı garantilenmemiştir, destructor’ların hangi sıra ile çağirilacagı belirsizdir. Bu işlemlerin hepsi ekstra yük getirir ancak manuel yaklaşımda ortaya çikan memory leak problemi meydana gelmez.



C++’in GC’u olmamasına ragmen kolaylıkla kendi GC’umuzu yazabiliriz veya Boost Library gibi bir kütüphanedeki kullanabiliriz. Her iki yöntemi de aynı anda C++’da kullanmak mümkündür.

Gargabe collection üzerinde yapılan akademik çalışmalarla onlarca algoritma ve varyasyonlari geliştirilmiştir. Fakat yazının konusu C++ ile uygulanması olduğundan en temel ve eski algoritmayi, reference counting’i kullanacağiz.

Reference counting’de tüm hafıza parçaların adresleri ve kaç kez kullanıldıkları bir listede tutulur. Eğer bir parçanın kullanım sayısı sıfıra düşerse parça bırakılır. (liste the list structure değil, nitekim uygulamada stl::map’de saklayacağız ve muhtemelen red-black tree)

Örneğin aşağidakine reference counting yaptığimızı varsayalım.

int *p,*q,*h;

p = new int; //new’in döndügü adresin counter’i 1’dir, Sadece p onu kullaniyor

q = p; //su an 2 oldu, q ve p kullaniyor

h = new int; //bu hafiza parçasinin adresinin 0xdeadbeef oldugunu varsayalim.

h = q; //0xdeadbeef’in counter’i 0 oldu ve birakildi.

Bir class tanımlayıp onu pointer gibi kullanarak bu sayma işlemini yapabiliriz. “=” operatörünü overload’lamamız yeterli olacaktır. Ancak tam bir pointer’a yakın davranması için “*”, “->”,”[]” ve hatta kullanım kolaylığı için “(degişken tipi)” operatörlerini de overload edebiliriz. Uygulamamızda class “+”,”-“,”++”,”--“ gibi operatörleri desteklemeyecek çünkü C++’da hafıza parçaları başlangıç adresleri ile bırakılırlar.

int *p;

p = new int[64];

p++;

delete[] p; // ???

Böyle bir durum oluşmaması için pointer aritmetigi desteklemeyecek, ancak gerçek bir pointer aktarıp yine kullanabileceğiz.

Kodu buradan indirebilirsiniz.:








Nasıl Kullanılır?

gcp<veri tipi> pointer_adi;

gcp<int> p; //int *p;

p = new int;

*p = 1234;

gcp<myclass> m = new myclass(“hello”);

m->do();

eğer array olarak kullanacaksanız

gcp<char,true> m = new char[64];

strcpy(m, "test string");

printf("%s\n",m);

gcp<int, true> p;

p = new int[64];

p[0] = 1234; //pointer aritmetigi için

int *r = p; // tanimini yapip r üzerinden kullanabilirsiniz.

References

Donald E. Knuth. The Art of Computer Programming Vol.1

Bjarne Stroustrup. The C++ Reference Manual.

Herbert Schildt. The Art of C++.

Daniel R. Edelson. A Mark-and-Sweep Collector for C++.







Nasıl çalışır?
Çoğu 16-bit’lik sistemlerin aksine 32 ve 64-bit sistemde C pointer’ları sadece offset’i gösterirler. Her offset register büyüklüğündedir. O halde pointer’larla unsigned long olarak işlem yapabiliriz. gcp’de m_CounterMap şöyle tanımlıdır. static std::map<unsigned long, gc_meminfo<T> > m_CounterMap;
pointer’ları unsigned bu map’in key’i olarak kullanabiliriz, gc_meminfo ise sadece 3 tane public member variable’a sahiptir. int m_nCount;
bool m_fArray;
T* m_pObject;
m_nCount: bu hafıza parçasının kullanım sayısı. m_fArray: array mi ? m_pObject: pointer
0xdeadbeef’in kaç farklı yerde kullanıldığını bulmak isterseniz map::find’i kullanmanız yeterli olur.
iter = m_CounterMap.find((unsigned long)0xdeadbeef);
{
gcp<char,true> m; //NULL pointer'in counter'i 1 atar
m = new char[64]; //NULL pointer'in counter'i 1 azalar ve "new"'in döndürdüğü değer için counter 1 artar
strcpy(m, "test string"); //operator T*(), m_pCurrent ile en son sahip olunan pointer'i döndürür
printf("%s\n",m);
} //Out of scope, m'in destructor'u çağırılır. Destructor m_pCurrent'in counter'ini 1 azaltır ve collect()'i çağırır. Collect() fonksiyonu counter'ları 0'a düşen bütün hafızaları bırakır.





References

Donald E. Knuth. The Art of Computer Programming Vol.1

Bjarne Stroustrup. The C++ Reference Manual.

Herbert Schildt. The Art of C++.

Daniel R. Edelson. A Mark-and-Sweep Collector for C++.