출처

이 글의 코드와 내용은 인터넷에 있는 생명 게임과 관련된 문서를 읽고 공부한 내용입니다. 원본은 https://www.jagregory.com/abrash-black-book/#chapter-17-the-game-of-life 과 https://johnhw.github.io/hashlife/index.md.html 두 개의 글입니다.

콘웨이의 생명 게임

Conway’s Game of Life라는 것이 있다. 격자 모양의 세상에서 점들이 규칙에 따라 변화하는 것을 보는 게임이 되겠다. 규칙은 아래와 같다.

  1. 게임판은 네모 반듯한 격자로 이루어져 있고, 한 칸에는 8개의 이웃이 있을 수 있다.
  2. 죽은 칸과 인접한 칸 중 정확히 3개가 살아있다면 다음 세대에 그 칸은 살아난다.
  3. 살아있는 칸은 인접한 2~3칸이 살아있어야 살게 되며, 그 이외의 경우에는 다음 세대에 죽는다.

위에서 보다시피 게임의 구성은 매우 단순하다. 그렇다면 이 게임을 빠르게 수행하기 위해서는 어떤 방법을 써야할까?

기본적인 코드

일반적인 생명게임은 1개의 격자의 변화를 따지기 위해서 인접한 8개의 셀에 접근해야 한다. 또한, 생명게임 격자의 좌우, 상하가 연결된 경우의 처리와 연결되지 않은 경우의 모서리에 대한 처리가 필요하다. 단순하게 모서리에 대한 처리를 전혀 생각하지 않더라도 O(8n)의 처리시간이 소요된다. 이것은 괜찮아 보이지만, 사실 이 속도의 처리는 예전에는 굉장히 느렸다. 언제냐고? 프로그래머들이 8086CPU 상에서 프로그래밍을 하던 그 시절엔 그랬다. 이 글을 보면 33MHz 486 CPU에서 평범하게 주변의 격자를 탐색하면서 하나하나를 갱신하면 96*96 크기의 격자를 초당 3번 정도 갱신할 수 있다고 한다.

개선

앞선 첫 번째 글의 필자는 바로 가설을 세운다. 렌더링 코드가 너무 느리지 않을까? 메모리 복사 코드가 너무 느리지 않을까? 그러나 직접 수행한 프로파일링 결과는 전혀 달랐다. 메모리 복사도 렌더링도 그 자체로는 다음 세대를 계산하는 코드에 비하면 미미한 수행시간을 가졌다. 그래서 필자는 자신의 가설로 성급하게 코드를 짜지 않은 것을 다행으로 여기고 다음 세대를 계산하는 함수를 개선하기 시작한다.

cell_state 함수의 문제 찾기

실행 시간 중 다음 세대를 계산하는 next_generation함수보다 더 많은 실행 시간을 기록한 것이 바로 cell_state였다. 그리고 그 함수는 이렇다.

/* Returns cell state (1=on or 0=off), optionally wrapping at the
   borders around to the opposite edge. */
int cellmap::cell_state(int x, int y)
{
   unsigned char *cell_ptr;

#if WRAP_EDGES
   while (x < 0) x += width;     // wrap, if necessary
   while (x >= width) x -= width;
   while (y < 0) y += height;
   while (y >= height) y -= height;
#else
   if ((x < 0) || (x >= width) || (y < 0) || (y >= height))
      return 0;   // return 0 for off edges if no wrapping
#endif
   cell_ptr = cells + (y * width_in_bytes) + (x / 8);
   return (*cell_ptr & (0x80 >> (x & 0x07))) ? 1 : 0;
}

이 함수가 느려지는 이유는 제일 중요하게 분기문과 반복문이 번잡하기 때문이다. 또 모서리를 넘어가는 부분은 메모리 상에서 인접하지 않아서 CPU의 캐시히트가 내려간다는 것이다. 캐시 적중률 낮음 + 긴 수행시간을 가지는 조건문을 가진 함수가 많이 호출되므로 저 코드는 필수적으로 느려지게 된다.

아이디어

이런 상황에서 우리는 어떻게 해야할까? 이 글의 필자는 모서리 부분을 빠르게 단순한 방법으로 읽어들이기 위해서 모서리 부분에 이어질 부분을 복사한 padding영역을 추가한다. 메모리를 더 쓰게 되지만 모서리를 읽는 코드가 단순해지고, 메모리에서 인접해 있으므로 캐시 적중률이 올라간다. 또 한 가지는 단지 켜지거나 꺼지는 하나의 정보에 접근하기 위해서 1바이트를 통째로 읽어야 한다는 것이다. 이것을 필자는 8비트 전체에 각각 1개의 칸을 할당하는 방식으로 해결한다. 코드는 비트마스크 등을 사용해서 조금 더 느려지는 듯 하지만, 실제로 이웃을 세는 코드 자체는 이로 인해서 더 빨라진다.

