스레드 피클링(pickling) 설계, 또는 “Stackless Python의 본질”

2007-07-22 작성 참고: 이 문서는 다소 오래되었으며, pickling에 대한 설명으로 바뀌어야 합니다. 명시적인 재개 지점(resume point) 등을 없애려면 추가적인 조사가 필요합니다…

스레드 피클링(Thread pickling)은 Stackless Python의 고유한 기능이며, PyPy에도 조만간 구현될 예정입니다.

피클링(pickling)이란 무엇을 의미합니까?

저는 스레드 피클링(thread pickling)을 실행 중인 프로그램의 재시작 가능한 부분 집합으로 정의하고자 합니다. 재실행 가능한 부분은 코루틴(coroutine), 태스크릿(tasklet) 또는 다른 애플리케이션 수준의 전환 가능한 서브컨텍스트로 표현되는 파이썬 프레임 체인을 기반으로 해야 합니다. 임의의 인터프리터 레벨 상태(interplevel state)의 피클링을 지원하는 것도 물론 가능하지만, Stackless를 참조 구현으로 간주하는 한 이는 필수는 아닌 것으로 보입니다. 기본 작업이 완료되면 이에 대한 확장을 고려할 수 있을 것입니다.

Pickling은 다른 머신에서, 같은 파이썬 버전으로—반드시 동일한 PyPy 변환일 필요는 없이—실행할 수 있는, 재시작 가능한 코루틴 비슷한 것을 생성해야 합니다. 이는 더 어려운 부분에 속합니다.

피클링(pickling)이 의미하지 않는 것은 무엇입니까?

전체 메모리 상태를 저장하고, 메모리에 있는 상태와 함께 전체 바이너리를 재구성하는 로더를 작성하는 것은 제가 생각하는 진정한 해결책이 아닙니다. 어떤 의미에서는 다른 모든 경우에 실패했을 때 사용할 대안이 될 수는 있지만, C 백엔드에게는 정말 골치 아픈 방법이라고 생각합니다.

프로그램과 그 상태를 직접 생성하는 것을 지원하는 동적 백엔드(예: Forth 백엔드)가 있다면, 이는 재배치 가능하므로 유효한 해결책으로 볼 수 있을 것입니다. 다른 방법으로 실패할 경우, 그러한 백엔드를 작성하는 것은 물론 가능한 대안입니다.

몇 가지 간단한 단계와 좀 더 어려운 단계가 있습니다. 간단한 것부터 시작해보겠습니다.

기본 필수 사항

실행 중인 스레드를 피클링하는 것은 일반적인 객체 피클링보다 조금 더 복잡한데, 피클링 인터페이스를 갖지 않은 객체가 많이 존재하며 사람들은 그것들을 피클링하는 데에 전혀 신경 쓰지 않기 때문입니다. 하지만 스레드 피클링에서는 이러한 객체들이 단순히 지역 변수로 존재하며 현재 런타임 환경을 복원하는 데 필요하므로, 사용자는 피클에 무엇이 들어가는지 알 필요가 없어야 합니다.

예를 들면 다음과 같습니다.

• 제너레이터
• 프레임
• 셀
• 이터레이터
• 트레이스백

몇 가지만 예를 들자면. 다행히 이런 객체 대부분은 이미 Stackless Python에 pickling 구현이 있습니다. 바로 prickelpit.c 파일입니다.

이 구현들을 다시 만드는 것은 간단하고 직관적이어야 합니다. 그럼에도 불구하고 복잡한 문제가 있습니다. 피클링을 지원하는 가장 자연스러운 방법은 __getstate__/__setstate__ 메서드 쌍을 제공하는 것입니다. 이것은 우리가 제어할 수 있는 coroutines/tasklets와 같은 확장 타입에는 괜찮지만, 기존 타입에는 피해야 합니다.

예를 들어 프레임을 생각해 보십시오. __getstate__와 __setstate__ 메서드를 추가해야 하는데, 이는 인터페이스 변경입니다. 게다가, 프레임 타입을 호출해서 프레임을 생성하는 것도 지원해야 하는데, 이는 실제로 의도된 것이 아닙니다.

