باستخدام RealLoc في C ++

Question

std::realloc أمر خطير في C ++ إذا كانت ذاكرة malloc'd تحتوي على أنواع غير POD. يبدو فقط المشكلة هي ذلك std::realloc لن اتصل بـ Type Destructors إذا لم يتمكن من نمو الذاكرة في الموقع.

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

هذا يبدو مفيدًا للغاية. std::vector يمكن أن تستفيد بشكل كبير من هذا ، وربما تجنب جميع النسخ/إعادة التخصيص.
تأخير اللهب وقائي: من الناحية الفنية ، هذا هو نفس الأداء الكبير ، ولكن إذا كان نمو المتجه عبارة عن رقبة زجاجة في تطبيقك ، فإن سرعة x2 لطيفة حتى لو كان Big-O لم يتغير.

لكن ، لا يمكنني العثور على أي واجهة برمجة تطبيقات C تعمل مثل أ try_realloc.

هل فاتني شيء؟ هو try_realloc ليست مفيدة كما أتخيل؟ هل هناك بعض الأخطاء المخفية التي تصنع try_realloc غير صالح للاستخدام؟

والأفضل من ذلك ، هل هناك بعض واجهة برمجة التطبيقات الأقل توثيقًا التي تؤدي مثلها try_realloc?

ملاحظة: من الواضح أنني في رمز محدد للمكتبة/النظام الأساسي هنا. أنا لست قلقًا try_realloc هو بطبيعته تحسين.

---

تحديث:بعد تعليق ستيف جيسوب على ما إذا كان vector سيكون أكثر كفاءة باستخدام RealLoc كتبت دليلًا على المفهوم للاختبار. ال realloc-vector يحاكي نمط نمو المتجه ولكن لديه خيار لإحداثه بدلاً من ذلك. قمت بتشغيل البرنامج حتى مليون عنصر في المتجه.

للمقارنة vector يجب تخصيص 19 مرة بينما تنمو إلى مليون عنصر.

النتائج ، إذا كان realloc-vector هو الشيء الوحيد الذي يستخدم الكومة ، والنتائج رائعة ، 3-4 تخصيص مع النمو بحجم مليون بايت.

إذا realloc-vector يستخدم جنبا إلى جنب vector أن ينمو بنسبة 66 ٪ من سرعة realloc-vector النتائج أقل واعدة ، وتخصيص 8-10 مرات أثناء النمو.

أخيرًا ، إذا كان realloc-vector يستخدم جنبا إلى جنب vector أن ينمو بنفس المعدل ، realloc-vector يخصص 17-18 مرة. بالكاد حفظ تخصيص واحد على سلوك المتجه القياسي.

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

Answer 1

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

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

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

إذا vector بطيء بسبب إعادة التخصيص ، deque قد يكون بديلا جيدا.

Answer 2

يمكنك تنفيذ شيء مثل try_realloc اقترحت ، باستخدام mmap مع MAP_ANONYMOUS و MAP_FIXED و mremap مع MREMAP_FIXED.

يحرر: لاحظت للتو أن صفحة Man for Mremap تقول:

يستخدم MREMAP () مخطط جدول صفحة Linux. MREMAP () يغير التعيين بين العناوين الافتراضية وصفحات الذاكرة. يمكن استخدام هذا لتنفيذ RealLoc فعال للغاية (3).

Answer 3

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

طالما أنك لا تقوم باستمرار بإعادة تخصيص صفيفك في كل مرة تضيف فيها عنصرًا ، ولكن بدلاً من ذلك تنمو الصفيف بشكل كبير (على سبيل المثال بنسبة 25 ٪ أو 50 ٪ أو 100 ٪) كلما نفدت من الفضاء ، فقط تخصيص ذاكرة جديدة يدويًا ، إن نسخ ، وتحرير القديم سيؤدي إلى نفس الأداء (ومتطابق ، في حالة تجزئة الذاكرة) لاستخدامه realloc. هذا بالتأكيد هو النهج الذي تستخدمه تطبيقات C ++ STL ، لذلك أعتقد أن اهتمامك كله لا أساس له من الصحة.

يحرر: حالة (نادرة ولكن غير مسموح بها) حيث realloc من المفيد بالفعل أن تكون الكتل العملاقة على الأنظمة ذات الذاكرة الافتراضية ، حيث تتفاعل مكتبة C مع kernel لنقل الصفحات بأكملها إلى عناوين جديدة. السبب في أنني أقول أن هذا أمر نادر الحدوث هو أنك تحتاج إلى التعامل مع كتل كبيرة جدًا (على الأقل عدة مئات من كيلو بايت) قبل أن تدخل معظم التطبيقات في مجال التعامل مع تخصيص الحصرية ، وربما أكبر بكثير (عدة ميغابايت ربما) قبل الدخول والخروج من مساحة kernelspace لإعادة ترتيب الذاكرة الافتراضية هو أرخص من مجرد القيام بالنسخة. بالطبع try_realloc لن تكون مفيدة هنا ، لأن الفائدة كلها تأتي من الواقع القيام بهذه الخطوة غير مكلفة.