close
프로필 배경
프로필 로고

SCRIPTS BY

C++ · 2023. 2. 23. fullscreen 넓게보기

잘못 쓰면 백 배 느린 for 문-이중 for 문 제대로 쓰는 법, 캐시 친화적 반복문

개요

프로그래밍을 하다보면, 혹은 백준 문제를 풀다 보면 자주 이중 for문, 혹은 그 이상의 중첩된 반복문을 사용해야 할 때가 있는데, 이때 이중 for 문을 잘 못 쓰면 코드가 100배 가까이 느려질 수도 있다. 이건 비단 C++만의 문제는 아니고 모든 프로그래밍에 적용되는 이야기이다.

백 배 이상 느린 중첩 반복문


// 1번 방법
for (std::size_t i = 0; i < N; ++i) {
    for (std::size_t j = 0; j < M; ++j) {
        arr[i][j] *= 2;
    }
}

// 2번 방법
for (std::size_t i = 0; i < M; ++i) {
    for (std::size_t j = 0; j < N; ++j) {
        arr[j][i] *= 2;
    }
}

위에 코드를 보면 똑같은 역할을 하는 두 개의 이중 for문이 있는데, 둘 중 어느 것이 맞는 방법인지 생각해보자. 1번? 2번? 혹은 둘 다? 결론부터 말하자면 옳은 방법은 1번이고, 로직이 똑같다는 가정 하에 1번 방법이 2번 방법보다 거의 대부분의 상황에서 (사실상 무조건) 빠르다.

 

결론을 미리 내자면 반복문은 arr[i][j][k]가 있을 때 오른쪽에서 왼쪽 방향, 즉 k -> j -> i 순서로 도는 게(루프문의 안쪽에 위치하는 게) 빠르고, 최대한 그렇게 돌게끔 설계해야 한다.

이유

결론만 알아도 되지만, 왜 이게 느린 지에 대해서 이유를 알기 위해서는 약간의 컴퓨터 구조에 대한 지식이 필요하다. 또한 사전지식으로는 기본적으로 벡터가 메모리 상의 어떻게 할당이 되는 지에 대해서 알고 있다고 가정한다.

컴퓨터의 구조와 캐시 메모리의 한계

컴퓨터의 기초적인 구성 요소를 설명하는 부분이니, 이 부분에 대해서 알고 있다면 그냥 넘어가도 괜찮다.

컴퓨터의 구조

컴퓨터의 구조를 이야기할 때 중앙처리장치(CPU), 주기억장치(RAM), 보조기억장치(SSD 혹은 HDD)로 이루어진다고 말을 한다. CPU, RAM, 보조기억장치로 구성되는 이 구조는 모든 컴퓨터가 공통적으로 갖고 있는 기본적인 구조이다. 이 구조를 설계한 사람의 이름을 따서 폰 노이만 구조(중앙처리장치, 기억장치, 프로그램)라고 부른다.

  • CPU는 연산기계이다. 주어진 입력과 데이터에 따라 명령을 수행하고 수학적 연산을 처리한다. 그 외에도 메모리를 할당하고 해석하는 일 역시 CPU의 역할이다. 참고로 전자는 ALU(Arithmetic Logical Unit), 후자는 CU(Control Unit)이라 하는데 여기서 중요한 건 아니다.
  • RAM은 주기억장치이다. CPU가 연산하기 위해서 필요한 데이터를 저장한다.
  • 보조기억장치는 데이터를 영구적으로 저장할 때 쓴다.

왜 굳이 주기억장치와 보조기억장치를 분리했냐면, 이는 경제적 관점에서의 문제점때문이다. 속도때문인데, 주기억장치가 훨씬 빠르다. 보조기억장치의 속도에 비할 바가 못 된다.


HDD야 속도가 200-400MB/s로 비교할 바가 안 되고, 보통 SSD의 쓰기 속도가 3.5GB/s라 하자. 사실 SATA 시절에만 해도 SSD의 읽기 속도는 500MB/s 정도였다. 그런데 3.5GB/s가 매우 빨라보이지만, 이를 램의 클럭으로 계산해보면 약 218MHz 정도 된다. 참고로 그냥 시중에서 구할 수 있는 DRAM의 클럭 속도는 보통 3500-4000MHz정도 된다.


반대로 DRAM의 속도를 GB/s로 변환해보면 25.6GB/s가 나온다. 그냥 차원이 다른 속도다. 보통 가장 빠른 NVMe SSD의 속도가 7GB/s라는 점을 고려해봐도, 차원이 다른 속도임을 알 수 있다.


이 계산은 어림잡은 값이고, 실제로는 MHz와 MB/s는 직접적으로 변환되는 관계가 아니여서 정확한 값은 아니다.

 