이미 호출 가능한 다른 타입의 경우, 새 인스턴스를 생성하는 것이 해당 타입을 호출하는 기존 방식과 충돌하지 않도록 해야 하므로 상황이 더 복잡해집니다.

기존 타입에 피클링 인터페이스를 직접 추가하면 호출 인터페이스에서 중복이 발생할 가능성이 매우 높습니다. 예를 들어 모듈 타입이 호출 가능해졌을 때 이런 일이 발생했는데, 그 시그니처가 이전에 Stackless가 추가한 것과 달랐습니다.

Stackless의 경우, 대신 copyreg 모듈을 사용했고, 언피클링 후 객체의 타입을 올바른 타입 포인터로 교체하는 자리표시자 역할의 특수한 대리(surrogate) 객체를 만들었습니다. 자세한 내용은 Stackless 배포판에 있는 prickelpit.c 파일을 참고하십시오.

결론적으로, tasklet의 피클링(pickling)은 Stackless에 대한 추가 기능이며, Python의 확장을 의도한 것은 아닙니다. 특정 객체의 피클링 지원 필요성이 인터페이스를 변경해서는 안 됩니다. 이를 분리하여, Python의 향후 추가 사항과 충돌할 수 없는 대리(surrogate) 타입을 피클링에 사용하는 편이 더 좋습니다.

진짜 문제

현재 Stackless Python(이하 SLP)과 PyPy의 Stackless 지원(이하 PyPy) 간에는 지금까지의 발전 정도에서 몇 가지 중요한 차이가 있습니다. CPython이 Python 함수를 호출할 때, 매개변수를 조정하고 메서드를 언패킹하는 등의 작업을 위해 여러 헬퍼 함수가 관여합니다. SLP는 해당 함수를 위한 Python 인터프리터를 시작하기 전에 이 모든 C 함수를 C 스택에서 제거하기 위해 많은 노력을 기울입니다. 이러한 동작 변경은 호출 이후에도 어떤 변수가 여전히 필요한지 파악하여 모든 헬퍼 함수에 대해 수동으로 이루어집니다. 결국 대부분의 경우, 인터프리터가 시작되기 전에 모든 헬퍼 함수가 작업을 마치고 함수 호출로부터 반환되도록 하는 것이 가능한 것으로 나타났습니다.

이는 PyPy를 위해 반드시 다뤄야 할 주요한 차이점입니다. Python 함수를 실행할 때마다 상당수의 함수가 C 스택에 구체화되며, 새 프레임을 실행하기 전에 완료되지 않은 채로 남습니다. 코루틴 전환의 경우, 우리는 그저 활성화 레코드의 전체 체인 - 저장된 블록 변수를 가진 C 함수 진입점들 - 을 저장할 뿐입니다. 이것은 코루틴 전환에는 괜찮지만, SLP의 관점에서는 오히려 불완전하며 전혀 스택리스(stackless)하지 않습니다. 스택은 여전히 존재하며, 우리는 그것을 풀고(unwind) 다시 만들 수 있지만, 이것이 문제입니다.

왜 문제인가?

이상적인 세계에서는, 스레드 피클링은 피클된 프레임의 체인을 구축하는 것일 뿐, 그 외에는 아무것도 아닐 것입니다. 위에서 언급한 것과 같은 서로 다른 추가 활성화 레코드마다, 이 정보를 어떻게 저장할지의 문제가 있습니다. 우리는 머신이나 컴파일러에 종속되지 않는 표현이 필요합니다. 현재 PyPy는 어떤 블록을 생성할지, 무엇이 인라인될지 등의 측면에서 상당히 불안정합니다. 가능한 최선의 해결책은 이러한 추가 구조를 완전히 제거하려고 시도하는 것입니다.

안타깝게도 이것은 SLP로도 불가능한데, 상태(state)에는 여러 형태가 있어서 추가 정보 없이는 진행하기 어렵게 만들기 때문입니다.

SLP 전환 전략

