2017-01-28

[Python] negative index를 사용하자

 일반적으로 random access 가능한 자료 구조에서 뒤에서 k번째 원소를 가져오는 방법은 다음과 같다.

  1. 자료구조의 크기를 가져온다.
  2. 크기를 기반으로 접근할 인덱스를 구한다.
  3. 원하는 자료를 가져온다.

 이를 코드로 표현하면 다음과 같다.
 파이썬에서는 이를 보다 간결하게 표현하기 위해 negative indexing을 지원한다. negative indexing은 말 그대로 음수를 이용해서 뒤에서부터 자료에 접근하는 것이다. negative indexing을 이용하면 위의 코드는 아래와 같이 표현된다.

 파이썬에서는 뒤에서부터 접근할 때 negative indexing을 사용하는 것이 권장되지만 다른 언어로 코딩을 처음 배운 사람들은 파이썬에서도 길이를 가져와 인덱스를 계산하는 방식을 사용하는 경우가 종종 있다. 이런 사람들은 negative indexing이 단순한 syntactic sugar라고 생각하는 것 같다. 하지만 negative indexing은 syntactic sugar가 아니다.
 negative indexing이 syntactic sugar라면 negative indexing을 쓴 것과 같은 바이트 코드가 생성돼야 한다. 하지만 둘은 서로 다른 바이트 코드가 생성된다. 위의 각 코드가 실제로 생성하는 바이트 코드는 다음과 같다.
 첫 번째 코드는 global memory에서 len 함수를 찾아 호출하여 그 결과에 k를 뺀 값을 인덱스로 사용하는 코드를 생성하고, 두 번째 코드는 k를 음수로 만들어 바로 인덱스로 사용한다. 인덱싱을 통해 값을 가지고 오는 바이트 코드는 BINARY_SUBSCR인데, 물론 인터프리터가 BINARY_SUBSCR 를 실행할 때 주어진 인덱스가 음수이면 내부적으로 리스트의 길이를 가져와 인덱스를 다시 계산하는 과정을 거친다. 하지만 Global Interpreter Lock(a.k.a. GIL) 때문에 이 둘의 동작은 같지 않다.
 파이썬의 GIL은 바이트 코드 단위의 atomic만을 보장한다. LOAD_FAST 같은 몇몇 바이트 코드는 GIL을 릴리즈하지 않지만, CALL_FUNCTION을 포함한 대부분의 바이트 코드는 실행 후 GIL을 릴리즈 할 수도 있다.

 또한, 두 코드는 생성되는 바이트 코드가 다르므로 수행 시간도 다르다. 첫 번째 코드는 global memory에서 len 함수를 가지고 와 호출하는 비용이 더 든다.
 게다가 negative indexing을 사용할 때 BINARY_SUBSCR가 내부적으로 계산한 인덱스와 다르게 첫 번째 코드에서 직접 계산한 인덱스는 단순한 정수가 아니라 정수를 들고 있는 PyObject이다. 따라서 값을 할당하고 해제하는 비용이 더 들기 때문에 negative indexing을 사용하는 것이 더 빠르다.

2017-01-10

