행렬과 벡터 연산 (3) - 파이썬 리스트와 numpy 연산 속도 차이

 

행렬과 벡터 연산 (1) - 확산 방정식 예제

행렬과 벡터 연산 (2) - 확산 방정식 순수 파이썬 구현

---

지난 포스트에서 확산 방정식을 파이썬 리스트로만 구현했습니다. 매 timestep 마다 확산을 모델링하기 위해서 grid 변수를 리스트의 리스트 형태로 구현했습니다. 하지만 파이썬의 리스트는 실제 데이터가 아닌 데이터가 저장된 위치를 가리키는 포인터를 저장합니다. 데이터 타입에 상관없이 리스트에 어떤 형태의 데이터도 저장할 수 있으나 이는 벡터, 행렬 연산에서 큰 성능 저하의 원인이 됩니다. 또한, 파이썬 바이트 코드는 벡터 연산에 최적화되지 않았기에 파이썬은 벡터 연산을 기본으로 제공하지 않습니다.

Vectorization

따라서 리스트의 리스트 형태로 구현된 grid 변수에서 값을 가져오기 위해서는 리스트에서 항목을 찾아 저장된 위치를 반환하고 여기서 선택된 리스트에서 항목을 찾아 저장하는 위치를 가져오게 됩니다. 만약 grid 리스트에 저장된 데이터가 연속된 메모리 블록 하나에 저장됐다면 전체 데이터를 한 번에 불러올 수 있겠죠. 하지만 리스트 안의 값들이 메모리 여러 군데에 단편화되어있다면 전체 블록을 한 번에 읽는 대신에 데이터 조각을 하나씩 읽어야 합니다. 따라서 메모리 I/O 오버헤드가 더 많이 발생하게 됩니다.

CPU가 데이터를 필요하면 메모리부터 읽어야 합니다. 다만, 메모리와 CPU 사이의 대역폭이 무한하지 않고 제한되어 있으므로 폰 노이만 병목이 발생하게 됩니다. 따라서 이를 해결하기 위해 메모리에서 데이터를 미리 읽어와 용량은 작지만 더 빠른 CPU 캐시에 데이터를 미리 보관하고 나중에 어떤 데이터가 필요할지를 미리 알기 위해 현재 명령을 실행하는 동안 다음에 실행할 명령을 미리 가져와 캐시에 적재해주는 분기 예측 및 파이프라이닝 기법 도입의 배경이 되었죠. 하지만 이런 기법을 넘어서서 병목을 최소화하는 최고의 방법은 처음부터 효율적으로 메모리를 할당하고 계산을 수행하는 것이죠.

그럼 효율적으로 메모리를 할당할 수 있는 방법은 무엇일까요? CPU가 메모리의 데이터를 참조하면 CPU L1/L2/L3 캐시와 같은 다양한 계층을 거쳐 데이터가 이동하게 됩니다. 캐시에 데이터가 미리 적재되지 않았따면 메모리에서 일거와야할 것이고 필요한 데이터가 최근에 읽었던 데이터거나 최근에 읽은 데이터와 인접한 데이터 (메모리에서 캐시로 데이터를 복사할 때 인접한 데이터를 미리 복하합니다) 라면 캐시 미스가 발생하지 않는다. 이러한 캐시 미스는 메모리에서 데이터를 읽어오기까지 기다려야 할 뿐 아니라 실행 파이프라이느이 흐름을 방해하여 CPU를 집중적으로 사용하는 작업에서 성능을 떨어뜨리는 원인이 됩니다. 따라서 배열의 데이터를 메모리에 잘 모아두지 않으면, 매번 캐시에 없는 데이터를 요청할 가능성이 커져 성능 병목이 생길 가능성이 높겠죠. 

