تعتبر القسمة واحدة من أغلى العمليات في المعالجات الحديثة. ليس عليك أن تذهب بعيدًا لإثبات: يقوم Agner Fog [
1 ] ببث أنه من خلال معالجات Intel / AMD ، يمكننا بسهولة الحصول على زمن الانتقال في دورات 25-119 على مدار الساعة ، والإنتاجية المتبادلة - 25-120. ترجمت إلى الروسية -
بطيئة ! ومع ذلك ، هناك فرصة لتجنب تعليمات القسمة في التعليمات البرمجية الخاصة بك. وفي هذه المقالة ، سوف أخبرك كيف تعمل ، لا سيما في المجمعين الحديثين (لقد استطاعوا القيام بذلك منذ 20 عامًا بالفعل) ، وسأخبرك أيضًا كيف يمكن استخدام المعرفة المكتسبة لجعل الشفرة أفضل وأسرع وأكثر قوة.
في الواقع ، أنا أتحدث عن: إذا كان المقسوم معروفًا في مرحلة الترجمة ، فمن الممكن استبدال القسمة الصحيحة بالضرب والانتقال المنطقي إلى اليمين (وأحيانًا يمكنك الاستغناء عنه على الإطلاق - أنا بالتأكيد أتحدث عن التطبيق بلغة البرمجة). يبدو الأمر مشجعًا للغاية: تشغيل الضرب الصحيح والانتقال إلى اليمين ، على سبيل المثال ، لن يستغرق Intel Haswell أكثر من 5 دورات على مدار الساعة. يبقى فقط أن نفهم كيف ، على سبيل المثال ، عن طريق إجراء تقسيم عدد صحيح في 10 ، للحصول على نفس النتيجة عن طريق ضرب عدد صحيح وتحول منطقي إلى اليمين؟ تكمن الإجابة على هذا السؤال في الفهم ... حساب النقطة الثابتة (يشار إليه فيما يلي بـ FPA). قليلا من الأساسيات.
عند استخدام FP ، لا يتم حفظ الأس (موضع الأس 2 => موضع النقطة في التمثيل الثنائي للرقم) في الرقم (على عكس حساب الفاصلة العائمة ، راجع IEE754) ، لكنه يعتبر بعض الكمية المتفق عليها المعروفة للمبرمجين. يتم الاحتفاظ فقط السرعوف (ما يأتي بعد العلامة العشرية). مثال:
0.1 - في الترميز الثنائي ، يكون له "تمثيل غير محدود" ، والذي يشار إليه بالأقواس في المثال أعلاه - سيتم تكرار هذا الجزء من وقت لآخر ، يتبع كل منهما الآخر بترميز FP ثنائي بالرقم 0.1.في المثال أعلاه ، إذا استخدمنا سجلات 16 بت لتخزين أرقام FP ، فلن نتمكن من احتواء تمثيل FP للرقم 0.1 في مثل هذا السجل دون فقدان الدقة ، وسيؤثر هذا بدوره على نتيجة جميع العمليات الحسابية الأخرى التي تنطوي على قيمة هذا السجل.
افترض أننا حصلنا على عدد صحيح 16 بت A وجزء كسر 16 بت من B. ينتج منتج A by B رقماً يحتوي على 16 بت في الجزء الصحيح و 16 بت في الجزء الكسري. للحصول على الجزء الصحيح فقط ، من الواضح أنك تحتاج إلى تحويل النتيجة بمقدار 16 بت إلى اليمين.
مبروك ، مقدمة إلى FPA قد انتهت.
نحن نشكل الفرضية التالية: لإجراء تقسيم عدد صحيح بمقدار 10 ، نحتاج إلى ضرب العدد القابل للقسمة بتمثيل FP للرقم 0.1 ، ونأخذ الجزء الصحيح والمادة الموجودة في القبعة ... انتظر لحظة ... ولكن هل ستكون النتيجة دقيقة ، وبدقة أكثر دقة جزءها الصحيح؟ - بعد كل شيء ، كما نتذكر ، في ذاكرتنا يتم تخزين نسخة تقريبية فقط من الرقم 0.1. أدناه ، كتبت ثلاثة عروض مختلفة من 0.1: تمثيل دقيق بشكل لا نهائي 0.1 ، تم قطعه بعد 16 بت دون التقريب ، تمثيل 0.1 ، واقتطاع بعد البتة 16 مع التقريب لأعلى ، تمثيل 0.1.
0001100110011001|10011001....−اللانهايةالدقة :00011001100110011001|00000000....−اقتطاعبدونالتقريب0001100110011010|00000000....−اقتطاعمعالتقريبup
دعونا نقدر أخطاء اقتطاع تمثيلات الرقم 0.1:
infinityprecision−اقتطاعبدونالتقريب=0.6∗2−16الاقتطاعمعالتقريبup−اللانهايةالدقة=0.1∗2−14
من أجل نتيجة ضرب الأعداد الصحيحة A بالتقريب 0.1 لإعطاء الجزء الصحيح الصحيح ، نحتاج إلى:
IntegerPart(A∗0.1)=IntegerPart(A∗(0.1+0.1∗2−14))،
أو
IntegerPart(A∗0.1)=IntegerPart(A∗(0.1+0.6∗2−16))
هو أكثر ملاءمة لاستخدام التعبير الأول: متى
0.1∗2−14∗A<0.1 نحصل دائمًا على الهوية (لكن ، ضع في اعتبارك أن جميع القرارات ليست أكثر من كافية في إطار هذه المشكلة). حل ، نحصل عليه
A<214 . أي بضرب أي رقم من 14 بت A من خلال الاقتراب من جمع تمثيل 0.1 ، نحصل دائمًا على الجزء الصحيح الصحيح ، والذي سنحصل عليه بضرب بلا حدود تمامًا بدقة 0.1 بألف. ، في حالتنا ، ستكون الإجابة غير دقيقة ، ولا يمكننا الوثوق في الضرب البسيط عن طريق اقتطاع 0.1. الآن ، إذا استطعنا توفير تمثيل FP للرقم 0.1 وليس 16 بت ، ولكن ، على سبيل المثال ، 19 ، 20 ، فسيكون كل شيء على ما يرام. وبعد كل شيء نستطيع!
نحن ننظر بعناية إلى التمثيل الثنائي - يتم اقتطاعه مع التقريب لأعلى 0.1: أعلى ثلاثة بتات هي صفر ، مما يعني أنها لا تقدم أي مساهمة في نتيجة الضرب (بتات جديدة).
لذلك ، يمكننا تحويل رقمنا إلى اليسار بثلاث بتات ، مع التقريب ، وبعد إجراء الضرب والانتقال المنطقي إلى اليمين ، أولاً بمقدار 16 ، ثم 3 (وهذا يعني ، بشكل عام في وقت واحد في 19) - نحصل على عدد صحيح صحيح المطلوب . يشبه إثبات صحة مثل هذا الضرب "19" الشيء السابق ، مع أن الفرق الوحيد هو أنه يعمل بشكل صحيح مع أرقام 16 بت. المنطق المنطقي ينطبق أيضًا على أعداد ذات سعة أكبر ، وليس فقط للقسمة على 10.
في وقت سابق ، كتبت أنه ، بشكل عام ، يمكنك الاستغناء عن أي تحول على الإطلاق ، مع قصر نفسك على الضرب. كيف؟ المجمع x86 / x64 على الأسطوانة:
في المعالجات الحديثة ، هناك أمر MUL (هناك أيضًا نظائرها لـ IMUL ، MULX - BMI2) ، والتي ، بأخذ واحدة ، على سبيل المثال ، المعلمة 32/64 بت ، يمكنها إجراء ضرب 64/128 بت ، مما يوفر النتيجة في أجزاء في سجلين (أعلى 32/64 بت والأصغر سنا ، على التوالي):
MUL RCX ; RCX RAX, (128 ) RDX:RAX
اترك بعض الأعداد الصحيحة 62 بت A مخزّنة في سجل RCX ، ودع تمثيل FA 64 بت باقتطاع مع تقريب الرقم 0.1 ليتم تخزينه في سجل RAX (لاحظ ، لا توجد نوبات اليسار). بعد الانتهاء من الضرب 64 بت ، نحصل على أن أعلى 64 بت من النتيجة مخزنة في سجل RDX ، أو بشكل أكثر دقة ، الجزء الصحيح ، والذي سيكون دقيقًا لعدد 62 بت. وهذا هو ، ليست هناك حاجة إلى التحول إلى اليمين (SHR ، SHRX). إن وجود مثل هذا التحول يحمّل خط أنابيب المعالج ، بغض النظر عما إذا كان يدعم OOOE أم لا: على الأقل هناك تبعية إضافية في سلسلة طويلة من الأرجح مثل هذه التبعيات (ويعرف أيضًا باسم سلسلة التبعية). وهنا ، من المهم جدًا الإشارة إلى أن المترجمين المعاصرين ، الذين يرون تعبيرًا عن الشكل some_integer / 10 ، يقومون تلقائيًا بإنشاء رمز المجمّع لكامل مجموعة الأرقام القابلة للقسمة. هذا هو ، إذا كنت تعلم أن لديك دائمًا أرقامًا من 53 بتًا (وهذا هو بالضبط ما كان عليه الحال في مهمتي) ، فإنك لا تزال تحصل على تعليمات الإزاحة الإضافية. ولكن الآن ، بعد أن تفهمت كيف تعمل ، يمكنك بسهولة استبدال تقسيم نفسك بضرب ، دون الاعتماد على رحمة المترجم. بالمناسبة ، الحصول على البتات العالية لمنتج 64 بت في كود C ++ يتم تنفيذه بواسطة شيء مثل mulh ، والذي وفقًا لرمز Asm ، يجب أن يكون مكافئًا لخطوط تعليمات {I} MUL {X} أعلاه.
ربما مع ظهور العقود (في C ++ 20 نحن لا ننتظر) سيتحسن الوضع ، وفي بعض الحالات ، يمكننا الوثوق في السيارة! على الرغم من أن هذا هو C ++ ، فإن المبرمج مسؤول عن كل شيء هنا - وليس غير ذلك.
المنطق الموصوف أعلاه - ينطبق على أي مقسومات من الثوابت ، حسناً ، وفيما يلي قائمة بالروابط المفيدة:
[1] https://www.agner.org/optimize/instruction_tables.pdf[2] أكثر حدة من أجنر فوغ[3] قناة Telegram مع معلومات مفيدة حول تحسينات Intel / AMD / ARM[4] عن التقسيم تماما ، ولكن باللغة الإنجليزية