애플리케이션 레벨 Stackless 기능¶
소개¶
PyPy는 사용자에게 Stackless Python에 있는 것과 유사한 언어 기능, 즉 대규모 동시성 스타일로 코드를 작성할 수 있는 능력을 제공할 수 있습니다. (더 이상 재귀 깊이 제한 없이 실행하는 기능은 제공하지 않지만, 같은 효과는 간접적으로 얻을 수 있습니다.)
이 기능은 continulet라는 사용자 정의 프리미티브를 기반으로 합니다. Continulet은 애플리케이션 코드에서 직접 사용할 수 있으며, (완전히 앱 레벨에서) 더 사용자 친화적인 인터페이스를 작성하는 것도 가능합니다.
현재 PyPy는 continulets 위에서 그린렛(Greenlets)를 구현합니다. 또한 (근사적으로) tasklets와 channels를 구현하며, Stackless Python의 모델을 모방합니다.
Continulet은 매우 경량이므로, PyPy가 대량의 continulet을 포함하는 프로그램도 처리할 수 있어야 함을 의미합니다. 하지만 구현상의 제약으로 인해, --gcrootfinder=shadowstack으로 컴파일된 PyPy는 살아 있는 continulet마다 최소 한 페이지의 물리 메모리(4KB)와, 32비트에서는 0.5메가바이트, 64비트에서는 1메가바이트의 가상 메모리를 소비합니다. 게다가 이 기능은 (지금까지는) x86 및 x86-64 CPU에서만 사용할 수 있으며, 다른 CPU에서는 rpython/translator/c/src/stacklet/에 짧은 분량의 사용자 정의 어셈블리 코드를 추가해야 합니다.
이론¶
기본 아이디어는 프로그램이 임의의 시점에 하나의 프레임 스택을 실행하고 있다는 것입니다(멀티스레딩의 경우 스레드마다 하나씩). 스택을 확인하려면 최상위 프레임에서 시작해서 최하위 프레임에 도달할 때까지 f_back의 연쇄를 따라가면 됩니다. 이 프레임들 중 하나의 관점에서 보면, 그것은 다른 프레임을 가리키는 f_back을 가지고 있으며(최하위 프레임이 아닌 이상), 그 자신도 다른 프레임에 의해 가리켜지고 있습니다(최상위 프레임이 아닌 이상).
continulets의 배경 이론은 앞 문장을 말 그대로 “정상적인(O.K.) 상황”의 정의로 삼는 것입니다. 트릭은 스택 하나만 있는 것보다 더 복잡한 정상적인 상황들이 있다는 것입니다: 여러분은 항상 스택 하나를 갖지만, 그 외에 분리된 프레임 순환을 하나 이상 추가로 가질 수도 있으며, 이 경우 f_back 체인을 따라가면 원을 그리며 돌게 됩니다. 하지만 이 순환들은 실제로 완전히 분리되어 있다는 점에 유의하십시오: 최상위 프레임(현재 실행 중인 프레임)은 항상 다른 누구의 f_back도 아닌 프레임이며, 항상 최하위 프레임으로 끝나는 스택의 최상단이지, 이 추가 순환의 일부가 되는 경우는 결코 없습니다.
이러한 순환은 어떻게 만들 수 있을까요? 이를 위한 기본 연산은 두 프레임을 가져와 그 f_back을 치환하는 것 — 즉, 서로 교환하는 것입니다. “O.K. 상황”이라는 규칙을 깨지 않고도 임의의 두 f_back을 치환할 수 있습니다. 예를 들어 f가 스택 중간쯤에 있는 어떤 프레임이라고 하고, 이 프레임의 f_back을 최상위 프레임의 f_back과 치환한다고 가정합니다. 그러면 일반 스택에서 모든 중간 프레임들을 제거하여 하나의 독립적인 순환으로 만든 것입니다. 같은 치환을 다시 수행하면 원래 상황으로 복원됩니다.
실제로 PyPy에서는 임의의 프레임의 f_back을 변경할 수 없으며, continulets에 저장된 프레임의 것만 변경할 수 있습니다.
Continulet은 내부적으로 스택릿(Stacklets)을 사용하여 구현됩니다. Stacklet은 좀 더 원시적입니다(사실은 일회성 continuation입니다). 하지만 그 아이디어는 Python이 아니라 C에서만 동작합니다. Continulet의 기본 아이디어는 언제든지 완전하고 유효한 스택을 유지하는 것입니다. 이는 예를 들어 예외를 올바르게 전파하는 데 중요합니다(그리고 의미 있는 트레이스백을 제공하는 것으로도 보입니다).
애플리케이션 레벨 인터페이스¶
Continulets¶
번역(translation)된 PyPy는 기본적으로 continulet 타입을 내보내는 _continuation이라는 모듈을 포함합니다. 이 모듈의 continulet객체는 “일회성 연속(one-shot continuation)”을 저장하는 컨테이너입니다. 이는 스택에 삽입할 수 있는 추가 프레임의 역할을 하며, 그 f_back을 변경할 수 있습니다.
continulet 객체를 만들려면, 호출 가능한 객체와 선택적인 추가 인자와 함께 continulet()을 호출합니다.
나중에 continulet으로 처음 switch()를 호출하면, 호출 가능 객체(callable)는 동일한 continulet 객체를 추가 첫 번째 인자로 받아 호출됩니다. 그 시점에 continulet에 저장된 일회용 연속(continuation)은 switch()의 호출자를 가리킵니다. 다시 말해, 완전히 정상적으로 보이는 프레임 스택을 갖게 됩니다. 하지만 switch()가 다시 호출되면, 저장되어 있던 이 일회용 연속은 현재 연속과 교환됩니다. 즉, switch()의 호출자는 자신의 연속을 컨테이너에 저장한 채 일시 중단되고, continulet 객체의 이전 연속이 재개됩니다.
가장 원시적인 API는 사실 ‘permute()’이며, 이는 두 개(또는 그 이상)의 continulet에 저장된 원샷 continuation을 그저 순열(permute)할 뿐입니다.
더 자세히 설명하면:
continulet(callable, *args, **kwds): 새로운 continulet을 만듭니다. 제너레이터와 마찬가지로, 이것은 생성만 할 뿐입니다;callable은 처음 전환될 때 비로소 실제로 호출됩니다. 다음과 같이 호출됩니다:callable(cont, *args, **kwds)
여기서
cont는 동일한 continulet 객체입니다.사실 continulet을 바인딩하는 것은
cont.__init__()입니다. 아직 바인딩되지 않은 continulet을 명시적으로continulet.__new__()를 호출하여 생성한 다음, 나중에 명시적으로cont.__init__()을 호출하여 바인딩하는 것도 가능합니다.cont.switch(value=None, to=None): continulet이 아직 시작되지 않았다면 시작합니다. 그렇지 않으면 현재 컨티뉴에이션(continuation)을cont에 저장하고, 이전에cont에 저장되어 있던 대상 컨티뉴에이션을 활성화합니다. 대상 컨티뉴에이션 자체도 이전에 다른switch()호출에 의해 일시 중단되었다는 점에 유의하십시오. 이 이전의switch()는 이제 반환되는 것처럼 보이게 됩니다.value인수는 대상으로 전달되고, 대상의switch()에 의해 반환되는 모든 객체입니다.to가 주어지면, 이는 또 다른 continulet 객체여야 합니다. 이 경우 “이중 전환(double switch)”을 수행합니다: 위에서 설명한 대로cont(으)로 전환한 다음, 즉시 다시to(으)로 전환합니다. 이는to(으)로 직접 전환하는 것과 다릅니다: 현재 컨티뉴에이션은cont에 저장되고,cont의 이전 컨티뉴에이션은to에 저장되며, 그런 다음에야to에서 나온 이전 컨티뉴에이션으로부터 실행을 재개합니다.cont.throw(type, value=None, tb=None, to=None):switch()와 유사하지만, 전환이 완료된 직후 대상에서 주어진 예외를 발생시킨다는 점이 다릅니다.cont.is_pending(): continulet이 대기 중이면 True를 반환합니다. 이는 초기화되지 않았을 때(__new__를 호출하고__init__은 호출하지 않았기 때문에) 또는 완료되었을 때(callable()이 반환되었기 때문에) False가 됩니다. False일 때, continulet 객체는 비어 있으며switch()로 전환될 수 없습니다.permute(*continulets): 주어진 continulets 인자들에 저장된 continuation들을 순환 치환(permute)하는 전역 함수입니다. 대부분 이론적인 것입니다. 실제로는permute()를 사용하는 것보다cont.switch()를 사용하는 것이 더 쉽고 효율적입니다. 후자는 그 자체로는 현재 실행 중인 프레임을 변경하지 않습니다.
Genlets¶
_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을 출력합니다. 일반 제너레이터를 사용하는 것에 비해 유일한 장점은 제너레이터 자체가 모두 같은 함수 안에 구문적으로 위치해야 하는 yield문에 국한되지 않는다는 것입니다. 대신 cont를 예를 들어 중첩된 하위 함수로 전달하고, 그곳에서 cont.switch(x)를 호출할 수 있습니다.
generator데코레이터는 메서드에도 적용할 수 있습니다:
class X:
@generator
def f(self, cont, a, b):
...
그린렛(Greenlets)¶
Greenlet은 lib_pypy/greenlet.py에서 continulet 위에 구현됩니다. greenlet의 공식 documentation of the greenlets를 참고하십시오.
CPython의 greenlet과 달리, 이 버전은 GC 문제를 겪지 않는다는 점에 유의하십시오: 프로그램이 완료되지 않은 greenlet을 “잊어버리더라도”, 항상 다음 가비지 컬렉션에서 수집됩니다.
미구현 기능¶
다음 기능들(과거 PyPy의 일부 Stackless 버전에 있었던)은 현재로서는 더 이상 지원되지 않습니다:
- 코루틴(app-level에서 다시 작성될 수 있음)
- 다른 스레드에서 continulet의 실행을 계속하는 것(단, “충분히 단순”하다면, 다른 스레드에서 피클(pickle)하고 언피클(unpickle)할 수 있습니다).
- 자동 무제한 스택(지금까지는 에뮬레이트되어야 함)
- x86 및 x86-64 이외의 CPU에 대한 지원
또한 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):
# this loop runs forever, at a very low recursion depth
callable, arg = c.switch()
while True:
# start a new continulet from here, and switch to
# it using an "exchange", i.e. a switch with to=.
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) # prints ('ok', 999999)
이 예제를 실행하는 동안 Ctrl-C를 누르면, C 스택에 들어갈 수 있는 개수보다 많더라도 지금까지의 모든 recursive() 호출로 트레이스백이 생성된다는 점에 유의하십시오. 이 프레임들은 C 스택의 관점에서 서로 “겹쳐” 있습니다. 더 정확히 말하면, 필요에 따라 C 스택 안팎으로 복사됩니다.
(위 예제는 또한 newcomer가 continulet을 작성하는 데 도움이 되는 다음과 같은 일반적인 “지침”도 사용합니다: bootstrap(c)에서는 다른 continulet 객체가 아니라 c에 대해서만 메서드를 호출하라는 것입니다. 그래서 상태를 망가뜨릴 수 있는 to.switch()가 아니라 c.switch(to=to)를 사용한 것입니다. 하지만 이것은 단지 지침일 뿐이며, 일반적으로는 genlet이나 greenlet과 같은 다른 인터페이스를 사용하는 것을 권장합니다.)
스택릿(Stacklets)¶
Continulet은 내부적으로 stacklet을 사용하여 구현되며, 이는 “일회성 continuation(one-shot continuation)”을 위한 일반적인 RPython 수준의 빌딩 블록입니다. 이에 대한 자세한 정보는 rpython/translator/c/src/stacklet/stacklet.h에 있는 C 소스 문서를 참조하십시오.
rpython.rlib.rstacklet 모듈은 위 함수들을 감싸는 얇은 래퍼입니다. 핵심은 new()와 switch()가 항상 새로운 stacklet 핸들(또는 빈 핸들)을 반환하며, switch()는 추가로 하나를 소비한다는 점입니다. 반환된 핸들이 무시되거나 두 번 이상 사용되는 코드는 말이 되지 않습니다. stacklet.c는 사용자가 이를 알고 있다고 가정하고 작성되었으며, 그래서 추가적인 검사가 이루어지지 않는다는 점에 유의하십시오. PyPy의 ‘_continuation’ 모듈과 같은 래퍼를 사용하지 않으면, 이는 쉽게 알아내기 어려운 크래시로 이어질 수 있습니다.
조합성(composability) 이론¶
코루틴이라는 개념은 결코 새로운 것이 아니지만, 주류 언어들에 일반적으로 통합되지 못했거나, 통합되었더라도 파이썬의 제너레이터나 C#의 이터레이터처럼 제한된 형태로만 존재해왔습니다. 그 이유로는 프로그램의 복잡도가 증가할 때 코루틴이 잘 확장되지 않는다는 점을 들 수 있습니다: 작은 예제에서는 매력적으로 보이지만, 대상 코루틴의 이름을 지정하는 방식처럼 명시적 전환을 요구하는 모델은 자연스럽게 조합되지 않습니다. 이는 서로 관련 없는 두 가지 목적으로 코루틴을 사용하는 프로그램이 예기치 않은 상호작용으로 인한 충돌을 겪을 수 있음을 의미합니다.
문제를 설명하기 위해 다음 예제를 살펴보겠습니다(가상의 coroutine 클래스를 사용하는 단순화된 코드). 먼저, coroutine의 간단한 사용법입니다.:
main_coro = coroutine.getcurrent() # the main (outer) coroutine
data = []
def data_producer():
for i in range(10):
# add some numbers to the list 'data' ...
data.append(i)
data.append(i * 5)
data.append(i * 25)
# and then switch back to main to continue processing
main_coro.switch()
producer_coro = coroutine()
producer_coro.bind(data_producer)
def grab_next_value():
if not data:
# put some more numbers in the 'data' list if needed
producer_coro.switch()
# then grab the next value from the list
return data.pop(0)
grab_next_value() 호출은 매번 값을 하나만 반환하지만, 필요한 경우 프로듀서 함수로 전환되어(그리고 다시 돌아와) 값을 좀 더 채워 넣을 기회를 줍니다.
이제 코루틴(coroutine)을 이용한 파이썬 제너레이터의 간단한 재구현을 생각해봅시다:
def generator(f):
"""Wrap a function 'f' so that it behaves like a 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):
"""Yield the value from the current generator."""
g = coroutine.getcurrent()
g.answer = value
g.caller.switch()
def squares(n):
"""Demo generator, producing square numbers."""
for i in range(n):
Yield(i * i)
squares = generator(squares)
for x in squares(5):
print x # this prints 0, 1, 4, 9, 16
이 두 예시 모두 매력적일 만큼 우아합니다. 하지만 이들은 조합할 수 없습니다. 다음과 같은 제너레이터를 작성하려고 하면:
def grab_values(n):
for i in range(n):
Yield(grab_next_value())
grab_values = generator(grab_values)
그러면 프로그램이 예상대로 동작하지 않습니다. 그 이유는 다음과 같습니다. grab_values()를 실행하는 제너레이터 코루틴은 grab_next_value()를 호출하며, 이는 producer_coro 코루틴으로 전환될 수 있습니다. 지금까지는 잘 동작하지만, data_producer()에서 main_coro로 다시 전환하는 부분은 잘못된 코루틴에 도달합니다: 실행이 메인 코루틴에서 재개되는데, 이는 원래 전환이 시작된 코루틴이 아닙니다. 우리는 data_producer()가 grab_next_values() 호출로 다시 전환되기를 기대하지만, 후자는 wrappedfunc에서 생성된 제너레이터 코루틴 g 안에 존재하며, 이는 data_producer() 코드에는 전혀 알려져 있지 않습니다. 대신, 실제로는 메인 코루틴으로 다시 전환되며, 이는 generator_iterator.next() 메서드를 혼란스럽게 만듭니다(재개되기는 하지만 Yield() 호출의 결과로 재개되는 것이 아닙니다).
따라서 코루틴(coroutine)의 개념은 합성 가능하지 않습니다. 반대로 continulet의 기본 개념은 합성 가능합니다: 이를 기반으로 서로 다른 두 인터페이스를 구축하거나, 프로그램에서 동일한 인터페이스를 두 부분에서 두 번 사용하는 경우, 두 부분이 각각 독립적으로 동작한다고 가정하면 두 부분을 합성한 결과도 여전히 동작합니다.
이 주장에 대한 완전한 증명에는 세심한 정의가 필요하지만, 다음과 같은 관찰에 근거하여 이 사실이 참이라고만 주장하겠습니다: continulet의 API는 switch()를 수행할 때 프로그램이 명시적으로 조작할 어떤 continulet을 가지고 있어야 하도록 되어 있습니다. 이는 현재 continuation을 해당 continulet에 저장된 continuation과 서로 뒤바꾸지만, 외부에는 아무런 영향을 미치지 않습니다. 따라서 프로그램의 일부가 continulet 객체를 가지고 있으면서 이를 전역으로 노출하지 않는다면, 프로그램의 나머지 부분은 해당 continulet 객체에 저장된 continuation에 실수로 영향을 미칠 수 없습니다.
다시 말해, continulet 객체를 본질적으로 수정 가능한 f_back으로 간주한다면, 이는 단지 callable()의 프레임과 부모 프레임 사이의 링크일 뿐이며 — 관련 없는 코드가 continulet 객체를 명시적으로 조작하지 않는 한, 임의로 변경될 수 없습니다. 일반적으로 callable()의 프레임(보통 지역 함수)과 그 부모 프레임(즉, 그것으로 전환한 프레임)은 모두 동일한 클래스나 모듈에 속합니다. 따라서 이 관점에서 보면 continulet은 두 지역 프레임 사이의 순수하게 지역적인 링크입니다. 이 링크를 외부에서 조작할 수 있게 하는 개념은 말이 되지 않습니다.