MicroPython 문자열 인터닝(interning)

MicroPython은 RAM과 ROM을 모두 절약하기 위해 string interning 을 사용합니다. 이는 동일한 문자열의 중복 복사본을 저장할 필요를 없애줍니다. 주로 코드의 식별자에 적용되는데, 함수나 변수 이름과 같은 것은 코드의 여러 곳에 등장할 가능성이 매우 높기 때문입니다. MicroPython에서 인터닝된 문자열은 QSTR(uniQue STRing)이라고 합니다.

QSTR 값(타입 qstr)은 QSTR 풀의 연결 리스트에 대한 인덱스입니다. QSTR은 중복 제거 과정에서 빠른 비교를 위해 길이와 내용의 해시를 저장합니다. 문자열을 다루는 모든 바이트코드 연산은 QSTR 인수를 사용합니다.

컴파일 시점 QSTR 생성

MicroPython C 코드에서 최종 펌웨어에 인터닝되어야 하는 문자열은 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 구문으로 표현할 수 없는 일부 추가 문자열(예: 영숫자가 아닌 문자를 포함하는 경우)은 $(QSTR_DEFS) 변수를 통해 qstrdefs.h 와 qstrdefsport.h 에 명시적으로 제공됩니다.

처리는 다음 단계로 진행됩니다:

  1. qstr.i.last 는 모든 단일 입력 파일을 C 전처리기에 통과시킨 결과를 이어 붙인 것입니다. 이는 조건부로 비활성화된 코드가 제거되고 매크로가 확장됨을 의미합니다. 즉 최종 펌웨어에서 사용되지 않을 문자열을 풀에 추가하지 않게 됩니다. 이 단계에서는 (QSTR_GEN_CFLAGS 가 추가한 NO_QSTR 매크로 덕분에) MP_QSTR_Foo 에 대한 정의가 없기 때문에 이 단계를 영향 없이 통과합니다. 이 파일에는 행 번호 정보를 포함하는 전처리기의 주석도 들어 있습니다. 이 단계는 변경된 파일만 사용하므로 qstr.i.last 에는 마지막 컴파일 이후 변경된 파일의 데이터만 포함됨에 유의하세요.

  2. qstr.split 은 qstr.i.last에 makeqstrdefs.py split 을 실행한 후 생성되는 빈 파일입니다. 단지 해당 단계가 실행되었음을 나타내는 의존성으로 사용됩니다. 이 스크립트는 입력 C 파일마다 하나씩 genhdr/qstr/...file.c.qstr 파일을 출력하며, 이 파일에는 일치한 QSTR만 들어 있습니다. 각 QSTR은 Q(Foo) 로 출력됩니다. 이 단계는 기존 파일을 qstr.i.last 의 증분 업데이트에서 생성된 새 데이터와 결합하는 데 필요합니다.

  3. qstrdefs.collected.h 는 makeqstrdefs.py cat 를 사용하여 genhdr/qstr/* 를 이어 붙인 결과입니다. 이는 이제 코드에서 발견된 MP_QSTR_Foo 의 전체 집합으로, Q(Foo) 형식으로 한 줄에 하나씩, 중복을 포함하여 포맷됩니다. 이 파일은 qstr 집합이 변경된 경우에만 업데이트됩니다. QSTR 데이터의 해시가 다른 파일(qstrdefs.collected.h.hash)에 기록되어 빌드 간 변경 사항을 추적할 수 있게 합니다.

  4. 각 항목이 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 의 출력입니다. qstrdefs.preprocessed.h의 각 Q(Foo) 에 대해(일부 추가로 하드코딩된 것 포함) 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

“load attr” 바이트코드에서 사용할 수 있도록 x 값에 대한 QSTR을 생성해야 합니다.

또한 Python 코드를 컴파일할 때 식별자와 리터럴에 대해 QSTR을 생성해야 합니다. 참고: 10자보다 짧은 리터럴만 QSTR이 됩니다. 이는 힙에 있는 일반 문자열이 항상 최소 16바이트(하나의 GC 블록)를 차지하는 반면, QSTR은 풀에 더 효율적으로 패킹할 수 있기 때문입니다.

QSTR 풀(과 문자열 데이터를 저장하는 기반 “청크”)은 최소 크기로 힙에 필요할 때마다 할당됩니다.