Garbage Collection in Julia

Introduction

تحتوي جوليا على جامع علامات-مسح غير متحرك، جزئي التزامن، متوازي، جيلّي ومعظم دقته عالية (يتم توفير واجهة لمسح المكدس المحافظ كخيار للمستخدمين الذين يرغبون في استدعاء جوليا من C).

Allocation

تستخدم جوليا نوعين من المخصصات، حيث يحدد حجم طلب التخصيص أيهما يتم استخدامه. يتم تخصيص الكائنات التي تصل إلى 2 كيلو بايت من خلال مخصص قائمة حرة لكل خيط، بينما يتم تخصيص الكائنات التي تزيد عن 2 كيلو بايت من خلال malloc في libc.

يخصص مُخصص تجمع جوليّا الكائنات في فئات حجم مختلفة، بحيث تحتوي صفحة الذاكرة التي يديرها مُخصص التجمع (الذي يمتد على 4 صفحات نظام تشغيل على منصات 64 بت) فقط على كائنات من نفس فئة الحجم. يتم إقران كل صفحة ذاكرة من مُخصص التجمع ببعض بيانات الصفحة المخزنة في قوائم خالية من القفل لكل خيط. تحتوي بيانات الصفحة على معلومات مثل ما إذا كانت الصفحة تحتوي على كائنات حية على الإطلاق، وعدد الفتحات المجانية، والإزاحات إلى أول وآخر كائنات في قائمة الفتحات الموجودة في تلك الصفحة. تُستخدم هذه البيانات لتحسين مرحلة الجمع: يمكن إعادة صفحة لا تحتوي على كائنات حية على الإطلاق إلى نظام التشغيل دون الحاجة إلى مسحها، على سبيل المثال.

بينما يمكن إعادة صفحة لا تحتوي على كائنات إلى نظام التشغيل، فإن البيانات الوصفية المرتبطة بها مخصصة بشكل دائم وقد تعيش لفترة أطول من الصفحة المعطاة. كما ذُكر أعلاه، يتم تخزين البيانات الوصفية للصفحات المخصصة في قوائم خالية من القفل لكل خيط. ومع ذلك، قد يتم تخزين البيانات الوصفية للصفحات الحرة في ثلاث قوائم خالية من القفل منفصلة اعتمادًا على ما إذا كانت الصفحة قد تم تعيينها ولكن لم يتم الوصول إليها أبدًا (page_pool_clean)، أو ما إذا كانت الصفحة قد تم تنظيفها بشكل كسول وتنتظر أن يتم إبلاغها بواسطة خيط GC في الخلفية (page_pool_lazily_freed)، أو ما إذا كانت الصفحة قد تم إبلاغها (page_pool_freed).

يتبع مُخصص الذاكرة في جوليا نظام تخصيص "مستويات". عند طلب صفحة ذاكرة لمخصص الذاكرة، ستقوم جوليا بـ:

• حاول المطالبة بصفحة من page_pool_lazily_freed، والتي تحتوي على صفحات كانت فارغة في آخر مرحلة توقف العالم، ولكن لم يتم معالجتها بعد بواسطة خيط جمع القمامة المتزامن.
• إذا فشل في المطالبة بصفحة من page_pool_lazily_freed، فسيحاول المطالبة بصفحة من the page_pool_clean، والتي تحتوي على صفحات تم تخصيصها في طلب تخصيص صفحة سابق ولكن لم يتم الوصول إليها أبدًا.
• إذا فشلت في المطالبة بصفحة من pool_page_clean ومن page_pool_lazily_freed، فستحاول المطالبة بصفحة من page_pool_freed، والتي تحتوي على صفحات تم تقديم نصائح بشأنها بالفعل بواسطة خيط جامع قمامة متزامن ويمكن إعادة تدوير عنوانها الافتراضي الأساسي.
• إذا فشلت في جميع المحاولات المذكورة أعلاه، فسوف تقوم بعمل mmap لمجموعة من الصفحات، وتدعي صفحة واحدة لنفسها، وتدرج الصفحات المتبقية في page_pool_clean.

Marking and Generational Collection

تتمثل مرحلة العلامة في جوليا من خلال بحث متعمق تكراري متوازي على رسم الكائنات. جامع جوليا غير متحرك، لذا لا يمكن تحديد معلومات عمر الكائن من خلال منطقة الذاكرة التي يقيم فيها الكائن وحدها، ولكن يجب أن تكون مشفرة بطريقة ما في رأس الكائن أو في جدول جانبي. تُستخدم أدنى بتين من رأس الكائن لتخزين، على التوالي، بت علامة يتم تعيينه عندما يتم فحص كائن خلال مرحلة العلامة وبت عمر لجمع الأجيال.