그래서 주기억장치는 전원을 끄면 데이터가 휘발된다는 단점에도 불구하고 사용하는 것이다. 그래서 CPU가 당장 필요하지 않은 데이터는 보조 기억 장치에 보관하고 당장 연산에 필요한 데이터를 RAM에서 요청한다.

캐시 메모리

하지만 실제로는 CPU의 비약적인 발전과 그 연산 속도로 인해, DRAM만으로도 CPU의 연산 속도를 따라갈 수 없게 되었다. 그래서 병목 현상을 방지하기 위해서 DRAM보다 더 빠른 SRAM이라는 것을 CPU 내부에 둔다. 이 SRAM이 바로 캐시 메모리이다.

 

그런데 SRAM이 DRAM보다 훨씬 빠르고 다 좋은데 단점은 가격이 아주 비싸다. 그래서 램처럼 8GB, 16GB 이런 식으로 둘 수가 없다. 기껏해야 64kb, 500kb 정도의 사이즈를 갖고 있다.

 

사실 캐시 메모리 내에서도, 그 속도 차이에 따라 L1, L2, L3 등의 캐시로 계층을 구분한다. L1 캐시가 가장 빠르고, 그렇기 때문에 가장 비싸기에 용량도 제일 적다. 내 윈도우 노트북은 64kb 사이즈이다. L3는 사실 없는 노트북도 있는데, 내 노트북에선 500kb 정도 크기다.

즉 그림으로 나타내면 아래 그림처럼 된다.

레지스터는 저 L1 캐시에서 메모리를 읽어들인다.

 

문제는 이때 레지스터가 한 번에 읽어드릴 수 있는 메모리의 양에 한계가 있다. 따라서 레지스터는 적은 양의 메모리 청크 단위로만 메모리를 읽고, 만약 CU가 필요한 메모리 (주소)가 메모리 청크가 없다면, 레지스터는 해당 메모리 청크를 L1에서 찾아서 다시 읽는다. 만약 L1에 찾고자 하는 메모리가 없다면, L2, L2에서도 없다면 L3, RAM... 까지 내려가면서 메모리를 찾는다. 그래서 캐시 프렌들리한 프로그램을 짜기 위해서는, 최대한 되도록 같은 메모리 청크 블록 내에서 메모리를 읽을 수 있게 해야 한다.

올바른 이중 for 문, 잘못된 이중 for 문


std::vector<std::vector<int> > arr;

위와 같은 이차원 배열(벡터) arr을 생각해보자. STL은 형태가 조금 복잡해서 알아보기 힘든데, C-스타일로 써보자면 int arr[M][N]과 비슷하다. 다만 2차원 배열은 조금 이야기가 달라서 벡터로 먼저 설명하겠다.

 

이를 그림으로 나타내보면


위와 같은 형태로 나타낼 수가 있다.


// 1번 방법
for (std::size_t i = 0; i < N; ++i) {
    for (std::size_t j = 0; j < M; ++j) {
        arr[i][j] *= 2;
    }
}

아까 1번 방식의 메모리 접근 구조를 그림으로 나타내보자.


그러면 굉장히 자연스러운 형태로 접근하고 있음을 알 수 있다. 실제로 레지스터가 한 번에 빨간색 블록만큼 메모리 청크를 읽을 수 있다고 가정했을 때, 0 다음 1, 2가 있는 메모리 위치를 읽으려면 그냥 같은 청크 내에서 읽으면 된다. 그리고 빨간색 청크를 벗어나도, 그 다음 메모리를 읽는데 물리적으로 거리가 멀지 않다.

 

반면 2번 방식을 그림으로 나타내보자.


안쪽 반복문은 파란색 방향으로 돌고 있는데, 캐시 메모리 관점에서 보면 상당히 부자연스러운 방식으로 돌고 있음을 알 수 있다. 레지스터는 빨간색 메모리 영역을 읽고 있는데, 반복문에서 요청하는 다음 메모리 주소는 레지스터가 읽고 있는 영역에서 한참 떨어져있다. 이러면 매 번 새 메모리를 읽을 때마다 CPU는 L1 캐시에서 해당 메모리가 있는 곳으로 메모리 청크를 다시 읽어야 하는 거고, 그만큼 비효율적인 I/O 시간이 발생하면서 성능 저하가 일어나고 있다. 1번 방식에 비해 청크를 매 번 옮겨야 하니 얼마나 비효율적인지 감이 온다.

실제 성능 측정

이게 실제로 얼마나 유의미한 영향을 주는 지 간단히 테스트를 해보자.


#include <chrono>
#include <iostream>
#include <thread>
#include <vector>

void fn1(const std::size_t size) {
  const size_t N = size;
  const size_t M = size;
  std::vector<std::vector<int>> arr(N, std::vector<int>(M, 0));

  auto start = std::chrono::system_clock::now();
  for (std::size_t i = 0; i < N; i++) {
    for (std::size_t j = 0; j < M; j++) {
      arr[i][j] = i + j;
      arr[i][j] *= 2;
    }
  }
  auto end = std::chrono::system_clock::now();
  std::chrono::duration<double> diff = end - start;
  std::cout << "fn1 : " << diff.count() << std::endl;
}