계산을 벡터화하기 위해서는 (CPU가 여러 계산을 한꺼번에 실행할 수 있게 하려면) 필요한 데이터를 모두 캐시에 담아두어야 하고 이를 위해서는 메모리에 연속적으로 데이터가 저장되어야 합니다. 하지만 리스트는 실제 데이터가 아니라 데이터를 가리키는 포인터를 저장하므로 격자의 실제 데이터는 메모리 여기저기에 흩어져 있게 됩니다. 리스트 대신 array 모듈을 사용하면 array 객체가 데이터를 메모리에 순차적으로 저장하므로 array 조각은 연속된 메모리에 존재합니다. 하지만 파이썬 자체에서 벡터 연산을 지원하지 않아 문제를 완전히 해결할 수는 없습니다. 또한, array 객체는 아주 저수준의 형태로 수를 저장하므로 사용자에게 반환하기 전에 파이썬에서 호환되는 형태로 변환되어야 하기에 리스트 순회보다 더 느립니다. 

Numpy

Numpy는 데이터를 연속된 메모리 공간에 저장하면서 이에 대한 벡터 연산도 지원합니다. 따라서 numpy 배열에 대해서 수행하는 산술 연산은 개별 항목을 하나씩 순회하며 처리할 필요가 없습니다.

Example

from array import array
import numpy

vector = list(range(1000000))
def norm_square_list(vector):
    norm = 0
    for v in vector:
        norm += v * v
    return norm
    
>>> %timeit norm_square_list(vector)
98.9 ms ± 2.44 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

def norm_square_list_comprehension(vector):
    return sum([v*v for v in vector])

>>> %timeit norm_square_list_comprehension(vector)
93.1 ms ± 4.24 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

def norm_square_array(vector):
    norm = 0
    for v in vector:
        norm += v*v
    return norm

>>> %timeit norm_square_array(vector)
99.5 ms ± 2.55 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

vector = numpy.arange(1000000)
def norm_square_numpy(vector):
    return numpy.sum(vector*vector)
    
>>> %timeit norm_square_numpy(vector)
1.99 ms ± 268 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

def norm_square_numpy_dot(vector):
    return numpy.dot(vector, vector)

>>> %timeit norm_square_numpy(vector)
1.59 ms ± 17.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

리스트를 순회하며 계산한 norm_square_list 함수는 98.9ms 걸리고 이를 리스트 컴프리헨션화 하면 93.1ms 가 걸립니다. 하지만 단순히 numpy 변환한 norm_square_numpy 함수는 1.99ms 가 걸립니다. 이는 파이썬 코드로 명시적인 계산을 수행하는 것보다 파이썬 내부 구현이 더 낫다는 사실을 알 수 있고 이를 수 배열을 다루는 특수한 목적으로 최적화된 numpy를 사용하면 처리 속도를 훨씬 개선할 수 있다는 것을 알려줍니다. Numpy 배열은 메모리 공간 상에서 지역적으로 존재하고 벡터 연산을 지원하므로 CPU 상의 명령 횟수나 캐시 미스를 크게 줄일 수 있습니다.

norm_square_numpy 함수에서 vector*vector 가 실행 될 때 numpy에서 관장하는 암시적인 루프가 포함되어 있습니다. 이 루프에는 매 항목에 대한 제곱과 덧셈을 수행하는 두 번의 루프가 내재되어 있는데, 이를 명시적으로 처리하는 것이 아닌 numpy에 넘김으로써 벡터화 연산의 장점을 얻을 수 있습니다. 또한, norm_square_numpy_dot 함수 경우에는 두 벡터를 곱한 다음 더할 필요 없이 numpy.dot 함수로 쉽게 벡터의 내적을 구할 수 있는데, 이는 vector*vector 를 수행하는 과정에서 생성된 임시값을 저장할 필요가 없기 때문입니다. 내부 구현이나 numpy 구현체가 있는지부터 찾는지가 최적화의 정도임을 알 수 있습니다. 

 

---

행렬과 벡터 연산 (4) - numpy 배열을 이용한 확산 방정식

행렬과 벡터 연산 (5) - numpy 배열 메모리 최적화

행렬과 벡터 연산 (6) - numexpr 모듈 이용하기