/* Turns cell on. x and y are offset by 1 byte down and to the right, to compensate for the
padding bytes around the cellmap. */
void cellmap::set_cell(unsigned int x, unsigned int y)
{
   unsigned char *cell_ptr =
         cells + ((y + 1) * width_in_bytes) + ((x / 8) + 1);

   *(cell_ptr) |= 0x80 >> (x & 0x07);
}

위의 코드는 x & 0x07로 x를 8로 나눈 나머지를 구해서 셀 주소의 8비트에서 기록할 위치를 찾아 적는 과정을 보여준다. 0x80은 10000000(2)이므로 0~7번 비트시프트를 한 계산결과를 cell_ptr에 적는 것으로 켜진 셀을 기록한다.

인접한 이웃을 세는 코드는 아래와 같이 적었다.

/* Counts the number of neighboring on-cells for specified cell. */
int cellmap::count_neighbors(int x, int y)
{
   unsigned char *cell_ptr, mask;
   unsigned int neighbor_count;

   // Point to upper left neighbor
   cell_ptr = cells + ((y * width_in_bytes) + ((x + 7) / 8));
   mask = 0x80 >> ((x - 1) & 0x07);
   // Count upper left neighbor
   neighbor_count = (*cell_ptr & mask) ? 1 : 0;
   // Count left neighbor
   if ((*(cell_ptr + width_in_bytes) & mask)) neighbor_count++;
   // Count lower left neighbor
   if ((*(cell_ptr + (width_in_bytes * 2)) & mask)) neighbor_count++;

   // Point to upper neighbor
   if ((mask >>= 1) == 0) {
      mask = 0x80;
      cell_ptr++;
   }
   // Count upper neighbor
   if ((*cell_ptr & mask)) neighbor_count++;
   // Count lower neighbor
   if ((*(cell_ptr + (width_in_bytes * 2)) & mask))  neighbor_count++;

   // Point to upper right neighbor
   if ((mask >>= 1) == 0) {
      mask = 0x80;
      cell_ptr++;
   }
   // Count upper right neighbor
   if ((*cell_ptr & mask)) neighbor_count++;
   // Count right neighbor
   if ((*(cell_ptr + width_in_bytes) & mask)) neighbor_count++;
   // Count lower right neighbor
   if ((*(cell_ptr + (width_in_bytes * 2)) & mask))  neighbor_count++;

   return neighbor_count;
}

위의 코드는 부분 발췌라 알기 힘드나, 패딩을 1바이트 단위로 하고, 자신의 이웃비트가 속한 바이트 위치를 구하고 해당 바이트 위치에서 해당 이웃비트의 위치를 마스크 연산으로 구해내는 코드이다. 비트 연산을 우아하게 활용하는 예시이다. 메모리를 작게 쓰고, 비트 연산은 매우 빠르게 실행되기 때문에 코드의 속도는 상당히 빨라졌다.

더 나아가기

위와 같은 아이디어를 적용한 후, 필자는 속도를 더 빠르게 하기 위해서 함수 호출을 줄이고자 함수를 통합해서 작성하는 시도도 한다. 하지만 그 후 더 빠른 처리를 위해서 이웃한 켜진 칸의 갯수를 기록하는 자료구조를 만든다. 이 자료구조는 아래와 같이 제시된다.

xxxyyyyz
  • x : 사용하지 않는 비트
  • y : 주변의 켜진 비트의 갯수(최대 8개의 비트가 켜질 수 있다.)
  • z : 자신의 모습

위와 같이 자료구조를 수정하면, 다시 메모리를 적게 쓰는 장점은 잃어버린다. 하지만 그것을 뛰어넘어서 주변 칸의 갯수를 미리 기억해두고, 처리가 필요한 칸이 필요하지 않은 칸보다 더 적을 것이라는 가정(콘웨이의 생명게임에서 대개의 경우 이것은 참으로 보인다.)으로 처리가 필요한 칸과 필요하지 않은 칸을 빠르게 구별해서 수행시간의 이득을 얻으려 한다.

/* Turns an off-cell on, incrementing the on-neighbor count for the
   eight neighboring cells. */
void cellmap::set_cell(unsigned int x, unsigned int y)
{
   unsigned int w = width, h = height;
   int xoleft, xoright, yoabove, yobelow;
   unsigned char *cell_ptr = cells + (y * w) + x;

   // Calculate the offsets to the eight neighboring cells,
   // accounting for wrapping around at the edges of the cell map
   if (x == 0)
      xoleft = w - 1;
   else
      xoleft = -1;
   if (y == 0)
      yoabove = length_in_bytes - w;
   else
      yoabove = -w;
   if (x == (w - 1))
      xoright = -(w - 1);
   else
      xoright = 1;
   if (y == (h - 1))
      yobelow = -(length_in_bytes - w);
   else
      yobelow = w;

   *(cell_ptr) |= 0x01;
   *(cell_ptr + yoabove + xoleft) += 2;
   *(cell_ptr + yoabove) += 2;
   *(cell_ptr + yoabove + xoright) += 2;
   *(cell_ptr + xoleft) += 2;
   *(cell_ptr + xoright) += 2;
   *(cell_ptr + yobelow + xoleft) += 2;
   *(cell_ptr + yobelow) += 2;
   *(cell_ptr + yobelow + xoright) += 2;
}

