N * N 배열이 있고 이 배열을 전부 0으로 채우는 함수가 있다고 가정한다. loop1()과 loop2()의 실행 속도에는 어떤 차이가 있을까?

static const int N = 4096;

static const int CNT = 10;

void loop1() {

  static volatile char arr[N * N];

  for (int cnt = 0; cnt < CNT; cnt++)

    for (int a = 0; a < N; a++)

      for (int b = 0; b < N; b++)

        arr[a * N + b] = 0; // (A)

}

void loop2() {

  static volatile char arr[N * N];

  for (int cnt = 0; cnt < CNT; cnt++)

    for (int a = 0; a < N; a++)

      for (int b = 0; b < N; b++)

        arr[b * N + a] = 0;// (B)

}

loop1()과 loop2()의 함수의 차이는 (A)와 (B) 밖에 없다. 얼핏 봐서는 성능의 차이가 없을 것으로 보이지만, 실제로 실행을 해 보면 많은 차이가 나게 된다. 허걱!!! (숫자의 단위는 nano second)

이런 차이가 나는 이유를 valgrind, kcachegrind를 이용하여 확인해 보도록 한다. 다음과 같은 명령어를 이용하여 valgrind와 kcachegrind를 설치한다(설치 용량이 100MB 조금 넘는다).

sudo apt install valgrind kcachegrind

실행 파일(loop_test)을 다음과 같이 실행하여 profile 파일을 생성시킨다.

valgrind --tool=callgrind ./loop_test

같은 폴더에 "callgrind.out.*"이라는 파일이 생성되었음을 확인할 수 있다.

설치된 kcachegrind 툴을 이용하여 profile 파일을 열어 본다. main함수 내에서 loop1()과 loop2()의 instruction code 실행 횟수가 일치함을 확인할 수 있다. 실제로 disassembled instruction code를 봐도 loop1()과 loop2()가 거의 동일하다.

이를 가지고서는 실제적으로 loop1()이 loop2()보다 빠르다는 것을 입증할 수는 없다. loop1()이 loop2()보다 빠른 이유는 실행되는 instruction code의 실행 횟수 차이가 아닌 CPU와 Memory간의 cache miss의 차이에 기인한다. 이를 위해서 다시 다음과 같은 명령어를 통하여 cache profiling을 해 보도록 한다.

valgrind –tool=cachegrind ./loop_test

생성된 "cachegrind.out.*" 파일을 kcachegrind 툴에서 열어 본다. loop1()과 loop2()가 Insturction Fetch에서는 동일한 횟수의 instruction code가 실행되어 지지만

L1 Data Write Miss에서는 loop1()보다 loop2()가 현저히 높음을 알 수 있다.

이와 같이 valgrind 관련 툴을 이용하면 binary code profiling을 통해 특정 코드의 실행에 있어서 instruction code의 실행 횟수와 cache miss등의 정보를 확인해 볼 수 있다.

[download]

loop_test.zip