고성능 파이썬(7) - 6장. 행렬과 벡터 연산

CHAPTER 6. 행렬과 벡터 연산

 

6.3 메모리 단편화

파이썬은 벡터 연산을 기본으로 제공하지 않는다. 리스트로 확산(diffusion) 등을 계산할 때 문제가 있다. 파이썬의 리스트는 실제로 데이터를 가리키는 포인터를 저장하며, 파이썬 바이트코드는 벡터 연산을 위해 최적화되지 않았다. 따라서 for 루프는 연산을 언제 벡터화해서 수행해야 이루올지 예측할 수 없다.

 

파이썬 리스트가 실제 데이터가 아닌 포인터를 저장한다는 얘기는 리스트가 실제 데이터 대신 각 데이터가 저장된 위치를 담는다는 의미다. 이렇게 하면 데이터 종류에 상관없이 저장할 수 있으므로 대부분의 상황에선 좋은 선택이다. 하지만 벡터나 행렬 연산에서 이는 커다란 성능 하락의 원인이 된다.

 

성능이 하락하는 이유는 grid 행렬에서 항목 하나를 가져올 때마다 탐색을 여러 번 해야 하기 때문이다. 예를 들어 grid[5][2]를 실행하면 먼저 grid 리스트에서 5번째 항목을 찾아 반환한다. 이 값은 데이터가 저장된 위치를 가리키는 포인터다. 그리고 이렇게 반환된 객체에서 2번째 리스트 항목을 찾기 위한 탐색을 다시 수행한다. 이 과정까지 거쳐야 실제 데이터가 저장된 위치를 알 수 있다.

 

이런 탐색으로 인한 부하는 크지 않고 대부분의 경우 무시할 수 있다. 하지만 데이터가 하나의 연속된 메모리 블록에 저장되어 있다면 각 항목마다 명령을 두 번씩 수행할 필요 없이 한 번에 전체 데이터를 불러올 수 있다. 이는 데이터 단편화 문제에 있어서 중요한 부분이다.

 

메모리와 CPU 사이의 데이터 전달이 더 많이 일어나고, 그때마다 필요한 데이터를 모두 가져올 때까지 CPU가 대기해야 한다.

perf 도구로 cache-misses를 살펴볼 때 이게 얼마나 심각한 문제인지 알아보도록 하자.

 

메모리의 내용이 CPU로 얼마나 잘 이동 중인지 파악하기는 쉽지 않다. 하지만 리눅스의 perf 명령을 이용하면 프로그램 실행 중에 CPU에서 일어난 일을 자세히 살펴볼 수 있다. 

 

$perf stat -e cycles, stalled-cycles-frontend, stalled-cycles-backend, instructions,\

 cache-references, cache-misess, branches, branch-misses, task-clock, faults, \

 minor-faults, cs, migrations -r 3 python diffusion_python_memory.py

 

6.3.1 perf 이해하기

perf가 측정한 각 항목이 어떤 의미인지, 그리고 코드와는 어떻게 연관되는지 알아보자. task-clock 항목은 소비한 총 클럭 수를 나타낸다. 이는 실제 전체 실행 시간과는 다른데, 만약 2개의 CPU를 사용해서 1초가 걸렸더라도, 밀리초로 표현하는 task-clock 값은 1,000이 될 것이다. 그리고 얼마나 많은 CPU가 활용되었는지 계산해서 항목 옆에 표시해준다. 이 값은 프로세스가 다른 하위 시스템에 의존하는 기간(예컨대 메모리 할당 같은)을 포함하므로 정확히 1이 되지 않는다.

 

context-switches와 CPU-migrations 항목은 I/O같은 커널 작업이 끝나기를 기다리거나, 다른 애플리케이션이 실행되는 동안 대기하거나, 또는 다른 CPU 코어로 작업을 옮기기 위해 프로그램이 얼마나 오래 멈춰 있었는지를 알려준다.

CPU-migrations는 context-swithes 항목과 비슷한데, CPU를 골고루 활용하도록 기존에 실행 중이던 CPU에서 실행을 멈췄다가 다른 CPU에서 실행이 재개된 횟수를 나타낸다. 이는 프로그램이 잠시 멈출 뿐만 아니라 L1 캐시에 있던 내용까지 모두 버려야 하므로(L1 캐시는 각 CPU마다 따로 존재한다) 좋지 않은 문맥 전환이라고 볼 수 있다.

 

page-fault 항목은 유닉스 메모리 할당 구조의 한 부분이다. 메모리를 처음 할당하면 커널은 메모리에 대한 참조를 프로그램에게 돌려주는 것 외에는 그다지 많은 일을 하지 않는다. 하지만 나중에 프로그램이 그 메모리를 처음 실행하면, 운영 체제는 가벼운 페이지 폴트 인터럽트를 발생시켜 실행 중인 프로그램을 잠시 멈추고 실제 필요한 메모리를 할당한다. 이런 방식을 지연 할당(lazy allocation) 시스템이라고 한다. 

 

