شكل رنين يبطئ البرنامج

سنقوم اليوم بقياس أداء التطبيقات المختلفة لوظيفة toupper ، لأن هذا ما يفعلونه كل يوم ثلاثاء.

في الواقع ، لا أهتم بوظيفة toupper ، لقد كتبت للتو وظيفة أخرى مؤخرًا وكنت بحاجة إلى نوع من النواة الشائعة ، ويبدو أن toupper مرشح مثير للاهتمام وغير ضار للمعايير. حاولت أن أختار شيئًا بسيطًا بقدر الإمكان لن يدفعني جانباً ، لكن حدث ما حدث في هذا الاختبار أنني واجهت مشكلة غريبة.

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

لذلك ، دعونا نلقي نظرة على ثلاثة تطبيقات لوظيفة toupper ، والتي تحول أحرف صفيف تتكون من عناصر type char إلى أحرف كبيرة - وهي تأخذ صفيفًا كوسيطة وتغير عناصرها مباشرةً بحيث يتم تكبير الأحرف الكبيرة.

في التطبيق الأول ، ندعو ببساطة الدالة toupper [1] للمكتبة القياسية C وننفذ حلقة نمط C:

void toupper_rawloop(char* buf, size_t size) { for (size_t i = 0; i < size; i++) { buf[i] = toupper(buf[i]); } } 

في التطبيق الثاني ، نستخدم نهجًا أكثر حداثة مع استبدال الدورة الخام بـ std :: convert :

 void toupper_transform(char* buf, size_t size) { std::transform(buf, buf + size, buf, ::toupper); } 

أخيرًا ، في التطبيق الثالث ، نستخدم خوارزمية خاصة تعمل مع أحرف ASCII. يتحقق ما إذا كان الحرف في النطاق a - z ، وإذا نجح ، يستبدل نفس الحرف في الحالة العليا ، مع طرح الرقم 32 من رمز الحرف [2]:

 void toupper_branch(char* buf, size_t size) { for (size_t i = 0; i < size; i++) { char c = buf[i]; if (c >= 'a' && c <= 'z') { buf[i] = c - 32; } } } 

تبدو سهلة ، أليس كذلك؟

سنقوم الآن بقياس سرعة هذه التطبيقات على جهاز الكمبيوتر المحمول بواسطة معالج Skylake i7-6700HQ على برنامج التحويل البرمجي gcc 5.5 بالإعدادات الافتراضية. وترد النتائج في شكل مخطط مبعثر [3]:

على الفور ، سنتعامل مع ثلاثة أسئلة لا صلة لها بمهمتنا.

أولاً ، انظر إلى الرسم البياني لخوارزمية التفريع (كما هو موضح باللون الأخضر). يختلف اختلافًا كبيرًا وفقًا لحجم بيانات الإدخال - يبقى الرسمان الآخران مسطحين تقريبًا. هذا هو في الواقع مجرد قطعة أثرية الاختبار. يتم اختيار أحرف ASCII المدخلة بشكل عشوائي [4] ، وبالتالي ، فإن العامل الحاسم في حالة التنفيذ الثالث هو تشغيل خوارزمية تنبؤ الفرع. مع كمية صغيرة من البيانات ، فإنه يحفظ تماما تسلسل العناصر كما يتم تنفيذ التكرار ، وبالتالي فإن عدد يخطئ صغير وسرعة عالية ، كما هو مبين في هذه الملاحظة . مع نمو حجم تسلسل البيانات ، تتذكر خوارزمية التنبؤ أقل وأقل حتى تبدأ أخيرًا في فقدان كل حرف كبير (0.27 حرف لكل حرف) ، ثم يتم تسوية الرسم البياني.

ثانياً ، انتبه إلى مجموعة البقع الخضراء في أعلى اليسار ، والتي تقابل سرعات أقل بكثير من المتغير مع toupper_branch branching:

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

ثالثًا ، يبدو تنفيذ toupper_rawloop (كما هو موضح باللون الأزرق) على الرسم البياني كخطين منفصلين: أحدهما أعلى بقليل من علامة 2 مقاييس لكل حرف ، والآخر عند مستوى 1.5 مقاييس لكل حرف. ظهر هذان الخطان في جميع الاختبارات. الخيار الأسرع ، بسرعة 1.57 حرفًا في كل دورة ، يبطئ فعليًا على منافذ التنزيل: تحدث قراءة البيانات على المنفذين 2 و 3 بسرعة 1.54 من العمليات المصغرة لكل دورة ، بحيث تكون مشغولة بنسبة 98٪. لم أتمكن من تحديد سبب "النظام" الأبطأ.

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

