programming notes

View on GitHub

Windows Via C/C++ 책에 Chapter 8장 section2에 캐시 라인에 대해서 나온다.
캐시 라인이 무효화되었을 경우 얼마나 느려지는지 테스트 해봤고 그것에 대한 기록이다.

우선 캐시 라인에 대해서 알아보자.
캐시 라인은 성능 향상을 위해서 존재한다.
보통의 경우 애플리케이션에서 인접한 바이트들을 자주 사용하는 경향이 있기 때문에 캐시에 뭉탱이로 읽어오면 CPU가 메모리 버스에 추가적으로
접근하는 것을 줄여서 불필요한 비용을 줄일 수 있다는 것이다.

하지만 문제는 멀티프로세서 환경.
멀티프로세서 환경에서 캐시라인이 무효화 될 수 있다.
무효화 되는 경우는 다음과 같다.
CPU1과 CPU2가 인접한 메모리에 접근을 하였고, CPU1이 1바이트를 수정하였다.
근데 가만히 있으면 CPU2는 CPU1이 수정한 것을 모른다.
그렇기에 CPU2는 CPU1이 변경한 것을 알아차리고 자신의 캐시 라인을 무효화 시킨다.
(책에 내용이 길어서 요약했는데 잘 전달 될 것이라고 생각한다.)

책에서 말하는 요점은 캐시 라인이 무효화되면 성능이 저하되기 때문에 잘 설계하라는 것이다.
그럼 캐시 라인이 무효화되면 얼마나 성능이 저하 될까?
궁금해서 테스트 해봤다.

테스트는 다음과 같이 진행하였다.
우선 테스트 머신의 캐시라인 크기는 64byte이다.
스레드를 2개 만들어서 스레드1은 write만, 스레드2는 read만 하였다.
각각 w/r하는 부분은 처음 같은 위치에서 read위치만 4바이트씩 증가시켰다.
각각 스레드에서는 1,000,000,000만번 w/r하였다.

테스트 결과는 다음과 같다.

offset write thread read thread
0 6201(ms) [0x4790c0] 6310(ms) [0x4790c0]
4 6295(ms) [0x4790c0] 6302(ms) [0x4790c4]
8 6328(ms) [0x4790c0] 6189(ms) [0x4790c8]
12 6187(ms) [0x4790c0] 6337(ms) [0x4790cc]
16 6145(ms) [0x4790c0] 6341(ms) [0x4790d0]
20 6152(ms) [0x4790c0] 6319(ms) [0x4790d4]
24 6200(ms) [0x4790c0] 6318(ms) [0x4790d8]
28 6147(ms) [0x4790c0] 6331(ms) [0x4790dc]
32 8555(ms) [0x4790c0] 5486(ms) [0x4790e0]
36 8592(ms) [0x4790c0] 5584(ms) [0x4790e4]
40 8568(ms) [0x4790c0] 5403(ms) [0x4790e8]
44 8566(ms) [0x4790c0] 5434(ms) [0x4790ec]
48 8621(ms) [0x4790c0] 5557(ms) [0x4790f0]
52 8619(ms) [0x4790c0] 5559(ms) [0x4790f4]
56 8517(ms) [0x4790c0] 5510(ms) [0x4790f8]
60 8678(ms) [0x4790c0] 5541(ms) [0x4790fc]
64 4875(ms) [0x4790c0] 3484(ms) [0x479100]
68 4914(ms) [0x4790c0] 3460(ms) [0x479104]
72 4838(ms) [0x4790c0] 3515(ms) [0x479108]
76 4781(ms) [0x4790c0] 3486(ms) [0x47910c]
80 4898(ms) [0x4790c0] 3449(ms) [0x479110]
84 4903(ms) [0x4790c0] 3428(ms) [0x479114]
88 4958(ms) [0x4790c0] 3413(ms) [0x479118]
92 4844(ms) [0x4790c0] 3487(ms) [0x47911c]
96 4879(ms) [0x4790c0] 3474(ms) [0x479120]
100 4859(ms) [0x4790c0] 3460(ms) [0x479124]
104 4859(ms) [0x4790c0] 3472(ms) [0x479128]
108 4875(ms) [0x4790c0] 3466(ms) [0x47912c]
112 4833(ms) [0x4790c0] 3465(ms) [0x479130]
116 4800(ms) [0x4790c0] 3510(ms) [0x479134]
120 4782(ms) [0x4790c0] 3544(ms) [0x479138]
124 4903(ms) [0x4790c0] 3420(ms) [0x47913c]
128 4827(ms) [0x4790c0] 3512(ms) [0x479140]

테스트 결과를 보면 offset 64byte에서 부터 write thread는 성능이 1.8배 정도 향상하였다.
캐시라인이 64byte이니 offset 64byte에서부터 각각의 CPU는 메모리 블록에 독립적으로 접근을 한 것이다.
그래서 캐시 라인 무효화가 일어나지 않았고 불필요한 메모리 버스로의 접근일 일어나지 않았다.

