[High Performance] Profiling & Numpy for Matrix and Vector Computation

올해 초에 딥러닝 분석을 돌리는데 필요한 많은 연산에서 어느 부분에 병목이 발생하는지 프로파일링 해보고, 해결하는 과정을 진행했다. 

 

시간 복잡도가 O(|V|^3)인  floyd_warshall  알고리즘을 사용하고 있었기 때문에 여기서 시간이 오래 걸리는게 아닐까 예상하였지만 프로파일링 결과를 보니 행렬과 벡터 연산을 순수 파이썬 리스트로 구현한 곳에서 속도가 늦어지고 있다는 것을 알게 되었다. 

그래서 이를 numpy를 사용한 행렬과 벡터 연산으로 수정하였고, 그 결과 시간을 약 86% ~ 97% 정도로 줄일 수 있었다. 

 

<고성능 파이썬 - 미샤 코렐릭, 이안 오스발트 지음, 한빛미디어> 책을 참고 하였으며, 이 과정에서 배운 '프로파일링으로 병목 지점 찾기'와 '행렬과 벡터 산술 계산에서 numpy가 순수 파이썬보다 빠른 이유'를 중점으로 정리하고자 한다. 

---

1. 프로파일링으로 병목 지점 찾기

1) 프로파일링이란

위키에서 프로파일링에 대해 소개한 글을 보자. 

프로파일링(profiling, 프로그램 프로파일링/소프트웨어 프로파일링) 또는 성능 분석은 프로그램의 시간 복잡도 및 공간(메모리), 특정 명령어 이용, 함수 호출의 주기와 빈도 등을 측정하는 동적 프로그램 분석의 한 형태이다. 프로파일링 정보는 대개가 프로그램 최적화를 보조하기 위해 사용된다. 프로파일링은 프로파일러(profiler)라는 도구를 사용하여 프로그램 소스 코드나 이진 실행 파일을 계측 분석함으로써 수행한다.

프로파일링을 통해 애플리케이션의 코드를 살펴보고 각 기능/ 코드라인에 걸리는 시간을 비롯하여 CPU시간, 메모리 사용량, 네트워크 대역폭, 디스트 I/O.. 여러가지 등을 측정 및 분석할 수 있고, 특히 이를 통해 해당 코드에서 병목 현상을 찾을 수 있다. 

 

그래서 프로그램이 너무 느리거나 RAM을 많이 잡아먹는 등 성능 이슈가 있을 때 감에 의존해서 원인이라고 의심되는 코드를 수정하는 것이 아닌, 프로파일링을 진행하여 해결해야 할 병목지점을 빠르게 찾아내고 그 부분을 효과적으로 수정할 수 있다. 

 

그리고 프로파일링을 하기 전에  앞서 'floyd_warshall  알고리즘을 사용하고 있었기 때문에 여기서 시간이 오래 걸리는게 아닐까' 예상하였던 것 처럼 하려는 코드의 기대 속도에 대한 가설을 세우는 습관을 들이는게 좋다. 

 

2) cProfile - 어떤 함수가 가장 오래 걸리는지 알아 볼 수 있는 내장도구

cProfile은 표준 라이브러리에 내장된 프로파일링 도구로, CPython의 가상 머신 안에서 확인되는 모든 함수에, 시간 측정을 위한 장치를 연결한다. 

cProfile 모듈을 사용하면,

1. 전체 코드가 실행된 total run time을 알 수 있다. 
2. 또한 각각의 step이 실행된 시간도 알 수 있다. 그래서 어느 부분이 최적화가 필요한지 파악 할 수 있다.
3. 특정 함수가 called된 회수를 알 수 있다. 
4. pstats module을 통해 측정 데이터를 쉽게 export할 수 있다. 
5. snakeviz module을 통해 측정 데이터를 쉽게 시각화 할 수 있다. 

2-1. cProfile 모듈을 사용해서 프로파일링 실행 )

# import module
import cProfile

cProfile.run(statement, filename=None, sort=-1)

• statement: 프로파일링하려는 코드 또는 함수명
• filename: 측정 데이터 결과를 저장할 파일명
• sort: 측정 데이터를 보이는 기준 지정

또는 명령어로 실행

python -m cProfile [-o output_file] [-s sort_order] (-m module | myscript.py)

2-2. cProfile 프로파일링 결과 보기 )

import numpy as np
cProfile.run("20+10")

3 function calls in 0.000 seconds # 함수 호출 횟수와 실행에 걸린 시간

   Ordered by: standard  # sort 기준

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

