buddy allocator workshop
1.0.0
يحتوي هذا المستودع على بعض تطبيقات الأمثلة الصغيرة لمخصصات الأصدقاء. وهي مصممة لتخصيص الذاكرة المادية ، على الرغم من أنها يمكن استخدامها لأنواع أخرى من التخصيص ، مثل الكومة. في النهاية ، سيتم دمج أفضل أداء في زهرة.
أولا ، استنساخ الريبو. بعد ذلك ، cd فيه وقم بتشغيل cargo +nightly run لتشغيل جميع مخصصات العرض التجريبي. بشكل افتراضي ، يكون حجم الكتلة 4KIB ومقدار الكتل هو 100000 ، لذلك قد يستغرق ذلك بعض الوقت للحصول على مثال القوائم المرتبطة. لا تقلق ، لن يخصص أي شيء في الواقع - فقط كتل الذاكرة وهمية. تمرير -h أو --help للحصول على المساعدة وعرض الاستخدام. يمكنك تحرير التعليمات البرمجية المصدر لتغيير أحجام كتلة Min/Max ، وما إلى ذلك لتشغيل اختبارات الوحدة ، cargo test . لسوء الحظ ، لا توجد معايير شحن حتى الآن ، لكنني قمت بتقييمها بشكل غير علمي على جهاز Windows الخاص بي.
لقد اختبرت الخوارزميات عن طريق توقيت تطبيقات مختلفة باستخدام الإبلاغ المبني ، وتخصيص gibibyte في كتل 4Kib (مع الطباعة) على جهاز Windows الخاص بي. إذا كان لديك أي معايير أخرى لإضافتها ، فيرجى الاطلاع على المساهمة.
(MSI CX61-2QF)
| تطبيق | وقت | إنتاجية |
|---|---|---|
| قوائم - المتجهات | 2 دقيقة | ~ 8.33e-3 gib/s |
| القوائم - قوائم مرتبطة بشكل مضاعف | 25 دقيقة | ~ 6.66e-4 gib/s |
| أشجار RB - المتجهات | ~ 0.3s | ~ 3.33 gib/s |
| أشجار RB - القوائم المرتبطة بمفرد | ~ 0.5s | ~ 2 gib/s |
| شجرة صورة نقطية | ~ 0.07s | ~ 14.28 gib/s |
ملاحظة: يتم استقراء الإنتاجية من الوقت الذي استغرقته لتخصيص 1 GIB في كتل 4KIB. بالنسبة للتطبيقات التي لها تعقيد> o (log n) (مثل التنفيذ القائم على القائمة الساذجة) ، لن يكون هذا دقيقًا - ستتباطأ الإنتاجية مع تخصيص المزيد من الكتل. يجب أن يكون هذا دقيقًا بالنسبة لأولئك الذين لديهم تعقيد من O (log n) أو أقل.
يحتفظ هذا التنفيذ بقائمة لكل ترتيب كتلة. إنه عام على قوائم typeof المستخدمة. قررت استخدام نوعين من القوائم: المتجهات ( Vec من std ) ، وقوائم مرتبطة بشكل مضاعف ( LinkedList ، أيضًا من std ). غالبًا ما يتم تقييم القوائم المرتبطة لوقت الدفع الذي يمكن التنبؤ به (لا يوجد تخصيص ضروري للدفع) ، في حين أن المتجهات لديها موقع ذاكرة التخزين المؤقت أفضل حيث يتم تخصيص العناصر في كتلة ذاكرة متجاورة. لقد استخدمت قوائم مرتبطة بشكل مضاعف لأنها أسرع للفهرسة من القوائم المرتبطة المنفردة ، حيث يمكن أن تكرر من الخلف أو الأمامي اعتمادًا على ما إذا كان الفهرس أقرب إلى بداية أو نهاية القائمة. قررت اختبار كلاهما لمعرفة أي من سيؤدي بشكل أفضل بشكل عام.
التنفيذ متكرر. لتخصيص كتلة مجانية من الطلب K ، تقوم أولاً بالبحث عن أي كتل مجانية في قائمة كتل Order K. لا يحتفظ بقائمة مجانية. إذا لم يتم العثور على أي منها ، فإنه يتكرر من خلال محاولة تخصيص كتلة من الطلب K + 1. أخيرًا ، إذا لم يتم العثور على أي كتل مجانية في أي وقت من الأوقات. بمجرد أن ينقسمها إلى النصف ، قم بإزالة الكتلة الأصلية من قائمة الطلبات ودفع النصفين إلى قائمة الطلبات على الفور. ثم يعيد ترتيب وفهرسة الكتلة الأولى في قائمة الطلبات الخاصة بها. يمكنك العثور على هذه الخوارزمية في find_or_split .
يقول معيار سريع غير علمي على جهاز Windows الخاص بي أن الأمر استغرق حوالي دقيقتين لتخصيص gibibyte الكامل (1024^3 بايت). لقد لاحظت تقسيم التوقف الثاني بين الحين والآخر عندما كان عليه إعادة تخصيص المتجه بأكمله لدفع عنصر.
std على قوائم مضاعفةيقول معيار مماثل إن الأمر استغرق خمسة وعشرين دقيقة لتخصيص gibibyte الكامل. هذا أكثر من اثني عشر مرة أبطأ من نفس التنفيذ مع المتجهات. ومع ذلك ، لم يتم تحسين هذا التنفيذ للقوائم المرتبطة ، لذلك فهو غير عادل بعض الشيء. على عكس التنفيذ مع المتجهات ، لم ألاحظ أي توقف مؤقت ، لكن التخصيص أصبح أبطأ وأبطأ تدريجياً.
يمكننا أن نستنتج أنه على الرغم من أن القوائم المرتبطة بشكل مضاعف من الناحية النظرية أسرع في الدفع من المتجهات ، إلا أنها كانت لا تزال أبطأ 12 مرة من المتجهات. قد يكون هذا لأن التنفيذ كان لصالح المتجهات (الكثير من الفهرسة) ، أو لأن المتجهات لديها موقع ذاكرة التخزين المؤقت أعلى ، وبالتالي فقد خضعت لذاكرة التخزين المؤقت أقل ، بينما تواجه القوائم المرتبطة أخطاء ذاكرة التخزين المؤقت العالية لأنها لديها عناصر مخصصة بشكل فردي.
يحتفظ هذا التنفيذ بشجرة أسود حمراء واحدة (من intrusive_collections ) لجميع الكتل وقائمة مجانية لكل طلب. تم تنفيذ القوائم المجانية لـ SinglyLinkedList من STD's Vec و intrusive_collections . لقد اخترت قائمة مرتبطة منفردة حيث لم تكن هناك فائدة حقيقية للربط المزدوج - الطريقة الوحيدة التي كانت ستستفيد (بشكل مهمل) هي FreeList::remove ، ولكن هذا يسمى دائمًا على الأكثر في العنصر الثاني في هذه القائمة المجانية ، لذلك لا توجد نقطة حقيقية في تحسين ذلك. تخصص شجرة اللون الأسود الأحمر بشكل فردي كل عقدة ، مما يجعل كفاءة ذاكرة التخزين المؤقت أسوأ ، ولكن على عكس BTreeSet / BTreeMap من std ، فإن بحثها O(log n) ، بينما يستخدم std البحث الخطي ، وهو ليس O(log n) (يمكنك أن تقرأ عن هذا هنا). ومع ذلك ، فإن أشجار std لا تخصص الكومة بشكل فردي العقد ، لذا فإن موقع ذاكرة التخزين المؤقت أفضل. قررت أنه على الرغم من أن هذا كان صحيحًا ، حيث يجب أن يتعامل مخصص الأصدقاء مع أعداد كبيرة بشكل لا يصدق من الكتل ، إلا أنه كان من المهم أن يكون لديك خوارزمية بحث أكثر كفاءة.
التنفيذ متكرر. لتخصيص كتلة مجانية من الطلب k ، تقوم أولاً بالبحث عن أي كتل مجانية في قائمة القائمة المجانية للكتل K. إذا لم يتم العثور على أي منها ، فإنه يتكرر من خلال محاولة تخصيص كتلة من الطلب K + 1. أخيرًا ، إذا لم يتم العثور على أي كتل مجانية في أي وقت من الأوقات. بمجرد أن يقسمها إلى النصف ، إزالة الكتلة الأصلية من الشجرة وإدخال نصفي ، ودفع عناوينها إلى القائمة الحرة ذات الصلة. ثم يعيد مؤشر يشير إلى الكتلة الأولى. يمكنك العثور على هذه الخوارزمية في find_or_split . في الطبقة الخارجية من العودية (الوظيفة التي تستدعي فعليًا وظيفة find_or_split المتكررة) ، يتم وضع علامة على الكتلة التي تم إرجاعها على أنها مستخدمة وإزالتها من القائمة الحرة.
باستخدام المتجهات كقوائم مجانية استغرق ~ 0.3s لتخصيص GIB كامل. هذا هو ~ 0.2s أسرع من القوائم المرتبطة كإصدار قوائم مجانية. ربما يرجع هذا إلى وجود متجهات ذات مخبأ أفضل.
باستخدام القوائم المرتبطة كقوائم مجانية استغرق ~ 0.5s لتخصيص GIB كامل. انظر المتجهات كقسم قوائم مجانية أعلاه.
كان هذا التنفيذ أسرع 400x من التنفيذ القائم على القائمة الساذجة (في أحسن الأحوال ، باستخدام المتجهات كقوائم مجانية). ربما يرجع ذلك إلى أن أشجار الأسود الأحمر لها عمليات O(log n) في جميع أنحاء اللوحة ، أسرع من عمليات البحث ، وإدراج ، وإزالة المتجهات أو القوائم المرتبطة.
هذا التنفيذ ليس بشكل صارم نقطات ، في حد ذاته ، ولكنه تعديل لنظام نقطات. في الأساس ، تخزن كل كتلة في الشجرة أكبر ترتيب (تم دمجه بالكامل) في مكان ما تحته. على سبيل المثال ، تبدو شجرة مجانية مع 4 أوامر مثل:
3
2 2
1 1 1 1
0 0 0 0 0 0 0 0
إذا قمنا بتخصيص كتلة واحدة 0 ، يبدو أن هذا (t هو t aken):
2
1 2
0 1 1 1
T 0 0 0 0 0 0 0
يتم تنفيذه كصفيف مسطح ، حيث مثل شجرة مثل
1
2 3
التمثيل هو 1; 2; 3 . يحتوي هذا على خاصية لطيفة أنه إذا استخدمنا مؤشرات تبدأ من 1 (أي مؤشرات وليس إزاحة) ، فإن فهرس الطفل الأيسر لأي فهرس معين هو 2 * index ، والطفل الصحيح هو ببساطة 2 * index + 1 . الوالد هو floor(index / 2) . نظرًا لأن كل هذه العمليات تعمل مع 2S ، يمكننا استخدام bitshifting فعالة لتنفيذها ( index << 1 ، (index << 1) | 1 ، index >> 1 ).
يمكننا إجراء بحث ثنائي للعثور على الكتلة الخالية من الترتيب المطلوب. أولاً ، نتحقق مما إذا كانت هناك أي كتل للطلب المطلوب مجانًا عن طريق التحقق من كتلة الجذر. إذا كان هناك ، فإننا نتحقق مما إذا كان لدى الطفل الأيسر ما يكفي من الحرية. إذا كان الأمر كذلك ، فإننا نتحقق مرة أخرى من أنه ترك الطفل ، وما إلى ذلك. إذا لم يكن لدى الطفل الأيسر من الكتلة الكتل الكافية مجانًا ، فسنستخدم ببساطة طفله الأيمن. نحن نعلم أن الطفل المناسب يجب أن يكون لديه ما يكفي من الحرية ، أو أن كتلة الجذر غير صالحة.
كان هذا التنفيذ سريعًا جدًا. على جهاز الكمبيوتر الخاص بي ، استغرق الأمر ~ 0.07s فقط لتخصيص 1GIB. لقد رأيت أنه يؤدي ما يصل إلى 0.04s على جهاز الكمبيوتر الخاص بي ، على الرغم من ذلك - يتقلب الأداء قليلاً. أفترض أن هذا يتعلق بحمل وحدة المعالجة المركزية.
لا يحتوي هذا التنفيذ على موقع ذاكرة التخزين المؤقت جيدًا للغاية ، حيث يتم تخزين المستويات بعيدًا عن بعضها البعض ، لذلك يمكن أن تكون كتلة الوالدين بعيدة جدًا عن طفلها. ومع ذلك ، لا يزال كل شيء آخر سريعًا جدًا ، لذلك يتكون من ذلك. إنه أيضًا O (log n) ، ولكن من الناحية العملية ، لا يهم هذا الأمر. للرجوع إليها: استغرق تخصيص 8GIB 0.6s بالنسبة لي ، لكنني رأيته أفضل بكثير في> 150ms على الكمبيوتر المحمول في Gegy1000.
إذا كان لديك أي شيء تضيفه (مثل تحرير إلى ReadMe أو تطبيق آخر أو معيار) لا تتردد في تقديم طلب سحب! يمكنك أيضًا إنشاء مشكلة. إذا كنت ترغب فقط في الدردشة ، فلا تتردد في Ping Me على Discord Restioson#8323).