void fn2(const std::size_t size) {
  const size_t N = size;
  const size_t M = size;
  std::vector<std::vector<int>> arr(N, std::vector<int>(M, 0));

  auto start = std::chrono::system_clock::now();
  for (std::size_t j = 0; j < M; j++) {
    for (std::size_t i = 0; i < N; i++) {
      arr[i][j] = i + j;
      arr[i][j] *= 2;
    }
  }
  auto end = std::chrono::system_clock::now();
  std::chrono::duration<double> diff = end - start;
  std::cout << "fn2 : " << diff.count() << std::endl;
}

int main(void) {
  constexpr std::size_t size = 20000;
  std::jthread t1(fn1, size);
  std::jthread t2(fn2, size);

  return 0;
}

약 2만 * 2만의 integer 배열을 각각 생성하고, 실행 시간을 측정해보자. 함수 fn1은 1번 방식(올바른 방식), fn2는 2번 방식(잘못된 방식)으로 돌고 있다. 반복문을 안쪽에서 도냐 바깥쪽에서 도냐의 차이점 외에는 로직은 똑같다. 실행 시간을 측정하기 위해 chrono를 사용하였다.


결과:


fn1 : 1.86167
fn2 : 4.38487

초단위여서 별거 아니라 생각할 수 있는데, 무려 42%의 차이이다. 실제로는 이 함수가 매우 자주 호출되고, 내부에서 복잡한 연산과 반복이 일어나고 있다면? 이 같은 로직임에도 단순히 반복문의 반복 순서만으로도 성능 차이가 제법 발생함을 알 수 있다.

 

그래서 반복문을 돌 때 많이 호출되는 반복문(안쪽에 있는 반복문)은 가능하다면 캐시 프렌들리하게 메모리 구조를 잡아주는게 좋다.

스택 위 2차원 배열의 경우


int arr[SIZE][SIZE];
std::array< <std::array<int>, SIZE>, SIZE> arr2;

위와 같이 배열이 생성된 경우도 비슷하면서도 살짝은 다르다. 사실 힙 위에 할당되는 벡터와는 다르게, 위와 같이 C-style이나 std::array를 사용해서 스택 위에 정적 배열로 선언한 경우 2차원처럼 표현은 되지만, 실제로는 컴파일러가 알아서 1차원 배열로 생성해주기 때문이다. 그래서 벡터처럼 그렇게까지 다이나믹한 성능차이가 발생하지 않기는 하다(일단 기본적으로 스택 위 배열은 그 최대 사이즈도 훨씬 작기 때문에).

 

그럼에도 일단 메모리상 물리적으로 arr[1][N]과 arr[2][N]은 거리가 N만큼 떨어져 있고, arr[N][1], arr[N][2]은 물리적 거리가 1만큼 떨어져있기에, 이 또한 성능 차이가 발생하니 벡터랑 똑같이 오른쪽에서 왼쪽 방향으로 반복문을 도는게 좋다.

실제로...

실제로 보통 CV 등 이미지 처리를 할 때, 이미지가 보통은 다음과 같이 구성되어 있다.


image[color][x][y]

for i in range(color):
    for j in range(x):
        for k in range(y):
            # 어떤 연산들

그 이유가 상황마다 다르긴 하겠지만, 보통은 색을 채널별로 나누어서, 그 안쪽에서 (x, y)에 대한 연산을 진행하는 경우가 많기 때문이다. 때문에 색은 반복문에서 잘 바뀌지 않기 때문에 가장 바깥쪽 루프에서 돌게 하고, 자주 바뀌는 x, y를 루프 안쪽에서 돌게 하는 게 일반적이다.

직접 구현할 일이 없을 수도 있지만, 내부 구조가 왜 이런 지 궁금하다면 이런 이유가 하나 숨어 있다.

마무리

기억해두자!


arr[0][N] ~ arr[1][N] # -> 거리 N
arr[N][0] - arr[N][1] # -> 거리 1

결론적으로 반복문을 돌 때는 오른쪽에서 왼쪽으로 이동하게끔, 즉 가장 많이 호출되는 안쪽 반복문에 메모리상 가까운 원소를 배치하는 게 좋다. 의외로 성능 차이가 심하게 발생하는 부분이니 기억해두자. 사실 암기할 필요도 없이, 어떻게 벡터가 할당이 되는지, 그리고 컴퓨터 구조와 CPU가 어떻게 동작하는지에 대한 가벼운 지식정도만 있어도, 어떻게 반복문이 돌면 좋을 지 떠올릴 수 있을 것이다.

C++ 관련 글
더 보기

티스토리툴바