메모리에 있는 데이터를 참조하면 1.1.3절 "통신 계층"에서 설명한 대로 다양한 경로를 거쳐 데이터가 이동한다. 캐시에 있는 데이터를 참조하면 cache-references 항목이 증가한다. 이 데이터가 캐시에 존재하지 않아 RAM에서 읽어와야 할 때는 cache-miss 항목이 증가한다. 최근에 읽은 데이터(cache에 남아있는 데이터)거나 그와 인접한 데이터(RAM에서 캐시로 데이터를 복사할 때 인접한 데이터를 미리 복사한다)라면 캐시 미스가 발생하지 않을 것이다.

 

instructions 항목은 CPU에서 수행한 명령의 개수를 나타낸다. 파이프라이닝 덕분에 한 번에 여러 명령을 수행할 수 있는데 insns per cycle에서 확인할 수 있다. 이런 파이프라이닝을 좀 더 잘 다룰 수 있도록 stalled-cycles-frontend와 stalled-cycles-backend 항목에서 파이프라인 앞단(front-end)과 뒷단(back-end)이 채워질 때까지 얼마나 많은 사이클을 대기했는지 보여준다.

 

... 중략

 

* 여기서 소개한 항목과 관련된 CPU 내부 동작에 대해서 자세한 설명이 필요하다면, 컴퓨터 아키텍처 튜토리얼(http://bit.ly/ca_tutorial)을 읽어보자.

 

6.4.1 메모리 할당과 제자리 연산

메모리와 관련된 여향을 최적화할 목적으로 메모리 할당 횟수를 줄이기 위한 방법을 사용하자. 메모리 할당은 앞서 살펴본 캐시 미스보다 더 나쁘다. 메모리 할당은 캐시에서 필요한 데이터를 찾지 못하면 단순히 RAM을 찾아보는 대신, 필요한 크기만큼의 데이터를 운영 체제에 요청한 다음 예약해둔다. 캐시를 채우는 과정은 메인보드 수준에서 하드웨어적으로 최적화된 과정인 반면, 메모리 할당은 요청을 완료하기 위해서 다른 프로세스, 즉 커널과 통신을 해야 한다.

메모리 할당을 줄이기 위해 코드 시작 부분에 테스트용 배열을 미리 할당한 다음에 제자리 연산(in-place operation)만을 사용해 본다. 제자리 연산은 +=, *= 처럼 입력 중 하나를 결과값을 저장하는 용도로 사용하는 연산을 말한다.

id는 참조하고 있는 메모리 구역을 나타내므로 이 numpy 배열을 추적하기 위한 목적으로 안성맞춤이다. 만일 두 numpy 배열의 id가 같다면 둘은 같은 메모리 구역을 참조하고 있다는 뜻이다.

>>> import numpy as np
>>> array1 = np.random.random((10, 10))
>>> array2 = np.random.random((10, 10))
>>> id(array1)
>>> array1 += array2
>>> id(array1)
>>> array1 = array1 + array2)
>>> id(array1)

 

6.4.2 선택적 최적화: 고칠 부분 찾기

# 직접 작성한 roll_add 함수
import numpy as np

def roll_add(rollee, shift, axis, out):
  """ 행렬 rollee에 대하여 다음 계산을 수행하여 결과를 out에 저장한다.
  >>> out += np.roll(rollee, shift, axis=axis)
  이 함수는 다음 가정하에 동작한다.
  * rollee는 2차원 배열이다.
  * shift는 +1 아니면 -1이다.
  * axis는 0 아니면 1이다(rolle가 2차원 배열이므로 이를 유추할 수 있었다).
  위와 같은 가정하에, numpy에서 범용적인 목적으로 구현한 roll 함수에서 불필요한 부분을 회피하고 계산 과정을 함수 내부로 옮겨서 속도를 향상시켰다."""
  if shift == 1 and axis == 0:
    out[1:, :] += rollee[:-1, :]
    out[0, :] += rollee[-1, :]
  elif shift == -11 and axis == 0:
    out[:-1, :] += rollee[1:, :]
    out[-1, :] += rollee[0, :]
  elif shift == 1 and axis == 1:
    out[:, 1:] += rollee[:, :-1]
    out[:, 0] += rollee[:, -1]
  elif shift == -11 and axis == 1:
    out[:, :-1] += rollee[:, 1:]
    out[:, -1] += rollee[:, 0]

def test_roll_add():
  rollee = np.asarray([[1,2],[3,4]])
  for shift in (-1, +1):
    for axis in (0, 1):
      out = np.asarray([[6,3],[9,2]])
      expected_result = np.roll(rollee, shift, axis=axis) + out
      roll_add(rollee, shift, axis, out)
      assert np.all(expected_result == out)

def laplacian(grid, out):
  np.copyto(out, grid)
  out *= -4
  roll_add(grid, +1, 0, out)
  roll_add(grid, -1, 0, out)
  roll_add(grid, +1, 1, out)
  roll_add(grid, -1, 1, out)

perf에서 확인할 수 있는 instructions 수가 2.86배 줄어서 70% 빨라졌다.

 

6.5 numexpr: 제자리 연산을 더 빠르고 간편하게 쓰기

from numexpr import evaluate

def evolve(grid, dt, next_grid, D=1):
  laplacian(grid, next_grid)
  evaluate("next_grid*D*dt+grid", out=next_grid)

numexpr을 사용하여 우리가 작성한 프로그램에 캐시를 잘 활용하기 위한 연산이 추가되었다.