Vectorization

Numpy 연산이 매우 빠른 이유는 무엇일까요? 다음과 같이 50만개의 배열에 대해 numpy array 연산으로 1을 더하는 것과 모든 element를 for 문으로 순회하면서 1을 더하는 것은 시간 상의 명백한 차이가 있습니다. Numpy 연산이 수십 배나 빠르죠. 

import numpy as np
from timeit import Timer
li = list(range(500000))
nump_arr = np.array(li)

def python_for():
    return [num + 1 for num in li]
    
def numpy_add():
    return nump_arr + 1
    
>>> print(min(Timer(python_for).repeat(10, 10)))
>>> print(min(Timer(numpy_add).repeat(10, 10)))
0.40353689999999975
0.010338700000000145

이는 numpy는 각 element에 대해 for 문을 수행하는 것이 아니라 전체 array에 대한 vectorization 연산을 수행하기 때문입니다. Vectorization 이란 명시적인 for 문 없이 array expression으로 연산을 수행하는 것을 말합니다. 따라서 numpy는 명시적인 파이썬의 for 루프 대신 빠르고 최적화된 C 레벨의 vectorization 연산을 수행하기에 매우 빠른 거죠. 

Using NumPy arrays enables you to express many kinds of data processing tasks as concise array expressions that might otherwise require writing loops. This practice of replacing explicit loops with array expressions is commonly referred to as vectorization. In general, vectorized array operations will often be one or two (or more) orders of magnitude faster than their pure Python equivalents, with the biggest impact in any kind of numerical computations.

---

그렇다면 vectorization은 정확히 무엇일까요? Vectorization은 하드웨어 상의 SIMD (Single Instruction Multiple Data) 동작과 관련이 있습니다. 최신 64비트 프로세서들은 정수에 대해 수치 연산을 수행하는 64 비트 register 16개를 포함하고 있습니다. 이러한 register들은 RAX, RBX, .. 등으로 불리는데 이 register들은 한 번에 하나의 값만 가질 수 있기 때문에 scalar register라고도 불리웁니다. 따라서 다음 코드와 같이 1000 쌍의 정수를 더하는 연산을 수행하려면 RAX, RBX register를 이용해 1000번의 연산을 수행해야 하는 거죠.

  1: 1    const int N = 1000;
  2: 2    float a[N], b[N];
  3: 3    // Initialize a[i] = i; b[i] = 100 + i
  4: 4    int main() {
  5: 5        for (int n = 0; n < N; ++n) a[n] += b[n];
  6: 6    }

하지만 이러한 칩들은 256 bit register 16개를 추가적으로 포함하도록 발전합니다. Register 용량이 커졌으니 64 비트 값 4개, 32 비트 값 8개 등을 동시에 저장할 수 있으니 vector register라 불리고 XMM0, XMM1, ... 식의 이름을 가지고 있습니다. 따라서 register에 올라가 있는 여러 값들을 한 번에 수치 연산할 수 있는 instruction이 가능해지게 됩니다. 즉, single instruction에 multiple data를 처리할 수 있게 된 것이죠. 위의 예에 비쳐봤을 때 a[n] += b[n] 연산이 한 스텝에 b[4]부터 b[7]까지 병렬적으로 이루어지게 되니 RAX, RBX register를 이용했을 때보다 이론적으로는 속도가 4배 증가하겠죠.

결과적으로 vectorization은 scalar register 대신 vector register를 이용하여 수치 연산을 더 빠르게 하는 과정을 의미합니다. Vectorization을 구현하기 위해서는 assembly language를 직접 작성하거나 built-in (intrinsic) 함수들을 이용해야 합니다. (요새는 compiler가 똑똑해져서 자동으로 vectorize 해준다고 하네요.) 파이썬 코드를 speed up하기 위해서는 이러한 low-level의 vectorization 연산을 지원해야하며, scipy나 numpy 등이 vectorization을 활용하는 대표적인 라이브러리 입니다. 그래서 직접 연산을 구현하는 것보다는 numpy의 built-in 함수를 쓰는 것이 vectorization 관련해서 최적화가 되어 있으니 훨씬 빠르겠죠.

 

참조

• https://stackoverflow.com/questions/47755442/what-is-vectorization
• https://stackoverflow.com/questions/35091979/why-is-vectorization-faster-in-general-than-loops
• https://docs.microsoft.com/ko-kr/archive/blogs/nativeconcurrency/what-is-vectorization
• https://stackoverflow.com/questions/16899332/why-does-trivial-loop-in-python-run-so-much-slower-than-the-same-in-c-and-how