سؤال فعال لإعادة تخصيص الذاكرة

Question

دعنا نقول أن لدي برنامج (C ++ ، على سبيل المثال) الذي يخصص كائنات متعددة ، وليس أكبر من حجم معين (دعنا نسميها max_object_size).

لدي أيضًا منطقة (سأسميها "صفحة") على الكومة (المخصصة ، على سبيل المثال ، malloc (region_size) ، حيث region_size> = max_object_size).
أستمر في الحفاظ على المساحة في تلك الصفحة حتى تساوي المساحة المملوءة page_size (أو على الأقل يحصل على> page_size - max_object_size).

الآن ، أريد تخصيص المزيد من الذاكرة. من الواضح أن "صفحتي" السابقة لن تكون كافية. لذلك لدي خياران على الأقل:

1. استخدم RealLoc (صفحة ، new_size) ، حيث new_size> page_size ؛
2. قم بتخصيص "صفحة" جديدة (Page2) ووضع الكائن الجديد هناك.

إذا أردت الحصول على وظيفة تخصيص مخصصة ، ثم:

1. باستخدام الطريقة الأولى ، أرى مقدار ملأي ، ثم وضع كائني الجديد هناك (وأضف حجم الكائن إلى متغير الذاكرة المملوء).
2. باستخدام الطريقة الثانية ، كان لدي قائمة (متجه؟ صفيف؟) من الصفحات ، ثم ابحث عن الصفحة الحالية ، ثم استخدم طريقة مشابهة لـ 1 في الصفحة المحددة.

في النهاية ، سأحتاج إلى طريقة لتحرير الذاكرة أيضًا ، لكن يمكنني معرفة هذا الجزء.

لذلك سؤالي هو: ما هي الطريقة الأكثر كفاءة لحل مشكلة مثل هذه؟ هل هو الخيار 1 أو الخيار 2 أو خيار آخر لم أفكر فيه هنا؟ هل هناك حاجة إلى معيار صغير/ما يكفي لاستخلاص استنتاجات لحالات العالم الحقيقي؟أفهم أن العمليات المختلفة قد تؤدي بشكل مختلف ، لكنني أبحث عن مقياس شامل.

Answer 1

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

ولكن من الصعب تأهيل "الأكثر كفاءة" دون معرفة بالضبط المقاييس التي تستخدمها.

هذا هو مدير الذاكرة الذي أستخدمه دائمًا. إنه يعمل للتطبيق بأكمله وليس مجرد كائن واحد.

تخصيص:

لكل تخصيص تحديد حجم الكائن المخصص.

1 انظر إلى قائمة رابط من الحشرات لكائنات من هذا الحجم لمعرفة ما إذا كان قد تم تحرير أي شيء إذا كان الأمر كذلك خذ أول مجانا

2 ابحث عن طاولة البحث وإذا لم يتم العثور عليها

2.1 تخصيص مجموعة من الكائنات n من الحجم الذي يتم تخصيصه.

3 إرجاع الكائن المجاني التالي للحجم المطلوب.

3.1 إذا كانت المصفوفة كاملة إضافة صفحة جديدة.

يمكن أن تكون الكائنات n المبرمج. إذا كنت تعلم أن لديك مليون بايت ، فقد ترغب في أن تكون n أعلى قليلاً.

بالنسبة للكائنات على بعض الحجم x ، لا تحتفظ بمصفوفة ببساطة تخصيص كائن جديد.

تحرر:

حدد حجم الكائن ، وأضفه إلى قائمة رابط الحشرات.

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

المشكلة في هذه الطريقة هي أن الذاكرة لا يتم إرجاعها إلى نظام التشغيل حتى يتم خروج التطبيق أو يقرر المبرمج تحرير الذاكرة. إلغاء التجزئة هو وظيفة أخرى. يمكن إنجازه.

Answer 2

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

إذا كان بالفعل بمثابة صفيف ،malloc-تمنحك كتلة أخرى جزءًا آخر من الذاكرة التي يجب عليك الوصول إليها عبر مؤشر آخر (في حالتك page2). وبالتالي لم يعد على كتلة متجاورة ولا يمكنك استخدام الكتلتين كجزء من صفيف واحد.

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

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

Answer 3

لم تقدم أي تفاصيل عن النظام الأساسي الذي تجربته. هناك بعض الاختلافات في الأداء ل realloc ما بين Linux و Windows, ، فمثلا.

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

سيكون Sugestion الخاص بي هو استخدام النهج الثاني ، أو استخدام مخصص مخصص (يمكنك تنفيذ بسيط تخصيص الأصدقاء [2]).