좀 의아한 것은 offset 0~28까지이다. 왜 애매한 수치가 나온지 모르겠다.
offset 0~60까지는 무효화가 일어나니 다들 비슷해야 하는데 몇번을 테스트해봐도 애매한 수치가 나온다.

아시는분 계시면 정중히 조언 부탁드리겠습니다.

2013-02-01 추가.

곰곰히 생각을 해보니 write thread와 read thread가 동시에 시작되리라는 보장이 없다. 그래서 0~28까지는 애매한 수치가 나온 것으로 생각된다. 애매한 수치라고 말하기도 뭐하다.

완벽하게 두 스레드를 동시에 실행하는 방법도 없다. 스케줄 가능 상태로 만들 수는 있지만 러닝상태로 만들수는 없기 때문이다.

캐시라인 무효화가 일어나는 범위와 아닌 범위에서 어느정도의 성능 차이가 있다는 것을 확인하는 것으로 만족해야겠다.

마지막 테스트 코드는 다음과 같다.

// 비아책에서 가져온 시간측정 클래스
class CStopwatch {
public:
  CStopwatch() { QueryPerformanceFrequency(&m_liPerfFreq); Start(); }

  void Start() { QueryPerformanceCounter(&m_liPerfStart); }

  // Returns # of milliseconds since Start was called
  __int64 Now() const {
    LARGE_INTEGER liPerfNow;
    QueryPerformanceCounter(&liPerfNow);
    return(((liPerfNow.QuadPart - m_liPerfStart.QuadPart) * 1000)
      / m_liPerfFreq.QuadPart);
  }

private:
  LARGE_INTEGER m_liPerfFreq;   // Counts per second
  LARGE_INTEGER m_liPerfStart;  // Starting count
};

typedef UINT64 loopType;
//loopType LOOP_COUNT = 200000000;
loopType LOOP_COUNT = 1000000000;
//loopType LOOP_COUNT = 0x1fffffff;
//loopType LOOP_COUNT = 0xff;

__int64 writeThreadElapsedTime;
__int64 readThreadElapsedTime;
int readThreadTemp;

#pragma optimize( "", off )
unsigned int __stdcall WriteThread(void* p)
{
  CStopwatch watch;

  int* pValue = (int*)p;

  for (loopType i = 0 ; i < LOOP_COUNT ; ++i)
  {
    *pValue += 1;
  }
  writeThreadElapsedTime = watch.Now();
  return 0;
}

unsigned int __stdcall ReadThread(void* p)
{
  CStopwatch watch;

  int* pValue = (int*)p;
  for (loopType i = 0 ; i < LOOP_COUNT ; ++i)
  {
    readThreadTemp = *pValue;
  }
  readThreadElapsedTime = watch.Now();
  return 0;
}
#pragma optimize( "", on )

void CacheLineTest(int* pWriteBuffer, int* pReadbuffer)
{
  UINT threadId1, threadId2 = 0;
  HANDLE hThread[2];
  hThread[0] = (HANDLE)_beginthreadex(NULL, 0, WriteThread, pWriteBuffer, 0, &threadId1);
  hThread[1] = (HANDLE)_beginthreadex(NULL, 0, ReadThread, pReadbuffer, 0, &threadId2);

  WaitForMultipleObjects(2, hThread, TRUE, INFINITE);

  CloseHandle(hThread[0]);
  CloseHandle(hThread[1]);

  printf("%2d      | %5d(ms) [0x%x]  | %5d(ms) [0x%x]\n",
    reinterpret_cast(pReadbuffer) - reinterpret_cast(pWriteBuffer),
    static_cast(writeThreadElapsedTime), reinterpret_cast(pWriteBuffer),
    static_cast(readThreadElapsedTime), reinterpret_cast(pReadbuffer));
}

int _cdecl _tmain ()
{
  DWORD timeAdjustment = 0;
  DWORD timeIncrement = 0;
  BOOL timeAdjustmentDisabled = FALSE;

  GetSystemTimeAdjustment(&timeAdjustment, &timeIncrement, &timeAdjustmentDisabled);

  // 버퍼는 넉넉하게 할당!
  int* pBuffer = new int[512];

  // 내 머신은 캐시라인사이즈가 64byte!!
  // 캐쉬라인 사이즈 단위에 맞춰서 시작주소 계산해야한다.
  // 포인터 주소 계산을 편하게 하려고 char*로 한다.
  char* temp = reinterpret_cast(pBuffer);
  char* temp2 = temp + (64 - (reinterpret_cast(temp) % 64));

  // 이걸 버퍼 시작주소로 하자.
  int* pBeginBuffer = reinterpret_cast(temp2);

  // 혹시 계산이 잘못되진 않았겠지?
  assert(reinterpret_cast(pBeginBuffer) % 64 == 0);

  cout << "offset" << "\t| " << "write" << "\t\t\t| " << "read" << endl;

  for (int offset = 0 ; offset < 64 ; ++offset)
  {
    // 깔끔하게 초기화하자.
    memset(pBuffer, 0, sizeof(*pBuffer) * 512);

    CacheLineTest(pBeginBuffer, pBeginBuffer+offset);
  }

  delete[] pBuffer;

  return 0;
}