ما الذي يهمنا إذن في هذا المثال؟

ولكن ما يهمنا هو أن الإصدار ذو الدورة الأولية أسرع من 3 إلى 4 مرات من الإصدار مع std :: convert: 1.5-2 دورة لكل حرف مقابل 7 مع بضع دورات لكل حرف.

ما هي المسألة هنا؟ هل فشلت الخوارزميات القياسية؟ هل الأمراض المنقولة جنسيا :: تحويل لديها أي عيب؟

ليس حقا بتعبير أدق ، ليس على الإطلاق.

اتضح أن هذه النتائج تظهر عندما يتم تجميع الوظائف في ملفات مختلفة . إذا وضعتهم في نفس الملف ، يصبح أدائهم منخفضًا على حد سواء.

ولا ، لا علاقة للمحاذاة به.

ولكن هذا ليس كل شيء: النسخة السريعة ذات الدورة الأولية ، عندما يتم تجميعها في ملف منفصل ، تبطئ إذا قمت ببساطة بإرفاق ملف الرأس <algorithm> به. نعم ، هذا صحيح: ما عليك سوى توصيل هذا الملف ، والذي لا يتم استخدامه مطلقًا ولا يُنشئ أي رمز في ملف الكائن النهائي ، وستنخفض سرعة الدورة "الأولية" 3-4 مرات. على العكس من ذلك ، يتم تسريع الإصدار مع std :: convert إلى الحد الأقصى إذا قمت بنسخ ولصق تطبيق std :: convert من ملف <algorithm> ، لكن لا تقم بتضمين هذا الملف.

الغايات لا تنتهي عند هذا الحد (لن يكون هناك المزيد ، فأعدك بذلك): بما في ذلك ملف <algorithm> لا يؤدي دائمًا إلى التأثير الموصوف. يحدث انخفاض السرعة إذا كان <algorithm> متصلًا قبل <ctype.h> ، ولكن إذا قمت بتبديلهما ، فلا:

رمز بطيء:

 #include <algorithm> #include <ctype.h> 

كود سريع:

 #include <ctype.h> #include <algorithm> 

في الواقع ، ظهر هذا الشذوذ في داخلي (في مشروع آخر) عندما قام clang-format تلقائيًا بفرز ملفات الرأس المضمنة ووضع <algorithm> في بداية القائمة ، حيث ينتمي (ومن ثم رأس clickbait للمقال).

وبطبيعة الحال ، كان علينا أن نغرق في قائمة المجمّع عاجلاً أم آجلاً. لن نؤخر هذه اللحظة غير السارة.

يتم عرض الإصدارات السريعة والبطيئة للوظائف [5] أدناه ، ويتم توفير حلقات صغيرة مع تعليقات توضيحية:

تتصل الخوارزمية أولاً:

 toupper_rawloop(char*, unsigned long): push rbp push rbx lea rbp, [rdi+rsi] sub rsp, 8 test rsi, rsi je .L1 mov rbx, rdi .L5: movsx edi, BYTE PTR [rbx] ;  char-  *buf add rbx, 1 ; buf++ call toupper ;  toupper(c) mov BYTE PTR [rbx-1], al ;    buf[-1] cmp rbp, rbx ;  buf == buf_end jne .L5 ; .L1: add rsp, 8 pop rbx pop rbp ret 

<الخوارزمية> متصلة الثانية:

 toupper_rawloop(char*, unsigned long): test rsi, rsi je .L7 push rbp push rbx mov rbp, rsi mov rbx, rdi sub rsp, 8 call __ctype_toupper_loc lea rsi, [rbx+rbp] mov rdi, rbx .L4: ;  char-  buf movsx rcx, BYTE PTR [rdi] ;      toupper ; (   __ctype_toupper_loc) mov rdx, QWORD PTR [rax] ; buf++ add rdi, 1 ;   toupper  , ;       mov edx, DWORD PTR [rdx+rcx*4] mov BYTE PTR [rdi-1], dl ;   cmp rsi, rdi ;  buf == end_buf jne .L4 ; add rsp, 8 pop rbx pop rbp .L7: rep ret 

الفرق الرئيسي هو أنه في الإصدار البطيء ، يتم استدعاء وظيفة toupper ببساطة في حلقة ، بينما في النسخة السريعة ، تكون مكالمات الوظيفة غائبة تمامًا ، ولا يوجد سوى بحث في جدول المراسلات [6] ، أي يتم استبدال نص الدالة std :: toupper في مكان الاستدعاء.

