การ interning สตริงใน MicroPython

MicroPython ใช้ string interning เพื่อประหยัดทั้ง RAM และ ROM ซึ่งช่วยหลีกเลี่ยงการเก็บสำเนาสตริงเดียวกันซ้ำซ้อน โดยหลักแล้วจะใช้กับตัวระบุในโค้ด เนื่องจากชื่อฟังก์ชันหรือตัวแปรมีแนวโน้มที่จะปรากฏในหลายตำแหน่งในโค้ด ใน MicroPython สตริงที่ผ่านการ intern เรียกว่า QSTR (uniQue STRing)

ค่า QSTR (ซึ่งมีประเภทเป็น qstr) คือดัชนีในรายการลิงก์ของพูล QSTR QSTR จัดเก็บความยาวและค่าแฮชของเนื้อหาเพื่อการเปรียบเทียบที่รวดเร็วระหว่างกระบวนการตรวจสอบความซ้ำ การดำเนินการ bytecode ทั้งหมดที่ทำงานกับสตริงจะใช้อาร์กิวเมนต์ QSTR

การสร้าง QSTR ในช่วงคอมไพล์

ในโค้ด C ของ MicroPython สตริงใดๆ ที่ควรผ่านการ intern ในเฟิร์มแวร์สุดท้ายจะเขียนเป็น MP_QSTR_Foo ในช่วงคอมไพล์ จะถูกประเมินเป็นค่า qstr ที่ชี้ไปยังดัชนีของ "Foo" ในพูล QSTR

กระบวนการหลายขั้นตอนใน Makefile ทำให้สิ่งนี้ทำงานได้ โดยสรุปกระบวนการนี้มีสามส่วน:

  1. ค้นหา token MP_QSTR_Foo ทั้งหมดในโค้ด

  2. สร้างพูล QSTR แบบ static ที่มีข้อมูลสตริงทั้งหมด (รวมถึงความยาวและแฮช)

  3. แทนที่ MP_QSTR_Foo ทั้งหมด (ผ่านตัวประมวลผลก่อน) ด้วยดัชนีที่สอดคล้องกัน

token 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 ซึ่งหมายความว่าโค้ดที่ถูกปิดใช้งานตามเงื่อนไขจะถูกลบออก และมาโครจะถูกขยาย ดังนั้นเราจึงไม่เพิ่มสตริงลงในพูลที่จะไม่ถูกใช้งานในเฟิร์มแวร์สุดท้าย เนื่องจากในขั้นตอนนี้ (ด้วย macro NO_QSTR ที่เพิ่มโดย QSTR_GEN_CFLAGS) ไม่มีนิยามสำหรับ MP_QSTR_Foo จึงผ่านขั้นตอนนี้โดยไม่เปลี่ยนแปลง ไฟล์นี้ยังมีคอมเมนต์จากตัวประมวลผลก่อนที่มีข้อมูลหมายเลขบรรทัดด้วย โปรดทราบว่าขั้นตอนนี้ใช้เฉพาะไฟล์ที่มีการเปลี่ยนแปลง ซึ่งหมายความว่า qstr.i.last จะมีข้อมูลเฉพาะจากไฟล์ที่มีการเปลี่ยนแปลงตั้งแต่การคอมไพล์ครั้งล่าสุด

  2. qstr.split คือไฟล์ว่างที่สร้างขึ้นหลังจากรัน makeqstrdefs.py split บน qstr.i.last ใช้เพียงเป็น dependency เพื่อระบุว่าขั้นตอนนี้ทำงานแล้ว สคริปต์นี้ส่งออกหนึ่งไฟล์ต่อไฟล์ 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) ซึ่งช่วยติดตามการเปลี่ยนแปลงระหว่างการ build

  4. สร้างการ enumerate โดยแต่ละรายการจะ map 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 (บวกกับรายการที่ hard-code บางส่วน) จะส่งออก 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 ในช่วงรันไทม์

พูล QSTR เพิ่มเติมสามารถสร้างได้ในช่วงรันไทม์เพื่อให้สามารถเพิ่มสตริงลงไปได้ ตัวอย่างเช่น โค้ด:

foo[x] = 3

จะต้องสร้าง QSTR สำหรับค่าของ x เพื่อให้ bytecode "load attr" สามารถใช้งานได้

นอกจากนี้ เมื่อคอมไพล์โค้ด Python ตัวระบุและ literal จำเป็นต้องสร้าง QSTR หมายเหตุ: เฉพาะ literal ที่สั้นกว่า 10 อักขระเท่านั้นที่จะกลายเป็น QSTR เนื่องจากสตริงปกติบนฮีปจะใช้พื้นที่ขั้นต่ำ 16 ไบต์เสมอ (หนึ่ง GC block) ในขณะที่ QSTR ช่วยให้เก็บข้อมูลได้อย่างมีประสิทธิภาพมากขึ้นในพูล

พูล QSTR (และ "chunks" พื้นฐานที่เก็บข้อมูลสตริง) ถูกจัดสรรตามต้องการบนฮีปด้วยขนาดขั้นต่ำ