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

2007-07-22 작성 참고: 이 문서는 내용이 다소 오래되었으므로 피클링(pickling)에 대한 설명으로 바꾸어야 합니다. 명시적인 재개 지점(resume point) 등을 없애려면 추가 연구가 필요합니다…

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

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

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

피클링은 다른 머신에서 실행할 수 있고 다시 시작할 수 있는 코루틴 비슷한 것을 만들어야 합니다. 이때 Python 버전은 같아야 하지만, PyPy 변환까지 같을 필요는 없습니다. 이는 비교적 어려운 부분에 속합니다.

피클링(pickling)이란 무엇이 아닙니까?

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

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

간단한 단계도 있고 좀 더 어려운 단계도 있습니다. 간단한 것부터 시작합시다.

기본 필수 요소

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

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

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

몇 가지만 예로 들어도 이 정도입니다. 다행히 이 객체들 대부분은 Stackless Python에 이미 피클링 구현이 있습니다. 바로 prickelpit.c 파일입니다.

이러한 구현을 다시 만드는 일은 간단하고 수월할 것입니다. 그럼에도 한 가지 복잡한 문제가 있습니다. 피클링을 지원하는 가장 자연스러운 방법은 __getstate__/__setstate__ 메서드 쌍을 제공하는 것입니다. 이 방법은 코루틴/태스클릿처럼 우리가 제어할 수 있는 확장 타입에는 괜찮지만, 기존 타입에는 피해야 합니다.

예를 들어 프레임 인스턴스를 생각해 봅시다. __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로도 이것은 불가능합니다. 상태의 종류가 여러 가지여서 추가 정보 없이는 처리하기 어렵기 때문입니다.

SLP 전환 전략

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

음, 이는 부분적으로만 사실입니다. 필요한 지원을 추가하려면 구현을 대대적으로 다시 작성해야 하므로 재귀 호출을 피할 수 없었던 상황이 몇 가지 있습니다.

예시는 다음과 같습니다.

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

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

위에서 설명한 개념을 Hard (switching)라고 하며, 협력적인 방식을 Soft (switching)라고 합니다. Hard의 개선된 버전이 여전히 greenlet의 기반이라는 점에 유의하십시오. 이 때문에 greenlet은 사실 진정한 green이라고 할 수 없으며, 저라면 yellow라고 부르겠습니다.

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

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

SLP와 PyPy 사이의 유사점

현재 PyPy는 함수의 C 상태를 작은 활성화 레코드에 저장합니다. 여기에는 블록의 살아 있는 변수와, 빠져나온 함수의 진입점이 함께 들어갑니다. 이는 원시 스택 조각을 그대로 저장하는 방식보다 개선된 것이지만, 패턴은 비슷합니다. 전환할 때 C 스택 상태가 복원됩니다.

이런 의미에서, 지난주 Richard와 제가 이 문제를 논의했을 때 놀라운 결론에 이르렀습니다. PyPy는 본질적으로 Hard switching의 한 변형을 수행하고 있다는 것입니다! 적어도 피클링에는 별로 도움이 되지 않는 절충안을 택하고 있습니다.

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

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

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

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

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

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

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

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

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

필요한 분석의 대략적인 개요는 다음과 같습니다:

unwind에 도달할 수 있는 RPython 함수의 모든 블록에 대해: 제어 흐름을 분석합니다. 해당 블록은 출력 변수가 하나뿐인 반환 블록으로 곧바로 이어져야 합니다. 그 밖의 살아 있는 변수는 모두 이 블록에서 생존 구간이 끝나야 합니다.

애초에 이 방식은 동작하지 않을 것이라고 생각합니다. 예를 들어 바인딩된 프레임 인자의 인스턴스를 보면, 이 인자들은 프레임이 보유하고 있다는 표기가 필요하고, 호출 전에 그 활성 상태를 해제할 수 있으므로 이 변수들을 활성화 레코드에 저장할 필요가 없으며, 따라서 활성화 레코드 전체를 제거할 수 있다고 생각합니다.

이 불완전한 첫 분석의 결론으로, 피클링을 지원하려면 쓸모없는 활성화 레코드를 식별해야 할 것으로 보입니다. 그러면 남아 있는, 더 이상 줄일 수 없는 활성화 레코드는 Python 프레임에 대한 참조를 가진 레코드여야 합니다. 이러한 체인은 그 루트가 코루틴의 인터프리터 수준(interp-level) 구현에 있는 컨텍스트 전환 코드를 다시 가리키면 피클링할 수 있습니다.

참고로, 이 변환은 피클링을 가능하게 할 뿐만 아니라, 많은 활성화 레코드를 저장하지 않아도 된다면 최적화 효과도 있습니다.

제가 증명할 수 있기를 바라는 또 다른 관찰은 다음과 같습니다. Python 프레임만 담고 있지 않고 더 이상 줄일 수 없는 나머지 활성화 레코드들이 바로 특별하게 다루어야 할 대상입니다. 이들은 특별한 프레임과 같은 것으로 바꾸어야 하며, PyPy를 완전히 스택리스(stackless)로 만드는 열쇠가 될 것입니다. 이는 SLP로서는 사실상 불가능한 목표입니다! 이러한 활성화 레코드들은 공식 인터페이스의 일부가 되어야 하며, 여기에 필요한 함수들에 이름을 붙일 수 있도록 지원해야 합니다.

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

안부를 전합니다 - chris

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

사실 이것을 커밋한 뒤에 문득 떠오른 생각인데, 어떤 블록이 상태를 저장해야 하고 어떤 블록은 그럴 필요가 없는지 판별하는 문제는 사실 Stackless만의 문제가 아닙니다. 이는 최적화가 빠져 있어서 생기는 시스템 내재적인 문제로, 우리가 아직 해결을 시도하지 않은 문제입니다.

GC 변환, 특히 참조 카운팅의 관점에서 말씀드리면 제가 무슨 뜻으로 드리는 말씀인지 쉽게 이해하실 수 있을 것입니다. 현재 저희의 참조 카운팅 구현은 모든 확장 모듈 작성자가 직접 손으로 하는 최적화를 시도하지 않는다는 점에서 단순(naive)합니다. 즉, 참조를 아끼려고 하지 않습니다.

이것은 또한 제가 참조 카운팅(refcounting)이 효율적일 수 있으며 실제로 효율적이라고 늘 주장하는 이유이기도 합니다. CPython이 이를 매우 잘 해내고 있기 때문입니다.

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

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

제가 진실을 말했기를 바라며, 이를 증명하도록 노력하겠습니다.

안녕히 계십시오 - chris