تنفيذ خوارزميات عالية الأداء يدويا في .NET

Question

كخبرة تعليمية حاولت مؤخرا تنفيذها QuickSort مع 3 طريقة التقسيم في ج #.

بصرف النظر عن الحاجة إلى إضافة فحص نطاق إضافي على المتغيرات اليسرى / اليمنى قبل المكالمة المتكررة، يبدو أن العمل جيدا.

كنت أعرف مسبقا أن الإطار يوفر تطبيق QuickSort المدمج في القائمة <>. فرز (عبر Array.Sort). لذلك حاولت بعض التنميط الأساسي لمقارنة الأداء. النتائج: القائمة المدمجة في <>. طريقة فرز، تعمل في القوائم نفسها، تؤدي حوالي 10 مرات أسرع من تطبيقي اليدوي الخاص بي.

باستخدام العاكس، وجدت أن الفرز الفعلي في القائمة <> يتم تطبيق هذا النوع في التعليمات البرمجية الخارجية، وليس IL (في وظيفة تسمى TrySzSort ()).

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

لذا سؤالي: هل من الواقعي أن نتوقع أن يكون الأداء في خوارزمية محسنة (مكتوبة في .NET IL، جيتز إلى الرمز الأصلي) يمكن أن يتنافس مع أداء خوارزمية مطبوعة خارجيا؟

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

لذلك إذا كنت بحاجة إلى تنفيذ مثل هذه الخوارزمية في .NET، فما هي اعتبارات الأداء الرئيسية لفهمها، بحيث يمكن لخوارجك أن تقترب على الأقل أداء الرمز الخارجي؟

تحديث

لقد قمت بتحسين سرعة التنفيذ إلى داخل حوالي 10٪ من الصفات المضمنة. من خلال تغيير الخوارزمية للعمل على مجموعة بسيطة من int، بدلا من القائمة. في العاكس، أستطيع أن أرى أن هذا يتجنب عملية CallVirt () على كل الحصول على القائمة أو تعيينها في القائمة. اعتقدت أن هذا قد يحسن الأشياء، لكنني فوجئت كم

Answer 1

باستخدام رمز غير متقيد، وخاصة، باستخدام كتل "غير آمنة" ومؤشر حساب حسابي (إن وجد) استطاع في الواقع رؤية مكاسب أداء X5 أو X10 مع خوارزمية مكتوبة في C #. كما هو الحال دائما مع الأداء (وأكثر من ذلك عند التعامل مع بيئة مدارة)، فأنت لا تعرف أبدا حتى تجربته ومعيارها.

الآن، في عموما التحدث، يجب عليك الكتابة في الغالب الأشياء في C #، ثم تحسينه، وتحسين الأمر، وإذا لم يكن الأمر كذلك، فسيظل غير جيد بما فيه الكفاية، حدد القطعة الحرجة الدقيقة، وينفذها إلى C ++ (أثناء حذرين عن الحد من الرقم حدود المكالمات المدارة / الأم).

Answer 2

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

على افتراض أنك قمت بتجميعه في وضع الإصدار، لا ينبغي أن يكون هناك اختلاف كبير في الأداء إذا قمت بتنفيذ الخوارزمية بالمثل (أي تكراري مقابل تكراري أو متكرر مقابل العودية). إذا كنت ترغب في رؤية تنفيذ .NET والشكل، يمكنك تنزيل SSCLI، شارك-مصدر البنية التحتية اللغوية المشتركة. وبعد هذا هو تطبيق CLI متوافق مع CLI المتوافق مع Microsoft. ليس 100٪ من .NET Framework نعلم جميعا والحب، لكنه جزء مهم منه. يمكن أن توفر الكثير من المعلومات التي لا يستطيع العاكس، بما في ذلك التطبيقات الداخلية. تتوفر جميع أنواع الكود، بما في ذلك C #، C ++، وحتى بعض المجمع في حالات زوجين.

Answer 3

تأكد من مقارنة التفاح والتفاح.

عند الفرز، من الممكن أن تكون الوظيفة المقارنة مهيمنة، وقد تختلف ذلك بين التطبيقات.

على افتراض الوظيفة المقارنة في كلتا الحالتين بسرعة كافية لا تكون مشكلة، فإن الوقت يمكن أن تهيمن عليه الأشياء مثل التحقق من حدود الصفيف، والتي يمكن أن تحدث فرقا كبيرا بسهولة.