• ncalls: 호출 수.
• tottime: 주어진 함수에서 소비된 총 시간 (서브 함수 호출에 든 시간은 제외)
• percall: tottime을 ncalls로 나눈 몫
• cumtime: 이 함수와 모든 서브 함수에서 소요된 누적 시간 (호출에서 종료까지)
• percall: cumtime을 프리미티브 호출로 나눈 몫
• filename:lineno(function): 각 함수의 해당 데이터– 파일명:줄 번호(함수)

cProfile로 프로파일링을 하는 핵심은 이것이고 이 외에도 cProfile data export와 visualize 등 많은 기능들이 있고, 해당 글을 참고 하면 좋을 것 같다. 

 

3) line_profiler - 선택한 함수를 한 줄씩 프로파일링 할 수 있는 도구

내가 프로파일링 해야하는 애플이케이션의 경우에는 함수로 나뉘어져있는 로직들이  main에서 순차적으로 실행되도록 짜여져있었다. 

그래서 한 눈에 어느 로직(함수)에서 시간을 오래 잡아먹는지를 파악하기엔 cProfile보단 line_profiler가 좀 더 편리했다. 

또한 line_profiler는 프로파일링에 따른 코드를 수정해가면서 line_profiler 결과마다 버전을 기록해두면 성공/실패의 비교가 쉬워질 수 있다.

 

3-1. line_profiler 설치)

pip install line_profiler

3-2. 어느 함수에 line_profiler를 적용 할 것인지)

@profile 데코레이터를 선택한 함수에 적어준다. 

@profile
def main():
	...
    ...

3-3. line_profiler 프로파일링 실행 )

kernprof.py -l -v main.py

kernprof.py 스크립트는 코드르 실행하고 선택한 함수를 표시하기 위해 사용한다. -l 옵션은 함수 단위가 아니라 한 줄ㅆ기 프로파일링 하겠다는 옵션이며, -v 옵션은 출력 결과를 다양하게 보여준다.

3-3. line_profiler 프로파일링 결과 보기 )

Timer unit: 1e-06 s

Total time: 20.6782 s
File: main.py
Function: main at line 28

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
    28                                           @profile
    29                                           def main():
    30         1          2.0      2.0      0.1      s = 0 
    31      1001        309.0      0.3     18.1      for i in range(0, n):
    32      1000        363.0      0.4     21.3          s+=i 
    33      1000       1028.0      1.0     60.4          s+=i**2
 ...
 ..
 ...

• Line number: The number of the line that was run
• Hits: The number of times that line was run
• Time: The execution time of the line in microseconds (Time)
• Per Hit: Time divided by hits
• % Time: Fraction of the total time spent executing that lineㅆ
• Line Contents: the source of the corresponding line

 

내가 실행 시간을 줄여야 할(최적화 해야 할) 코드의 line_profiler 결과는

• floyd_warshall  알고리즘을 사용하는 함수는
  • Time: 15034.0ms,  % Time: 0.1 인 반면
• 2중 for문을 돌면서 list의 데이터 값 탐색이 이루어지고, 값을 변경해야 하는 3가지 함수는 각각
  • Time: 8641157.0ms,  % Time: 41.8 
  • Time: 4628812.0ms, % Time: 22.4
  • Time: 5442133.0ms, % Time: 26.3

으로 행렬 연산을 순수 파이썬 loop 코드로 구현함으로써 오는 병목이 대부분을 차지하고있었다.

 

그래서 이 3가지 함수를 numpy로  다 변경하였고 다시 line_profiler를 해 보니

• Time: 363530.0ms, % Time: 12.8
• Time: 189133.0ms, % Time: 6.7
• Time: 3017.0ms, % Time: 0.1

으로 엄청나게 시간을 줄일 수 있었다. 

 

 

이렇게 해결을 하고 나니 '왜 numpy를 사용하면 획기적으로 빨라지는가'에 대해 궁금해졌다. 

---

2. 행렬과 벡터 연산에서 numpy가 순수 파이썬보다 빠른 이유

파이썬은 벡터 연산을 기본으로 제공하지 않기 때문에 벡터화해서 연산 가능한 식을 파이썬에서 사용할 때 순수 파이썬으로 작성한 코드는 비효율적인 문제가 있다. 

 

어떤 점 때문에 파이썬이 벡터 연산을 기본으로 제공하지 않는다고 하는 것일까?

1)  파이썬의 리스트는 데이터가 아닌 각 데이터가 저장된 위치(포인터)를 저장한다. 

각 데이터가 저장된 위치를 저장하는 방식은 데이터 종류에 상관없이 저장할 수 있다는 점 때문에 장점도 있지만, 벡터나 행렬 연산 측면에서 서는 성능상 좋지 않다. 