SLP는 여러 차례 재작성을 거쳤습니다. 첫 번째 구현은 완전한 협업을 목표로 했습니다. 새 프레임의 실행은 모든 준비용 C 함수 호출이 C 스택을 벗어날 때까지 지연되었습니다. 저장해야 할 추가 상태는 없었습니다.

음, 이는 부분적으로만 사실입니다 - 재귀 호출을 피할 수 없는 몇 가지 상황이 있는데, 필요한 지원을 위해서는 구현을 대대적으로 다시 작성해야 하기 때문입니다.

예시는 다음과 같습니다

• map은 일련의 연산을 순회하는 상태 유지(stateful) 구현입니다. map 연산이 상태를 유지하기 위해 자체 프레임을 생성한다면 비재귀적으로 만들 수 있습니다.
• __init__은 사소해 보이지만, __init__의 반환값은 None이어야 한다는 의미론이 있으며, CPy는 호출 후 이에 대한 특별한 검사를 수행합니다. 이는 단순히 무시될 수도 있지만, 자동으로 처리될 수 없는 경우를 보여주는 간단한 예시입니다.
• operator.__add__ 같은 것들은 CPy가 그것이 숫자 덧셈인지 시퀀스 덧셈인지 판별하려는 동안 이론적으로 걷잡을 수 없는 재귀 호출 패턴을 만들어낼 수 있으며, __coerce__ 같은 메서드가 관여하면 다른 콜백들이 발생할 수도 있습니다. 이는 SLP에서는 결코 해결되지 않겠지만, 아래에 설명된 전략으로 해결책을 얻을 수도 있습니다.

두 번째 구현은 근본적으로 다른 접근 방식을 취했습니다. 컨텍스트 전환은 C 스택의 일부를 가로채어 따로 저장한 다음, 목표가 필요로 하는 스택 조각으로 교체하는 방식으로 이루어졌습니다. 이 방식은 매우 강력하며, 외부 코드의 컨텍스트 안에서도 전환할 수 있게 해줍니다. 약간의 위험을 감수하면, 외부 Fortran 코드에도 동시성을 추가할 수 있었습니다.

위에서 설명한 개념은 하드(Hard) 전환이라 부르고, 협력적인 방식은 소프트(Soft) 전환이라 부릅니다. 개선된 버전의 Hard가 여전히 그린렛(greenlets)의 구성 요소라는 점에 유의합니다. 이 때문에 그린렛은 사실 그린(green)이라 할 수 없는데, 저라면 옐로(yellow)라고 부르겠습니다.

최신 SLP 재작성은 두 아이디어를 결합하여, 가능한 한 Soft를 사용하려고 시도하지만, 중첩된 인터프리터가 방해가 될 때는 Hard를 사용합니다.

주의할 점은, Hard가 관여된 경우에는 태스클릿(tasklet)을 피클링하는 시도가 전혀 없었다는 것입니다. SLP에서는 피클링이 Soft와 함께 동작합니다. 피클 가능한 상황을 더 많이 모으려면, 새로운 프레임 타입을 고안하거나 대체 Python 코드를 작성한 뒤 Soft를 사용해 전환해야 합니다.

SLP와 PyPy 간의 유사점

현재 PyPy는 함수의 C 상태를 작은 활성화 레코드에 저장합니다: 블록의 생존 변수들과, 벗어난 함수의 진입점을 함께 저장합니다. 이는 원시 스택 슬라이스를 저장하는 방식보다 개선된 것이지만, 패턴은 비슷합니다: 전환할 때 C 스택 상태가 복원됩니다.

이런 의미에서, 지난주 리처드와 이 문제를 논의했을 때 놀라운 결론이 나왔습니다: PyPy는 본질적으로 Hard switching의 변형을 수행하고 있습니다! 적어도 pickling에 실제로는 도움이 되지 않는 타협을 하고 있습니다.

반면, 이 접근 방식은 절반의 해법일 뿐입니다. 애초에 재귀를 피할 필요가 없다는 점에서, 이는 SLP보다 개선된 방식으로 드러납니다. 오히려, 그 이전이 아니라 전환(switch)이 일어나는 바로 그 시점에서만 불필요한 상태를 제거하는 것이 더 우아하고 효율적인 것으로 보입니다!