تتم عملية جمع الأجيال من خلال بتات لاصقة: يتم دفع الكائنات إلى كومة العلامة، وبالتالي تتبعها، فقط إذا لم تكن بتات العلامة الخاصة بها مضبوطة. عندما تصل الكائنات إلى الجيل الأقدم، لا يتم إعادة تعيين بتات العلامة الخاصة بها خلال ما يسمى "الكشط السريع"، مما يؤدي إلى عدم تتبع هذه الكائنات في مرحلة العلامة التالية. ومع ذلك، فإن "الكشط الكامل" يتسبب في إعادة تعيين بتات العلامة لجميع الكائنات، مما يؤدي إلى تتبع جميع الكائنات في مرحلة العلامة التالية. يتم ترقية الكائنات إلى الجيل التالي خلال كل مرحلة كشط تنجو منها. على جانب المحول، يتم اعتراض كتابة الحقول من خلال حاجز كتابة يدفع عنوان كائن إلى مجموعة مذكورة لكل خيط إذا كان الكائن في الجيل الأخير، وإذا لم يكن الكائن في الحقل الذي يتم الكتابة عليه. يتم تتبع الكائنات في هذه المجموعة المذكورة خلال مرحلة العلامة.

Sweeping

يمكن أن تقع عملية تنظيف تجمعات الكائنات في جوليا ضمن فئتين: إذا كانت الصفحة المعينة التي يديرها مُخصص التجمع تحتوي على كائن حي واحد على الأقل، فيجب تمرير قائمة مجانية عبر كائناتها الميتة؛ إذا كانت الصفحة المعينة لا تحتوي على أي كائنات حية على الإطلاق، فيمكن إرجاع الذاكرة الفيزيائية الأساسية إلى نظام التشغيل من خلال، على سبيل المثال، استخدام استدعاءات نظام madvise على لينكس.

الفئة الأولى من التنظيف تتم بشكل متوازي من خلال سرقة العمل. بالنسبة للفئة الثانية من التنظيف، إذا تم تمكين تنظيف الصفحات المتزامن من خلال العلم --gcthreads=X,1 نقوم بتنفيذ استدعاءات نظام madvise في خيط تنظيف في الخلفية، بالتزامن مع خيوط المحور. خلال مرحلة التوقف عن العمل لجمع القمامة، يتم دفع الصفحات المخصصة التي لا تحتوي على كائنات حية في البداية إلى pool_page_lazily_freed. ثم يتم إيقاظ خيط التنظيف في الخلفية ويتولى مسؤولية إزالة الصفحات من pool_page_lazily_freed، واستدعاء madvise عليها، وإدراجها في pool_page_freed. كما هو موضح أعلاه، يتم مشاركة pool_page_lazily_freed أيضًا مع خيوط المحور. وهذا يعني أنه في أعباء العمل المتعددة الخيوط التي تركز على التخصيص، سيتجنب خيوط المحور غالبًا حدوث خطأ في الصفحة عند التخصيص (الناجم عن الوصول إلى صفحة mmaped جديدة أو الوصول إلى صفحة تمت معالجة madvise) من خلال التخصيص مباشرة من صفحة في pool_page_lazily_freed، بينما يحتاج خيط التنظيف في الخلفية إلى madvise عدد أقل من الصفحات نظرًا لأن بعض منها تم المطالبة به بالفعل من قبل المحور.

Heuristics

تقوم خوارزميات جمع القمامة بضبط جمع القمامة عن طريق تغيير حجم فترة التخصيص بين عمليات جمع القمامة.

تقيس خوارزميات جمع القمامة (GC) حجم كومة الذاكرة بعد عملية الجمع وتحدد عملية الجمع التالية وفقًا للخوارزمية الموضحة في https://dl.acm.org/doi/10.1145/3563323، باختصار، تجادل بأن الهدف من الكومة يجب أن يكون له علاقة جذرية تربيعية مع الكومة الحية، وأنه يجب أيضًا أن يتم توسيعه بناءً على مدى سرعة تحرير GC للأشياء ومدى سرعة تخصيص المحولات. تقيس الخوارزميات حجم الكومة عن طريق عد عدد الصفحات المستخدمة والأشياء التي تستخدم malloc. سابقًا، كنا نقيس حجم الكومة عن طريق عد الأشياء الحية، لكن ذلك لا يأخذ في الاعتبار التجزئة التي قد تؤدي إلى قرارات سيئة، وهذا يعني أيضًا أننا استخدمنا معلومات محلية خاصة بالخيوط (التخصيصات) لاتخاذ قرارات حول عملية واسعة (متى يتم جمع القمامة)، مما يعني أن قياس الصفحات يجعل القرار عالميًا.

ستقوم GC بإجراء عمليات جمع كاملة عندما يصل حجم الذاكرة إلى 80% من الحجم الأقصى المسموح به.