على السؤال حول بت

"ألم يحن الوقت ، يا أصدقائي ، لكي نتأرجح في وليام ، كما ترى ، شكسبير لدينا؟ ".

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

ملاحظة ضرورية - أرى 4 طبقات لتنفيذ لوحة المفاتيح: 0 - اكتشاف الأحداث ، 1 - قراءة البيانات ، 2 - تنظيف البيانات وتخزينها ، 3 - إنشاء الرسائل ، 4 - تحويل الشفرة ، إلخ. الأكثر واعدة بالنسبة للطبقة 1 والطبقة 0 المرتبطة بها يبدو لي استخدام قوالب Anton Chizhov للعمل مع دبابيس MK (بناءً على فئة Loki) ، وربما ، في يوم من الأيام ، لن تخجل النتيجة الناتجة من المشاركة ، ولكن بالتأكيد لا اليوم. الآن أنا أفكر في الطبقة 2.

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

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

لذلك ، تم اعتماد تقنية دراسة "الصندوق الأسود" - نحن نطعم أجزاء مختلفة من الشفرة ونعتبر المجمّع الذي تم إنشاؤه. لسوء الحظ ، لا يمكن استخدام موقع godbolt المفضل لبنية AVR المألوفة ، حيث لا توجد مكتبة قيد الدراسة في هذا التطبيق. يمكنك بالطبع سحبها مع الأقلام ، لكن ليس هناك ما يضمن أنها ستكون شفرة المصدر الصحيحة.

لذلك ، سوف ننظر إلى بنية مختلفة. لم يتم تقديم الإصدار x51 لبرنامج التحويل البرمجي لـ gcc ، ولم يعجبني أبدًا x86 ، و ARM ليس ملائمًا جدًا (لشخص) وجامعًا مفهومًا ، MIPS محددة للغاية وليست شائعة جدًا ، وكل أنواع SPARC أسوأ من ذلك (حسنًا ، حسنًا ، لن أسيء لأي شخص بالهندسة المعمارية المفضلة لديك ، ليس أفضل) ، ولكن هناك مرشح كبير MSP430 ، والذي كان يعتمد على بنية واضحة وضوح الشمس من PDP و TI لا يمكن أن يفسد ذلك بكثير (على الرغم من أن اللاعبين حاولوا). يتم تقديم مكتبة تحتوي على العديد من وحدات البت لهذه البنية ، بحيث يمكنك البدء في الدراسة.

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

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

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

لنبدأ العمل مع تعديل المجموعة ، والتي تركناها بين قوسين معقوفين وطرق ضبط وإعادة التعيين. يمكننا أن نتوقع أن نرى شيئا مثل:

M[n / w] |= (1<<(n % w)) 

حيث w هو عدد البتات في العنصر الأساسي ، والتي بالنسبة للهندسة المعينة ، محددة بشكل ثابت n (على سبيل المثال ، 4) ويؤدي التحسين المضمّن إلى رمز للنموذج:

 bis.w #0x0010, m 

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

نلفت الانتباه إلى أن القيمة المعينة لعنصر من مجموعة لا يمكن أن تكون فقط 0 و 1 ، كما قد يتوقع المرء ، ولكن أيضًا أي عدد صحيح للقاعدة "ما هي الوحدة؟ ليس صفرا "، إنه منطقي تمامًا ، لكنه ينعكس بشكل سيء في الوثائق. تم القيام بغرابة بعض الشيء ، لكن القيم المنطقية ستكون أكثر طبيعية ، وتتوقف عن الحركة وتتقدم.

توضح مقارنة الكود الذي تم إنشاؤه لحالة رقم عنصر غير محدد بشكل ثابت للمجموعة أن كفاءة الشفرة في كلتا الحالتين ([] والأساليب) وثيقة للغاية وصغيرة ، حيث يتم استدعاء روتين فرعي من المكتبة القياسية لحساب (1 << n) ، وهذه التحولات الفرعية رقم 32 بت 0x00000001 ، وضعت في سجلين. لا يمكننا رؤية نص المصدر الخاص به ، ولكن حقيقة الدعوة تؤدي إلى أفكار حزينة. والحقيقة هي أنه في الهندسة المعمارية قيد النظر لا يوجد أي تحول إلى اليسار (وليس هناك حق أيضًا) من خلال عدد تعسفي من المواقف ، كما هو الحال في جميع (ARM) ARMs المحبوب. هناك تحول بمقدار موضع واحد (سيكون غريباً إذا لم يكن موجودًا على الإطلاق) ، هناك تحول بمقدار 2،3،4 موضعًا (ولكن برقم ثابت تمامًا في الأمر ، وليس بواسطة معلمة) ، هناك بادئة REPT (لكن يترك سرعة التنفيذ أتمنى للأفضل). يمكنك تنفيذ تحول أصغر وحدة (وهذا أمر مهم ، وحدة واحدة فقط) ، أي الحصول على قناع بت بواسطة رقم البتات في وقت قصير نسبيًا عن طريق الحيل مثل تبادل التتراد ، لكن هذا سيكون جزءًا يعتمد عليه للغاية ، وفي الحالة العامة ، من الأفضل عدم القيام بذلك.