문제를 최소한으로 처리하는 방법

SLP와 PyPy의 서로 다른 접근 방식을 비교해보면, 애초에 인터프리터를 변경할 필요가 없어 보입니다. PyPy는 협조적으로 동작하기 위해 호출 방식을 변경할 필요가 없습니다. 핵심은 어떤 활성화 레코드(activation record)가 애초에 저장되어야 하는지 알아내는 것입니다. 이는 스택리스 변환(stackless transform)의 일부로서 식별할 수 있어야 합니다.

일반적인 Python 함수를 호출하는 가장 단순하고 흔한 경우를 생각해보십시오. 여기에는 준비 작업을 수행하는 여러 함수 호출이 관여합니다. 정확하게 기술하려 하지 않고(이는 앞으로 해야 할 작업의 일부입니다), 관련된 단계들은 다음과 같습니다

• 함수의 인자를 디코딩합니다
• 새 프레임을 준비합니다
• 프레임에 인자를 저장합니다
• 프레임을 실행합니다
• 결과를 반환합니다

이제 프레임을 실행하지 않고 대신 컨텍스트 스위치를 수행한다고 가정하면, 지금 이 순간 일련의 활성화 레코드(activation record)가 힙에 저장되어 있습니다. 이 활성화 레코드 연쇄를 다시 활성화하려면, 함수 호출을 수행하기 전에 실제로 무엇을 복원해야 할까요?

• 인자 디코딩은 이미 완료되었으며, 함수 호출을 수행할 수 있었다는 사실은 예외가 발생하지 않았음을 보여줍니다. 이 활성화 레코드의 나머지 부분은 무시하고 뒷정리를 수행하면 됩니다.
• 프레임이 준비되고, 인자가 그 안에 저장됩니다. 연산이 성공했고, 프레임을 얻었습니다. 예외 처리는 무시하고 참조를 제거하는 정리 작업만 하면 됩니다.
• 프레임을 실행하기 위해서는 프레임을 실행하는 특수한 함수가 필요합니다. 컨텍스트에 따라 서로 다른 종류가 필요할 수 있습니다. SLP는 프레임의 상태(최초 진입, 호출 후 재진입, 반환, yielding 등)에 따라 프레임에서 동작하는 서로 다른 등록 함수를 사용하여 이를 수행합니다.
• 프레임 실행 후에는 예외를 일반적인 방식으로 처리해야 하며, 호출자에게 복귀해야 합니다.

이러한 것들을 정확하게 처리하려면 좀 더 깊은 분석이 필요합니다. 하지만 모든 준비 단계가 끝나면, Python 프레임에 있는 것 외에는 다른 상태가 필요하지 않다는 점이 꽤 명확해졌을 것입니다: 바인딩된 인자, 명령어 포인터, 그게 전부입니다.

제 제안은, 이제 이러한 분석을 손수 수행하여 처리해야 할 여러 경우를 식별한 다음, 전체 프로그램에서 C 스택 복원을 피할 수 있고 이전 호출자로 곧바로 되돌아갈 수 있는 블록들을 자동으로 식별해내는 알고리즘을 찾아보는 것입니다.

필요한 분석에 대한 대략적인 스케치입니다:

unwind에 도달할 수 있는 RPython 함수의 모든 블록에 대해: 제어 흐름을 분석합니다. 이는 출력 변수가 하나뿐인 반환 블록으로 곧바로 이어져야 합니다. 그 외의 모든 생존 변수는 이 블록에서 생존 기간이 종료되어야 합니다.

애초에 이것은 작동하지 않을 것이라고 생각합니다. 예를 들어 바인딩된 프레임 인자의 경우, 이들이 프레임에 의해 유지된다는 것을 나타내는 어떤 표기법이 필요하다고 생각하며, 호출을 수행하기 전에 이들의 활성 상태(liveness)를 제거할 수 있으므로, 이 변수들을 활성화 레코드(activation record)에 저장할 필요가 없고, 따라서 전체 활성화 레코드를 제거할 수 있습니다.

