PyPy의 continulet, genlet, greenlet, 재귀 깊이 제한 우회, stacklet 이론과 인터페이스를 설명합니다.
PyPy는 사용자 언어에 Stackless Python에 있는 것과 비슷한 기능, 즉 대규모 동시성 스타일로 코드를 작성할 수 있는 능력을 노출할 수 있습니다. (더 이상 재귀 깊이 제한 없이 실행하는 기능은 제공하지 않지만, 같은 효과를 간접적으로 얻을 수는 있습니다.)
이 기능은 continulet라는 사용자 정의 원시 기능에 기반합니다. Continulet은 애플리케이션 코드에서 직접 사용할 수도 있고, 또는 더 사용자 친화적인 인터페이스를 전적으로 앱 수준에서 작성할 수도 있습니다.
현재 PyPy는 continulet 위에 greenlet을 구현합니다. 또한 Stackless Python의 모델을 에뮬레이션하는 tasklet과 channel도 (근사적으로) 구현합니다.
Continulet은 극도로 가볍기 때문에, PyPy는 그것들이 대량으로 포함된 프로그램도 처리할 수 있어야 합니다. 하지만 구현상 제약 때문에 --gcrootfinder=shadowstack으로 컴파일된 PyPy는 살아 있는 continulet 하나당 최소 한 페이지의 물리 메모리(4KB), 그리고 32비트에서는 0.5MB의 가상 메모리, 64비트에서는 1MB 전체를 소비합니다. 게다가 이 기능은 (현재까지는) x86 및 x86-64 CPU에서만 사용할 수 있습니다. 다른 CPU에서는 rpython/translator/c/src/stacklet/에 짧은 사용자 정의 어셈블리 페이지를 추가해야 합니다.
근본적인 아이디어는, 어떤 시점이든 프로그램은 하나의 프레임 스택(또는 멀티스레딩의 경우 스레드당 하나)을 실행하고 있다는 것입니다. 스택을 보려면 맨 위 프레임에서 시작해 맨 아래 프레임에 도달할 때까지 f_back 체인을 따라가면 됩니다. 이 프레임들 중 하나의 관점에서 보면, 그것은 다른 프레임을 가리키는 f_back을 가지며(맨 아래 프레임이 아니라면), 동시에 다른 프레임이 그것 자신을 가리키고 있습니다(맨 위 프레임이 아니라면).
Continulet 이론은 문자 그대로 앞 문장을 “정상적인 상태”의 정의로 삼습니다. 비결은, 단순히 하나의 스택만 있는 경우보다 더 복잡한 정상 상태가 존재한다는 점입니다. 언제나 하나의 스택은 있지만, 그에 더해 하나 이상의 분리된 프레임 사이클 도 있을 수 있으며, f_back 체인을 따라가면 원을 그리며 돌게 됩니다. 하지만 이 사이클들은 완전히 분리되어 있다는 점에 유의해야 합니다. 맨 위 프레임(현재 실행 중인 프레임)은 언제나 누구의 f_back도 아닌 프레임이며, 언제나 맨 아래 프레임으로 끝나는 스택의 꼭대기에 있고, 이런 추가 사이클의 일부가 아닙니다.
이런 사이클은 어떻게 만들까요? 이를 위한 근본 연산은 두 프레임을 골라 그들의 f_back을 교환 하는 것입니다. 즉, 서로 바꾸는 것입니다. 어떤 두 f_back이든 “정상적인 상태” 규칙을 깨지 않고 교환할 수 있습니다. 예를 들어 f가 스택 중간쯤에 있는 어떤 프레임이고, 그 f_back과 맨 위 프레임의 f_back을 교환한다고 합시다. 그러면 일반 스택에서 그 사이에 있던 중간 프레임들이 모두 제거되어 독립된 하나의 사이클이 됩니다. 같은 교환을 다시 수행하면 원래 상태가 복원됩니다.
실제로 PyPy에서는 임의의 프레임의 f_back을 바꿀 수는 없고, continulet에 저장된 프레임들에 대해서만 가능합니다.
Continulet은 내부적으로 stacklet을 사용해 구현됩니다. Stacklet은 조금 더 원시적입니다(실제로는 원샷 continuation입니다). 하지만 그 아이디어는 C에서는 가능해도 Python에서는 그렇지 않습니다. Continulet의 기본 아이디어는 어느 시점에서나 완전하고 유효한 스택을 갖는 것입니다. 이것은 예를 들어 예외를 올바르게 전파하는 데 중요합니다(그리고 의미 있는 traceback도 제공하는 것으로 보입니다).
번역된 PyPy에는 기본적으로 _continuation이라는 모듈이 포함되어 있으며, 이 모듈은 continulet 타입을 내보냅니다. 이 모듈의 continulet 객체는 “원샷 continuation”을 저장하는 컨테이너입니다. 이것은 스택에 삽입할 수 있고 f_back을 변경할 수 있는 추가 프레임 역할을 합니다.
Continulet 객체를 만들려면 callable과 선택적 추가 인수를 넣어 continulet()을 호출합니다.
그 후 처음 switch()로 continulet으로 전환하면, 그 callable은 동일한 continulet 객체를 추가 첫 번째 인수로 받아 호출됩니다. 그 시점에서 continulet에 저장된 원샷 continuation은 switch()의 호출자를 가리킵니다. 즉, 완전히 정상적으로 보이는 프레임 스택이 생깁니다. 하지만 switch()가 다시 호출되면, 저장된 이 원샷 continuation이 현재의 것과 교환됩니다. 이는 switch()의 호출자가 자신의 continuation을 컨테이너에 저장한 채 중단되고, continulet 객체에 있던 이전 continuation이 재개된다는 뜻입니다.
가장 원시적인 API는 사실 permute()로, 두 개(또는 그 이상)의 continulet에 저장된 원샷 continuation을 그저 서로 교환합니다.
좀 더 자세히 말하면:
continulet(callable, *args, **kwds): 새로운 continulet을 만듭니다. generator와 마찬가지로 이것은 생성만 하며, callable은 처음 전환될 때만 실제로 호출됩니다. 호출 형태는 다음과 같습니다:callable(cont, *args, **kwds)
여기서 cont는 같은 continulet 객체입니다.
실제로 continulet을 바인딩하는 것은 cont.__init__()라는 점에 유의하세요. continulet.__new__()를 명시적으로 호출해 아직 바인딩되지 않은 continulet을 만들고, 나중에 cont.__init__()를 명시적으로 호출해 바인딩하는 것도 가능합니다.
cont.switch(value=None, to=None): 아직 시작되지 않았다면 continulet을 시작합니다. 그렇지 않으면 현재 continuation을 cont에 저장하고, 이전에 cont에 저장되어 있던 대상 continuation을 활성화합니다. 대상 continuation 역시 이전에 다른 switch() 호출로 중단되어 있었던 점에 유의하세요. 이 더 오래된 switch()는 이제 반환하는 것처럼 보이게 됩니다. value 인수는 대상에게 전달되어 대상의 switch()가 반환하는 임의의 객체입니다.to가 주어지면, 그것은 다른 continulet 객체여야 합니다. 이 경우 “이중 전환”을 수행합니다. 먼저 위에서 설명한 대로 cont로 전환한 다음, 즉시 다시 to로 전환합니다. 이것은 곧바로 to로 전환하는 것과 다릅니다. 현재 continuation은 cont에 저장되고, cont의 이전 continuation은 to에 저장되며, 그 후에야 to에서 꺼낸 이전 continuation부터 실행을 재개합니다.
cont.throw(type, value=None, tb=None, to=None): switch()와 비슷하지만, 전환이 끝난 직후 대상에서 주어진 예외를 발생시킵니다.
cont.is_pending(): continulet이 보류 중이면 True를 반환합니다. __new__만 호출하고 __init__는 호출하지 않아 초기화되지 않았거나, callable()이 반환되어 종료된 경우에는 False입니다. False일 때 continulet 객체는 비어 있으며 switch()로 전환할 수 없습니다.
permute(*continulets): 주어진 continulet 인수들에 저장된 continuation을 서로 교환하는 전역 함수입니다. 대부분 이론적인 기능입니다. 실제로는 permute()를 사용하는 것보다 cont.switch()를 사용하는 편이 더 쉽고 효율적입니다. permute() 자체는 현재 실행 중인 프레임을 바꾸지 않습니다.
_continuation 모듈은 generator 데코레이터도 노출합니다:
@generator def f(cont, a, b): cont.switch(a + b) cont.switch(a + b + 1)
for i in f(10, 20): print i
이 예제는 30과 31을 출력합니다. 일반 generator를 사용하는 것보다 나은 점은, generator 자체가 문법적으로 모두 같은 함수 안에 있어야 하는 yield 문에 제한되지 않는다는 것입니다. 대신 cont를 넘겨줄 수 있고, 예를 들어 중첩된 하위 함수에 전달한 뒤 그 안에서 cont.switch(x)를 호출할 수 있습니다.
generator 데코레이터는 메서드에도 적용할 수 있습니다:
class X: @generator def f(self, cont, a, b): ...
Greenlet은 lib_pypy/greenlet.py에서 continulet 위에 구현되어 있습니다. 자세한 내용은 공식 greenlet 문서를 참조하세요.
CPython의 greenlet과 달리, 이 버전은 GC 문제를 겪지 않는다는 점에 유의하세요. 프로그램이 끝나지 않은 greenlet을 “잊어버려도”, 다음 가비지 컬렉션 때 항상 수집됩니다.
다음 기능들(PyPy의 과거 Stackless 버전에 있던 기능)은 현재로서는 더 이상 지원되지 않습니다:
또한 set_atomic() 같은 Stackless Python의 최근 API 추가 사항도 포함하지 않습니다. 기여를 환영합니다.
Continulet을 사용하면 Stackless Python 및 stackless가 활성화된 예전 버전의 PyPy에 있는 무한 재귀 깊이를 에뮬레이션할 수 있습니다.
비결은 continulet을 “이르게” 시작하는 것입니다. 즉, 재귀 깊이가 매우 낮을 때 시작하고, “나중에” 즉 재귀 깊이가 높을 때 그것으로 전환하는 것입니다. 예제:
from _continuation import continulet
def invoke(_, callable, arg): return callable(arg)
def bootstrap(c): # 이 루프는 매우 낮은 재귀 깊이에서 영원히 실행된다 callable, arg = c.switch() while True: # 여기서 새 continulet을 시작하고, "exchange" 즉 to=.가 있는 # switch를 사용해 그 continulet으로 전환한다. to = continulet(invoke, callable, arg) callable, arg = c.switch(to=to)
c = continulet(bootstrap) c.switch()
def recursive(n): if n == 0: return ("ok", n) if n % 200 == 0: prev = c.switch((recursive, n - 1)) else: prev = recursive(n - 1) return (prev[0], prev[1] + 1)
print recursive(999999) # ('ok', 999999)를 출력함
이 예제를 실행하는 동안 Ctrl-C를 누르면, traceback은 지금까지의 모든 recursive() 호출로 구성된다는 점에 유의하세요. 이 수는 C 스택에 실제로 들어갈 수 있는 수보다 많을 수도 있습니다. 이 프레임들은 C 스택의 의미에서 서로 “겹쳐져” 있습니다. 더 정확히 말하면 필요에 따라 C 스택 밖으로 복사되었다가 다시 안으로 복사됩니다.
(위 예제는 continulet을 처음 사용하는 사람이 continulet을 작성하는 데 도움이 되는 다음과 같은 일반적인 “지침”도 사용합니다. bootstrap(c)에서는 다른 continulet 객체가 아니라 c에 대해서만 메서드를 호출하세요. 그래서 to.switch()가 아니라 c.switch(to=to)를 쓴 것입니다. 전자는 상태를 망가뜨릴 수 있습니다. 하지만 이것은 어디까지나 지침일 뿐입니다. 일반적으로는 genlet이나 greenlet 같은 다른 인터페이스를 사용하는 것을 권장합니다.)
Continulet은 내부적으로 “원샷 continuation”을 위한 일반적인 RPython 수준 구성 요소인 stacklet을 사용해 구현됩니다. 이에 대한 자세한 정보는 rpython/translator/c/src/stacklet/stacklet.h의 C 소스 문서를 참조하세요.
rpython.rlib.rstacklet 모듈은 위 함수들에 대한 얇은 래퍼입니다. 핵심은 new()와 switch()가 항상 새 stacklet 핸들(또는 빈 핸들)을 반환하고, switch()는 추가로 핸들 하나를 소비한다는 점입니다. 반환된 핸들을 무시하거나, 한 번보다 많이 사용하는 코드는 의미가 없습니다. stacklet.c는 사용자가 이 사실을 알고 있다고 가정하고 작성되었기 때문에 추가 검사도 하지 않습니다. 따라서 PyPy의 _continuation 모듈 같은 래퍼를 사용하지 않으면 알아보기 어려운 충돌이 쉽게 발생할 수 있습니다.
Coroutine 개념 자체는 결코 새로운 것이 아니지만, 주류 언어에 일반적으로 통합되지는 않았고, 통합되더라도 제한된 형태에 그쳤습니다(Python의 generator나 C#의 iterator처럼). 가능한 이유 중 하나는 프로그램의 복잡성이 증가할수록 이것이 잘 확장되지 않기 때문이라고 주장할 수 있습니다. 작은 예제에서는 매력적으로 보이지만, 예를 들어 대상 coroutine의 이름을 지정하여 명시적 전환을 요구하는 모델은 자연스럽게 조합되지 않습니다. 이것은 서로 무관한 두 목적에 coroutine을 사용하는 프로그램이 예상치 못한 상호작용으로 인한 충돌에 부딪힐 수 있음을 의미합니다.
문제를 설명하기 위해 다음 예제를 생각해 봅시다(이론적인 coroutine 클래스를 사용하는 단순화된 코드입니다). 먼저 coroutine의 단순한 사용 예:
main_coro = coroutine.getcurrent() # 메인(바깥쪽) coroutine data = []
def data_producer(): for i in range(10): # 숫자 몇 개를 'data' 리스트에 추가하고 ... data.append(i) data.append(i * 5) data.append(i * 25) # 그런 다음 main으로 다시 전환하여 처리를 계속한다 main_coro.switch()
producer_coro = coroutine() producer_coro.bind(data_producer)
def grab_next_value(): if not data: # 필요하면 'data' 리스트에 숫자를 더 넣는다 producer_coro.switch() # 그런 다음 리스트에서 다음 값을 가져온다 return data.pop(0)
grab_next_value()를 호출할 때마다 하나의 값을 반환하지만, 필요하면 producer 함수로 전환했다가 다시 돌아와 더 많은 숫자를 넣을 기회를 줍니다.
이제 coroutine으로 Python의 generator를 간단히 재구현한 예를 봅시다:
def generator(f): """함수 'f'를 generator처럼 동작하도록 감싼다.""" def wrappedfunc(*args, **kwds): g = generator_iterator() g.bind(f, *args, **kwds) return g return wrappedfunc
class generator_iterator(coroutine): def iter (self): return self def next(self): self.caller = coroutine.getcurrent() self.switch() return self.answer
def Yield(value): """현재 generator에서 값을 산출한다.""" g = coroutine.getcurrent() g.answer = value g.caller.switch()
def squares(n): """제곱수를 생성하는 데모 generator.""" for i in range(n): Yield(i * i) squares = generator(squares)
for x in squares(5): print x # 이것은 0, 1, 4, 9, 16을 출력한다
이 두 예제는 모두 우아하고 매력적입니다. 그러나 이들은 조합될 수 없습니다. 다음 generator를 작성하려고 하면:
def grab_values(n): for i in range(n): Yield(grab_next_value()) grab_values = generator(grab_values)
프로그램은 기대한 대로 동작하지 않습니다. 이유는 다음과 같습니다. grab_values()를 실행하는 generator coroutine이 grab_next_value()를 호출하고, 이 함수는 producer_coro coroutine으로 전환할 수 있습니다. 여기까지는 잘 동작합니다. 하지만 data_producer()에서 main_coro로 다시 전환하면 잘못된 coroutine으로 착지합니다. 실행이 메인 coroutine에서 재개되는데, 그것은 방금 전환이 일어난 원래 coroutine이 아닙니다. 우리는 data_producer()가 grab_next_values() 호출로 다시 전환되기를 기대하지만, 후자는 wrappedfunc 안에서 생성된 generator coroutine g 안에 있으며 data_producer() 코드는 그것을 전혀 모릅니다. 대신 실제로는 메인 coroutine으로 돌아가 버리고, 이 때문에 generator_iterator.next() 메서드는 혼란에 빠집니다(Yield() 호출의 결과로 재개된 것이 아닌데도 재개되기 때문입니다).
따라서 coroutine이라는 개념은 조합 가능하지 않습니다. 반대로 continulet의 원시 개념은 조합 가능합니다. 그 위에 서로 다른 두 인터페이스를 구축하거나, 같은 인터페이스를 프로그램의 두 부분에서 두 번 사용하더라도, 두 부분이 각각 독립적으로 동작한다면 그 둘의 조합도 여전히 동작합니다.
이 주장을 완전히 증명하려면 주의 깊은 정의가 필요하겠지만, 여기서는 다음 관찰 때문에 이 사실이 참이라고만 주장하겠습니다. Continulet의 API는 switch()를 할 때 프로그램이 명시적으로 조작할 어떤 continulet을 가지고 있어야 하도록 되어 있습니다. 그것은 현재 continuation과 그 continulet에 저장된 continuation을 서로 뒤섞지만, 그 밖의 외부에는 영향을 주지 않습니다. 따라서 프로그램의 한 부분이 continulet 객체를 가지고 있고 그것을 전역으로 노출하지 않는다면, 프로그램의 나머지 부분은 그 continulet 객체에 저장된 continuation에 우연히 영향을 줄 수 없습니다.
다르게 말하면, continulet 객체를 본질적으로 수정 가능한 f_back이라고 본다면, 그것은 callable()의 프레임과 부모 프레임 사이의 연결일 뿐이며, 관련 없는 코드가 continulet 객체를 명시적으로 조작하지 않는 한 임의로 변경될 수 없습니다. 보통 callable()의 프레임(대개 지역 함수)과 그것의 부모 프레임(그쪽으로 전환한 프레임)은 같은 클래스나 모듈에 속합니다. 따라서 그런 관점에서 continulet은 두 개의 지역 프레임 사이에 있는 순전히 지역적인 연결입니다. 이 연결이 외부에서 조작될 수 있도록 허용하는 개념은 의미가 없습니다.