Pypy3과 Python3의 성능 차이

백준으로 파이썬 알고리즘을 푸는데, 같은 코드인데 Python3으로 풀었을 때는 시간초과가 났으나, Pypy3으로 풀고 나니 시간 초과가 나지 않았다.

처음에는 미처 문제에 있는 설명을 보지 못하고 Python3으로 제출했는데, 맨 아래 제출내역을 보다보면 알다시피 3%에서 시간초과가 나왔다.

 

중간은 input = sys.stdin.readline()을 쓰다가 오류가 난 것. 이것도 나중에 포스팅해봐야지

 

https://www.acmicpc.net/problem/20920

(해시를 연습하기 좋은 문제)

 

 

 

문제 밑의 설명을 보니 파이썬의 경우에는 Pypy를 권장하고 있었다.

 

Pypy란 무엇인가?

Python3 실행 시 시간이 매우 오래 걸린다는 단점이 있어서, 그것을 개선하고자 JIT 컴파일 방식을 도입한 것이다.

 

swea의 21295. 거듭제곱 분할 문제의 상단에 있는 설명인데, swea의 경우 언어별 제한시간을 명시했다. 대부분 파이썬이 C의 3배 이상은 된다.

저 문제 아직 안풀어봄 풀생각없음 왜냐 정답률이 1.82%거든

 

 

 

그 전에 Python이 어떤 언어인가에 대해서 알아보고자 한다.

 

파이썬은 사실 CPython이라는 표준 구현체를 의미한다.

이걸 설명하기 전에, 인터프리터 언어와 컴파일 언어가 무엇인지 한번 짚고 넘어가야 한다.

 

컴파일 언어란,

일단 코드가 전부 작성되면, 이 작성된 소스 코드를 저급 언어로 번역하는 프로그램인 컴파일러에 집어 넣고 한번에 기계어로 번역한 다음 실행파일을 만든다. 주로 C, C++, C#, JAVA가 여기에 속한다.

 

컴파일러 언어는 실행 단계와 컴파일 단계가 각각 분리되어 있으며, 컴파일을 단 한 번만 수행한다. 실행시에는 컴파일 과정을 거치지 않고 실행만 하면 되기 때문에 코드 실행 속도가 빠르나, 프로젝트의 규모가 클 경우 컴파일 시간이 오래 걸릴 수 있다는 단점이 있다.

 

 

당장 파이참으로 파이썬 코드를 짜서 실행할 때와 인텔리제이를 이용해서 자바 코드를 짜서 실행할 때 인텔리제이 컴파일 시간을 생각해보면, 컴파일 언어와 인터프리터 언어의 차이에 대해서 조금은 체감할 수 있지 않을까 싶다. 인텔리제이로 자바 알고리즘 코드 짜고 처음 실행 시, 컴파일 시간이 오래걸려서 인고의 시간을 감내해야 한다.

 

 

 

인터프리터 언어란,

 

컴파일 언어는 한번에 컴파일러에 넣어서 실행했다면, 인터프리터 언어는 줄 단위로 받을 때마다 실행하는 언어이다.

 

컴파일 하는 과정이 없어서 컴파일 시간은 소요되지 않으나, 실행시마다 인터프리트 과정이 반복되어 실행 속도가 느리다는 단점이 있다.

 

Python, Javascript, Ruby 등이 이에 속한다.

 

 

 

보통 우리가 이용하는 파이썬은 Cpython이라는 구현체를 의미한다. 

 

흔히 이용하는 CPython의 작동 과정에 대해 살펴보면,

 

Python은 C언어로 작성된 컴파일러를 활용해서 라인단위로 Code를 인터프리팅 하여 실행합니다.

 

반면, Pypy의 경우 Python 코드를 인터프리트 하는 대신, 실행 중에 코드의 일부를 네이티브 기계어로 변환하는 JIT 컴파일러를 사용합니다.

 

JIT 컴파일러란, 

프로그램을 실제 실행하는 시점에 기계어로 번역하는 컴파일 기법이다.

 

기존의 컴파일 언어가 컴파일을 다 마치고 나서 실행을 했고, 인터프리터 언어는  컴파일 과정이 아예 없다. JIT 컴파일러는 실행하면서 컴파일 과정까지 동시에 한다고 생각하면 될 것이다.

 

JIT는 프로그램의 실행 패턴을 분석한 후, 성능이 중요한 부분을 기계어로 변환하여 실행 속도를 크게 향상시킨다는 장점이 있다.

그래서 실행 속도가 중요한 부분에서는 Pypy로 제출할 것을 백준에서 권장하고 있다.

 

 

 

그러나, 꼭 Pypy가 항상 성능이 우수한 것은 아니다.

백준 기준으로 Pypy에서 메모리 초과가 나는 일부 문제들이 Python3으로 제출 시 정상적으로 잘 제출되는 것을 볼 수 있다.

 

출처: Pypy 공식 문서

 

Pypy의 경우에는 재귀 깊이를 임의로 설정하는 것을 볼 수 있다.(sys.setrecursionlimit(n) sets the limit only approximately)

 

이것과 관련하여 영문 사이트에 잘 정리된 글이 있어서 링크를 공유한다.

 

https://stackoverflow.com/questions/45117672/pypy-large-memory-usage-compared-to-cpython

https://morepypy.blogspot.com/2013/10/incremental-garbage-collector-in-pypy.html

 

위 그래프의 빨간색 선이 CPython, 파란 선과 초록 선이 Pypy이다. 

 

---

참고 문서

https://www.sktenterprise.com/bizInsight/blogDetail/dev/2434

CPython, Jython, Cython.... 니들은 정체가 뭐니? | 개발자 Story | SKT Enterprise

https://www.ibm.com/docs/ko/sdk-java-technology/8?topic=reference-jit-compiler

JIT 컴파일러

 

https://ko.wikipedia.org/wiki/JIT_%EC%BB%B4%ED%8C%8C%EC%9D%BC