python 프로그램을 최적화하던 도중 알고리즘 시간복잡도 최적화를 마친 뒤 상수시간에 해당하는 코드를 최적화하여 프로그램 전체 실행시간을 단축(from1)시킬 필요가 있었다.
가장 많이 실행되고 가장 오래 걸리는 작업은 다각형(polygon)을 생성하고, 그 면적을 구하는 알고리즘이었다. 세상에는 다각형을 생성하는 방법은 정말 다양하고, 다각형의 면적을 계산하는 방법도 다양하다. 이 부분에서 많은 시간이 소요되는 것은 사실이지만 함부로 최적화에 뛰어들 수는 없었다. 라이브러리 사용의 타당성을 검토하고 더욱 로우레벨 언어로 포팅하는 것의 feasibility 를 검증하기 위해 따라서 이 부분을 다양하게 구현해보고 벤치마킹을 해보는 것이 우선이라는 생각이 들었다.
1.
첫째는 가장 간단하고 쉬운 방법으로, python 의 기하라이브러리 shapely 의 Polygon 클래스를 이용하는 방법이다.
def get_polygon(p1, p2, p3, p4):
polygon = shapely.geometry.Polygon([p1, p2, p3, p4])
return polygon
# get_polygon(*args).area 를 통해 간단하게 다면체의 면적을 구할 수 있음.
Python
복사
2.
둘째는 단순히 파이썬의 기본 컨테이너인 리스트에 값을 담고 다각형이라고 취급하는 방법이다. 이들의 경우에는 직접 면적을 구하는 로직을 구현해 주어야 한다. 구현은 ‘신발끈 공식’ 으로 알려진 논리로 통일하고, 이를 파이썬 네이티브 (a), 파이썬 네이티브 + numba (b), 넘파이 (c), 넘파이 + numba(from2) (d) 로 구현해 보았다.
a.
파이썬 네이티브
def get_polygon_area(polygon: list):
area = 0
for i in range(len(polygon)):
p1 = polygon[i]
p2 = polygon[(i + 1) % len(polygon)]
area += (p1[0] * p2[1] - p2[0] * p1[1])
return abs(area) / 2
Python
복사
b.
파이썬 네이티브 + numba
@numba.jit(nopython=True)
def get_polygon_area_numba(polygon: list):
area = 0
for i in range(len(polygon)):
p1 = polygon[i]
p2 = polygon[(i + 1) % len(polygon)]
area += (p1[0] * p2[1] - p2[0] * p1[1])
return abs(area) / 2
Python
복사
c.
넘파이
def get_polygon_area_np(polygon: np.ndarray):
a = polygon[:, 0] * np.roll(polygon[:, 1], 1)
b = np.roll(polygon[:, 0], 1) * polygon[:, 1]
area = np.sum(a - b)
return np.abs(area) / 2
Python
복사
d.
넘파이 + numba
@numba.jit(nopython=True)
def get_polygon_area_np_numba(polygon: np.ndarray):
a = polygon[:, 0] * np.roll(polygon[:, 1], 1)
b = np.roll(polygon[:, 0], 1) * polygon[:, 1]
area = np.sum(a - b)
return np.abs(area) / 2
Python
복사
이들을 벤치마킹하는 소스코드는 아래와 같다.
n_iter = 100000
print('fn : get_polygon_area()')
it = iter(polygon_generator())
numpy_it = iter(polygon_generator('numpy'))
s = time.time()
for _ in range(n_iter):
get_polygon(*next(it)).area
e = time.time()
print(f'plain data\tshapely fn\t: {e - s:5f}')
s = time.time()
for _ in range(n_iter):
get_polygon_area(next(it))
e = time.time()
print(f'plain data\tplain fn\t: {e - s:5f}')
s = time.time()
for _ in range(n_iter):
get_polygon_area_numba(next(it))
e = time.time()
print(f'plain data\tplain fn (@)\t: {e - s:5f}')
s = time.time()
for _ in range(n_iter):
get_polygon_area_np(next(numpy_it))
e = time.time()
print(f'numpy data\tnumpy fn\t: {e - s:5f}')
s = time.time()
for _ in range(n_iter):
get_polygon_area_np_numba(next(numpy_it))
e = time.time()
print(f'numpy data\tnumpy fn (@)\t: {e - s:5f}')
Python
복사
결과는 아래와 같다. numpy (2.891172 sec) 는 대규모 배열 연산에 특화(참고1)된 라이브러리인만큼, 작은 연산에는 오히려 느릴 수 있다는 점을 고려하더라도 생각 이상으로 느렸다. 또 놀라웠던 점은 shapely (1.584651 sec) 의 성능이다. 언뜻 보기에 shapely 는 ‘최적화된 라이브러리’ 라는 인상을 풍긴다(참고2). 연산이 아무리 최적화가 잘 되어 있는데 도대체 왜 느릴까? 내 생각에는 별다른 최적화 없이 간단한 리스트만 가지고 로직을 구현한 경우 (0.727211 sec) 보다 2배 이상 느린 것으로 보아 shapely polygon 을 python 객체로 여러 번 생성하면서 생기는 오버헤드일 것이라는 생각이 들었다. shapely 객체를 이용한 연산이 아무리 날렵하더라도 이 다각형을 생성하는 데 오래 걸린다면 연산의 날렵함이 다 무슨 소용이겠는가 싶었다.
fn : get_polygon_area()
plain data shapely fn : 1.584651
plain data plain fn : 0.727211
plain data plain fn (@) : 0.499808
numpy data numpy fn : 2.891172
numpy data numpy fn (@) : 0.744016
Python
복사
거대한 객체에 대한 C-python 오버헤드가 여기에서 중요하지는 않다. 왜냐하면 우리는 단순히 파이썬 객체를 자주 만들어대는 일 자체가 무거워서 이런 일이 일어난 것이다. 실제로 거대한 기하데이터의 C-python 오버헤드를 shapely 보다 크게 줄였다(참고3)고 주장하는 라이브러리 pygeos 도 작은 기하데이터를 여러 번 반복해서 생성하는 경우 성능이 급격히 떨어지는 것을 알 수 있다.
거대한 기하 데이터를 생성하는 경우, 실제로 pygeos 의 성능이 shapely 보다 더 나아짐을 알 수 있다.
from shapely.geometry import Point, Polygon
s = time.time()
points = [Point(i, i) for i in range(10000)]
e = time.time()
print(f'create points\tshapely fn\t: {e - s:5f}')
import pygeos
s = time.time()
points = pygeos.points(range(10000), range(10000))
e = time.time()
print(f'create points\tpygeos fn\t: {e - s:5f}')
Python
복사
create points shapely fn : 0.059167
create points pygeos fn : 0.022165
Python
복사
오, 이정도라면 작은 기하 데이터를 여러 번 생성하는 경우에도 잘 될까? 라는 기대를 가져 봤지만 아니었다.
from shapely.geometry import Polygon
s = time.time()
for _ in range(100000):
poly = Polygon([(10, 10), (10, 100), (100, 100), (100, 10)])
e = time.time()
print(f'create polygons\tshapely fn\t: {e - s:5f}')
import pygeos
s = time.time()
for _ in range(100000):
poly = pygeos.polygons([(10, 10), (10, 100), (100, 100), (100, 10)])
e = time.time()
print(f'create polygons\tpygeos fn\t: {e - s:5f}')
Python
복사
create polygons shapely fn : 0.723505
create polygons pygeos fn : 1.347409
Python
복사
나는 처음에 python 에서 제공하는 다양한 최적화 라이브러리들이 python 이 고질적으로 느리다는 문제를 해결할 수 있을 것이라고 보았다. 한편으로는 맞는 이야기이기도 하지만, 그렇지 않은 경우도 충분히 많을 수 있다. 즉, 내 생각보다 이런 라이브러리들이 일부 상황에서 python 성능 최적화에 하등 도움이 되지 않을 수 있다.
요약하면, 아무리 저수준에서 최적화된 라이브러리이더라도 python 의 객체를 생성하는 일 자체에서 오는 오버헤드가 훨씬 영향이 클지도 모른다. 따라서 최적화가 잘 된 라이브러리를 사용한다고 해서 나의 태스크에서 최상의 퍼포먼스를 내고 있을 것이라고 확신해서는 안 된다.
parse me : 언젠가 이 글에 쓰이면 좋을 것 같은 재료들.
1.
None
from : 과거의 어떤 생각이 이 생각을 만들었는가?
supplementary : 어떤 새로운 생각이 이 문서에 작성된 생각을 뒷받침하는가?
1.
None
opposite : 어떤 새로운 생각이 이 문서에 작성된 생각과 대조되는가?
1.
None
to : 이 문서에 작성된 생각이 어떤 생각으로 발전되고 이어지는가?
1.
None
참고 : 레퍼런스