애플리케이션 수준 Stackless 기능¶
소개¶
PyPy는 Stackless Python에 있는 것과 비슷한 언어 기능, 즉 대규모 동시성 스타일로 코드를 작성할 수 있는 기능을 사용자에게 제공할 수 있습니다. (PyPy는 Recursion depth limit 없이 실행하는 기능을 (더 이상) 제공하지 않지만, 같은 효과를 간접적으로 얻을 수 있습니다.)
이 기능은 continulet이라는 사용자 정의 프리미티브를 기반으로 합니다. continulet은 애플리케이션 코드에서 직접 사용할 수 있으며, (전적으로 애플리케이션 수준에서) 더 사용하기 쉬운 인터페이스를 작성할 수도 있습니다.
현재 PyPy는 continulet 위에 Greenlets를 구현하고 있습니다. 또한 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을 가지고 있으며, (최상위 프레임이 아닌 한) 그 자신도 다른 프레임이 가리키고 있습니다.
continulet의 기반 이론은 앞 문장을 말 그대로 “정상적인(O.K.) 상황”의 정의로 삼는 것입니다. 요점은 스택 하나보다 더 복잡한 정상적인 상황도 있다는 것입니다. 스택은 항상 하나 있지만, 그에 더해 프레임들로 이루어진 분리된 순환이 하나 이상 있을 수도 있으며, 이러한 순환에서는 f_back 체인을 따라가면 원을 그리며 돌게 됩니다. 그러나 이 순환들은 실제로 완전히 분리되어 있다는 점에 유의하십시오. 최상위 프레임(현재 실행 중인 프레임)은 항상 다른 어떤 프레임의 f_back도 아닌 프레임이며, 언제나 최하위 프레임으로 끝나는 스택의 꼭대기이고, 이러한 추가 순환의 일부가 되는 일은 결코 없습니다.
이러한 순환은 어떻게 만들 수 있습니까? 이를 위한 기본 연산은 두 프레임을 골라 그 f_back을 치환(permute)하는 것 — 즉, 서로 교환하는 것입니다. “O.K. 상황”이라는 규칙을 깨뜨리지 않고도 임의의 두 f_back을 치환할 수 있습니다. 예를 들어 f가 스택 중간쯤에 있는 어떤 프레임이고, 그 f_back을 맨 위 프레임의 f_back과 치환한다고 합시다. 그러면 중간에 있던 모든 프레임을 일반 스택에서 제거하여 하나의 독립된 순환으로 만든 셈이 됩니다. 같은 치환을 한 번 더 수행하면 원래 상황으로 복원됩니다.
실제로 PyPy에서는 임의의 프레임의 f_back을 변경할 수 없으며, continulets에 저장된 프레임의 f_back만 변경할 수 있습니다.
Continulet은 내부적으로 Stacklets를 사용하여 구현되어 있습니다. Stacklet은 조금 더 원시적이지만(사실상 일회성(one-shot) 컨티뉴에이션입니다), 그 개념은 Python에서는 동작하지 않고 C에서만 동작합니다. Continulet의 기본 개념은 어느 시점에서든 완전하고 유효한 스택을 갖는 것입니다. 이는 예를 들어 예외를 올바르게 전파하는 데 중요합니다(그리고 의미 있는 트레이스백을 제공하는 데에도 도움이 되는 것으로 보입니다).
애플리케이션 수준 인터페이스¶
컨티뉼렛(Continulet)¶
변환된 PyPy에는 기본적으로 continulet 타입을 내보내는 _continuation이라는 모듈이 포함되어 있습니다. 이 모듈의 continulet 객체는 “일회성 컨티뉴에이션(one-shot continuation)”을 저장하는 컨테이너입니다. 이 객체는 스택에 삽입할 수 있는 추가 프레임의 역할을 하며, 이 프레임의 f_back은 변경할 수 있습니다.
continulet 객체를 만들려면 호출 가능한 객체와 선택적인 추가 인자를 넘겨 continulet()을 호출하십시오.
이후 continulet으로 처음 switch()하면, 호출 가능 객체(callable)가 같은 continulet 객체를 추가 첫 번째 인자로 받아 호출됩니다. 이 시점에 continulet에 저장된 일회성(one-shot) continuation은 switch()의 호출자를 가리킵니다. 다시 말해, 겉보기에는 완전히 평범한 프레임 스택이 만들어집니다. 하지만 switch()가 다시 호출되면, 저장되어 있던 이 일회성 continuation이 현재 continuation과 교환됩니다. 즉, switch()의 호출자는 자신의 continuation이 컨테이너에 저장된 채로 일시 중단되고, continulet 객체에 있던 이전 continuation이 재개됩니다.
가장 원시적인 API는 사실 ‘permute()’이며, 이는 두 개(또는 그 이상)의 continulet에 저장된 일회성(one-shot) continuation을 그저 서로 뒤바꿀(permute) 뿐입니다.
좀 더 자세히 설명하면 다음과 같습니다:
continulet(callable, *args, **kwds): 새 continulet을 만듭니다. 제너레이터와 마찬가지로 이 호출은 continulet을 생성하기만 합니다.callable은 이 continulet으로 처음 전환될 때 비로소 실제로 호출됩니다. 다음과 같이 호출됩니다:callable(cont, *args, **kwds)
여기서
cont는 동일한 continulet 객체입니다.실제로 continulet을 바인딩하는 것은
cont.__init__()이라는 점에 유의하십시오.continulet.__new__()를 명시적으로 호출하여 아직 바인딩되지 않은 continulet을 생성한 다음, 나중에cont.__init__()을 명시적으로 호출하여 바인딩하는 것도 가능합니다.cont.switch(value=None, to=None): continulet이 아직 시작되지 않았다면 시작합니다. 그렇지 않으면 현재 continuation을cont에 저장하고 대상 continuation을 활성화합니다. 대상 continuation은 이전에cont에 저장되어 있던 continuation입니다. 대상 continuation 자체도 이전에 다른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를 반환합니다. continulet이 초기화되지 않았을 때(__init__이 아니라__new__를 호출했기 때문입니다) 또는 완료되었을 때(callable()이 반환되었기 때문입니다) 이 값은 False입니다. 값이 False이면 continulet 객체는 비어 있으므로switch()로 이 객체에 전환할 수 없습니다.permute(*continulets): 인자로 주어진 continulet들에 저장된 컨티뉴에이션들을 서로 뒤바꾸는(permute) 전역 함수입니다. 대부분 이론적인 용도입니다. 실제로는permute()를 사용하는 것보다cont.switch()를 사용하는 편이 더 쉽고 효율적입니다.permute()는 그 자체만으로는 현재 실행 중인 프레임을 바꾸지 않습니다.
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)을 기반으로 구현되어 있습니다. 공식 documentation of the greenlets를 참고하십시오.
CPython의 greenlet과 달리 이 버전에는 GC 문제가 없다는 점에 유의하십시오. 프로그램이 완료되지 않은 greenlet을 “잊어버리더라도” 그 greenlet은 항상 다음 가비지 컬렉션 때 회수됩니다.
구현되지 않은 기능¶
(과거 PyPy의 일부 Stackless 버전에 있던) 다음 기능은 현재로서는 더 이상 지원되지 않습니다:
- 코루틴(애플리케이션 수준에서 다시 작성할 수 있음)
- 다른 스레드에서 continulet의 실행을 이어 가는 것(단, continulet이 “충분히 단순”하다면 피클(pickle)한 뒤 다른 스레드에서 언피클(unpickle)할 수 있습니다).
- 자동 무제한 스택 (현재까지는 에뮬레이션해야 합니다)
- x86 및 x86-64 이외의 CPU 지원
또한 set_atomic()과 같이 최근 Stackless Python에 추가된 API는 하나도 포함하지 않습니다. 기여를 환영합니다.
재귀 깊이 제한¶
continulet을 사용하면 Stackless Python과 스택리스(stackless) 기능이 활성화된 이전 버전의 PyPy가 제공하던 무한 재귀 깊이를 흉내 낼 수 있습니다.
요령은 continulet을 “일찍”, 즉 재귀 깊이가 아주 얕을 때 시작해 두고, “나중에”, 즉 재귀 깊이가 깊어졌을 때 그 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를 누르면, 트레이스백은 지금까지의 모든 recursive() 호출을 포함하여 만들어진다는 점에 유의하십시오. 그 수가 C 스택에 들어갈 수 있는 수보다 많더라도 마찬가지입니다. 이 프레임들은 C 스택의 관점에서 서로 “겹쳐” 있습니다. 더 정확히 말하면, 프레임들은 필요에 따라 C 스택 밖으로 복사되었다가 다시 C 스택 안으로 복사됩니다.
(위 예제에서는 처음 접하는 사람이 continulet을 작성하는 데 도움이 되는 다음과 같은 일반적인 “지침”도 사용합니다. bootstrap(c) 안에서는 다른 continulet 객체가 아니라 c의 메서드만 호출하십시오. 그래서 to.switch()가 아니라 c.switch(to=to)라고 작성했습니다. to.switch()를 사용하면 상태가 엉망이 됩니다. 하지만 이것은 지침일 뿐입니다. 일반적으로는 genlet이나 greenlet 같은 다른 인터페이스를 사용하기를 권장합니다.)
스택릿(Stacklets)¶
컨티뉼릿(continulet)은 내부적으로 스택릿(stacklet)을 사용하여 구현됩니다. 스택릿은 “일회성 컨티뉴에이션(one-shot continuation)”을 위한 범용 RPython 수준의 기본 구성 요소입니다. 이에 대한 자세한 내용은 rpython/translator/c/src/stacklet/stacklet.h에 있는 C 소스의 문서를 참조하십시오.
rpython.rlib.rstacklet 모듈은 위 함수들을 감싸는 얇은 래퍼입니다. 핵심은 new()와 switch()가 항상 새로운 stacklet 핸들(또는 빈 핸들)을 반환하며, switch()는 추가로 핸들 하나를 소비한다는 점입니다. 반환된 핸들을 무시하거나 두 번 이상 사용하는 코드는 의미가 없습니다. stacklet.c는 사용자가 이 점을 알고 있다고 가정하고 작성되었으므로 추가 검사를 전혀 하지 않는다는 점에 유의하십시오. 따라서 PyPy의 ‘_continuation’ 모듈과 같은 래퍼를 사용하지 않으면 원인을 알기 어려운 크래시가 쉽게 발생할 수 있습니다.
조합성(composability) 이론¶
코루틴이라는 개념은 결코 새로운 것이 아니지만, 주류 언어에는 대체로 통합되지 않았거나 (Python의 제너레이터나 C#의 이터레이터처럼) 제한된 형태로만 통합되었습니다. 그 이유 중 하나로 프로그램의 복잡도가 증가할 때 코루틴이 잘 확장되지 않는다는 점을 들 수 있습니다. 코루틴은 작은 예제에서는 매력적으로 보이지만, 예를 들어 대상 코루틴의 이름을 지정하는 방식처럼 명시적인 전환을 요구하는 모델은 자연스럽게 조합되지 않습니다. 이는 서로 관련 없는 두 가지 목적으로 코루틴을 사용하는 프로그램이 예기치 않은 상호작용으로 인한 충돌을 겪을 수 있음을 의미합니다.
문제를 설명하기 위해 다음 예제를 살펴보겠습니다(가상의 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)을 이용해 Python의 제너레이터를 간단하게 다시 구현한 예를 살펴봅시다:
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() 호출의 결과로 재개되는 것이 아닙니다).
따라서 코루틴이라는 개념은 합성 가능하지 않습니다. 반대로, continulet이라는 기본 개념은 합성 가능합니다. 그 위에 서로 다른 두 인터페이스를 빌드하거나, 같은 인터페이스를 두 부분에서 두 번 사용하는 프로그램이 있더라도, 두 부분이 각각 독립적으로 동작한다면 두 부분을 합성한 것도 여전히 동작합니다.
그 주장을 완전히 증명하려면 정의를 신중하게 내려야 하겠지만, 여기서는 다음 관찰에 근거하여 이 사실이 참이라고 주장하기만 합시다. continulet의 API는 switch()를 수행할 때 프로그램이 명시적으로 조작할 어떤 continulet을 가지고 있어야 하도록 되어 있습니다. 이 API는 현재 continuation을 그 continulet에 저장된 continuation과 뒤바꾸지만, 그 바깥에는 아무런 영향을 미치지 않습니다. 따라서 프로그램의 어떤 부분이 continulet 객체를 가지고 있으면서 그것을 전역으로 노출하지 않는다면, 프로그램의 나머지 부분은 그 continulet 객체에 저장된 continuation에 실수로 영향을 미칠 수 없습니다.
다시 말해, continulet 객체를 본질적으로 수정 가능한 f_back으로 본다면, 이것은 callable()의 프레임과 부모 프레임 사이의 연결일 뿐입니다 — 그리고 관련 없는 코드가 continulet 객체를 명시적으로 조작하지 않는 한, 그 코드가 이 연결을 임의로 바꿀 수는 없습니다. 일반적으로 callable()의 프레임(보통 지역 함수)과 그 부모 프레임(그 프레임으로 전환한 프레임)은 모두 같은 클래스나 모듈에 속합니다. 따라서 그런 관점에서 continulet은 두 지역 프레임 사이의 순수하게 지역적인 연결입니다. 이 연결을 외부에서 조작할 수 있게 하는 개념을 두는 것은 의미가 없습니다.