Nội hóa chuỗi (string interning) trong MicroPython

MicroPython sử dụng string interning để tiết kiệm cả RAM lẫn ROM. Điều này tránh việc phải lưu trữ các bản sao trùng lặp của cùng một chuỗi. Chủ yếu, điều này áp dụng cho các định danh trong mã của bạn, vì một thứ như tên hàm hay tên biến rất có thể xuất hiện ở nhiều nơi trong mã. Trong MicroPython, một chuỗi được nội hóa được gọi là QSTR (uniQue STRing).

Một giá trị QSTR (kiểu qstr) là chỉ mục vào một danh sách liên kết các pool QSTR. QSTR lưu trữ độ dài và giá trị băm (hash) của nội dung của chúng để so sánh nhanh trong quá trình loại bỏ trùng lặp. Tất cả các thao tác bytecode làm việc với chuỗi đều sử dụng đối số QSTR.

Sinh QSTR tại thời điểm biên dịch

Trong mã C của MicroPython, bất kỳ chuỗi nào cần được nội hóa trong firmware cuối cùng đều được viết là MP_QSTR_Foo. Tại thời điểm biên dịch, điều này sẽ được đánh giá thành giá trị qstr trỏ đến chỉ mục của "Foo" trong pool QSTR.

Một quy trình nhiều bước trong Makefile làm cho điều này hoạt động. Tóm lại, quy trình này có ba phần:

  1. Tìm tất cả các token MP_QSTR_Foo trong mã.

  2. Tạo một pool QSTR tĩnh chứa tất cả dữ liệu chuỗi (bao gồm độ dài và giá trị băm).

  3. Thay thế tất cả các MP_QSTR_Foo (thông qua bộ tiền xử lý) bằng chỉ mục tương ứng của chúng.

Các token MP_QSTR_Foo được tìm kiếm trong hai nguồn:

  1. Tất cả các tệp được tham chiếu trong $(SRC_QSTR). Đây là tất cả mã C (tức là py, extmod, ports/stm32) nhưng không bao gồm mã của bên thứ ba như lib.

  2. $(QSTR_GLOBAL_DEPENDENCIES) bổ sung (bao gồm mpconfig*.h).

Lưu ý: frozen_mpy.c (được tạo bởi mpy-tool.py) có cơ chế sinh QSTR và pool riêng.

Một số chuỗi bổ sung không thể diễn đạt bằng cú pháp MP_QSTR_Foo (ví dụ: chúng chứa các ký tự không phải chữ số) được cung cấp tường minh trong qstrdefs.h và qstrdefsport.h thông qua biến $(QSTR_DEFS).

Quá trình xử lý diễn ra theo các giai đoạn sau:

  1. qstr.i.last là kết quả nối chuỗi của việc đưa từng tệp đầu vào riêng lẻ qua bộ tiền xử lý C. Điều này có nghĩa là bất kỳ mã bị vô hiệu hóa có điều kiện nào đều sẽ bị loại bỏ, và các macro sẽ được mở rộng. Điều này đảm bảo chúng ta không thêm các chuỗi vào pool mà sẽ không được sử dụng trong firmware cuối cùng. Vì ở giai đoạn này (nhờ macro NO_QSTR được thêm bởi QSTR_GEN_CFLAGS) không có định nghĩa nào cho MP_QSTR_Foo, nó sẽ đi qua giai đoạn này mà không bị thay đổi. Tệp này cũng bao gồm các chú thích từ bộ tiền xử lý có chứa thông tin số dòng. Lưu ý rằng bước này chỉ sử dụng các tệp đã thay đổi, nghĩa là qstr.i.last sẽ chỉ chứa dữ liệu từ các tệp đã thay đổi kể từ lần biên dịch trước.

  2. qstr.split là một tệp rỗng được tạo ra sau khi chạy makeqstrdefs.py split trên qstr.i.last. Nó chỉ được dùng như một phụ thuộc để chỉ ra rằng bước này đã chạy. Script này xuất một tệp cho mỗi tệp C đầu vào, genhdr/qstr/...file.c.qstr, chỉ chứa các QSTR đã khớp. Mỗi QSTR được in dưới dạng Q(Foo). Bước này cần thiết để kết hợp các tệp hiện có với dữ liệu mới được tạo ra từ bản cập nhật gia tăng trong qstr.i.last.

  3. qstrdefs.collected.h là kết quả của việc nối chuỗi genhdr/qstr/* bằng makeqstrdefs.py cat. Đây là tập hợp đầy đủ các MP_QSTR_Foo được tìm thấy trong mã, nay được định dạng thành Q(Foo), mỗi dòng một phần tử, có thể có trùng lặp. Tệp này chỉ được cập nhật nếu tập hợp qstr đã thay đổi. Giá trị băm của dữ liệu QSTR được ghi vào một tệp khác (qstrdefs.collected.h.hash) giúp theo dõi các thay đổi qua các lần build.

  4. Tạo một bảng liệt kê (enumeration), mỗi mục ánh xạ MP_QSTR_Foo đến chỉ mục tương ứng của nó. Nó nối qstrdefs.collected.h với qstrdefs*.h, sau đó chuyển đổi từng dòng từ Q(Foo) thành "Q(Foo)" để chúng đi qua bộ tiền xử lý mà không thay đổi. Sau đó bộ tiền xử lý được sử dụng để xử lý bất kỳ biên dịch có điều kiện nào trong qstrdefs*.h. Rồi sự chuyển đổi được hoàn tác về lại Q(Foo), và được lưu là qstrdefs.preprocessed.h.

  5. qstrdefs.generated.h là đầu ra của makeqstrdata.py. Với mỗi Q(Foo) trong qstrdefs.preprocessed.h (cộng thêm một số phần tử được mã hóa cứng), nó xuất ra QDEF(MP_QSTR_Foo, (const byte*)"hash" "Foo").

Sau đó trong quá trình biên dịch chính, hai điều xảy ra với qstrdefs.generated.h:

  1. Trong qstr.h, mỗi QDEF trở thành một mục trong một enum, làm cho MP_QSTR_Foo khả dụng với mã và bằng với chỉ mục của chuỗi đó trong bảng QSTR.

  2. Trong qstr.c, bảng dữ liệu QSTR thực tế được tạo ra như các phần tử của mp_qstr_const_pool->qstrs.

Sinh QSTR tại thời điểm chạy

Các pool QSTR bổ sung có thể được tạo tại thời điểm chạy để các chuỗi có thể được thêm vào chúng. Ví dụ, đoạn mã:

foo[x] = 3

Sẽ cần tạo một QSTR cho giá trị của x để nó có thể được sử dụng bởi bytecode "load attr".

Ngoài ra, khi biên dịch mã Python, các định danh và các hằng ký tự cần có QSTR được tạo. Lưu ý: chỉ các hằng ký tự ngắn hơn 10 ký tự mới trở thành QSTR. Điều này là do một chuỗi thông thường trên heap luôn chiếm tối thiểu 16 byte (một khối GC), trong khi QSTR cho phép chúng được đóng gói hiệu quả hơn vào pool.

Các pool QSTR (và các "chunk" cơ bản lưu trữ dữ liệu chuỗi) được cấp phát theo yêu cầu trên heap với kích thước tối thiểu.