*(cell_ptr) |= 0x01;의 의미는 쉬워보인다. 자신의 상태를 나타내는 비트를 켜는 것이다.

그렇다면 그 아래의 +=2는 무슨 의미일까? 이것은 자기 자신의 상태를 나타내는 구간을 건너띄워서 자신의 인접한 셀들의 숫자를 기록하는 비트구간에 1을 더하기 위함이다. 2는 2진수로 0010임을 떠올리면 된다.

마지막으로 필자는 모든 값이 0인 바이트 구간을 빠르게 넘어가기 위해서 어셈블리 최적화를 수행한다.(0이 아닌 값을 가진 바이트를 찾아가는 어셈블리 명령어를 사용하는데, 이것은 이런 종류의 명령을 수행하는 일반적인 반복문이 가지는 수행속도를 뛰어넘는다. 이런 최적화는 Instruction Cycle을 아끼는 것인데, 문자 그대로 명령 하나 하나의 수행 시간을 아끼는 것이다.)

구시대와 메모리모델

필자는 위의 비트열 연산을 적용한 버전은 크기가 다시 커지고, large 메모리 모델 하에서 동작해야 한다고 말한다. 라지 메모리 모델은 실행속도가 조금 느려지지만, 저 알고리즘의 효율성은 저 알고리즘이 실행시에 요구하는 큰 메모리를 들일 가치가 있다고 말했다.

최종 결과

위의 모든 개선을 거친 후에, 최종 결과물은 기본적인 CPP코드에 대비해서 30배 빨라졌다고 필자는 말했다.

다른 사람들은…?

그리고 필자는 다른 사람들의 코드를 받아보고자 했다. 그는 아래와 같은 규칙을 요구했다.

  1. 필자의 프로그램과 동일한 아웃풋 생성(필자는 화면 출력의 형태를 의도함)
  2. 엔진 코드는 400줄 이하여야 했다.
  3. 볼랜드 CPP컴파일러를 사용할 것.
  4. 최소 200x200이상의 격자를 처리할 수 있을 것 등등…

그 결과 그는 다양한 코드를 받았고, 모든 코드가 실행 규칙을 어겼고 사소하거나 큰 다양한 규칙 위반이 있었다고 했다. 그는 다음 대회에서는 규칙을 더 엄밀히 할 것을 다짐하지만, 여하간 그의 생명게임 코드 대회의 우승 코드는 아래와 같이 작동했다.

  • 룩업 테이블과 그것에 의존하는 상태머신
  • 위의 코드가 400줄 이상일 것이기에, CPP코드는 어셈블리 상태머신 코드와 룩업테이블을 생성하는 목적의 코드이다…
  • 상태머신과 룩업테이블이 각각 64KB크기.(이유는 당시 CPU의 메모리 크기가 대략 그 정도면 많은 부분을 차지하는 것이어서 그렇다.)

더 빠르게 해야할까?

물론 현재의 CPU들은 클럭도 100배 정도 빠르고, 클럭당 명령어도 훨씬 빠르기에 가장 기본적인 코드로도 96*96크기라면 초당 1000번 이상 갱신할 수 있을 것이다. 그러나 격자의 가로세로 크기가 4배로 커진다면 처리량은 16배로 많아지므로, 현대의 CPU로도 60프레임 수준의 처리가 될 것이다. 이것은 충분한가??? 그렇지 않다. 우리 인간은 384*384 정도의 격자를 초당 60번 처리하는 것으로는 만족할 수 없다. 더 많은 칸을 아무 이유 없이 계산하고 싶다는 우리의 간절한 바램을 이루기 위한 뛰어난 알고리즘이 있다.

Hash Life

아마도 한 개 한 개의 칸을 개별적으로 따지는 것으로는 속도 향상이 힘들 것이다. 어떤 사람은 변경된 칸과 인접 칸만을 링크드 리스트로 관리하여 빠른 처리를 하는 경우도 있다. HashLife는 이런 칸별 처리를 뛰어넘는다. 여러 칸을 블록 단위로 해시하고, 해당 영역이 이후에 어떤 방식으로 변화하는지를 미리 저장해두고, 나중에 그 값을 기억해서 사용한다. 이런 방식을 통해서 HashLife는 초기 메모이제이션이 끝난 후부터 갑자기 성능이 대단히 빨라진다. 다만 이 알고리즘도 다른 알고리즘보다 느려지는 경우가 있는데, 캐싱이 의미가 없어지는 Chaotic pattern들은 이 알고리즘이 메모리와 씨피유 시간을 더 잡아먹게 하고 별 이득을 거두지 못한다고 한다. https://johnhw.github.io/hashlife/index.md.html을 따라가면서 타입스크립트 버전의 해시라이프를 작성해보자.