Peephole optimization

해당 문서는 https://legacy.python.org/workshops/1998-11/proceedings/papers/montanaro/montanaro.html 를 번역한 것으로, 파이썬의 버전에 따라 결과가 다를 수 있습니다. 원본 문서 python 1.5 버전으로 1998.11월에 작성되었습니다. 

 

 

 

파이썬 코드는 간단한 방식으로 고수준 가상 머신에 의해 컴파일 됩니다. 성능을 향상시키기 위해 코드에 peephole optimizer를 적용할 수 있어야 합니다. 이 문서는 기존 바이트 컴파일러와 통합 된 Python으로 작성된 peephole optimization를 조사합니다.

 

일반적으로, peephole optimization는 opcode의 패턴을 찾아 더 효율적인 코드로 치환해줍니다. peephole optimization는 코드 생성 중에 컴파일러보다 많은 명령 스트림을 한 번에 볼 수 있습니다. 

 

예를 들어

x = hairy_calc()
y = x + 15

x를 할당 한 후 바로 데이터 값을 로드합니다. 컴파일러는 x에 저장하기 전에 스택에 함수 값이 어떻게 쓰이는지 몰랐습니다. 컴파일된 명령문 이후를 아직 보지 않았기 때문입니다. Peephole optimization은 매우 간단한 패턴을 볼 수 있습니다.

 

STORE x
LOAD x

위를 다음과 같이 치환합니다.

DUP_TOP
STORE x

DUP_TOP : 스택 top의 참조를 복사합니다. 

 

