जीसी में सफेद/ग्रे/काला क्यों?

Question

मैं एक साधारण स्क्रिप्टिंग भाषा एपीआई में मार्क-एंड-स्वीप कचरा संग्रह लागू कर रहा हूं, जिस पर मैं काम कर रहा हूं और कचरा संग्रह के विभिन्न कार्यान्वयन के बारे में पढ़ रहा हूं। एपीआई जैसे लुआ सफेद, भूरे और काले सूचियों के साथ मार्क-एंड-स्वीप का उपयोग करते हैं।

समस्या मैं क्यों ऐसी सूची रहे हैं और यही कारण है कि वे इन विशिष्ट रंगों में डाल रहे हैं की व्याख्या पढ़ सकते हैं नहीं कर पा रहे है।

मेरे वर्तमान, मामूली कार्यान्वयन में, मैं बस "मृत" या "जीवित" राज्यों का उपयोग करता हूं। स्वीप में, मृत वस्तुओं को हटा दिया जाता है। मैं देशी ढेर का उपयोग कर रहा हूं इसलिए मैं अपने जीसी में कोई भी कदम नहीं उठा रहा हूं। सब एक ग्रे ब्लॉक के वंशज काला के रूप में चिह्नित किया गया है अभी तक नहीं:

मैं इसे लिख रहा हूँ सी

में

// Performs a full garbage collection 
void GorCollect(GorContext *ctx) 
{ 
    Value *v, *end; 
    Collectable *c, *n; 

    // mark stack references 
    end = ctx->stack + ctx->stackTop + 1; 
    v = ctx->stack; 
    while(v != end) 
    { 
     if (gvisgc(v) && v->v.gc) // mark if a collectable obj 
      Mark(v->v.gc); 
     v = v++; 
    } 

    // mark global references 
    if (ctx->global) 
     Mark((Collectable *)ctx->global); // ctx->global is a collectable obj 

    // perform sweep 
    c = ctx->gchead; // full list of collectable objs 
    ctx->gchead = 0; 
    while(c) { 
     n = c->next;  
     // destroy unmarked collectable 
     if (!c->marked) 
      FreeCollectable(ctx, c); 

     // rebuild gc list (singly-linked) 
     else 
     { 
      c->marked = 0; 
      if (!ctx->gchead) 
       c->next = 0; 
      else 
       c->next = ctx->gchead; 
      ctx->gchead = c; 
     } 
     c = n; 
    } 
} 

Answer 1

ग्रे "लाइव लेकिन स्कैन नहीं" का मतलब है। वृद्धिशील कचरा-संग्राहक में ग्रे रंग आवश्यक है। यह मार्क-एंड-स्वीप जीसी को जारी रखने में मदद करता है कि अगली बार जब यह थोड़ा निशान लगाने का मौका मिलता है तो वह क्या कर रहा था।

यदि आपका जीसी गैर-वृद्धिशील है, तो यह आपको देख सकता है कि आपको भूरे रंग की आवश्यकता नहीं है: आप हमेशा किसी भी लाइव ब्लॉक के सभी बच्चों पर हमेशा की देखभाल कर सकते हैं। हालांकि, एक और अधिक सूक्ष्म मुद्दा यह है कि यह बेवकूफ गैर-वृद्धिशील रिकर्सिव एल्गोरिदम ढेर बह सकता है। एक ग्रे रंग भी ढेर के बजाय, ढेर में आगे आने के बारे में जानकारी संग्रहीत करने में मदद करता है।

यहां तक ​​कि अगर आप इस उद्देश्य के लिए ग्रे रंग का उपयोग करें, यह आप ब्लॉक कि दक्षता के लिए दौरा किया जा करने के लिए रहने के के एक बफर रखने से नहीं रोकता है। बेवकूफ पुनरावर्ती कार्यान्वयन के साथ एकमात्र अंतर यह है कि जब आप पहले से भर चुके हैं तो बफर को अपडेट करना बंद कर देते हैं, और यदि आप पूर्ण होने के बाद बफर खाली हो जाते हैं तो आप ग्रे ऑब्जेक्ट्स के लिए रैप को स्कैन करते हैं।

Answer 2

पहले की

, वे सेट, नहीं सूचियों कर रहे हैं और ढेर में प्रत्येक वस्तु वास्तव में सेट में से एक में किसी भी समय है।

दूसरा, किसी भी निशान & स्वीप कार्यान्वयन का उपयोग किया जा रहा है, लेकिन वे निहित हो सकते हैं। आप Mark के लिए कार्यान्वयन प्रदान नहीं करते हैं, लेकिन उस फ़ंक्शन में आप अपनी ऑब्जेक्ट्स को अपने सेट में ले जा रहे हैं।

/* Initally, the white set contains all objects, the black and 
    grey sets are empty. */ 
stack *st = m->mark_stack; 
/* First all roots are added to the gray set. */ 
for (size_t i = 0; i < m->roots->used; i++) { 
    ptr p = m->roots->array[i]; 
    if (p != 0) { 
     /* Mark the root and move it to the gray set. */ 
     AT(p) |= 1; 
     st_push(st, p); 
    } 
} 
while (st->used) { 
    /* Think of popping the object from the mark stack as moving 
     it from the gray to the black set. */ 
    ptr p = st_pop(st); 
    P_FOR_EACH_CHILD(p, { 
     if (!GET_MARK(p_child)) { 
      /* Then mark each non-black child and move it to the 
       gray set. */ 
      AT(p_child) |= 1; 
      st_push(st, p_child); 
     } 
    }); 
} 
/* When control has reached this point, the gray set is empty and 
    the whole heap has been divided into black (marked) and white 
    (condemned) objects. */ 

हम बजाय तीन सेटों के लिए स्पष्ट डेटा संरचनाओं इस्तेमाल कर सकते हैं:

यहाँ मेरी कचरा कलेक्टर के निशान चरण के लिए कार्यान्वयन है। लेकिन एक स्टॉप-द-वर्ल्ड मार्क & स्वीप जीसी के लिए, यह कार्यान्वयन बहुत अधिक कुशल है।