لماذا يتم تخصيص الذاكرة على كومة MUCH أبطأ من على مكدس الذاكرة المؤقتة؟




memory-management stack (2)

لقد قيل لي هذا عدة مرات. ولكن لا أعرف لماذا ... ما هي التكلفة الإضافية التي ينطوي عليها عند تخصيص الذاكرة من كومة الذاكرة المؤقتة؟ هل الأجهزة ذات الصلة؟ هل هو متعلق بدورات CPU؟ الكثير من التخمينات لكن بدون إجابات دقيقة ... هل يمكن أن يعطيني شخص ما بعض التفاصيل؟

كما قال "الاسترخاء" ، بنية بيانات الكومة أكثر تعقيدًا من بنية تخزين العناصر. وفي رأيي ، يتم تخصيص بعض مساحة الذاكرة إلى مؤشر ترابط كما المكدس الخاص به عند بدء تشغيل ، بينما يتم مشاركة الكومة بواسطة كافة مؤشرات الترابط ضمن عملية. يتطلب هذا النموذج بعض آلية إضافية لإدارة استخدام كل مؤشر ترابط الكومة المشتركة ، مثل "مجموعة garbage". هل أنا على حق في هذا؟


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

على كومة من ناحية أخرى ، يمكنك إزالة العناصر خارج الترتيب. وطالما أنك لا تحرك العناصر الأخرى بعد ذلك في الذاكرة (كما تفعل بعض أكوام القمامة المجمعة) ، فإن كومة الذاكرة المؤقتة تحتوي على "ثقب" في المنتصف. أي إذا قمت بإضافة A و B و C إلى كومة وقمت بإزالة B ، يبدو كومة الذاكرة المؤقتة كذاكرة في الذاكرة: A _ C حيث _ هي كتلة من الذاكرة غير المستخدمة (المجانية). إذا قمت بإضافة عنصر جديد D الآن ، يجب على المُخصص أن يجد مساحة حرة مستمرة كبيرة بما يكفي لملاءمة D. اعتمادًا على عدد الفراغات الحرة المستمرة الموجودة في ذاكرتك ، قد يكون هذا عملية مكلفة. وغالبًا ما تكون غالية أكثر من مجرد تحريك مؤشر "العنصر الأخير" للمكدس.


في تعديلك حيث تعيد التأكيد على إجابة الإجابة ، تذكر "بنية بيانات كومة الذاكرة المؤقتة". كن حذرًا جدًا نظرًا لأن بنية البيانات المعروفة باسم heap لا علاقة لها بتخصيص الذاكرة الديناميكية. لأكون واضحا جدا ، سوف أستخدم مصطلحات أكثر محامي اللغة من متجر مجاني .

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

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

لمقارنة بسيطة ، واستخدام jemalloc-2.2.5 والأرقام من sloccount كمرجع ، يحتوي تطبيق jemalloc على أكثر من 8،800 سطر من شفرة المصدر في لغة C وآخر أكثر من 700 سطر من كود الاختبار. يجب أن يعطيك هذا فكرة جيدة عن الاختلاف في التعقيد بين تخصيص المخزن الحر وتخصيص المكدس: آلاف الأسطر من كود C مقابل تعليمة واحدة.

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

  • تجزئة يضر محلة البيانات.
  • تفتيت الذاكرة.
  • تجزئة يجعل مهمة العثور على مساحة حرة لعمليات تخصيص كبيرة أصعب.

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

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

  • dlmalloc - dlmalloc دوغ ليا malloc ، هو تطبيق مرجعي dlmalloc التاريخي المستخدم في GNU C ++ في وقت واحد
  • phkmalloc - تنفيذ FreeBSD من malloc كتبه بول هينينج كامب مؤلف مخبأ الويب الورنيش
  • tcmalloc - الموضوع - التخزين المؤقت Malloc تنفيذها من قبل بعض مطوري Google
  • jemalloc - تنفيذ malloc في تطبيق Jason Evan لـ FreeBSD (خليفة phkmalloc)

إليك بعض الروابط الإضافية مع أوصاف تنفيذ tcmalloc:





stack