Python 함수 코드가 일반 코드보다 빠른 이유

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

문제 제기

알고리즘 문제를 풀다보면 항상 시간 제약에 민감해질 수밖에 없는데 그 중에서도 Python은 C나 Java에 비해 속도가 느려 체감이 더 크다. BOJ #10217 KCM Travel문제를 풀던 중 Python으로 해결 시 같은 로직임에도 함수 안에 넣고 넣지 않고로 통과 여부가 결정됨을 확인했다. 그 원인에 대해 찾아본 결과 Why does Python code run faster in a function?에서 질문/답변을 주고받은 글이 있어 개인적으로 정리해보려 한다.

시간 측정

$10^8$번 순회를 도는 시간을 체크해보자.

python 코드

from time import time


def check():
    start = time()
    for i in range(10 ** 8):
        pass
    return time() - start


print(check())
start = time()
for i in range(10 ** 8):
    pass
print(time() - start)

실행 결과 약 2배의 차이가 난다. 물론 코드를 실행하는 머신의 상태에 따라 가변적이겠으나 일반적인 경우에도 차이가 남을 확인할 수 있을 것이다. 글 원문에서는 프로세서의 차이인지 거의 4배에 가까운 속도 차이를 보여주었다. 이 정도면 실무에서든 문제 풀이에서든 충분히 의미 있는 시간 차이로 보인다.

function 코드와 global 코드와의 차이

결론부터 말하면 Python의 코어를 담당하는 CPython의 구현 방식으로 인해 차이가 발생한다. 함수가 컴파일되면 크기가 정해진 배열에 로컬 변수들을 저장한다. 이 과정으로 인해 함수에 동적으로 변수를 추가할 수 없는 것이다. 따라서, 함수 내부의 특정 변수를 global하게 접근하기 위해선 global 변수를 명시적으로 붙여주어야 한다. 그렇지 않으면 함수 내부 변수를 저장할 때 STORE_FAST opcode를 사용하는데 global 변수는 STORE_NAME opcode를 사용하기 때문에 접근할 수 없기 때문이다. 이러한 변수 저장 방식의 차이가 속도 차이의 요인으로 작용한다.

STORE_FAST와 STORE_NAME에 왜 차이가 발생하는가

위에서 function을 compile하면서 크기가 정해진 배열에 저장하니 global 변수와는 달리 호출이 빠르다는 점은 인지했다. 그러나 별도로 STORE_NAME opcode와 STORE_FAST opcode에 대한 요인도 언급된다. 일반적으로 반복문은 FOR_ITER opcode를 호출하는데 반복 순회 시 loop의 top에 FOR_ITER이 위치하게 되고 그 이후 STORE_NAME opcode가 올 것이라 "예측"하게 된다. 만약 함수 내부에 변수를 넣어 내부 변수로 처리되었다면 바로 STORE_FAST opcode로 점프하여 검증 과정을 생락하기 때문에 사실상 1개의 opcode로 작용한다.

만약 global 레벨에서 STORE_NAME opcode가 루프에 사용된 경우 예측에 실패하기 때문에 내부 변수와는 달리 skip 과정이 없다. 만약 아래와 같이 함수의 변수를 global로 선언하여 실행하면 확실히 시간 지연이 발생함을 확인할 수 있다.

from time import time

def check():
    start = time()
    global x
    for i in range(10 ** 8):
        x += 1
    return time() - start

x = 0
print(check())
start = time()
k = 0
for j in range(10 ** 8):
    k += 1
print(time() - start)

함수 내부의 변수를 global 변수로 선언해서 다루면 갑자기 소요시간이 급증함을 확인할 수 있다. 사실상 global 코드와 동일한 시간을 갖는 걸 볼 수 있다.

결론

시간 지연을 고려하여 모든 기능 단위 코드는 함수에 넣어 작성하고 혹여 global한 값을 반복문에 넣지 않았는지 체크해야 한다. 꼭 필요하다면 메모리 제약조건을 확인한 후 내부 변수로 받아서 실행함이 속도에 유리할 것이다.