تجميع السلاسل في MicroPython (string interning)

يستخدم MicroPython string interning لتوفير كل من ذاكرة RAM و ROM. وهذا يتجنّب الحاجة إلى تخزين نسخ مكررة من السلسلة نفسها. ينطبق هذا في المقام الأول على المعرّفات في شيفرتك، إذ من المرجّح جداً أن يظهر شيء مثل اسم دالة أو متغير في أماكن متعددة من الشيفرة. في MicroPython تُسمّى السلسلة المُجمَّعة QSTR (uniQue STRing).

قيمة QSTR (من النوع qstr) هي فهرس ضمن قائمة مترابطة من مجمّعات (pools) QSTR. تخزّن سلاسل QSTR طولها وقيمة تجزئة (hash) لمحتواها لإجراء مقارنة سريعة أثناء عملية إزالة التكرار. وجميع عمليات الشيفرة الثنائية (bytecode) التي تتعامل مع السلاسل تستخدم وسيطة QSTR.

توليد QSTR وقت الترجمة (compile-time)

في شيفرة C الخاصة بـ MicroPython، تُكتب أي سلاسل ينبغي تجميعها في البرنامج الثابت النهائي على هيئة MP_QSTR_Foo. وفي وقت الترجمة سيُقيَّم هذا إلى قيمة qstr تشير إلى فهرس "Foo" في مجمّع QSTR.

تتولّى عملية متعددة الخطوات في Makefile تحقيق هذا. وباختصار، تتألف هذه العملية من ثلاثة أجزاء:

  1. العثور على جميع رموز MP_QSTR_Foo في الشيفرة.

  2. توليد مجمّع QSTR ثابت يحتوي على جميع بيانات السلاسل (بما في ذلك الأطوال وقيم التجزئة).

  3. استبدال جميع MP_QSTR_Foo (عبر المعالج المسبق) بالفهرس المقابل لها.

يُبحث عن رموز MP_QSTR_Foo في مصدرين:

  1. جميع الملفات المُشار إليها في $(SRC_QSTR). وهذه هي كل شيفرة C (أي py و extmod و ports/stm32) ولكن دون تضمين شيفرة الطرف الثالث مثل lib.

  2. إضافات $(QSTR_GLOBAL_DEPENDENCIES) (التي تشمل mpconfig*.h).

ملاحظة: الملف frozen_mpy.c (المُولَّد بواسطة mpy-tool.py) له توليد ومجمّع QSTR خاصان به.

بعض السلاسل الإضافية التي لا يمكن التعبير عنها باستخدام صياغة MP_QSTR_Foo (مثل تلك التي تحتوي على محارف غير أبجدية رقمية) تُوفَّر بشكل صريح في qstrdefs.h و qstrdefsport.h عبر المتغير $(QSTR_DEFS).

تجري المعالجة في المراحل التالية:

  1. الملف qstr.i.last هو ناتج تمرير كل ملف إدخال على حدة عبر المعالج المسبق لـ C. وهذا يعني أن أي شيفرة معطَّلة شرطياً ستُزال، وأن الماكروهات ستُوسَّع. ويعني هذا أيضاً أننا لا نضيف إلى المجمّع سلاسل لن تُستخدم في البرنامج الثابت النهائي. لأنه في هذه المرحلة (بفضل الماكرو NO_QSTR الذي يضيفه QSTR_GEN_CFLAGS) لا يوجد تعريف لـ MP_QSTR_Foo، فإنه يمرّ عبر هذه المرحلة دون تأثّر. كما يتضمّن هذا الملف تعليقات من المعالج المسبق تحوي معلومات أرقام الأسطر. لاحظ أن هذه الخطوة تستخدم فقط الملفات التي تغيّرت، مما يعني أن qstr.i.last سيحتوي فقط على بيانات من الملفات التي تغيّرت منذ آخر عملية ترجمة.

  2. الملف qstr.split هو ملف فارغ يُنشأ بعد تشغيل makeqstrdefs.py split على qstr.i.last. ويُستخدم فقط كاعتمادية للإشارة إلى أن الخطوة قد جرت. يُخرج هذا البرنامج النصي ملفاً واحداً لكل ملف C مُدخل، genhdr/qstr/...file.c.qstr، يحتوي فقط على سلاسل QSTR المطابقة. وتُطبع كل QSTR على هيئة Q(Foo). هذه الخطوة ضرورية لدمج الملفات الموجودة مع البيانات الجديدة المُولَّدة من التحديث التزايدي في qstr.i.last.

  3. الملف qstrdefs.collected.h هو ناتج دمج genhdr/qstr/* باستخدام makeqstrdefs.py cat. وهذا الآن هو المجموعة الكاملة من MP_QSTR_Foo الموجودة في الشيفرة، مُنسَّقة الآن على هيئة Q(Foo)، واحدة في كل سطر، مع التكرارات. ولا يُحدَّث هذا الملف إلا إذا تغيّرت مجموعة سلاسل qstr. وتُكتب قيمة تجزئة لبيانات QSTR إلى ملف آخر (qstrdefs.collected.h.hash) مما يتيح تتبّع التغييرات عبر عمليات البناء.

  4. توليد تعداد (enumeration)، يربط كل مدخل فيه MP_QSTR_Foo بفهرسه المقابل. يدمج qstrdefs.collected.h مع qstrdefs*.h، ثم يحوّل كل سطر من Q(Foo) إلى "Q(Foo)" كي يمرّ عبر المعالج المسبق دون تغيير. ثم يُستخدم المعالج المسبق للتعامل مع أي ترجمة شرطية في qstrdefs*.h. ثم يُعكَس التحويل عائداً إلى Q(Foo)، ويُحفظ باسم qstrdefs.preprocessed.h.

  5. الملف qstrdefs.generated.h هو ناتج makeqstrdata.py. ولكل Q(Foo) في qstrdefs.preprocessed.h (بالإضافة إلى بعض القيم المُضمَّنة بشكل ثابت)، يُخرج QDEF(MP_QSTR_Foo, (const byte*)"hash" "Foo").

ثم في عملية الترجمة الرئيسية، يحدث أمران مع qstrdefs.generated.h:

  1. في qstr.h، يصبح كل QDEF مدخلاً في تعداد (enum)، مما يجعل MP_QSTR_Foo متاحاً للشيفرة ومساوياً لفهرس تلك السلسلة في جدول QSTR.

  2. في qstr.c، يُولَّد جدول بيانات QSTR الفعلي على هيئة عناصر في mp_qstr_const_pool->qstrs.

توليد QSTR وقت التشغيل (run-time)

يمكن إنشاء مجمّعات QSTR إضافية وقت التشغيل بحيث يمكن إضافة سلاسل إليها. على سبيل المثال، الشيفرة:

foo[x] = 3

ستحتاج إلى إنشاء QSTR لقيمة x كي يمكن استخدامها بواسطة الشيفرة الثنائية "load attr".

كذلك، عند ترجمة شيفرة Python، تحتاج المعرّفات والقيم الحرفية (literals) إلى إنشاء سلاسل QSTR. ملاحظة: فقط القيم الحرفية الأقصر من 10 محارف تصبح سلاسل QSTR. وهذا لأن السلسلة العادية على الكومة (heap) تشغل دائماً 16 بايت كحد أدنى (كتلة GC واحدة)، بينما تتيح سلاسل QSTR حزمها بكفاءة أكبر داخل المجمّع.

تُخصَّص مجمّعات QSTR (و"القطع" (chunks) الأساسية التي تخزّن بيانات السلاسل) عند الطلب على الكومة بحدٍّ أدنى من الحجم.