إذا نظرت إلى الكود المصدري لمكتبة glibc ، فإننا نجد تنفيذ وظيفة toupper هناك:

 __extern_inline int // __NTH –  , ,      __NTH (toupper (int __c)) { return __c >= -128 && __c < 256 ? (*__ctype_toupper_loc ())[__c] : __c; } 

كما نرى ، يُعرّف toupper على أنه دالة مضمّنة خارجية تتحقق أولاً من أن حجم الحرف char يتلاءم مع بايت واحد [7] ، ثم يبحث عن الحرف في جدول المراسلات الذي يتم إرجاعه بواسطة الدالة __ctype_toupper_loc () . تقوم هذه الوظيفة بإرجاع مؤشر دفق محلي (من النوع const int ** ) ، والذي بدوره يشير إلى جدول المراسلات ، والذي يتم من خلاله استجابة لطلب رمزنا ، إرجاع إصدار الحالة العلوي الخاص به [8].

أصبح من الواضح الآن ما يحدث في القائمة. في الإصدار السريع من الخوارزمية ، يستبدل المترجم نص الدالة toupper ، ولكن لا يمكن استبدال الاستدعاء للدالة __ctype_toupper_loc () [9]. ومع ذلك ، يتم الإعلان عن هذه المكالمة كـ __attribute __ ((const)) ، مما يعني أن قيمة الإرجاع تعتمد فقط على الوسيطات (التي ليست هنا). يعرف المترجم أن هذه الوظيفة تُرجع نفس القيمة في كل مرة ، وبالتالي تأخذ مكالمتها خارج الحلقة ، وفي الحلقة نفسها توجد فقط بضع عمليات قراءة مرتبطة بالوصول إلى جدول المراسلات ، وكتابة قيمة جديدة إلى المخزن المؤقت ، والتحكم في الحلقة.

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

  lea edx,[rdi+0x80] ; edx = rdi + 0x80 movsxd rax,edi ;    c cmp edx,0x17f ; ,  c     -128  255 ja 2a ;  ,   mov rdx,QWORD PTR [rip+0x395f30] ;    ;   mov rdx,QWORD PTR fs:[rdx] ;     ;     mov rdx,QWORD PTR [rdx] ;    ;    mov rdx,QWORD PTR [rdx+0x48] ;     toupper mov eax,DWORD PTR [rdx+rax*4+0x200] ;  c   2a: ret 

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

لماذا هذا هكذا؟

في سلسلة طويلة من ملفات التضمين ، تتضمن ملفات رأس C ++ ، مثل <algorithm> ، بدورها ، ملف <bits / os_defines.h> ، والذي يحتوي على السطر التالي:

 //      isanum  .  //   . #define __NO_CTYPE 1 

عندما يتم توصيل الملف <ctype.h> أخيرًا ، بسبب هذا التوجيه ، لا يمكن تضمين التعليمات البرمجية التي يتم تعريف toupper على أنها مضمنة خارجي :

 #if !defined __NO_CTYPE # ifdef __isctype_f __isctype_f (alnum) //  ..  .. __isctype_f (xdigit) # elif defined __isctype # define isalnum(c) __isctype((c), _ISalnum) # define isalpha(c) __isctype((c), _ISalpha) //  ..  .. # endif //      # ifdef __USE_EXTERN_INLINES __extern_inline int __NTH (tolower (int __c)) { return __c >= -128 && __c < 256 ? (*__ctype_tolower_loc ())[__c] : __c; } __extern_inline int __NTH (toupper (int __c)) { return __c >= -128 && __c < 256 ? (*__ctype_toupper_loc ())[__c] : __c; } # endif //   tolower     # if __GNUC__ >= 2 && defined __OPTIMIZE__ && !defined __cplusplus # define tolower(c) __tobody (c, tolower, *__ctype_tolower_loc (), (c)) # define toupper(c) __tobody (c, toupper, *__ctype_toupper_loc (), (c)) # endif /* Optimizing gcc */ #endif /* Not __NO_CTYPE. */ 

يرجى ملاحظة أنه عند الاتصال <ctype.h> لا يتم تعريف إصدار C ++ من toupper على أنه ماكرو - الحد الأقصى كما هو مضمّن خارجي - نظرًا لأن تعريفات وحدات الماكرو محمية بواسطة التحقق! __cplusplus المحدد ، وبالتالي لن تسري أبدًا.