이 문서에서는 python 디스어셈블러의 표기법이 나옵니다.  (https://docs.python.org/3.7/library/dis.html)

 

 

Architecture

Peephole optimization은  Python 클래스로 구성됩니다. 각 클래스는 단일 최적화 적용에 특화된 OptimizeFilter 기본 클래스의 서브 클래스입니다. 전체 optimizer는 여러 optimizer를 파이프 라인에 연결하여 빌드됩니다. 

 

TupleRearranger

a, b, c = 1,2,3

 

튜플의 unpack 작업은 많은 오버헤드가 발생합니다. 오른쪽의 실행 순서는 영향을 받지 않지만, 왼쪽의 할당에 대한 부분이 최적화됩니다. 먼저 위의 코드는 다음의 명령어로 생성됩니다. 

 

LOAD_CONST   1
LOAD_CONST   2
LOAD_CONST   3
BUILD_TUPLE  3
UNPACK_TUPLE 3
STORE_FAST   a
STORE_FAST   b
STORE_FAST   c

BUILD_TUPLE/UNPACK_TUPLE는 스택의 top값의 순서를 바꾸는 역활을 합니다. 연산자의 순서를 바꾸는 것보다 할당을 반대로 해주는 게 간단합니다. 

LOAD_CONST   1
LOAD_CONST   2
LOAD_CONST   3
STORE_FAST   c
STORE_FAST   b
STORE_FAST   a

 

ConstantExpressionEvaluator

이 클래스는 상수 표현식을 미리 계산하여 이진 / 단항 연산으로 구성된 튜플을 함수 상수 목록에 저장합니다. 표현식 2 + 3j는 다음과 같이 나타납니다.

LOAD_CONST n (2)
LOAD_CONST m (3j)
BINARY_ADD

클래스는 다음과 같이 변환시킵니다. 

LOAD_CONST q (2+3j)

 

위와 같이 복잡한 상수를 사용하는 코드의 성능이 크게 향상 될 수 있습니다.

 

UnreachableCodeRemover

이 클래스는 기본 블록에서 사용하지 않는 모든 명령을 삭제합니다. 사용하지 않는 코드를 제거하여 프로그램의 성능을 직접 향상 시키지는 않지만 때로는 추가 최적화를 위한 기반이 됩니다. 

 

 

 

LoadStoreCompressor

LOAD_FAST/ LOAD_ATTR 또는 LOAD_FAST/ STORE_ATTR를 각각 LOAD_FAST_ATTR / STORE_FAST_ATTR opcode로 바꿉니다. LOAD_FAST_ATTR / STORE_FAST_ATTR는 많은 성능 향상을 가져오고, 다른 유형의 로드 및 저장 명령수를 증가시켜 스트림 최적화를 증가시킵니다. 

 

 

MultiLoadEliminator

동일한 객체의 n 연속로드를 단일 로드로 변환  및 n-1 DUP_TOP opcode로 변환합니다.

 

 

StoreLoadEliminator

이 클래스는 저장객체의 동일 객체가 있다면 DUP_TOP으로 변환 및 해당 저장 객체를 삭제합니다. 

foo = spam = some_hairy_function(...)
bar = foo * math.sin(math.pi/3)
baz = aunt_mabel * foo

이 클래스는 현재 foo의 첫 번째로드는 제거하지만 두 번째 로드는 제거하지 않습니다.

 

 

JumpNextEliminator

블록의 마지막 opcode 인 경우 무조건 점프합니다.

 

 

JumpOptimizer

n 개의 점프 체인을 통과하는  경우라면  2 번째에서 n 번째 점프까지 단락 시킵니다.

 

 

ConstantShortcut

LOAD_CONST / LOAD_NONE / LOADI 등을 LOAD_NONE로 변환하거나 small_ints 캐시를 통해 상수를 찾지 않도록 하여 메모리 참조를 줄입니다. 

(PyTupleObject *)(f->f_code->co_consts)->ob_item[i]

 

F가 최근 사용한 객체라면 small_ints[I] 이거나 Py_None이 됩니다. 

 

 

 

Branches Not Taken

숫자의 대수 성질을 이용하여 최적화를 하면 성능이 좋아질 수 있습니다. 하지만 불가능한 경우가 있는데, 객체가 특정한 작업을 실행하지만, 숫자와 관련된 일반적인 연결이나 사이드이팩트에 의해 할 수 없는 경우가 있습니다. 

 

예를 들어 

l + a + l

는 다음과 같이 변환됩니다.

 

LOAD l
LOAD a
BINARY_ADD
LOAD l
BINARY_ADD

 

l과 a가 숫자라면 로드를 피하기 위해 다음과 같이 변환이 가능합니다. 

LOAD l
DUP_TOP
BINARY_ADD
LOAD a
BINARY_ADD

하지만 l과 a가 문자열이라면 다른 방식으로 줄일 수 있습니다. 

만약 우리가 소수점이나 부동소수점을 다루고 있다면

a = a ** 2

 

는 다음과 같이 변환됩니다. 

a = a * a

곱셈이 지수보다 빠르기 때문입니다. 하지만 옵티마이저는 a가 숫자 인지 모릅니다..

 

최적화되는 코드가 기본 블록의 영역을 넘어 확장되면 다른 최적화가 가능합니다. 사용되지 않은 변수를 식별하여 제거합니다. 크로스 점프는 동일한 블록 두 개의 기본 블록의 끝 부분에 공통적인 코드를 병합합니다. 다음 코드 세그먼트는 크로스 점프를 보여줍니다.

 

if type(a) == types.ComplexType:
    x = cmath.sin(a)
    foo(x)
else:
    x = math.sin(a)
    foo(x)

를 다음과 같이 변환합니다.

if type(a) == types.ComplexType:
    x = cmath.sin(a)
else:
    x = math.sin(a)
foo(x)

 

POP n을 가상 머신에 추가하여 스택 오염 (지연된 스택 정리)을 수행할 수 있습니다. 스택 오염은 필요할 때까지 스택 정리를 저장합니다.

예를 들어

f(10)
g(20)

 

위의 코드를 컴파일 시 

LOADI 10
LOAD f
CALL_FUNCTION 1
POP_TOP
LOADI 20
LOAD g
CALL_FUNCTION 1
POP_TOP

 

에서 첫 번째 pop은 연기될 수 있습니다. 

LOADI 10
LOAD f
CALL_FUNCTION 1
LOADI 20
LOAD g
CALL_FUNCTION 1
POP 2

이를 위해서는 f(10) 호출이 g(20)가 반환 반환되기 전에 반환 값이  스택에 아래에 요소가 필요한지 않은지 확인합니다. 

 

 

 

 

Results

모든 성능 테스트는 다음 구성으로 컴퓨터에서 실행되었습니다.

 

100MHz 펜티엄, 64MB 메인 메모리

레드햇 리눅스 5.0

EGCS 1.0.3 컴파일러

파이썬 1.5.1

파이 벤치 0.6

 

Test	% diff	Test	% diff
Builtin Function Calls	-2.51%	Second Import	+1.37%
Builtin Method Lookup	-11.95%	Second Package Import	+1.63%
Comparisons	+2.06%	Second Submodule Import	+0.50%
Concat Strings	-7.34%	Simple Complex Arithmetic	-14.68%
Create Instances	-0.01%	Simple Dict Manipulation	-4.24%
Create Strings With Concat	-12.30%	Simple Float Arithmetic	+3.85%
Dict Creation	-5.01%	Simple Int Float Arithmetic	+1.55%
For Loops	-5.46%	Simple Integer Arithmetic	-0.74%
If Then Else	-3.52%	Simple List Manipulation	-8.07%
List Slicing	-0.34%	Simple Long Arithmetic	-7.83%
Nested For Loops	-0.97%	Small Lists	-7.11%
Normal Class Attribute	-20.64%	Small Tuples	-3.74%
Normal Instance Attribute	+3.84%	Special Class Attribute	-23.11%
PPrint	-1.88%	Special Instance Attribute	+1.65%
Pickler	+0.31%	String Slicing	-9.55%
Python Function Calls	+0.81%	Try Except	+0.67%
Python Method Calls	-2.72%	Try Raise Except	-2.33%
Random	+4.32%	Tuple Slicing	-6.39%
Recursion	+7.30%

 

 

결과는 매우 큰 개선점을 보여주는 몇 가지 테스트가 있고, 그중 일부는 중간 정도의 개선점을 보여 주지만, 그 변화로 인해 많은 어려움을 겪는 것은 아래의 토론으로 이어집니다. 

 

Discussion

 

인터 프린터 밴치마크 결과

이 작업은 올바른 환경에서 peephole optimization가 상당한 성능 향상을 가져올 수 있음을 보여줍니다. 이러한 개선 측정의 정확성은 매우 어려운데 일반적으로 측정이 가능한 도구가 조잡하거나 (단순한 타이밍), 아직 잘 특성화되지 않았거나 (pybench) 비현실적인 혼합을 보여주기 때문입니다. 실제 프로그램에 대한  어렵게 하는 작업 (pystone 및 pybench) 또한 컴파일러, 최적화 수준 및 대상 프로세서 간의 차이로 인해 개선 사항을 숨길 수 있습니다. 여기에 적용된 최적화 범위는 바이트 코드를 스캔하는 동안 작성자가 본 패턴이나 다른 사람이 제안한 패턴으로 제한됩니다.

 

 프로세서 아키텍처, 컴파일러, 최적화 수준 및 캐시 크기 등 많은 요소의 영향을 받습니다. 옵티마이저의 사용 여부를 결정하기 전에 전체 범위의 측정을 수행하는 것이 가장 좋습니다.

 

 

기타 변경사항

 

Optimization of stack access

스택 포인터의 이동을 최소화하여, 메모리 참조 같은 스택을 많이 사용하는  DUP_TOP / ROT_TWO / ROT_THREE 등의 코드를 opcode에 대한  성능 향상합니다.

 

 

Caching the top element of the stack in a register

인터프리터의 메모리 액세스 패턴을 조금 더 향상합니다.


Short-circuiting interpreter error checks

인터프리터 루프의 맨 아래에 있는 오류 검사 코드는 세 개의 변수 값 err, x, why를 테스트합니다. 몇 가지 예외가 있지만 각 가상 머신 명령어는 해당 변수 중 최대 하나를 설정하여 코드의 오류 조건을 확인합니다. 

이러한 최적화는 일부 파이 벤치 테스트에서 성능이 약간 향상되었지만 다른 테스트에서는 성능이 저하되었습니다

 

 

 

---

 

 

추가로 읽어보면 좋은 글들

https://tech.ssut.me/peephole-how-python-optimizes-bytecode/

 

https://akaptur.com/blog/2014/08/02/the-cpython-peephole-optimizer-and-you/