이 불완전한 첫 번째 분석의 결론으로, 피클링(pickling)을 지원하려면 쓸모없는 활성화 레코드(activation record)를 식별할 필요가 있어 보입니다. 그렇다면 남는, 더 이상 줄일 수 없는 활성화 레코드는 Python 프레임에 대한 참조를 가지고 있는 것들이어야 합니다. 이러한 체인은 그 루트가 코루틴(coroutine)의 인터프리터 레벨 구현에 있는 컨텍스트 전환 코드로 다시 이어질 경우 피클링 가능합니다.

하나의 관찰로서, 이 변환은 피클링을 가능하게 할 뿐만 아니라, 많은 활성화 레코드 저장을 피할 수 있다면 최적화이기도 합니다.

제가 증명할 수 있기를 바라는 또 다른 가능한 관찰은 다음과 같습니다: Python 프레임만 담고 있는 것이 아닌, 나머지 축약 불가능한 활성화 레코드들이 특별하게 취급되어야 할 것들입니다. 이들은 특별한 프레임과 같은 것으로 바뀌어야 하며, PyPy를 완전히 스택리스(stackless)로 만드는 핵심이 될 것입니다. 이는 SLP로는 사실상 불가능한 목표입니다! 이러한 활성화 레코드들은 공식 인터페이스의 일부가 되어야 하며, 필요한 함수들에 대한 네이밍 지원을 받아야 할 것입니다.

이 논문은 여기서 멈추고자 합니다. 나머지는 모두 실제 구현에서 시도해 보아야 한다고 생각하며, 이는 지금까지 상상만으로 제가 할 수 있는 전부입니다.

안부 전하며 - 크리스

좀 더 생각해 본 후 덧붙이는 내용입니다

사실 이것을 커밋한 후에 문득 든 생각인데, 어떤 블록이 상태를 저장해야 하고 어떤 블록은 그렇지 않은지를 판단하는 문제는 사실 Stackless만의 문제가 아닙니다. 이는 우리가 아직 해결을 시도하지 않은, 시스템에 내재된 최적화 부재의 문제입니다.

GC 변환(GC transform), 특히 참조 카운팅(refcounting)의 관점에서 말씀드리면, 제가 의도하는 바를 이해하시기는 아마 쉬울 것입니다. 현재 저희의 참조 카운팅 구현은 나이브(naive)한데, 이는 모든 확장 모듈 작성자가 수동으로 수행하는 최적화를 시도하지 않는다는 의미입니다: 저희는 참조를 저장하려 하지 않습니다.

이것이 또한 제가 참조 카운팅(refcounting)이 효율적일 수 있고 실제로 효율적이라고 항상 주장하는 이유이기도 한데, CPython이 이를 매우 잘 수행하기 때문입니다.

우리의 참조 카운팅은 변수의 수명(liveness)을 인식하지 못하며, 다른 객체가 보유하고 있다고 알려진 참조는 추적하지 않습니다. 이를 최적화하면 두 가지 효과를 얻을 수 있습니다. 참조 카운팅이 매우 효율적이게 될 것인데, 그중 약 80%를 절약할 수 있기 때문입니다. 피클링 문제와 관련된 두 번째 부분은 다음과 같습니다. 적절한 분석을 수행하면, 더 이상 저장할 필요가 없는 모든 변수에 대한 참조를 이미 잃은 상태가 될 것입니다. 왜냐하면 예를 들어 그것들이 프레임에 보유되어 있다는 것을 알기 때문입니다.

이 점을 이해해 주시기 바랍니다: 변수의 수명 분석을 개선하면, 어떤 블록이 상태를 저장해야 하고 어떤 블록은 그럴 필요가 없는지에 대해 위에서 개략적으로 설명한 문제는 사소한 것이 되어 그냥 사라져야 합니다. 이를 올바르게 수행하면 피클링 문제가 거의 자동으로 해결되는 동시에 더 효율적인 구현으로 이어질 것입니다.

저는 진실을 말했기를 바라며 그것을 증명하려 노력하겠습니다.

차오 - chris