بشكل عام ، لا أعرف على وجه اليقين ما إذا كان __NO_CTYPE في هذه الحالة يجب أن يستثني جسدي وظائف tolower و toupper المعلنة كخارجية مضمنة ، ولكن هذا هو بالضبط ما يحدث - وبالتالي انخفاض كبير في سرعة دورتنا. في الختام ، أستطيع القول أنه إذا قمت بتضمين <cctype> بدلاً من <ctype.h> (أي ، C ++ هو إصدار ملف الرأس C الذي يضع الوظائف في مساحة std :: namesd ) ، فسيعمل الرمز في هذه الحالة ببطء لأن <cctype> يتضمن في النهاية <bits / os_defines.h> .

هل كل هذا مهم؟ لا ، لا.

وظيفة toupper غير مناسبة للعمل الجاد مع أحرف بلغات مختلفة ، لذلك إذا كنت بحاجة إلى معالجة أحرف ASCII فقط ، فيمكنك كتابة التنفيذ الأسرع. إذا كنت بحاجة إلى عمل جاد مع النص ، فمن المرجح أنك ستستخدم UTF-8 وتحتاج إلى استخدام نوع من وحدة العناية المركزة لدعم الإعدادات الإقليمية ، أو الانتظار حتى يظهر دعم Unicode في C ++ (قد يستغرق الانتظار وقتًا طويلاً) . لذا فإن عبارة "clang-format يمكن أن تسبب انخفاض أداء 4x" مناسبة فقط كرأس clickbait.

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

النتائج الموضحة أعلاه صحيحة بالنسبة إلى gcc 5.5 و glibc 2.23 ، حيث أنني استخدمت هذه الإصدارات ، لكن هناك شيئًا جديدًا يحدث في الإصدارات الجديدة (بدءًا من حوالي glibc 2.27). هناك ، يؤدي تشغيل <algorithm> قبل <ctype.h> إلى إعطاء نفس التأثير ، ولكن <stdlib.h> [10] الآن يخلق مشاكل أيضًا: إذا قمت بتشغيله قبل <ctype.h> ، فسوف ينخفض ​​الأداء أيضًا ، وهو ليس كذلك لوحظ في الإصدارات السابقة. من الواضح ، في الإصدارات الأحدث ، يحتوي الملف <stdlib.h> أيضًا على تعريف __NO_CTYPE . على الأقل ، لن يكون من الممكن الآن إلقاء اللوم على تنسيق clang للفرز - هنا يمكن أن يساعد في حل المشكلة (في حالة عدم وجود ملفات مشاكل أخرى في قائمة الملفات المتصلة).

لقد نشرت تقريرًا عن الأخطاء في libc ، لذا فمن المحتمل أن يتم إصلاح هذا الخطأ ، ولكن لا شك في أن الأخطاء المتعلقة بالترتيب الذي تتصل به ملفات الرأس ستزيد من قلقنا.

تعليقات

ليس لدي نظام للتعليق على موقعي ، لكنني أعمل على ذلك (وهذا يعني ، بشكل دوري ، من الصعب تقديم تعليقات على موقع ثابت).

في هذه الأثناء ، يمكنك مناقشة هذه المقالة على موقع Hacker News على الويب أو lobste.rs .

شكر

بفضل مستخدم ufo مع Hacker News ، الذي أوضح أنه ليس من الضروري استخدام وظيفة lambda لتكييف std :: toupper للاستخدام في std :: convert ، وأيضًا إلى Jonathan Muller الذي أوضح أنه لا تزال هناك حاجة إلى وظيفة lambda.

