ما الذي يؤثر على سرعة برامج C ++ وكيفية تحقيقها بمستوى عالٍ من الكود؟ أجاب Evgeny Petrov ، المطور الرئيسي لمكتبة CatBoost ، على هذه الأسئلة باستخدام أمثلة ورسوم توضيحية من تجربة العمل على CatBoost لـ x86_64.
تقرير بالفيديو
- أهلاً بكم. أقوم بتحسين وحدة المعالجة المركزية لمكتبة التعلم الآلي من CatBoost. الجزء الرئيسي من مكتبتنا مكتوب بلغة C ++. سأخبرك اليوم بأي طرق بسيطة نحقق بها السرعة.
تتكون سرعة الحساب من جزأين. الجزء الأول هو الخوارزمية. إذا أخطأنا في اختيار الخوارزمية ، فلا يمكنك جعلها تعمل بسرعة لاحقًا. الجزء الثاني هو كيفية تحسين الخوارزمية الخاصة بنا لنظام الحوسبة الذي لدينا ، بأدائه وإنتاجيته.
بشكل منفصل ، يجب أخذ تبادل البيانات والحسابات في الاعتبار بسبب الاختلاف الكبير في سرعتها. إذا أخذنا سرعة الذاكرة على أنها سرعة المشاة ، فإن سرعة الحسابات تكون تقريبًا سرعة إبحار طائرة ركاب.
لتخفيف هذا الاختلاف ، تحتوي البنية على عدة مستويات من التخزين المؤقت. الأسرع والأصغر هو ذاكرة التخزين المؤقت L1. ثم هناك ذاكرة تخزين مؤقت أكبر وأبطأ ، المستوى الثاني. وهناك ذاكرة تخزين مؤقت كبيرة جدًا ، يمكن أن تكون عشرات الميجابايت ، ذاكرة تخزين مؤقت من المستوى الثالث ، لكنها الأبطأ.
نظرًا لمعدلات تبادل البيانات المختلفة للحسابات ، يتم تقسيم الكود الحسابي إلى فئتين. فئة واحدة محدودة بالنطاق الترددي ، أي سرعة تبادل البيانات. الفئة الثانية محدودة بسرعة المعالج. يتم تعيين الحدود بينهما اعتمادًا على عدد العمليات التي يتم إجراؤها ببايت بيانات واحد. هذا عادة ما يكون ثابتًا لرمز معين.
تمت كتابة معظم الكود الحسابي الثقيل لفترة طويلة ، وتم تحسينه بشكل جيد للغاية ، وهناك عدد كبير من المكتبات ، لذلك فمن المنطقي إذا رأيت عمليات حسابية ثقيلة في التعليمات البرمجية الخاصة بك ، فابحث عن مكتبة يمكنها القيام بها من أجل أنت.
من بين البقية ، لا يعرف المترجمون كيفية القيام بكل شيء ، حيث يتم إنفاق نسبة محدودة جدًا من الموارد على تطويرهم. أي منهم يتطور بشكل أكثر أو أقل نشاطًا اليوم ، أي أنه يدعم المعايير ويحاول اتباعها؟ هذه هي الواجهة الأمامية EDG ، والتي تستخدم في مشتقات مختلفة ، على سبيل المثال ، مترجم Intel ؛ LLVM. جنو والواجهة الأمامية لمايكروسوفت.
نظرًا لوجود عدد قليل منهم ، فإن المجمعين يدعمون فقط أنماط التحكم في التردد وتبعيات البيانات. إذا نظرنا إلى عنصر التحكم ، فهذه أقسام خطية ودورات بسيطة ، أي سلسلة من التعليمات والتكرار. يتعلمون الاعتماد على التردد على البيانات من الاختزال ، عندما نقوم ، على سبيل المثال ، بجمع العديد من العناصر في عنصر واحد ، وننهار وننفذ إجراءات عنصرًا تلو الآخر على مصفوفة واحدة أو أكثر.
ماذا بقي للمطورين؟ يمكن تقسيم هذا تقريبًا إلى أربعة أجزاء. الأول هو بنية التطبيق ، فالمجمّعون ببساطة غير قادرين على ابتكارها لنا.
التوازي هو أيضًا أمر صعب للمترجمين. العمل مع الذاكرة - لأنه صعب حقًا: يجب أن تأخذ في الاعتبار البنية والتوازي ، وكل ذلك معًا. بالإضافة إلى ذلك ، لا يعرف المترجمون كيفية تقييم جودة التحسين بشكل صحيح ، ومدى سرعة ظهور الكود. نحن ، المطورين ، علينا أيضًا القيام بذلك ، واتخاذ قرار - لتحسين أو التوقف.
في الجزء المتعلق بالهندسة المعمارية ، سننظر في استهلاك المكالمات الظاهرية العلوية ، والتي تستند إليها البنية في عدد كبير من الحالات.
دعنا نترك الموازاة خارج المعادلة. فيما يتعلق باستخدام الذاكرة: هذا أيضًا ، بمعنى من المعاني ، إهلاك والعمل الصحيح مع البيانات ، ووضعها الصحيح في الذاكرة. فيما يتعلق بتقييم الكفاءة ، فلنتحدث عن التنميط وكيفية البحث عن الاختناقات في الكود.
يعد استخدام الواجهات وأنواع البيانات المجردة أحد أساليب التصميم الرئيسية. ضع في اعتبارك رمزًا حسابيًا مشابهًا من التعلم الآلي. هذا رمز شرطي يقوم بتحديث التنبؤ باستخدام طريقة التدرج اللوني.
إذا نظرنا إلى الداخل قليلاً وحاولنا فهم ما يحدث في الداخل ، فسنحصل على واجهة IDerCalcer لحساب مشتقات دالة الخسارة ، ودالة تغير التنبؤ (توقعنا) وفقًا لتدرج دالة الخسارة.
على الجانب الأيمن من الشريحة ، ترى ما يعنيه هذا بالنسبة للحالة ثنائية الأبعاد. وفي التعلم الآلي ، حجم التوقعات ليس اثنين أو ثلاثة ، بل ملايين ، عشرات الملايين من العناصر. دعونا نرى مدى جودة هذه الشفرة لمتجه يبلغ حوالي 10 ملايين عنصر.
لنأخذ الانحراف المعياري كدالة موضوعية ونقيس كيف يعمل ، وكم سيغير هذا التوقع. يتم عرض مشتق هذه الوظيفة الموضوعية على الشريحة. وقت التشغيل على الجهاز الشرطي ، والذي يظل ثابتًا بعد ذلك ، هو 40 مللي ثانية.
دعنا نحاول فهم ما هو الخطأ هنا. أول ما يجذب الانتباه هو المكالمات الافتراضية. إذا نظرت إلى ملف التعريف ، يمكنك أن ترى أنه ، اعتمادًا على عدد المعلمات ، هذا هو حوالي خمسة إلى عشرة تعليمات. وإذا كان حساب المشتق نفسه ، كما في حالتنا ، مجرد عمليتين حسابيتين ، فيمكن أن يتحول هذا بسهولة إلى مقدار كبير من النفقات العامة. بالنسبة لجسم كبير عند حساب المشتقات ، يكون هذا تقريبًا. بالنسبة لجسم قصير يقوم بحساب مشتق - على سبيل المثال ، ليس حتى 500 تعليمات ، ولكن 20 أو 50 أو حتى أقل - ستكون هذه بالفعل نسبة مئوية كبيرة من الوقت. ما يجب القيام به؟ دعنا نحاول تخزين استدعاء الوظيفة الافتراضية مؤقتًا عن طريق تغيير الواجهة.
في البداية ، قمنا بحساب المشتقات نقطة بنقطة ، لكل عنصر من عناصر المتجه على حدة. دعنا ننتقل من معالجة عنصر بعنصر إلى معالجة بواسطة المتجهات. لنأخذ قالب C ++ القياسي ، والذي يسمح لك بالعمل مع عرض على متجه. أو ، إذا كان المترجم الخاص بك لا يدعم أحدث معيار ، فيمكنك استخدام فئة منزلية بسيطة تحتوي على مؤشر للبيانات والحجم. كيف سيتغير الرمز؟ يتبقى لنا استدعاء واحد يحسب المشتقات ، ثم يتعين علينا إضافة حلقة من شأنها أن تحدث التنبؤ بالفعل.
بالإضافة إلى إضافة دورة ، لا يزال يتعين علينا النظر إلى البيانات مرة ثانية ، أي قراءة متجه التنبؤ نفسه ومتجه التدرج اللوني الذي حسبناه للتو مرة ثانية.
سنقوم بالقياس مرة أخرى على نفس الجهاز ونرى ما الذي ظهر بشكل أسوأ ، حدث خطأ ما. دعونا نفهم ما حدث للكود.
ليس من المنطقي الشك في دورة شيء ما ، لأن هذا هو بالضبط نفس نمط التردد الذي يتعرف عليه المترجمون ويقومون بتحسينه جيدًا. سيكون عدد العمليات لكل عنصر بيانات أقل من تكلفة مكالمة افتراضية.
لكن إنشاء متجه كبير ومرور ثانٍ - في هذا المكان ، يجدر الشك في وجود مشكلة. لفهم سبب كون هذا أمرًا سيئًا ويؤدي إلى تباطؤ ، عليك أن تتخيل ما يحدث في الذاكرة عند تشغيل الكود الذي نراه على الشريحة على اليمين.
عندما يتم حساب متجه المشتقات ، يتعلق الأمر بدورة تغير التوقعات. قبل هذه الدورة ، سيبقى جزء صغير جدًا من البيانات في ذاكرة التخزين المؤقت السريعة LXNUMX ، والتي تعمل بتردد المعالج. على الشريحة ، يكون لونه أخضر عند إشارة المرور. سيتم دفع باقي البيانات من ذاكرة التخزين المؤقت إلى الذاكرة ، وعندما تنتقل الحلقة لتحديث التنبؤات ، يجب قراءة البيانات من الذاكرة مرة ثانية. وهي تعمل بالنسبة لنا ، بشكل عام ، ببطء شديد ، بسرعة المشاة.
عندما نقوم بتحديث التوقعات ، لا يتعين علينا قراءة جميع المشتقات مرة واحدة. يكفي عدها في حزم كبيرة لاستيعاب المكالمات الافتراضية. لذلك ، من المنطقي تقسيم حساب المشتقات وتحديث التنبؤ إلى كتل صغيرة وخلط هذين الإجراءين. ما الذي سيؤدي إليه هذا إذا نظرت إلى المكان الذي ستُقرأ منه البيانات؟
سيؤدي ذلك إلى حقيقة أننا سنأخذ البيانات طوال الوقت ، وإلى حقيقة أن البيانات ستبقى في ذاكرة التخزين المؤقت L1 ولن يتوفر لها الوقت للانتقال إلى الذاكرة البطيئة. ومن ثم علينا أن نفهم من سيخبرنا بحجم الكتلة هذا.
من المنطقي أن نعهد إلى الآلة الحاسبة المشتقة نفسها ، لأنه فقط يعرف مقدار ذاكرة التخزين المؤقت التي يحتاجها. بعد ذلك ، تحتاج إلى إعادة كتابة الحلقة التي بحثنا فيها من خلال المصفوفة. يجب تقسيمها إلى قسمين. سوف تمر الحلقة الخارجية عبر الكتل ، وفي الداخل سنمر بعناصر الكتلة مرتين.
ها هو خارجي بالكتل.
وهنا العنصر الداخلي للكتلة.
نأخذ في الاعتبار أن الكتلة الأخيرة قد تكون غير مكتملة.
دعونا نرى ما يأتي منه. نرى أننا خمّننا بشكل صحيح ، وفهمنا بشكل صحيح ما كان يحدث ، وبتكلفة تغييرات صغيرة نوعًا ما في الكود ، قللنا وقت العمل بنسبة ثمانية بالمائة. لكن يمكننا فعل المزيد. نحن بحاجة إلى إلقاء نظرة نقدية أخرى على ما كتبناه. انظر إلى الدالة التي تحسب المشتقات لنا. إنها تعيد لنا متجهًا للمشتقات ، سيكون الوصول إلى عناصرها في المواقف المعاكسة بطيئًا.
هناك سببان. أولاً ، تخصيص متجه على الكومة. من الجيد أن يتم إنشاء هذا المتجه وتدميره بشكل متكرر. العيب الثاني من حيث السرعة هو أنه في كل مرة نتلقى ذاكرة ، ربما في عنوان جديد. ستكون هذه الذاكرة "باردة" من وجهة نظر ذاكرة التخزين المؤقت ، أي قبل الكتابة إليها ، سيقوم المعالج بإجراء قراءة إضافية لتهيئة البيانات الموجودة في ذاكرة التخزين المؤقت.
لإصلاح ذلك ، تحتاج إلى إخراج التخصيص من الحلقة. للقيام بذلك ، سيتعين علينا تغيير الواجهة مرة أخرى ، والتوقف عن إرجاع المتجهات والبدء في كتابة المشتقات في الذاكرة التي نتلقاها من رمز الاستدعاء.
هذه تقنية قياسية - إزالة جميع عمليات التلاعب بالموارد من الاختناقات في التعليمات البرمجية الحسابية. دعنا نضيف معلمة أخرى إلى طريقة CalcDer ، اعرض على المتجه حيث يجب أن تسقط المشتقات.
سيتغير الرمز أيضًا بطريقة واضحة. سيكون المتجه المشتق واحدًا ، خارج كل الحلقات ، وسيُضاف معامل جديد ببساطة إلى الطريقة.
نحن ننظر. اتضح أننا فزنا بحوالي ثمانية بالمائة أخرى مقارنة بالإصدار السابق ، ومقارنة بالإصدار الأساسي - بالفعل 15٪.
من الواضح أن التحسينات لا تقتصر على إطفاء التكاليف العامة ، وأن هناك أنواعًا أخرى من الاختناقات.
لتوضيح كيفية البحث عن الاختناقات ، نحتاج إلى رمز تجريبي بسيط آخر. على سبيل المثال ، أخذت نقل المصفوفة. لدينا مصفوفة تقريبية ومصفوفة تقريبية حيث نحتاج إلى وضع البيانات المنقولة. وعش بسيط من دورتين. لا توجد مكالمات افتراضية هنا لإنشاء ناقلات. إنه مجرد نقل بيانات. الحلقة مريحة نسبيًا للمترجم.
دعونا نقيس كيفية عمل هذا الرمز على مصفوفة كبيرة بما فيه الكفاية وعلى جهاز معين.
على سبيل المثال ، أخذت عدد الصفوف 1000 ، عدد الأعمدة 100. الجهاز عبارة عن خادم Intel ، نواة واحدة. الذاكرة بهذه الطريقة ، إنها مهمة بالنسبة لنا ، لأن كل العمل بالذاكرة والسرعة سيعتمدان على سرعة الذاكرة. قمنا بالقياس وحصلنا على 000 ثانية. هل هو كثير أم قليلا؟ ماذا يمكننا أن نفعل خلال هذا الوقت؟
لدينا الوقت لقراءة 800 ميغا بايت ، هذه ليست مصفوفة منقولة ، لكنها مصفوفة أصلية. وأيضًا قراءة وكتابة 1,6 جيجا بايت ، فهذه بالفعل مصفوفة منقولة. يقوم المعالج بقراءة مساعدة قبل الكتابة لتهيئة البيانات في ذاكرة التخزين المؤقت.
دعنا نحسب مقدار عرض النطاق الترددي الذي استخدمناه مع الفائدة. اتضح أن معدل نقل الكود الخاص بنا كان 1,7 جيجابايت / ثانية.
لقد كان حسابًا نظريًا. ثم يمكنك أن تأخذ ملف تعريف يمكنه قياس سرعة العمل مع الذاكرة. أخذت VTune. دعونا نرى ما يظهر. يظهر رقم مماثل - 1,8 جيجا بايت. من حيث المبدأ ، يتفق جيدًا ، لأنه في حساباتنا لم نأخذ في الاعتبار أنه يتعين علينا قراءة عناوين الصفوف وعناوين الأعمدة. بالإضافة إلى ذلك ، يقوم VTune بتسجيل نشاط الخلفية مع نظام التشغيل. لذلك ، فإن نموذجنا يتوافق مع الواقع.
لفهم ما إذا كانت 1,7 جيجا بايت كبيرة أو قليلة ، تحتاج إلى معرفة الحد الأقصى لعرض النطاق الترددي المتاح لنا.
للقيام بذلك ، تحتاج إلى قراءة المواصفات الموجودة على المعالج. يوجد موقع خاص ark.intel.com حيث يمكنك معرفة كل شيء عن أي معالج. إذا نظرنا على وجه التحديد إلى خادمنا ، فسنجد أنه يحتوي على ثمانية مراكز ولأسرع ذاكرة DDR3 يدعمها ، يتم نقله بسرعة 60 جيجابايت / ثانية في اتجاه واحد.
ولكن هنا يجب أن نأخذ في الاعتبار أننا نستخدم نواة واحدة فقط وأن ذاكرتنا أبطأ ، أي أننا بحاجة إلى توسيع مساحة 60 جيجا بايت لظروفنا بما يتناسب مع عدد النوى وتردد الذاكرة.
اتضح أن الكود الخاص بنا يمكن أن يستخدم 5,3 جيجا بايت في اتجاه واحد. وبما أنه يمكنك القراءة والكتابة بالتوازي ، فمن الأفضل إذا نسخنا البيانات من مكان إلى آخر ، فسنصل إلى 10,6. نظرًا لأن لدينا قراءتان وكتابة واحدة ، يجب أن يكون حوالي 8 جيجابايت / ثانية. نتذكر أننا حصلنا على 1,7. أي أننا استخدمنا في مكان ما حوالي 20٪.
لماذا هو كذلك؟ مرة أخرى ، تحتاج إلى التعامل مع الهندسة المعمارية. الحقيقة هي أن البيانات بين الذاكرة وذاكرة التخزين المؤقت لا يتم نقلها في حزم عشوائية ، ولكن في 64 بايت بالضبط ، لا أكثر ، ولا أقل. هذا هو الاعتبار الأول.
الاعتبار الثاني هو أننا نكتب البيانات المنقولة ليس بالتسلسل ، ولكن بشكل عشوائي ، لأن صفوف المصفوفة موجودة في الذاكرة بطريقة لا يمكن التنبؤ بها.
اتضح أنه قبل كتابة عدد حقيقي واحد ، علينا طرح 64 بايت من البيانات. إذا أشرنا إلى حجم المصفوفة N ، فبدلاً من وقت التشغيل الأمثل (N / 5,3 + N / 10,6) ، نحصل على (8 * N / 5,3 + N / 10,6). في مكان ما من أربع إلى خمس مرات أكثر ، وهو ما يفسر هذه الكفاءة بنسبة 20 ٪.
ماذا نفعل معها؟ تحتاج إلى التوقف عن كتابة البيانات في عمود واحد والبدء في كتابة أكبر عدد ممكن من الأعمدة في سطر ذاكرة تخزين مؤقت واحد (64 بايت). للقيام بذلك ، قمنا بتقسيم الدورة على الأعمدة إلى دورة فوق خطوط ذاكرة التخزين المؤقت وحلقة متداخلة فوق عناصر سطر ذاكرة التخزين المؤقت.
ها هم ، التكرارات على سطور ذاكرة التخزين المؤقت.
وها هم ، التكرارات داخل سطر ذاكرة التخزين المؤقت. هنا ، من أجل التبسيط ، نفترض أن البيانات تتماشى مع حدود خط ذاكرة التخزين المؤقت. الآن دعنا نتحقق مع VTune مما يحدث.
نرى ما حدث بالقرب من ثمانية غيغابايت المحسوبة في الثانية - 7,6. ولكن ليس من المعروف بعد أن كل هذه 7,6 هي عمل مفيد. ربما البعض منهم فوق.
لفهم مقدار الفائدة التي حصلنا عليها ، دعنا نقيس وقت التشغيل بعد التحسين. اتضح 0,5 ثانية على نفس الجهاز. أصبح معدل النقل ، الذي يتم حسابه بواسطة التحويل نفسه ، 4,8 جيجابايت / ثانية. يمكن ملاحظة أنه لا يزال هناك هامش لم نختاره ، لكن على أي حال ، حصلنا على 20 في المائة من 60 في المائة من الكفاءة.
بمساعدة المحلل ، يمكنك معرفة سبب عدم حصولنا على 80٪ أو 95٪.
الحقيقة هي أننا نخزن المصفوفات كمتجه للمتجهات ، أي أننا نستخدم الوصول إلى الذاكرة مع المراوغة المزدوجة.
باستخدام VTune ، يمكنك معرفة التعليمات التي تم إنشاؤها للوصول إلى عناصر المصفوفة. يتم تمييز التعليمات التي تطرح عناوين أعمدة المصفوفة المنقولة باللون الأصفر على اليسار. وهذه ، أولاً ، تعليمات إضافية ، وثانياً ، عمليات نقل بيانات إضافية. لكننا لن نحسن أكثر ، سنتوقف ونلخص.
ماذا قلت لك اليوم؟ نصيحة مفيدة للعمل مع الكود الحسابي هي المعالجة في كتل ، لاستهلاك التكاليف العامة المرتبطة ، على سبيل المثال ، بالمكالمات الافتراضية. بالإضافة إلى ذلك ، بسبب الحظر ، يتحسن موقع البيانات ، ونحصل على سرعة وصول أعلى.
إزالة المخصصات من الاختناقات هو أيضا استهلاكها. وأيضًا زيادة سرعة الوصول عن طريق إصلاح مخازن مؤقتة في الذاكرة.
حول التنميط. أولاً ، يعتبر التنميط تقنية مفيدة لإيجاد الاختناقات "في الحالة العامة". ثانيًا ، يسمح لنا بتقييم كفاءة الكود ، وتحديد ما إذا كنا راضين عن السرعة أو نريد المزيد من التحسين ، ويظهر في أي اتجاه نتحرك.
هذا كل شيء بالنسبة لي. إذا كنت تستخدم CatBoost أو سمعت عنه لأول مرة وترغب في معرفة ما هو ، فاقرأ تعال لزيارتنا ، اكتب ل . شكرا جزيلا لكم على اهتمامكم.
المصدر: www.habr.com