Python은 어떻게 swap하는가

 지난번 글에서 Lua의 multiple assignment를 이용한 swap이 내부적으로 어떻게 돌아가는지 설명했었다. 그렇다면 파이선은 어떨까?

 자신의 버추얼 머신의 구현까지 제공하는 루아와 다르게 파이선은 공식적으로 어떤 버추얼 머신을 사용해야 하는지 제공하지 않는다. dis 라이브러리를 통해서 어떤 바이트 코드가 나오는지 알 수 있지만, 구체적인 버추얼 머신의 스펙을 정의하거나 바이트 코드의 구현을 정의하지 않는다. 덕분에 PyPy, IronPython, Jython 등 다양한 구현체가 존재한다. 이번에는 우선 그중에서 사실상 표준 구현체라고 할 수 있는 CPython의 구현에 대해서 살펴보겠다.
 CPython의 버추얼 머신이 어떻게 구현돼야 하는가는 명확히 기술되지 않았지만, CPython의 바이트 코드를 보면, CPython은 Lua가 레지스터 머신을 사용하는 것과 다르게 스택 머신을 사용한다는 것을 쉽게 알 수 있다. CPython의 버추얼 머신은 스택과 글로벌/로컬 메모리를 가지고 있다. 글로벌 메모리와 로컬 메모리는 객체의 레퍼런스를 저장하는 데 사용되고 계산을 하기 위해서는 스택으로 레퍼런스를 복사해온 뒤 사용해야 한다.

 이제 swap이 CPython에서 어떤 바이트 코드로 컴파일되는지 살펴보자.  위와 같은 코드는 아래와 같은 바이트 코드로 컴파일된다.  여기서 ROT_TWO는 스택의 가장 위의 두 아이템의 위치를 바꿔주는 바이트 코드다. 즉, 위의 바이트 코드는 스택에 a를 올리고 b를 올린 뒤, 스택의 가장 위의 두 아이템의 위치를 바꾸고, 스택 가장 위의 아이템을 b에 다음 아이템을 a에 저장하는 것이다.

 그렇다면 ROT_TWO는 어떻게 구현됐을까? 현재 CPython에서 ROT_TWO는 임시 변수 2개를 사용하여 스택의 두 값의 위치를 바꾸는 것으로 돼 있다. 즉, CPython에서는 변수 2개를 스왑하기 위해서 스택의 두 자리, ROT_TWO에서 사용하는 임시 변수 두 자리까지 총 6개의 의자가 필요하다.

 로컬 메모리를 바로 복사하지 않고 스택에 올린 뒤 다시 로컬 메모리로 아이템을 옮기도록 하는 이유는 CPython이 로컬 메모리 사이의 연산을 허용하지 않는 stack-based 머신이기 때문이다. 하지만 이 점을 고려해도 CPython의 swap 구현은 비효율적이다. 왜냐하면, 이미 스택을 다른 의자로 사용하고 있는데, ROT_TWO의 내부 구현이 다시 임시변수를 의자로 사용하기 때문이다. 그래서 조금 더 효율적인 바이트 코드를 생성하는 PyPy의 경우 이는 아래와 같은 바이트 코드를 생성한다.  이는 단순히 스택에 a를 올리고, b를 올린 뒤 스택의 가장 위에 있는 아이템을 a로 다음 아이템을 b로 내리는 코드이다. 하지만 여전히 스택에 ab를 둘 다 올릴 자리가 필요하므로 총 4개의 의자가 필요하다.

 그렇다면 파이선에서도 전통적인 방법으로 3번째 변수를 사용해서 스왑하는 것이 좋을까? 아쉽게도 그렇지 않다. 이는 파이선이 스택 머신이기 때문이다. 전통적인 스왑 코드를 컴파일하면 CPython이나 PyPy 양쪽 모두 다음과 같은 바이트 코드가 나온다.  전통적인 방법을 사용하면 우선 a의 아이템을 스택에 올린 뒤 스택에 있는 아이템을 temp에 내린다. 같은 방식으로 ba로 옮기고, tempb로 옮긴다. 즉, temp 변수를 사용하더라도 스택을 한 칸 사용하기 때문에 역시나 총 4개의 의자가 필요하다. 또한, PyPy를 사용하면 LOAD_FASTSTORE_FAST를 각각 한 번씩 적게 사용하고, CPython을 사용하더라도 LOAD_FASTSTORE_FAST를 하는 것보다 ROT_TWO를 하는 것이 더 빠르므로 성능 면에서도 multiple assignment를 이용해 스왑하는 것이 더 빠르다.

2017-01-08

Lua를 쓰면 3번째 의자가 필요하지 않을까 - lua는 어떻게 swap할까

 프로그래머들 사이에서 자주 하는 농담 중에 프로그래머 두 명이 자리를 바꾸려면 의자가 3개 필요하다는 농담이 있다. 둘이 동시에 자리에서 일어나 자리를 옮길 수 있는 사람과 달리 컴퓨터가 다루는 값은 언제나 어딘가에는 할당돼 있어야 해서 나온 말이다. c++로 작성하면 아래와 같은 코드가 되는데, 여기서 local 변수인 temp가 3번째 의자가 된다.

 그렇다면 multiple assignment가 가능한 lua같은 언어는 어떨까?

 lua로 swap 하는 함수를 짜면 위와 같은 코드가 된다. 일단 겉보기에는 3번째 의자가 필요 없어 보인다. 하지만 정말로 3번째 의자가 필요 없을까? 어떤 트릭을 쓰기에 그런 것이 가능한 것일까?

 일단 결론부터 말하면 그런 마법은 없다. 위의 코드가 루아 바이트 코드로 컴파일되면 다음과 같은 바이트 코드가 나온다.
 이 코드를 이해하기 위해 우선 루아 버츄얼 머신을 이해해야 한다. 루아 버츄얼 머신은 stack-based가 아니라 register-based 머신이다. 루아 버츄얼 머신은 최대 256개의 레지스터를 사용할 수 있으며, 함수의 인자는 순서대로 0번 레지스터부터 할당된다. 물론 이는 어디까지나 버츄얼 머신이 이렇다는 것이기 때문에 실제로 256개의 레지스터가 필요하지는 않고, 적절히 번역돼서 실행된다.
 이제 위의 바이트 코드를 읽어보자. b, a = a, bMOVE 2 0; MOVE 0 1; MOVE 1 2로 컴파일됐다. 이를 이해하기 위해서는 MOVE x y는 x번째 레지스터에 y번째 레지스터의 값을 복사해 넣는 바이트 코드라는 것과 인자로 넘어온 ab는 각각 0번 레지스터와 1번 레지스터에 저장돼 있다는 것을 알아야 한다. 그러면 위의 바이트 코드는 3번째 의자인 2번 레지스터를 이용해서 두 변수를 스왑한다는 것을 알 수 있다.