1. نعم ، وظيفة toupper (3) من ملف الرأس <ctype.h> غير مناسبة للعمل مع معظم الأحرف غير ASCII ، مثل لا يمكن التعامل مع الأحرف الأكبر من بايت واحد ، لكنها مناسبة لمهمتنا ، حيث أننا سنمرر سلاسل أحرف ASCII فقط إليها.
2. في جدول ASCII ، توجد أحرف الأحرف الكبيرة والصغيرة في مكان ملائم جدًا - على مسافة 32 موضعًا من بعضها البعض ، مما يعني أنه يمكنك نقل الأحرف من حالة إلى أخرى ببساطة بطرح أو إضافة 32. بشكل عام ، إذا علمنا بالتأكيد أن جميع المدخلات البيانات هي أحرف ASCII ، يمكننا إعادة تعيين البت الخامس دون أي اختبارات (على سبيل المثال ، c & 0b11011111 ) لتحويل أي حرف كبير إلى أحرف صغيرة ، في حين أن هذا لن ينعكس في أحرف صغيرة. لكن من المحتمل أننا لا نعرف ، لذلك يتعين علينا التحقق مما إذا كانت الشخصية عبارة عن حرف ، حتى لا يتم كسر الأحرف غير الحرفية بطريق الخطأ مثل حرف char .
3. يجب أن يطلق عليه مؤامرة مبعثرة مع إضافة "ضوضاء" إلى موقع النقاط. في الواقع ، يعد هذا مخططًا مبعثرًا عاديًا يتم فيه رسم المعلمة التي تهمنا (حجم بيانات الإدخال) على المحور السيني ، وتكون سرعة العمل على المحور ص (المقاييس لكل رمز - كلما انخفضت القيمة ، ارتفعت السرعة ). الميزة الرئيسية لهذا المخطط هي أنه بالنسبة لكل قيمة معلمة على المحور س ، يتم أخذ العينات عدة مرات: في هذه الحالة ، يتم تكرار الاختبار 10 مرات لكل حجم صفيف.
4. وهي ، يتم اختيار الحروف بشكل عشوائي وموحد من النطاق [32 ، 127] ، وبالتالي فإن الحالة في الوظيفة ستكون صحيحة في حوالي 27 ٪ من الحالات.
5. تشير كلتا القائمتين إلى تطبيق دورة أولية وتختلف فقط بالترتيب الذي يتم به تضمين ملفات <algorithm> و <ctype.h> . شفرة المصدر التي تم إنشاؤها هي نفسها لجميع التطبيقات - سواء في الإصدارات السريعة أو البطيئة. على سبيل المثال ، سينتج عن تنفيذ باستخدام std :: convert نفس رمز التجميع البطيء إذا قمت بتضمين ملف <algorithm> ، والرمز السريع نفسه إذا قمت بنسخ تعريف الوظيفة فقط وعدم تضمين الملف.
6. ومع ذلك ، فإن هذه الحلقة السريعة أبطأ مما يمكن ؛ لأن المؤشر إلى جدول المراسلات يقرأ عدة مرات ( mov rdx ، QWORD PTR [rax] ) داخل الحلقة. قد يكون هذا المؤشر مختلفًا وفقًا للإعدادات الإقليمية ، ولكن لا يتم تحديثه أثناء تنفيذ الدورة وبالتالي يمكن نقله خارج الدورة. يجب أن يكون المترجم يعتقد أنه لا توجد أسباب كافية لذلك ، لأننا نكتب إلى مجموعة من عناصر النوع char ، ويمكن استخدامها من حيث المبدأ كأسماء مستعارة لـ [rax] أي مؤشر إلى الجدول. على أي حال ، حتى __restrict__ لن يساعد هنا. ولكن في إصدار آخر من الحلقة ، حيث تتم إضافة قيم toupper ببساطة ولا تتم كتابة أي شيء إلى المصفوفة ، يتم تطبيق هذا التحسين - يتم قراءة المؤشر خارج الحلقة.
7. لا ينعكس هذا الاختبار في رمز المجمّع القابل للاستبدال ، لأن المترجم يعرف بالفعل أن قيم char موجودة دائمًا في النطاق [-128 ، 255] . يعد الاختيار ضروريًا فقط لأن واجهة برمجة التطبيقات للدالة toupper © تقبل قيمة type int بدلاً من char ، بحيث يمكن للمستخدم تمرير أي عدد مألوف من النوع int إليها ، بينما يتم تصميم جداول المراسلات لقيم type char فقط ، وبالتالي فإن الفحص يساعد على تجنب القراءة خارج المخزن المؤقت .
8. بالمناسبة ، يوضح هذا سبب استقلالية إجراءات std :: toupper عن حجم بيانات الإدخال: فهي لا تستخدم الفروع (باستثناء عمليات التحقق من النطاق ، والتي يتم التنبؤ بها بشكل ملحوظ) ، ولكن تستخدم جدول مراسلات مستقل عن الفروع. ↵
9. استبدال هذه المكالمة لن يعمل حتى مع وجود رغبة قوية للغاية: نص الوظيفة غير متوفر في ملف الرأس.
10. لا أجد خطأً بأي حال من الأحوال مع stdlib.h (أو <خوارزمية> ، لهذه المسألة) - من المحتمل جدًا أن تتسبب العديد من ملفات رأس C الأخرى وجميع ملفات رأس C ++ أيضًا في حدوث هذا السلوك ، لم أختبرها. أنا مرتبطة stdlib.h فقط من أجل تحديد size_t .

المذكرة. تم نشر هذا المقال لأول مرة على موقع "مسائل الأداء" . يتم نشر المقالات المترجمة هنا بإذن من المؤلف.