لذلك ، تتمثل الطريقة العالمية والسريعة في تخزين أقنعة البت في صفيف وفهرس ، كما أنها فعالة للغاية في هذا الهيكل ، ثم يبدو الرمز كما يلي:

 M[n/w] |= BitArray[n %w] 

الحصول على المجمّع مثل:

  bis.b BitArray(r0),M(r1) 

نظرًا لأننا نتحدث عن الأنماط و w هو مضاعف لحجم البايت ، يتم تنفيذ عمليات التقسيم بكفاءة عالية هنا. نلاحظ الميزة الواضحة لعنصر التخزين الذي تم تنفيذه في الحد الأدنى: بالنسبة للبايت ، يلزم وجود صفيف من 8 بايت للبايت ، -2 * 16 = 32 بايت لتنظيم الكلمات ، و 4 * 32 = 128 بايت لكلمة طويلة من 32 بت لتخزين كل ما هو مطلوب أقنعة ، لماذا تدفع أكثر إذا لم تتغير النتيجة. دعونا نتذكر واحدًا من التحسينات الممكنة والمضي قدمًا.

نلاحظ حقيقة أخرى - من الممكن تنفيذ عمليات أكثر فعالية بكثير من العمليات مع عنصر محدد إذا كانت البنية المستهدفة بها منطقة ذاكرة ذات علامة بت (هنا مرة أخرى ، يتم استدعاء ARM المرفوض سابقًا) ، حيث تتحول عملية تثبيت العنصر إلى BitSetAddr [n] = اليقطين بشكل عام 1 ، والتي تُترجم إلى أمر تجميع واحد من أجل ثابت n ، ولكن هناك بالفعل تحولات فعالة كافية هناك ، لذلك سيكون هذا التحسين أكثر زائدة عن الحاجة ، خاصة مع مراعاة حدوده. من حيث المبدأ ، توجد منطقة مماثلة يمكن تناولها في كل من x51 و AVR ، ولكن هناك أوامر فعالة فقط لأرقام العناصر الثابتة ، وفي الحالة العامة ، كل شيء ليس جيدًا (سيئ بصراحة).

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

 bic #0,r0 

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

بالمناسبة ، ما زلت لا أستطيع العثور على إجابة السؤال - هل من الممكن في C ++ على مستوى الماكرو أو القالب تحديد تطبيق مختلف للمعرف الثابت في مرحلة الترجمة مقابل المعلمة غير المحددة بشكل ثابت. إذا كان أي شخص يعرف طريقة الساموراي ، فأخبرني في التعليقات ، لقد جربت كونسيكسبر ، لم ينجح ذلك.

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

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

في الختام ، ملاحظة صغيرة - يتطلب تنفيذ مستودع البيانات "وجهاً لوجه" ، حتى في الإصدار الأمثل من المجموعة ، N / 8 بايت من ذاكرة البيانات (ستلزم 16 بايت من أجل 128 مفتاح تبديل) وعلى الرغم من أن العمليات ستتطلب O (1) وقتًا ، فإن المضاعف سيكون العديد من الوحدات ( وحتى ما يصل إلى 10 أو أكثر) دورات MK. لذلك ، مع الأخذ في الاعتبار متطلبات المشكلة وإدخال قيود معينة ، يمكننا تقديم تطبيق بديل لتخزين البيانات.

إذا اعتقدنا أنه لا يمكن إغلاق أكثر من مفتاح واحد في أي وقت (نتجاهل جميع المفاتيح الأخرى حتى يتم فتح الزر الذي يتم الضغط عليه حاليًا) ، فيمكننا تجاوز بايت واحد (بشرط ألا يكون هناك أكثر من 256 مفتاحًا) ستستغرق الكتابة / القراءة دورات المعالج O (1) ، وسيكون المضاعف متواضعًا جدًا.

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

سيتم إعطاء تنفيذ هذا النهج هناك.