يمكنك أيضًا استخدام مخصصات الذاكرة أكثر تقدماً ، مثل

• حمامات ذاكرة أبريل
• TCMALLOC من Google

Answer 4

في أسوأ الحالات ، يمكن أن يتسبب الخيار 1 في "تحرك" للذاكرة الأصلية ، وهو عبارة عن مقنع يتم القيام به. إذا لم يتم نقل الذاكرة ، على أي حال ، يتم تهيئة الحجم "الإضافي" ، وهو عمل آخر أيضًا. لذا realloc سيتم "هزيمتها" بواسطة طريقة Malloc ، ولكن لنقول كم ، يجب عليك إجراء الاختبارات (وأعتقد أن هناك تحيزًا على كيفية تنفيذ النظام عندما يتم إجراء طلبات الذاكرة).

اعتمادًا على عدد المرات التي تتوقع فيها تنفيذ RealLoc/Malloc ، قد تكون فكرة مفيدة أو فكرة غير مفيدة. أود استخدام malloc على أي حال.

تعتمد الاستراتيجية الحرة على التنفيذ. لتحرير جميع الصفحات ككل ، يكفي "اجتيازها" ؛ بدلاً من صفيف ، أود استخدام "الصفحات" المرتبطة: إضافة SizeOF (void *) إلى حجم "الصفحة" ، ويمكنك استخدام البايتات الإضافية لتخزين المؤشر إلى الصفحة التالية.

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

Answer 5

في Linux (وربما أنظمة Posix الأخرى) ، هناك احتمال ثالث ، وهو استخدام منطقة تم تعيينها مع الذاكرة shm_open. تتم تهيئة هذه المنطقة بواسطة الأصفار بمجرد الوصول إليها ، ولكن صفحات AFAIK التي لا تصل إليها لا تأتي دون أي تكلفة ، إذا لم تكن مجرد نطاق العنوان في الذاكرة الافتراضية التي تحتفظ بها. لذلك يمكنك فقط حجز جزء كبير من الذاكرة في البداية (أكثر مما ستحتاجه من أي وقت مضى) من التنفيذ الخاص بك ومن ثم ملئها بشكل تدريجي من البداية.

Answer 6

ما هي الطريقة الأكثر كفاءة لحل مشكلة مثل هذه؟ هل هو الخيار 1 أو الخيار 2 أو خيار آخر لم أفكر فيه هنا؟ هل هناك حاجة إلى معيار صغير/ما يكفي لاستخلاص استنتاجات لحالات العالم الحقيقي؟

الخيار 1. لكي تكون فعالة ، يجب أن يعتمد New_size على الحجم القديم غير خطية. وإلا فإنك تخاطر بالركض في أداء O (n^2) لـ RealLoc () بسبب النسخ الزائد. أنا أفعل عمومًا new_size = old_size + old_size/4 (زيادة بنسبة 25 ٪) كأفضل من الناحية النظرية new_size = old_size*2 قد في أسوأ حالة احتياطي الكثير من الذاكرة غير المستخدمة.

الخيار 2. يجب أن يكون أكثر الأمثل لأن معظم OSS الحديثة (بفضل C ++'s STL) تم تحسينه جيدًا بالفعل للفيضانات من تخصيصات الذاكرة الصغيرة. وتخصيصات صغيرة لديها فرصة أقل للتسبب في تجزئة الذاكرة.

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

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

في النهاية ، يجب عليك أيضًا النظر في الخيار رقم 3: LIBC. أعتقد أن Libc's Malloc () فعال بما يكفي للعديد من المهام. يرجى اختباره قبل استثمار المزيد من وقتك. ما لم تكن عالقًا في بعض nix إلى الوراء ، يجب ألا تكون هناك مشكلة في استخدام Malloc () لكل كائن صغير. لقد استخدمت إدارة الذاكرة المخصصة فقط عندما كنت بحاجة لوضع كائنات في أماكن غريبة (على سبيل المثال SHM أو MMAP). ضع في اعتبارك متعدد الخيوط أيضًا: malloc ()/realloc ()/free () عمومًا تم تحسينه بالفعل وجاهز MT ؛ يجب أن تضطر إلى تعويض التحسينات من جديد لتجنب تصادم المواضيع باستمرار على إدارة الذاكرة. وإذا كنت ترغب في الحصول على حمامات أو مناطق الذاكرة ، فهناك بالفعل مجموعة من المكتبات لذلك أيضًا.