nodes = len(graph)
for i in range(nodes):
	for j in range(nodes):
		if( graph[i][j] == 0 or graph[j][i] == 0 ):
			graph[i][j] =0
			graph[j][i] =0

이런 코드가 있다하자. 이 경우 graph 행렬에서 항목 하나를 가져올 때마다 탐색을 여러 번 해야한다. 

예를 들어 graph[5][2]를 실행하면 grid 리스트에서 5번째 항목의 데이터가 저장된 위치를 가리키는 포인터를 찾아서 반환한다. 

그리고 이렇게 반호나된 객체에서 2번째 리스트 항목을 찾기 위한 탐색을 다시 수행한다. 

이 과정까지 거쳐야 실제 graph[5][2] 데이터가 저장된 위치를 알 수 있다. 

 

만약 graph에 있는 데이터가 모두 단편화되어 있다면 전체 블록을 한꺼번에 읽어올 수 없고 나뉜 데이터 조각을 한 번에 하나씩 읽어야 한다. 그러면 메모리와 CPU 사이의 데이터 전달이 많이 발생하고 그만큼 CPU 대기 시간도 길어진다. 

 

정리하면 

리스트는 실제 데이터가 아니라 데이터를 가리키는 포인터를 저장하므로 행렬의 실제 데이터가 연속적이 아니라 메모리 여기저기에 흩어 있다면

데이터 단편화로 인해 메모리에서 CPU로의 데이터 전송 횟수가 많아지고

계산에 필요한 데이터를 CPU 캐시에 다 담을 수 없어서 계산을 벡터화(CPU가 여러 계산을 한 번에 수행) 할 수 없다. 

※ 리눅스의 perl 명령어를 사용하면 프로그램 실행 중에 CPU에서 일어난 일을 자세히 살펴 볼 수 있다.

2) 파이썬 바이트코드는 벡터 연산을 위해 최적화되지 않았다. 

그럼 리스트 대신 데이터를 메모리에 순차적으로 저장하는 array를 사용하면 어떨까? array의 slice는 연속된 메모리 공간에 존재하지만 여전히 행렬과 벡터 연산을 순수 파이썬으로 수행하는데는 적합하지 않다. 

왜냐하면 여전히 파이썬은 loop를 벡터화 하는 방법을 모르기 때문이다. 

배열에서 한 번에 하나의 항목에 대해서만 산술 연산을 하는 loop를 한 번에 여러 데이터를 처리하도록 하는게 좋겠지만 파이썬은 이런 종류의 바이트 코드 최적화를 지원하지 않는다. 

3) numpy

파이썬에서의 행렬과 벡터 연산처리에 대해서 정리해보았다. 

이를 통해 알 수 있는 건 

효율적인 벡터 연산을 위해 필요한 것은 1. 데이터를 연속된 메모리 공간에 저장할 수 있어야 하며, 2. 벡터 연산을 지원해야한다. 는 것이고,  이 모든 것을 제공해 주는 패키지가 numpy이다. 

 

1. numpy배열은 array 객체와 마찬가지로 저수준의 형태로 연속된 메모리 공간에 수를 저장한다. 그래서 numpy배열에 대해 수행하는 산술연산은 개별 항목을 하나씩 순회하며 처리 할 필요가 없다. 

2. 그리고 numpy는 최적화된 C코드를 통해 CPU가 지원하는 벡터화 기능의 장점을 활용한다. 그래서 직접 python코드로 명시적인 계산을 수행하는 것보다 numpy 내부 구현에 맡겨서 파이썬 자체를 구현하는데 사용된 C코드의 속도를 얻을 수 있다. 

 

 

 

지금까지 딥러닝 분석을 돌리는데 필요한 많은 행렬 곱 연산에서 어느 부분에 병목이 발생하는지 프로파일링 해보고, 해결해 본 과정을 정리해 보았다. 

 

참고한  고성능 파이썬 - 미샤 코렐릭, 이안 오스발트 지음, 한빛미디어에 좋은 내용이 많아서 다음에는 동시성과 multiprocessing에 대해서도 정리하면 좋을 것 같다.  

 

 

 

 

 

Reference
고성능 파이썬 - 미샤 코렐릭, 이안 오스발트 지음, 한빛미디어

cProfile – How to profile your python code

프로파일링 (컴퓨터 프로그래밍)

https://qxf2.com/blog/saving-cprofile-stats-to-a-csv-file/

saving cProfile results to readable external file

How can I time-profile unittests in Python?

[python] 파이썬 line_profiler

scipy.sparse.csgraph.floyd_warshall