네, 정말 C는 C++보다 빠릅니다. by object

갑자기 kldp.org에서 많은 레퍼러가 잡혀서 뭔 일인가 싶어서 들어가봤다. 어떤 분이 정말 C가 C++보다 빠른지에 대한 의문을 제기했다. 이 기회에 잘못된 미신을 타파하고 C++ 가상함수에 대해 좀 더 정확하게 알아보자.

다 좋은데 밑줄 친 문장이 자신의 의견이나 느낌이면 문제 없다. 그런데 저렇게 단정적인 표현을 쓰려면 객관적인 자료가 필요하다 가상 함수 호출에 드는 비용이 정말 미약하다는 데이터를 달라는 것이다!

일단, 글 쓰신 분은 두 가지 문제점을 제기했는데 내가 볼 땐 결국 하나다. 1번에서 제기한 "클레스 설계에 따른 잦은 함수 호출에 드는 비용"은 다소 모호하다. 클래스 설계로 인해 과도한 가상 함수 사용이라면 성능에 문제가 될 수 있지만, 일반 클래스 함수들을 호출하는데 부가적인 비용은 거의 (this 넣는 것 빼곤) 없다. 일반 클래스 멤버 함수는 컴파일할 때 함수의 주소가 바로 나오기 때문에 일반 함수 호출과 같다. 그리고 함수 호출이 많다고 해도 요즘 같이 똑똑한 컴파일러는 inline 키워드 안써도 알아서 잘 인라이닝 해준다. 게다가 IPO를 쓰면 다른 오브젝 파일에 있는 함수도 인라인 해준다. 그러니까 결국 "가상 함수 사용에 드는 비용"에 관한 의문 제기라고 할 수 있겠다. 정말 C++ 아니 C#, Java에 있는 가상 함수 호출에 드는 비용이 정말로 미약할까?

 

일단 가상함수의 실체부터 알아보자. Object는 base class, TurnOn은 가상 함수. 이걸 컴파일 하였을 때 가상 함수 호출 부분이 어떻게 번역되는지 보자. 잡다한 코드를 줄이기 위해 /RTCs와 같은 보안 관련 코드는 껐다.

Object* p = new Computer;
p->NoVirtual();
00BA15D9 mov ecx,dword ptr [p]
00BA15DC call Object::NoVirtual (0BA1028h)
p->TurnOn(10);
00BA15E1 push 0Ah ; 함수 인자 10
00BA15E3 mov eax,dword ptr [p] ; eax = p
00BA15E6 mov edx,dword ptr [eax] ; edx = *p
00BA15E8 mov ecx,dword ptr [p] ; this = p
00BA15EB mov eax,dword ptr [edx+8] ; eax = *(*p + 8)
00BA15EE call eax

Non-static인 (가상함수와 비가상함수 모두) 클래스 멤버 함수는 thiscall이라는 calling convention을 따른다. 즉, 우리가 멤버 함수에서 this를 묵시적으로 쓸 수 있도록 하기 위해 별도의 공간에 this에 해당하는 포인터를 넘겨주는 것을 약속한 것이다. VC++ 컴파일러는 this 포인터를 레지스터 ecx를 통해 넘어간다. 그래서 함수 call 명령어 앞에 ecx가 p로 초기화됨을 볼 수 있다. 첫 번째 NoVirtual 함수 호출은 보다시피 call 할 주소가 바로 계산이 되어있다. 반면, TurnOn이라는 가상 함수는 이 주소를 직접 계산 한다. 00BA15EB에 있는 문장은 C++ 클래스의 virtual table에 접근하는 부분이다. 이건 당연히 클래스 선언 레이아웃에 따라 달라질 것이다. vtable은 디버거로 쉽게 살펴볼 수 있다. vtable 3번 째 항목에 TurnOn이 있어서 +8 오프셋이 주어졌다.

대충 가상 함수가 어떻게 생겨먹었고 어떻게 불리는지 살펴봤다. 가상 함수를 한 줄로 요약하면

호출할 함수의 대상이 컴파일 시간에 정해지지 않고 실행 시간에 계산을 통해 결정 되는 간접 분기문

으로 요약할 수 있다. 따라서 OOP 언어의 가상 함수 뿐만 아니라 C 언어에서도 함수 포인터를 통한 호출도 이와 동일한 맥락이다. C에서도 함수 포인터를 모아놓은 자료구조로 얼마든지 OOP틱하게 코딩 할 수 있다. 따라서 이 포스팅이 답하고자 하는 질문은 프로그래밍 언어를 막론하고 간접 분기문에 대한 비용은 얼마나 큰가? 로 정리할 수 있다.

 

사실 왜 이 가상 호출과 같은 간접 분기문에 많은 비용이 드는지는 CPU 마이크로아키텍처를 이해하지 못하면 제대로 알기 힘들다. 그런데 여기서 이 모든 내용을 쓸 수 없고 정말로 이 간접 분기문이 얼마나 오버헤드를 가지는지 몇 가지 데이터를 가지고 피부로 느껴보자.

가상 함수를 보다 프로그래밍 랭귀지틱 하게 얘기하면 Dynamic dispatch라고 말 할 수 있는데, 여기에 대한 성능을 주로 측정하는 Richard라는 벤치 마크가 있다. 원래는 BCPL 언어로 만들어진 작은 규모의 벤치 마크 프로그램인데 객체 지향 정도를 여러 단계로 해서 Java, C++로 포팅이 되어 여러 성능을 가늠해볼 수 있다. 결과는 여기에서 가져왔다.

Java logo

먼저, 이 그래프는 자바로 7가지 다양한 객체 지향 정도로 작성된 Richard의 성능 그래프이다. Richard는 여러 다른 작업을 번갈아가며 해주는 그런 프로그램이다. 몇 가지 흥미있는 경우만 간략히 살펴보자.

1) 원래 BCPL로 만들어진 코드를 충실히 자바로 옮긴 경우다. 객체 지향적이지 않으며 switch 문으로 여러 상태를 구분하고 있다. 보다시피 가장 빠르다. 약 600 ms.

4) 이제 프로그램을 객체 지향 스타일로 만들었다. 참고로 모든 자바의 함수는 기본으로 virtual이다. 그래서 일단 자바 클래스의 accessor 없이 바로 접근이 되도록 만들었다. 성능이 다소 나빠져서 800ms 정도.

5) 이제 일반적으로 짤 수 있는 자바 형식으로 만들었다. 자바 메소드를 그대로 즉, 모든 함수들을 virtual로 만들면 보다시피 성능이 3배 이상 느려졌다.

6) 버전 5에서 가상 함수로 불릴 필요가 없는 녀석들을 final 처리하였다. 성능이 급격히 좋아졌다.

7) 가상 함수와 interface를 써서 만들었다. 역시 오버헤드가 엄청나다.

대충 이 정도만 보더라도 가상 함수 호출에 들어가는 비용이 생각보다 매우 클 수도 있다는 사실을 알았을 것이다. 그러면 C++로 만들어진 Richard의 성능도 살펴보자.

graph

일단 보다시피 시간 스케일이 확 다르다. 특별하게 매우 최적화되지 않은 자바 프로그램이 C++ 보다 매우 느리다는 사실을 한 눈에 알 수 있다. 이 그래프에서도 5) 버전 즉, 모든 함수를 버추얼로 만든 경우 최적의 경우보다 무려 5배 이상 느려짐을 볼 수 있다. 자 이제 가상 함수 호출 비용이 정말 미약하다고 할 수 있을까?


(익명님의 제보로 추가합니다) 4에서 5로의 성능이 급격히 저하된 것은 obj.field와 virtual obj.getField()의 차이에서 기인한 것입니다. 따라서 성능 하락이 모두 가상함수 호출에 기인한 것은 아닙니다. 가상함수 호출과 직접함수 호출만의 비용차이는 이 보다는 덜할 것입니다. 그러나 가상함수는 함수 인라이닝을 불가능하게 하기 때문에, 단순히 가상함수 호출에 대한 비용 뿐만 아니라 최적화 기회를 잃어서 오는 성능하락도 큽니다. 이 벤치마크는 이런 맥락에서 이해해주시면 되겠습니다.

 

이런 가상 함수 호출의 비용을 줄이기 위해 사람들이 가만히 있지 않다. 대표적인 자바 최적화 기술 중 하나인 devirtualization은 과도한 가상 함수를 직접적인 함수 호출로 대체한다. HotJava 같은 경우 dynamic profiling으로 가상 함수의 부담을 상당히 줄일 수 있다.

graph

이 그래프는 JVM이 이제 가상 함수를 직접 특정 타입에 대해 인라이닝 해서 성능을 높였을 때를 보여주고 있다. 보다시피 5번의 경우에도 성능이 상당히 우수함을 알 수 있다. (그래도 C++ 보다는 느리다)

이런 가상 함수 호출 비용을 줄이기 위한 노력은 Profile-Guided Optimization에서도 볼 수 있다. 컴파일러 최적화를 하는데 실제 프로파일링 데이터를 기초로 좀 더 똑똑하게 최적화 하는 것이다. 참고 PPT 파일을 보면 Virtual Call Speculation이라는 것이 있다. Base* 로 포인트된 클래스 포인터에서 call이라는 가상 함수를 부르는 것을 아래 그림과 같이 최적화 할 수 있다. 예를 들어, 프로파일 결과 중 Foo 타입이 대부분이었다고 하자. 그러면 이 부분의 경우를 가정하고 바로 이 함수의 구현을 호출한다. 여기서 인라인을 통해 성능을 더욱 높일 수 있다. 만약 이 가정이 틀리면 그냥 가상 호출을 그대로 한다.

void Func(Base *A){
while(true){
if(type(A) == Foo)
// inline of A->call();
else
A->call();
}
}

이런 것과 같이 가상 함수로 대표되는 간접 분기문의 성능을 높이기 위한 컴파일러 최적화 노력은 무수히 찾아볼 수 있다. 이것이 별로 느리지 않다면 왜 이렇게 많은 사람들이 이렇게 고생을 해가며 노력할까?

 

CPU 입장에서 분기문은 원래 처리하기 골치아프다. 그래서 분기문의 결과를 예측해서 성능을 높이는데, 일반적인 직접 분기문은 다음에 어디에 있는 명령이 실행될지를 쉽게 예측할 수 있다. 분기를 하느냐 마느냐, 이 Yes/No 질문에만 대답하면 어디로 갈지는 바로 알아낼 수 있다. 반면, 간접 분기문은 어디로 갈지가 Yes/No로 답이 나오지를 않는다. N개의 가능한 점프 대상이 있다면 N개의 답 중 하나를 골라줘야 한다. 그래서 처리하기 쉽지 않다.

저 kldp 스레드 중에 어떤 분이 Branch Target Buffer, BTB를 언급하셨다. 그런데 BTB로도 간접 분기문 처리는 쉽지 않다. BTB는 원초적으로 "가장 마지막으로 분기한 위치"를 기억해서 알려주는 구조다. 분기 예측기가 가장 마지막에 있었던 분기 결과를 기초로 알려주는 것과 같은 맥락이다. 그런데 가상 함수의 경우 호출 대상, 즉 분기 목적지가 수시로 바뀌기 때문에 BTB 구조 기반의 예측은 그리 정확하지 않다. 적중률이 50% 밖에 되지 않는다 (참고 논문은 귀찮아서 생략).

그래서 최초로 Pentium M에 쓰인 Core 마이크로아키텍처부터 이런 간접 분기문을 특별히 처리하기 위한 별도의 장치가 추가되었다. 그러나 여전히 이 방법도 완벽하지 못하다. 참고 논문에 따르면 이런 간접 분기문을 위한 하드웨어 장치가 있는 CPU에서도 실제 엑셀, IE, 파이어폭스와 같은 C++ 프로그램을 돌려보면 분기 예측 실패 중, 평균 28%가 이런 간접 분기문에서 기인함을 밝히고 있다. 천 개의 명령어 당 평균 약 6 번의 분기 예측 실패가 있고 이 중에 1.8개 정도가 간접 분기문 - 가상 함수, 함수 포인터 - 에서 기인한다. 여기에 관해 논문 쓰고 박사 받아 교수 하고 있는 사람도 있는 것을 보면 (... 내 지도 교수) 이 문제는 풀기 여전히 어려운 문제이다.

이래도 가상 함수 비용이 거의 무시할만한 수준인가!

 

3줄 요약:

  1. 가상 함수는 호출할 대상이 실행 시간에 결정되는 간접 분기문의 일종이다.
  2. 이런 간접 분기문은 현대 CPU에서도 여전히 처리하기 힘들다.
  3. 따라서 가상 함수 호출의 비용은 전혀 미약한 것이 아니다.

3줄 요약도 귀찮다. 한 줄로 요약해달라.

  1. 네, C언어는 C++ 보다 빠릅니다.

그러나 여기에 반전이 숨어있다. 이렇게 C++ 가상 함수, 자바 메소드의 호출 비용이 크다고 이들의 사용을 자제하라는 소리가 아니다. 분명, 가상 함수 호출에는 비용이 들지만 만약 가상 함수의 적절한 활용으로 프로그램 구조의 가독성이 높아지고 유지 보수가 용이하다면 당연히 써야 한다. 왕년에 했던 일이 C# Windows Form과 같은 컴포넌트 라이브러리를 만드는 일이었다. 당연히 가상 함수를 이용한 추상화가 핵심이었다.

그러나 이런 가상 함수가 어떠한 비용을 가지고 있다는 것은 정확하게 이해하는 것이 중요하다. MFC가 단순히 vtable 크기를 줄이기 위해 메세지 맵 함수를 비가상함수로 처리한 것만은 아니다. 이렇게 간접 분기문은 CPU에서 처리하기 힘들어 성능 저하에 주요 요소가 될 수 있기 때문에 그렇게 각종 매크로로 메세지 맵을 처리한 것이다. 세상에 공짜는 없는 법이다. printf와 cout을 비교한 글에서도 비용과 편의성의 tradeoff를 잘 살펴보았다. 버추얼 함수도 이런 것이다.

예전에 마이크로소프트에가서 모 팀이랑 이야기를 하는데 서버를 C도 아니고 C++도 아니고 무려 C#으로 만드는 것이었다! 난 너무나 이 무식함에 놀라 도대체 어떻게 서버를 만드는데 C#을 쓸 수 있습니까! 라고 반문했다. 그랬더니 팀장님 말씀: "5년 전에는 C++로 어떻게 서버를 만들어? 라는 이야기가 있었죠".

 

최종 결론:

  • 가상 함수의 비용을 잘 이해하고 적절히 이용하자.

핑백

  • art.oriented : C언어로도 얼마든지 객체 지향이 가능합니다. 2008-11-26 14:35:57 #

    ... 객체를 만드는 함수고 SetParent는 부모 윈도우라는 ‘속성’을 바꾸는 메소드다. “에이, 그래도 virtual 함수는 어떡해요?” 라고 물으신다면 역시 이건 virtual 함수의 본질을 모르는 데서 기인한 오해일 뿐이다. C++이 순수 가상 함수로 ‘인터페이스’를 만들 수 있다. C언어는 불가능할까? 가능하다. 왜냐면 가상 함수는 그냥 “함수에 ... more

  • My Dungeon... : 가상 함수에 드는 오버헤드.. 2009-08-14 15:42:08 #

    ... http://minjang.egloos.com/1973793 도움의 되는 글. ... more

  • dO_O : 네, 정말 C는 C++보다 빠릅니다. 라는 글 2012-04-21 01:57:28 #

    ... http://minjang.egloos.com/1973793이런것을 생각하고 코드를 짜려면 얼마나 노력해야할까.... ^^ ... more

  • C로도 얼마든지 객체지향이 가능하다. | StyleWear 2015-10-28 11:36:04 #

    ... 윈도우 객체를 만드는 함수고 SetParent는 부모 윈도우라는 ‘속성’을 바꾸는 메소드다. “에이, 그래도 virtual 함수는 어떡해요?” 라고 물으신다면 역시 이건 virtual 함수의 본질을 모르는 데서 기인한 오해일 뿐이다. C++이 순수 가상 함수로 ‘인터페이스’를 만들 수 있다. C언어는 불가능할까? 가능하다. 왜냐면 가상 함수는 그냥 “함수에 ... more

덧글

  • object 2008/07/12 09:18 # 답글

    그러니 우리 모두 잘못된 미신 타파에 앞장 서야 합니다.
  • xeraph 2008/07/12 09:49 # 답글

    대부분 왜 더 느리다는걸 이렇게 설명해주지 않기 때문이죠 (..)
    성능에 관해선 역시 아무도 믿지 말고 기계에게 직접 물어봐라가 정답이네요.
  • object 2008/07/12 11:47 #

    댓글로 달린 글 중에도 잘못된 부분이 한 두군데가 아닙니다. 느낌을 사실인냥 말하는 일은 컴퓨터에서는 정말로 경계해야 합니다. 하나하나 다 지적하면 욕 먹을거 같아 넘어갑니다;;
  • Sikuru 2008/07/12 10:17 # 답글

    잘읽었습니다. =)
  • object 2008/07/12 11:52 #

    감사합니다. =)
  • 지나가다 2008/07/12 10:21 # 삭제 답글

    애초의 미신은, C++은 컴파일러가 몰래 뭔가를 해 주므로 C보다 무조건 느리다 라는 거였지요.

    그래서, 컴파일러가 어떤 코드를 생성해 내며, 무엇을 최적화해주는지 알면
    그리고 주인장님처럼 가상함수나 가상상속 등의 내부 구현을 알면
    편의는 편의대로 가져 오고, C처럼 빠르게 쓸 수 있다라는 것이 정답 아닐까요.

    눈에 확 뜨이는 좋은 글을 쓰셨는데, 왜 결론이 C가 C++보다 빠르다입니까.

    일단 무난한 반론을 들면
    멀티 패러다임 언어인 C++을 C처럼 쓰면 (하위호환이 되니) 최소한 같잖아요.
    dynamic binding을 안 쓰면 C++이 아니다라는 법이 있는 것도 아니구요. ㅎㅎ

    그리고 원글쓴이도 가상함수의 오버헤드를 간과한 것 말고는 무난한 것 같은데요.
    1번의 경우, ctor/dtor를 사용하지 않으면 코드가 아예 생기지 않으니 잦은 함수 호출 자체가 없는 거구요.

    단정적인 말은 헛소리가 될 확률이 높습니다.
    알고 쓰면 C와 C++의 속도는 같다. 이런 식으로 피해갈 구멍을 만들자구요.
  • object 2008/07/12 11:46 #

    "최종결론"을 다시 읽어주세요.

    제 글을 제대로 읽으셨다면 "C가 C++ 보다 빠르다"라고 이해하시지 않으시겠죠? 잘 읽어보시면 C라고해도 함수 포인터를 마구 쓰면 역시 성능이 안나올 수 있구나라고 이해하실 수 있을 겁니다. 이 정도 코미디는 이해하실 줄 알았는데 곧이 곧대로 받아들이시면 곤란하지요. 원래 kldp에 올라온 글 제목을 한 번 따라 패러디(?)를 해 본 것입니다.
  • signer 2008/07/12 10:36 # 삭제 답글

    ㅎㅎ 글도잘쓰시고... 내용도알차고 처음부터끝까지 집중해서 잘읽었네요. 앞으로도 좋은글 부탁드릴게요.
  • 몽몽이 2008/07/12 10:46 # 답글

    가상함수의 비용이 통상 느꼈던 것보다 매우 크군요;;;
    분기 예측의 실패라는 점에서 생각해봄직한 것이었는데 전 지금껏 그런 생각을 별로 못해봤네요.
    역시 전문가와 야매의 차이를 통감합니닷.
  • object 2008/07/12 11:49 #

    컴퓨터가 아무리 빨라져도 현재까지는 가상함수의 비용이 예전처럼 여전히 큽니다. 다만 컴퓨터가 워낙 빨라졌으니 눈에 잘 안 보이는 것이죠. 피부로 안 느껴진다고 가상 함수 저거 뭐 별거냐.. 이렇게 생각하는 건 바람직하지는 않습니다. 그러나 또 제가 마지막에 얘기한 것 처럼 분명 가상 함수나 C#과 같은 언어 사용이 주는 성능 외적인 이득이 크기 때문에 잘 알고 쓰자가 역시나 정답이 되겠습니다.
  • 딱쮜 2008/07/12 13:07 # 답글

    전 유지보수성에 중점을 주다보니 성능에 대해서 신경을 덜 썼었는데
    (만드는 것도 퍼포먼스를 중요시 하는게 아니었고)
    오늘 저걸 보고나니 그동안 남발한 추상화가 꽤나 퍼포먼스 저하를 일으키는 원인이었군요.(반성중)
    앞으로는 추상화를 하더라도 좀더 신경써서 꼭 필요한데만 하도록 해야겠습니다.
  • object 2008/07/13 13:26 #

    가상함수는 필요할때만 쓰는 것이 사실 좋습니다. 비록 그게 눈에 띌 정도로 성능 저하를 준다고는 생각되지 않지만..
  • Tail 2008/07/12 15:13 # 삭제 답글

    개인적으로 해외의 모 게임 개발사에서 서버 소프트웨어 엔지니어 채용 공고에 C#가 채용의 Plus 요인으로 들어가 있는 것을 보고 좀 놀랐던 기억이 있습니다. 물론 요구 사항은 아니었습니다만... 뭐 개발 기간과 성능을 서로 Trade-off 한다고 치면 아주 납득하지 못할 일도 아니지 않을까 싶네요.
  • object 2008/07/13 13:27 #

    C#으로 서버짜는 것이 더 이상 새로운 일은 아니지요.
  • 가이우스 2008/07/12 15:24 # 답글

    임베디드에서는 c로 짜는 경우가 많아서 그러려니 했었습니다만...
    꼭 그렇지도 않았네요. 공부를 좀 더 해봐야겠군요
  • object 2008/07/13 13:24 #

    C로 만들어도 얼마든지 객체지향적으로 만들 수 있습니다. 리눅스 디바이스 드라이버들을 보면 다 함수 포인터들의 스트럭쳐로 되어있고 이 함수포인터들이 open/write 등을 가리키죠.
  • 누렁별 2008/07/12 18:41 # 답글

    벤치마크 프로그램 이름보고 "이거 만든 프로그래머 이름?" 이다 싶었는데 역시 그렇군요. BCPL로 시작했다면 역사와 전통을 자랑하는 프로그램이네요. 제 나이보다도 더 오래 되었을 듯 싶군요.
  • object 2008/07/13 13:30 #

    벤치마크 프로그램 이름치곤 좀 촌스러워 그런 예상이 가능했습니다.
  • ParkPD 2008/07/13 00:15 # 삭제 답글

    저희 회사 게임은 아니지만 모 게임 회사(그것도 큰)에서도 게임 서버를 C# 으로 만들고 있다고 합니다.
    성능은 C++ 의 60 ~ 70% 정도까지만 기대하는 대신, 개발 기간을 훨씬 앞당길 수 있을 거라고 생각한다더군요.
    C 로 짜면서 if else 나 case 를 마구 넣는 식이라면, 차라리 virtual 로 하는 게 더 좋다고 생각합니다.
    결국 속도냐, 유지보수냐를 취사선택할 수 있는 지혜가 필요하겠네요.
  • object 2008/07/13 13:23 #

    MS도 모바일 HotMail 서비스 중 일부를 C#으로 서버를 만들고 있었습니다. 성능 크리티컬 한 경우가 아니라면 사실 이렇게 쪼잔하게 버추얼 함수를 따질 필요는 솔직히 없습니다. 그래도 이런 비용이 있다는 것을 모르는 것과는 다르겠죠.
  • nineye 2008/07/16 10:46 # 삭제

    개발 기간을 앞당기기 위해서 C#으로 짠다는 것은 좀 잘못된 것 같네요... 어차피 C#에서는 서버를 구축하기 위한 편리한 library를 제공해 주기 때문이겠죠.. 하지만 이러한 library는 C나 C++로도 많이 나와 있고, 또한 직접 짜는 것도 그리 큰 시간이 걸리는 건 아닐겁니다. 그리고 대부분 개발 시간을 많이 차지하는 건, 그 게임 서버에서 필요한 기능들을 만드는 거라고 생각하며, 그런 것들은 C#에서 편리하게 library로 제작해 주진 않겠죠...
    그리고 C로 짠다고 해서 조건문이나 분기문이 많이 들어간다는 것은 잘못된 생각인 것 같네요... 그것은 전체적인 설계를 어떻게 하냐에 따른 이야기지 언어에 대한 선택문제는 아닌것 같네요...
  • Sikuru 2008/07/13 20:13 # 답글

    제가 개발하고 있는 프로젝트의 서버도 C# 으로 한번 해보고 싶네요. =)
    가능하지 않다는게 문제지만. ㅠㅠ
  • kc 2008/07/14 15:08 # 삭제 답글

    가상 함수가 느린 이유 중 주요한게 케시 미스에 의한 성능 저하 아닌가요?
    케시에 분기할 부분이 있는 경우하고 없는 경우하고를 벤치마크한 자료가 있으면 비교해주시는 것도 좋을 것 같네요.
  • object 2008/07/14 17:00 #

    궁극적으로는 더 많은 캐쉬미스가 일어나 성능 저하의 주요 원인이 될 수 있습니다. 그러나 그 전에 BTB miss로 인한 파이프라인 플러쉬가 더 큰 문제라고 생각합니다.

    일단 I$의 경우, fetch할 때 분기문이 있고 taken-branch이라면 indirect/direct를 막론하고 fetch에 제약이 생깁니다. 보통 superscalar fetch에서는 명령어 3~4개를 동시에 읽어야 하는데 taken-branch가 있으면 캐쉬 라인을 두 번 읽어야해서 front-end의 throughput이 저하가 됩니다. 따라서 indirect branch라고해서 특별히 I$가 고생한다고 보기는 조금 힘들어 보입니다.

    D$의 경우 vtable이 있는 영역을 메모리에 로드해야 하므로 캐쉬 미스가 더 유발 될 수 있습니다.

    그러나 이걸 능가하는 비용이 BTB가 가상함수와 같은 indirect branch에 우수한 성능을 내지 못해 일어나는 BTB miss가 주요한 성능 저하라고 생각합니다. BTB 테이블에 아예 예측 값이 없으면 보통 stall 시키기 때문에도 그렇구요. 정량적인 데이터를 뽑아내기는 조금 노가다라 ㅋ
  • anony 2008/07/14 17:16 # 삭제 답글

    전체적인 논조와 결론에는 "전적으로" 동감합니다만..
    중간에 벤치마크 해석에 대해 보충해야 할 것이 있어 보입니다.

    링크해 주신 원문을 읽고 저의 견해를 말씀드리면..
    2->3 에서 성능 저하는 하나의 state variable을 3개의 boolean으로 잘게 나누고 switch를 여러개의 if로 나눈 것이 주요 원인이고, 3->4 에서 성능 저하는 state를 primitive가 아닌 object를 이용해서 관리하기 때문으로 보입니다. 객체 생성 오버헤드가 더 큰 요인으로 생각되네요.

    가장 중요한 4->5의 성능 저하의 경우, obj.field; 로 접근하던 것을 obj.getField(); 로 바꿔서 접근하는 것이기 때문에 결국 메모리 간접 접근 vs. 함수 호출의 성능 비교가 되어 버립니다.
    5->6에서 성능이 좋아지는 이유는 자바 컴파일러가 final method를 inline 하기 때문으로 추측됩니다. (막연한 추측이지만, 제가 아는 한 많은 자바 컴파일러가 간단한 final 메소드를 inlining 합니다. 6과 4가 비슷한 성능을 내는 것에서 그렇게 추측하고 있습니다.)


    가상 함수 호출의 오버헤드에 대한 논지와는 별개로 근거로 드신 벤치마크가 논지를 뒷받침하기에는 좀 애매한 구석이 있어서 사족을 답니다.
  • object 2008/07/14 17:25 #

    감사합니다. 지적하신 것이 다 맞습니다. 5에서 성능이 급격히 떨어지는 이유가 모두 가상함수 때문은 아닙니다.

    보다 정확하게는 자바에서 obj.field와 obj.getField()는 "한번의 메모리 dereferencing"과 "가상함수호출" 정도가 되겠네요. 참고로 버추얼 함수는 인라인 자체가 불가능하지요. 그래서 정확하게 가상함수 호출만의 비용을 따지려면 가상함수 호출과 일반함수 호출을 비교해야하지만 최적화까지 고려한 궁극적인 성능 차이를 고려하면 이 벤치마크는 나름대로 의미가 있다고 봅니다. 즉, 가상함수를 씀으로해서 추가되는 비용외에 최적화 기회를 놓쳐서 잃는 성능 저하도 엄청날 수 있다는 것을 말해주는 것이죠.

    지적 정말 감사합니다. 이 정도 자세한 피드백이 올 줄은 기대도 못했습니다 ㅎㅎ
  • KGCA15기최익필 2008/07/15 06:31 # 삭제 답글

    새벽에 일어나 질문 올린것을 확인하러 갔다가 찾아 오게 되었습니다. 정리잘된 답변 감사합니다. 트랙백 날립니다.
  • 뽐뿌맨 2008/07/16 00:48 # 삭제 답글

    와우~ 손수 그래프까지도 그려주시고 잘 정리해 주셔서 많은 사람들에게 도움이 되리라 생각됩니다. 잘 읽었습니다. 참고로 마이크로소프트에서는 OS를 C#으로 만드는 프로젝트를 하고 있습니다. Singularity OS라고 아직 상품화 된 것은 아니고 Research 에서 실험중입니다.
  • nineye 2008/07/16 10:54 # 삭제 답글

    저도 C++에서의 객체지향을 위한 오버헤드를 싫어하는 편인데요. 꼭 C++로 짠다고 해서 성능이 느린 것은 아닙니다. C++에서는 template이라는 매력적인 기능이 있는데요. 이를 이용하면 객체지향적인 코드보다 더욱 재사용성을 증가시키며, 성능 오버헤드는 전혀 없는 설계를 할 수 있습니다. template + unit strategy를 이용하면 정말 버릴게 하나도 없는 코드들을 만들 수 있습니다. 이와 관련된 책 하나를 소개하자면 modern design c++ 이라는 책이 있는데 이 책을 읽으면, 유명한 library인 stl이나 boost library와 같은 library의 소스도 이해 가능할 것입니다.
  • object 2008/07/16 22:23 #

    Signature-based polymorphism 말씀하시는 것 같은데요. ATL Internals를 보면 뒷 부분에 잘 나와있고 ATL이나 ATLMFC collection 라이브러리에 많이 쓰이고 있죠. Traits 클래스가 대표적이죠. 처음 봤을 땐 정말 신선했고 저도 이러한 방법론을 많이 모방했습니다.
  • 방준영 2008/07/18 17:26 # 삭제 답글

    좋은 글 잘 읽었습니다. 그런데 어셈블리 리스팅에 오타가 있네요. mov eax,dword ptr [edx+4] -> [edx+8]이 되어야겠죠.
  • object 2008/07/19 20:44 #

    감사합니다. 센스가 넘치십니다.
  • 이세희 2008/11/04 10:43 # 삭제 답글

    오 좋은글이네요~ 제 블로그에 가져가겠습니다.ㅎㅎ
  • 최종욱 2008/12/11 11:15 # 답글

    "이 그래프는 JVM이 이제 가상 함수를 직접 특정 타입에 대해 인라이닝 해서 성능을 높였을 때를 보여주고 있다. 보다시피 5번의 경우에도 성능이 상당히 우수함을 알 수 있다. (그래도 C++ 보다는 느리다)"

    "Contrast this with an experimental implementation of the JavaTM Virtual Machine, called Pep, which was implemented on the Self Virtual Machine (do not compare absolute times as these runs are on a much slower machine)." http://research.sun.com/people/mario/java_benchmarking/richards/richards.html

    썬에서, 저 그래프에 나온 성능을 절대 비교를 삼가하라고 언급했습니다. 직접 실험해보면 어떤 결과가 나올지 궁금하네요.
  • object 2008/12/11 11:32 #

    그래도 C++ 보다 느린 것은 맞습니다.
  • object 2008/12/11 11:47 #

    가상함수와 같은 마이크로벤치마크는 결코 자바가 C++를 앞설 수는 없습니다. 같아질 수는 있겠죠. 자바가 아무리 JIT과 어댑티브 옵티마이제이션을 해도 C++ + 각종 최신 최적화(e.g., PGO + IPO)를 따라가기는 힘듭니다. 물론 서버단에서 아파치나 탐캣이나 그런 곳에서는 성능이 비등비등하다는 이야기가 있지만 그건 기타 시스템 전체의 쓰루풋이죠.
  • 최종욱 2008/12/11 13:18 # 답글

    우선 제 실험 결과를 트랙백합니다. 상당히 의외의 결과가 나와서, 제가 어디선가 실수를 한 건 아닌지 검토해주셨으면 좋겠습니다. ^^ 그리고 HotJava가 아니라 HotSpot JVM을 말씀하신 것이 아닌가 싶습니다.
  • object 2008/12/11 14:24 #

    HotSpot인가 보군요. 암튼 제가 말하는 건 Jalapeno JVM 같은 겁니다.. ㅎ
  • kalstein 2009/02/12 12:51 # 삭제 답글

    참고로...sorting 같은거 할때는 C++이 더 빠르기도합니다 ^^;

    functor 사용시에 (한글로 표현시에...보통 함수자 객체라고 합니다) 비교객체가 inline화 되어 들어가기때문에, 단순히 함수포인터를 넣어서 비교하는 sort() 함수에 비해 STL의 sort가 더 빠르다고 하더군요.
    (예전에 오호...신기한데. 라고 기억하고있어서 출처는 불명확합니다 ^^;;;;)

    근데 C로 OOP구현하자면 빡세서리...-ㅁ-
  • object 2009/02/12 13:46 #

    그렇죠. C++ STL의 sort는 템플릿 함수입니다. 그래서 비교 predicate에 따라 각각의 함수가 생성되기 때문에 코드가 대부분 인라인이 될 수 있습니다. 따라서 이 부분에서 함수 호출 비용이 약간 절약 될 수 있겠죠. 반면 C qsort는 컴파일러가 그 정도까지 최적화는 하기가 매우 힘들겠습니다.

    그러나.. 비교 연산 함수 호출 비용은 C++ 쪽이 저렴할지 몰라도 원소를 순회하는데 들어가는 비용이 C++이 더욱 크기 때문에 총 소요 시간은 그래도 C가 빠를 겁니다. 제가 C++ STL로 되어있는 걸 C 스타일로 특화하여 구현하니 해당 부분은 두 배 이상 빨라지더군요.

    언제나 그렇듯이 속도 최적화를 고려할 땐 암달의 법칙을 생각해야 합니다.
  • njh1983 2009/04/26 11:27 # 삭제 답글

    좋은 글 감사합니다. 개인적으로 많은 공부가 되었습니다. ^0^
    한 가지 궁금한 점이 있는데요, 댓글중에 2008/07/14날짜에 kc님이 지적한 내용에 대한 겁니다. 결론부터 말씀드리자면, "speculation이 안 되면 cache miss가 다른 문제를 압도한다."라는 생각이 들었습니다.

    2008년에 나온 글이니까 당연히 당시 마이크로 아키텍처에 적용되는 기술을 기준으로 생각해 봤습니다.

    일단, 무조건 분기해야하는 상황이고, 단지 분기할 곳을 미리알 수 없는 문제인데 이것은 branch prediction라기보다 speculation문제라는 생각이듭니다. branch prediction은 side effect가 되겠네요. 여기에 관해서는 Patterson-Hennessy book에 잘 설명되어 있는데요. 인용을 해보자면,

    * Branches that are difficult to predict, causing misprediction stalls and restarts when speculation fails.
    * Poor instruction locality, which causes the trace cache not to function effectively.
    * Long dependences-typically caused by long-running instructions or data cache misses-which lead to stalls.

    Performance delays arising in accessing memory that cause the processor to stall.

    1) 처음부터 메모리가 캐시만큼이나 빨랐다면, 이런 복잡한 사항이 발생하지 않았을 거라고 생각합니다. BTB라는 기술도 결국은 1940s부터 폰노이만이 이야기했던 Memory Hierarchy 문제를 해결하기 위한 잡기(?)에 불과할 뿐이라고 생각합니다.

    2) 더군다나, 이 논쟁이 언급되는 시점에서 이미 SMT(Simultaneous multithreading)이 수많은 상용프로세서에 적용되었다는 것을 감안하면(SMT를 intel에서는 하이퍼스레딩이라고 마케팅 용어를 떡하니 붙여놨더군요) 여기서 논쟁이 되고있는 ILP(Instruction Level Parallelism)문제는 Issue slot에 대해서 TLP(Thread Level Parallelism)를 적용하는 것으로 퍼포먼스 저하 문제가 상당수 해결됩니다.(Patterson-hennessy 3/E, 2005, Figure 9.7.1참조)

    이렇게되면, 논쟁이 되었던 indirect branch는 cache miss가 다른 문제를 압도한다고 생각합니다. 어쨌든 제가 내린 결론에 따르면 indirect branch가 성능저하를 일으키는 골칫거리인 것은 사실이지만 그 이유는 cache miss에서 비롯된다는 것입니다. 다른 문제들은 위에 언급한 기법들로 인해 실제로는 슬쩍 가려진다고 봅니다.
    (정량적인 데이터를 뽑아내는 건 여기서 시간낭비고 그럴 만한 능력도 안 되기 때문에 은근슬쩍 넘어가겠습니다.ㅋ 뽑아낼 경우 석사학위라도 주신다면 모르겠지만ㅎ 참고로 저는 경영전공에 두 달 전에 사표를 쓴 백수랍니다.)

    사족) 대부분의 BTB는 파이프라인 시작점에 가장 가까운 곳에서 처리되어 issue slot(파이프라인)에 bubble을 at most '1'로 줄이는 것으로 알고있는데요, 제가 잘못 알고 있는 것인지 너무 단순하게 생각한 것은 아닌지 모르겠습니다. MIPS에서만 그런 건가요??
  • object 2009/04/26 14:18 #

    재밌는 의견 감사합니다. 죄송하지만 전반적으로 BPred/BTB의 작동을 오해하고 있는 것 같습니다. 거의 모든 문장에서 오류가 발견되어 어떻게 지적해야 할지 모르겠습니다 (죄송합니다. 너무 낙담시키는 말을 해서..)

    일단, “이것은 branch prediction라기보다 speculation문제라는 생각이듭니다” 은 옳지 않습니다. 간단히 지적하면 speculation(이하 투기)가 가능한 이유가 BPred/BTB가 있기 때문인데 앞뒤가 맞지 않죠. 물론 BPred 외에 load 등에도 투기적 실행이 가능합니다. 흠.. 일단 기본부터 정리해보죠.

    1. BPred/BTB가 필요한 이유는?

    간단히 말하면 분기문의 결과를 기다리려면 시간이 많이 걸리기 때문입니다. 맨 마지막 문장에 파이프라인 버블을 최대 하나 줄인다고 하는데, COD 책에 나오는 원시적인 5단계 파이프라인에서는 맞는 말일 수도 있겠습니다만 현실은 그러하지 않습니다. 최신 프로세서들은 파이프라인 단계가 10 단계를 훌쩍 넘습니다. POWER5는 14단계고 Core 시리즈도 대략 14 단계로 알고 있습니다. NetBurst는 20/30단계까지 되죠. 그런데 여기서 말하는 파이프라인 단계가 무엇을 뜻할까요? 바로 분기문의 결과를 알 수 있는 시간을 가리킨답니다. 명령어가 완료되는 단계가 아닙니다. 명령어는 그 종류에 따라 시간이 들쭉 날쭉 할 수 있겠죠. 그래서 보통 파이프라인 단계는 분기문을 기준으로 합니다. 이건 분기문 예측(=투기)가 실패했을 때 비워야 하는 파이프라인 단계의 수이기도 하고요. 그러니까 BPred/BTB가 없으면 10 사이클 이상을 스톨 해야 합니다.

    2. BPred/BTB는 언제 일어나는가?

    Fetch 단계에서 일어납니다. “대부분의 BTB는 파이프라인 시적점에 가장 가까운 곳”이라는 모호한 표현을 쓸 필요도 없이 파이프라인의 첫 단계인 명령어 인출에서 BPred/BTB가 필요합니다. 파이프라인을 최대한 채우려면 Fetch 유닛은 매 사이클마다 명령어를 넣어줘야 합니다. 그런데 지금 만난 명령어가 분기문으로 알려졌다면 (사실 이것도 할 이야기가 많은데 x86 같은 놈은 명령어 해독이 매우 힘들어서 이것 조차 쉽지 않습니다. 그래서 pre-decode를 합니다) 여기서 이 분기문을 예측해 다음 사이클에 가져와야 할 명령어 주소(next PC)를 구합니다.

    분기문을 예측한다는 건 잘 아시겠지만 방향(BPred)과 목적지(BTB)가 있습니다. 그런데 여기서 또 이 분기문의 종류가 함수 리턴이면 특화된 BTB인 RAS(Return Address Stack, 함수 리턴은 보통 간접 함수 호출로 이루어지는데 이건 예측하기가 쉬움)를 쓰고 간접 분기문이면 별도의 iBTB를 쓰기도 합니다. 보통 BTB는 직접 분기문일 때 쓰입니다. BTB나 BPred나 모두 그 핵심은 캐시죠. 과거 분기문의 결과/목적지를 캐시하는 것입니다. 그런데 BPred는 단순히 해당 분기문의 결과 값만 캐시하는 것이 아니라 이 캐시문에 영향을 줄 수 있는 다른 분기문의 결과도 함께 엮어 복잡하게 관리됩니다. BTB는 비교적 단순한 편인데 그래서 가상함수 같은 간접분기문에 손해가 발생하는 겁니다. 자주 그 목적지가 바뀌는 가상함수는 당연히 문제가 되겠죠.

    정리하면 Fetch 단계에서 명령어를 가져올 때 아직 분기문의 방향도 모르고 그 목적지도 모르기 때문에 히스토리를 기반으로 예측을 합니다. 이 예측은 바로 투기적 실행으로 이어지죠. 예측이 옳으면 좋지만 실패하면 다시 다 되돌려야만 합니다.

    그래서 언급하신 내용에 대해 답변을 드리자면

    1) 너무 무시무시하고 순진한 가정입니다 :-) 아무리 메모리가 캐시 만큼 빨라도 레지스터 보다 느립니다. 극단적으로 모든 메모리가 레지스터와 같다 하더라도 디스크 장치는 필요하죠. 그러면 무조건 메모리 계층은 발생하고 캐시는 있을 수 밖에 없습니다.

    위의 제 설명을 잘 이해하셨다면, BPred/BTB가 단순히 캐시 때문에 나온 문제가 아님을 아실 겁니다. BPred/BTB는 캐시와 상관 없이 파이프라인 효율을 높이기 위해 나온 기술입니다. BPred/BTB는 현대 프로세서에서 가장 중요한 장치로 꼽아도 손색이 없을 만큼 중요합니다. 단순히 캐시 때문이 절대 아닙니다.

    2) SMT는 이 얘기와 전혀 무관합니다. ILP 문제는 싱글 스레드 문제입니다. 싱글 스레드의 레이턴시를 어떻게 하면 줄일까가 문제인데 SMT가 그것을 해결해주는 것이 아닙니다. SMT는 최소한의 자원복제(레지스터 파일 같은 것)로 제한된 ILP로 노는 연산 유닛의 효율을 최대한 높여주는 것입니다. 전체적으로는 당연히 많은 스레드가 있으므로 SMT로 이득을 보겠지만 싱글 스레드는 그러하지 않습니다.

    3) 그래서 캐시 문제와 간접 분기는 직접적인 관련이 없습니다. 캐시 때문에 간접 분기문 문제가 생기는 것이 아닙니다. 완벽한 캐시가 있더라도 문제가 생김은 이제 아셨으리라 믿습니다. 물론 off-chip 캐시 미스의 페널티가 너무 크므로 분기 예측의 중요성이 더욱 커지기는 하지만, 캐시 문제를 해결 한다면 간접 분기문이 해결 되는 것은 아니죠.

    시간이 나면 시뮬레이터로 직접 돌려보죠. 완벽한 캐시를 놓고 바보 멍텅구리 같은 BTB를 심었을 때와 똑똑한 BTB를 심었을 때의 차이를.. 아 당장에 RAS만 없어도 성능 저하가 눈에 보인답니다.

    그런데 현실은 훨씬 복잡합니다. 자세한 구현에 들어가서 발생할 수 있는 문제는 전혀 언급도 하지 않았습니다. 예를 들어, 수퍼스케일러가 된다면? 한 사이클 내에 분기 예측이 완료하기 힘들다면? 브랜치 히스토리 레지스터는 또 어떻게 업데이트를? 파이프라인 플러쉬할 때 어떻게 효율적으로? 등등..

    짧게 쓴다고 썼는데 너무 길어졌네요. BPred/BTB는 H&P COD 책만 봐서는 완벽히 이해하기 힘듭니다. 더 궁금한 내용이나 제 답변에서 이상한 점 있으면 또 물어보세요.
  • njh1983 2009/04/28 04:54 # 삭제 답글

    [정말 죄송합니다. 삭제된 글을 복원하였습니다.]
    컴퓨터아키텍처 전공으로 석사과정에 들어가려고 준비하고 있었는데, 너무 낙담해서 뭐라 드릴 말씀이 없습니다;; 험난한 미래가 눈앞에 어른거리네요. 프로세서 설계 쪽 공부는 접어야 할 것 같습니다. 비겁한 핑계거리를 몇 가지 남겨두고서요...

    1) 캐시가 indirect branch 문제를 일으킨 범인이다라는 의미로 글을 썼다면 저는 바보인가봐요.
    2) 또한, 제가 메모리가 캐시처럼 빨라지면 memory hierarchy가 필요없어진다는 의미로 글을 썼다면 드릴 말씀이 없습니다.(쥐구멍에라도 숨고 싶습니다.)
    3) IA32 or IA64가 MIPS처럼 단순한 구조와 상대적으로 얉은 pipeline을 사용한다고 생각하고 있다면 저는 지금까지 공부를 아니한만 못한 것이 될 것 같습니다.
    4) 저는 speculation이 '투기'로 번역되는 것을 처음 알았지만, BPred/BTB와 투기가 별개의 것이라는 의미로 글을 썼다면 쥐구멍에라도 숨고 싶습니다. 다만 용어의 포함관계가 달라서 이 경우에는 speculation이라는 용어가 더 적절하지 않을까했는데, 그 의견이 문맥속에 포함되어 있지 않다면 작문 공부부터 다시 해야할 것 같습니다.
    5) SMT가 ILP를 문제를 해결 하기위해 나왔고, 이제 ILP는 해결되었기 때문에 이런 논란은 필요없다는 의미로 글을 썼다면 저는 원글을 제대로 해석 못한 난독증 환자에 불과할 것 같습니다.

    "캐시미스가 다른 문제를 압도한다"는 가설을 증명하려고 가지고 있는 책들만 읽고 있었는데 정답을 구할 수 없어서(그래도 Inside the Machine/Jon Stokes책은 내용이 비교적 자세하여 많은 도움이 되었습니다..) 구글에서 관련 논문들을 검색해 보았습니다. 그중에서 적절하다싶은 논문을 찾았는데, front-end pipeline length, L1Imiss, L2Dmiss가 주요 penalty가 된다고 나와있네요. Figure1하고 Figure12하고 직접비교해보면, 다양한 애플리케이션에서 캐시미스가 약간 우세한 정도로 나온 것같습니다.

    http://www.ece.wisc.edu/~jes/papers/Eyerman_ISPASS.pdf

    정량화 시키는 것이 제 능력밖이었다는 사실을 논문을 보면서 알게되었네요.

    아... 무엇보다 프로세서에 대해 초보적인 의견임에도 불구하고 자세하고 친절하게 내용을 설명해주신것에 대해서 뭐라 감사의 말씀을 드려야할 지 모르겠습니다. 솔직하게 김민장님은 제가 가고자하는 분야에 있어서 역할모델로 생각하고 있었습니다. 마소잡지에 기고하신 글들도 많이 보았구요. 염치없지만 저같은 선무당이 웹상에 저질 뻘글을 남기지 않도록 앞으로도 많은 질책부탁드립니다.

    아.. 저는 언제쯤 미쿡 땅을 밟아 볼 수 있을까요..
  • 댓글복원 2009/04/28 05:00 # 삭제

    [이 댓글은 object님이 작성하신 것이 실수로 삭제되어 복원한 것입니다. 죄송합니다.]

    괜찮습니다. 낙담 할 필요 전~혀 없습니다. 저도 아는거 진짜 없습니다. 아키 그룹에 몸 담고 있지만 지금 저는 소프트웨어 관련 일을 해서 자세한 건 저도 몰라요. 캐시 코히런시 프로토콜만해도 L1/L2가 같이 있을 때 설명해보라면 지금 못 합니다. 그런데 학부 컴퓨터 구조만 들으면 당연히 njh1983님처럼 오해할 수 있습니다. 그러니절대 실망하지 마세요. 그렇게라도 생각하는 것이 훌륭한 겁니다. 암튼 학부 수준의 지식에다 대학원 컴구조 수업을 듣고 좀 더 고급 마이크로아키텍처 수업 및 관련 핵심 논문 30~40개를 읽으면 대충 감을 잡으실 수 있을 겁니다.

    1) 캐시가 분기예측 실패 비용에 더 가중을 주는 것은 맞습니다. 그런데 말씀하신 간접분기의 '원인'이 캐시는 아닙니다. 캐시가 전혀 없다 생각해도, fetch 단계에서 분기 목적지를 알아야 하는데, 이 분기 목적지를 캐시하고 있는 장치가 없다면 기다릴 수 밖에 없죠. 혹시 이런 뜻에서 '캐시'를 말씀하셨다면 맞습니다 :)

    간접 분기도 말씀드렸듯이 프로시져 리턴 같이 예측이 쉬운 것도 있습니다. 그런데 가상함수는 같은 PC에서 그 분기하는 대상이 상황에 따라 가변적일 수 있습니다. C++ 가상함수 예로 흔히 나오는 rect, triangle 같은 건 draw 함수의 목적지가 프로그램의 문맥에 따라 가변적으로 바뀌겠죠. 단순한 BTB는 이런 거에 취약합니다. 그래서 history 기반의 BTB로 해결하려 하죠. 시간이 나시면 "VPC Prediction"으로 검색해보세요. 저의 훌륭하신(...) 지도교수님이 쓰신 논문입니다. 이 논문의 서두 부분을 좀 읽어 보시면 감 잡힐겁니다. 그리고 관련된 논문을 읽어보시면 훨씬 이해가 더 잘 됩니다. 논문을 읽는 방법은 그 분야에 최신 페이퍼 한 두개를 잡고 거기에 있는 related work를 하나씩 읽어나가면 됩니다.

    2) 역시 아무리 생각해도 메모리 계층 구조는 사라지기 힘듭니다. 3D-stacking이 도입되면 이제 DRAM 기반의 온칩 캐시가 들어갈 수 있습니다. 그러면 하나 더 새로운 메모리 계층이 생겨나겠죠.

    3) H&P COD 책의 5단계 MIPS는 *정말* 간단한 구조입니다. IA64는 VLIW 머신이라 좀 많이 다르고 IA32 정도는 관련 논문이나 인터넷 검색 해보면 관련 정보 많이 구할 수 있습니다.

    4) Speculation을 늘 쓰자니 귀찮아서 투기로 번역했습니다. 예측이라고도 번역하는데 이건 너무 약합니다. 일본어도 보니 투기적으로 해석하더라고요. 투기적 실행의 핵심은 예측이 가능해야 한다는 점입니다. 이 분기문이 이러이러할 것이다, 이 주소의 데이터가 곧 올 것이다, 이 두 메모리 주소는 서로 다른 곳을 가리킬 것이다.. 등등 이런 예측을 기반으로 투기적으로 실행하는 것이죠. 투기적 실행은 이런 예측을 가능케 하는 일종의 캐시 자료구조가 필요하고, 예측이 틀렸을 때 복구할 수 있는 메커니즘이 필요하기 때문에 많은 오버헤드가 들어갑니다. 전력 또한 많이 먹고요. 그래서 인텔의 아톰 같은 프로세서는 투기적 실행은 극히 자제하고있습니다. 펜티엄4의 NetBurst는 투기적 실행의 극단이라 볼 수 있겠죠.

    5) SMT가 ILP의 문제 해결를 위해 나왔다고도 볼 수 있습니다. 그런데 SMT의 목적이 싱글 스레드의 성능을 높이는 것이 주안 점은 아니죠. 오히려 손해 보죠. 그걸 감수하고 상대적으로 활용하기 쉬운 TLP를 이용하자는 것입니다. 펜티엄4에는 SMT가 들어갔다가 Core2에는 빠졌는데 SMT는 자원 배분 등 복잡한 문제가 상당히 많습니다. 그래서 아마 설계자들은 SMT를 빼는 것이 당장에 이득이라 생각했던 것 같습니다. 그리고 다시 개선해서 Nehalem에 들어왔죠. SMT는 또 Sun의 UltraSparc 같은 구조에서는 흔히 찾아 볼 수 있죠. 아예 CMT라 부르기도 하고요. 그 밖에 Itanium은 SMT는 아니지만 이벤트가 뜰 때 하드웨어 컨텍스트 스위칭을 해주고, 비슷하게 Larrabee 역시 그런 식으로 멀티스레딩을 지원합니다. 이 모두... 싱글 스레드에서 뽑을 수 있는 ILP가 캐시 미스 등으로 제약이 있어 남는 공간을 조금이라도 더 활용하기 위한 방법입니다.

    "캐시미스 가 다른 문제를 압도한다"는 말을 뒤집어 설명하면 캐시미스가 없다면 다른 문제는 별로 눈에 띄지않을 것이다와 동일하겠죠. 이 말은 합리적으로 보입니다. 그 어떤 캐시 미스와 캐시 힛 패널티 조차 없다면... 즉 메모리 레이턴시 마저 한자리수 사이클로 떨어진다면... 엄청날 겁니다. 그런데 이런 상황이 된다 하더라도 분기예측 실패로 인한 비용은 있고 아키텍트들은 이걸 가만히 보고 있지는 않을 것입니다. 이 두 문제는 서로 밀접한 관련을 가지고는 있지만 캐시가 해결되면 간접 분기의 어려움이 사라지는 것이 아닙니다. 오히려 더 두드러지겠죠.


    언급하신 논문의 내용은 이렇게 이해하셔야 합니다. 분기 예측이 실패하는 건 단순히 파이프라인 깊이와 일단 관련이 있지만 (제 답글에도 이렇게 설명해드렸죠), 그런데 다양한 캐시 미스와도 관련이 있다는 이야기 입니다. 왜냐면 분기문을 풀기 위해서는 그 분기문을 결정하는 변수들의 값을 읽어와야 하는데 이 명령어들에서 캐시 미스가 난다면 분기문 해결은 시간이더 걸리겠죠? 캐시문제가 다른 문제를 압도한다라고 생각하시는 것 보다는 미스 프리딕션 패널티는 심각한데 그 중에는 *당연히* 캐시 미스 때문데 더 커진다는 것입니다. 간접 분기문 같은 걸 생각해보죠. jump *r0 이런 꼴이 될 건데, 이 레지스터 값을 읽어와야 분기 목적지가 정확히 밝혀집니다. 그런데 레지스터 r0이 단순히 어떤 값을 load하는 걸로 끝날 수 있지만 복잡한 연산을 거쳐 나올 수도 있겠죠. 그 과정에 데이터 캐시 미스가 나버린다면? 이 이야기를 하고 있는 것 같습니다. 논문을 자세히 보지는 않았는데 보니 크리티컬 패스도 나오고 그런데.. 매우 합리적이고 당연한 이야기 입니다 :) 크리티컬 패스가 보통 길어지는 이유는 사실 대부분 캐시 미스 때문이 맞습니다. 그래서 이 비용을 줄이고자 Runahead execution이라는 방법도 제시되었고 Sun에서 직접 구현도 하고 있습니다.

    혹시 찾으실 수 있으면 "Single-Threaded vs. Multithreaded: Where Should We Focus?" 라는 논문을 읽어보세요. 거기 Figure 1을 보면 이상적인 BPred나 Cache가 있을 때 뽑을 수 있는 IPC에 대해 나와있답니다 :)

    SPEC 벤치마크의 현재 얻을 수 있는 IPC는 약 3 정도입니다. 여기서 캐시가 완벽하다면 (BPred는 그대로 두고) IPC는 5.8 정도입니다. 그런데 캐시를 그대로 두고 이번에 BPred를 완벽히 두면 5.6 정도로 보이네요. 그러니 캐시가 분기예측 문제를 압도한다는 표현은 옳지 않습니다. 여기서 이제 재밌는 결과는 이제 BPred와 $가 모두 완벽하다면? 뽑을 수 있는 이론적인 IPC는 무려 12가 됩니다. 이 정도면 이제 확실히 이해하셨으리라 믿습니다.

    하나 충고하고 싶은 것은 이렇게 대충 말 하는 건 상관 없지만 논문을 쓴다거나 아니면 발표를 할 땐 단어 하나하나를 매우 명확하게 정의 해야 합니다. "캐시가 간접 분기 문제를 일으킨 범인" 이라는 표현애서도 캐시가 정확하게 어떤 녀석이고, 간접 분기 문제는 정확히 어떤 것인지 말을 해야합니다. 캐시야 많은 사람들이 알고 있지만 "간접 분기 문제"라는 것이 무엇인지는 기본 상식으로 볼 수 없거든요. 역시 "ILP 문제" 에서도 ILP 문제는 너무 포괄적이고 두리뭉실하답니다. 보통 많은 사람들이 쉽게 "성능"이란 말을 하는데 이 성능도 레이턴시와 스루풋이 있죠.

    저는 사실 가짜 아키 전공자라서.. 아는게 별로 없어요. 1년 넘게 하는 건 그냥 소프트웨어 관련 일이라.. 아는 거 더 없답니다. 그래도 궁금한거 있음 옆에 친구/교수한테 물어서라도 알려드리죠. 제가 쓴 댓글도 나름대로 강의자료 다시 찾아보고 충분한 시간을 갖고 생각한 뒤 드리는 답변이니 영 구라는 아닐 겁니다 :)
  • njh1983 2009/04/28 04:54 # 삭제 답글

    자세한 설명과 관련 자료에 다시 한 번 감사드립니다. 저뿐만 아니라 이 스레드를 접하는 많은 초보자에게 도움이 될것 같습니다.

    몇 가지를 저혼자 또 자폭/열폭해야할 것같습니다.(혹시나 제글을 읽으시는 다른 분들께 혹시나 참고가 될까 해서 비겁한 변명 두번째 글입니다.)

    1) 댓글 마다 A4용지 한 장씩 되는 내용을 올릴려다가 모두 삭제해버리고 정리된 내용만 올리다보니 본의 아니게 문장이 섞여서 오해의 소지가 다 분한 문장을 남발했습니다. 특히 "indirect branch가 성능저하를 일으키는 골칫거리인 것은 사실이지만 그 이유는 cache miss에서 비롯된다는 것입니다."라는 문장은 두 가지 의미로 해석되어서 읽을 때마다 글쓴이인 저 스스로도 저질 문장임을 시인하지 않을 수 없습니다. 사실 제 의도는 "성능저하의 가장 큰 이유는 cache miss에서 비롯된다."였습니다. 물론 결론적으로는 제 의견이 틀렸음을 논문을 스스로 인용하여 기쁜마음으로 자폭하였습니다.

    2) 압도한다는 엉뚱한 표현은 "dominant"의 저질 번역이었습니다. 부끄럽습니다만 제가 보는 책은 국문이없어서 한글로 어떻게 표현해야할지 항상 고민합니다. Cache misses are dominant in the indirect branch penalty.라고 쓰면 오해의 소지가 좀 덜어질지 모르겠습니다.

    3) 캐시라는 애매한 표현도 부족한 문장실력과 무지에서 비롯되었습니다. 제가 의미하는 캐시는 앞서 언급하신 것처럼 Pentium 4 640기준으로 Front-end BTB(4k entries), Trance cache BTB(2k entries), Execution trace cache(also called L1Icache, 12k uops), L1Dcache(16KB), L2 cache(2MB; 256bits to L1I), Instruction/Data TLB(요건 paging 캐시이지만 역시 예측 실패시 penalty가 되므로 고려하지 않을 수 없었습니다.). 인용된 논문에서 L2Icache같은 수많은 cache penalty가 주요 penalty가되지 않는 이유는 잘 설명되어 있어 생략했습니다.(정말로 몰라서 생략한 것이 아닙니다;;;)

    4) 역시 부끄럽습니다만, 간접분기문제는 원글에서 너무나 잘 설명해주셨는데 제가 다시 설명할 필요가 있을까 싶었습니다. 그리고 Load/store에도 투기가 필요한것조차 몰랐다면 댓글을 처음부터 달지 않았을 것같습니다만, 죽은 놈 불알만지기처럼 후회해봐야 저만 바보될 것같습니다. 역시나 쓸데없는 소리지만, 간접분기가 문제를 일으킨다는 것은 Patterson-Hennessy book에 너무하다싶을 만큼 자세히 설명되어 있어서 학부에서 놀지않았다면 누구나 이해할 수 있을 것같습니다.

    5) 아.. 저는 솔직하게는 컴공 학부수준/대학원 수준이 어떤 것인지 잘모릅니다. 일명 "비전공자;문과출신"의 설움이라고 할까요. SNU 학부/대학원에서 요구하는 커리큘럼 주교제를 독학하고 있지만 7년 동안 공부해온 느낌으로는(물론 주변에 친구들은 있습니다만...) 제가 공부한 것이 학부에서 커버되는 level은 아니라고 자뻑하고 있었는데;;; 역시나 창피할 뿐이라는 것을 보여주셨기 때문에 더 할말이 없습니다.

    6) ILP문제는 "TLP문제와 대조적인 표현"으로 사용했습니다. 역시나 저질 글솜씨로 ILP가 indirect branch문제를 대표하는 것즘 되는 양 댓글을 달았는데, 전 바보인것 같습니다. 다만, TLP문제와 대조되어 사용된 ILP문제라는 것은 다음과 같은 것을 의미했습니다. 아직도 많은 분들이 젖먹던 힘까지 짜내서 연구하고는 Forwarding and bypassing, Delayed branches and simple branch scheduling, Basic dynamic scheduling(데이터 해저드 블라 블라 비슷한 것들을 말합니다만 역시나 자세한 내용은 생략...), Dynamic scheduling with renaming, Branch prediction(인용해주신 김효순 교수님 논문은 여기에 해당되겠지요.. vpc같은것), Issusing multiple instruction per cycle, Hardware speculation(역시나 김효순교수님 전문분야), Dynamic memory disambiguation, Loop unrolling, Basic compiler pipeline scheduling, Compiler dependence analysis, software pipeling, trace scheduling, Hardware support for compiler speculation(김효순 교수님 dissertation이 이것과 관련이 있었던 기억이...) 등등.. 제가 문맥에서 이것들을 제마음대로 생략해서 꼴통처럼 "ILP문제요!"라고 댓글을 단것은 이제와서 후회해도 소용이 없겠지요...

    7) 바로 앞에 6)에서 언급했던 것처럼 SMT와 TLP가 뭔지도 모르면서 ILP를 해결한다는 둥 이상한 소리를 했으면 전 사기꾼입니다. 인용한 교재 figure를 보면 쉽게 이해가 되도록 설명되어져 있었습니다. 참고로 저는 issue slot에 TLP를 적용하면 싱글쓰레드에서 존재하던 stall문제가 뿅 사려져서 해결된다고는 생각하지 않습니다. 단지 잘 설명해 주신 것처럼 processor throughput이 향상될 뿐, single thread latency 향상되는 것이 아니라는 것은 알고 있었다고 변명할 수 밖에 없을 것같습니다. 암달의 법칙은 여기서도 힘을 발휘하겠죠. 그래서 관련논문을 인용해주셨으리라 생각하고 있었습니다. "슬쩍 가려진다"라는 용어는 영어로 어떻게 표현해야할지 잘 모르겠습니다. 이럴 때는 한글이 더 좋네요.

    8) Memory Hierarchy 운운한 것은 역시나 부끄럽습니다만, 프로세서 성능향상에 가장 큰 걸림돌(bottle-neck)이 memory이기 때문에 해결되었으면 좋겠다는 의미였습니다. 물론 memory가 해결되면 역시 자세하게 설명해주신 것처럼 다른 문제들이 dominant하게 되리라는 것은 의심의 여지가 없겠습니다. performance/cost를 해결하는 것은 인류가 존재하는 한 끊이지 않는 질문이 될 것같습니다.

    다 쓰고 나니가 왠지 안구에 습기 차오르려고 하는것같습니다. 솔직히 힘이 빠지기도 하고, 컴퓨터로 먹고 살기 힘들다고 선생님/교수님/부모님/친구들 다 말리는데 한 번해 보겠다고 객기로 버틴 세월이 7년이었습니다. 병역특례 이제 마치고 대학원입학(11월)을 준비하고 있었는데 댓글 잘 못달았다가 많이 창피해져서 과연 내가 뭘할 수 있을까 자신감이 NIL상태가 됐습니다. Red ocean에 괜히 뛰어들었다가 밥값도 못하는 신세가 될거라는 두려움이 가시질 않아서 하루 종일 책이 손에 안 잡히네요. 이 정도 수준에서 대학원 입학 자체도 불투명해지면 다 때려치울 수밖에 없을 것같습니다.

    아.. 많은 분들이 방문하는 블로그에서 혼자 열폭해서 죄송합니다. 덕분에 공부 많이해놓고 결론이 이상하게 맺어가는 것같은데...

    친절하게 답변해주신 것에서 대해서 역시나 감사하는 말밖에는 못할 것같습니다. 논문은 SNU도서관에서 열어보다가 컴퓨터가 뻗어버리는 바람에 그만두었습니다. 내일 다시 한 번 열어보고 혹시나 안 된다면 염치없이 부탁드려도 될까 모르겠습니다. ^^..

    돼지인플루엔자가 뉴스에 많이 나오던데, 아무쪼록 별탈이 없어야 할텐데요.. 좋은 하루 되세요.^0^
  • Reason 2010/10/26 22:27 # 삭제 답글

    퍼포먼스 에 대한 환상에 사로잡혀 우연히 들리게되었는데, 길가다 보석을 주슨 기분입니다.
    국내웹에서 이런 해묵은 이슈에 대해 잘 정리한 포스트가 있다는거 참 멋진일이네요.

    좋은글 보고갑니다.. 건승하세요.
  • luxtella 2010/10/30 05:12 # 삭제 답글

    '프로그래머가 몰랐던 멀티코어 CPU이야기'를 읽고 감동해서 하루종일 김민장님 블로그의 글들을 읽고 있습니다. 저도 위에서 열폭하신분처럼 비전공자 출신 개발자입니다. 항상 OS와 CPU쪽은 넘사벽처럼 느껴졌었는데 김민장님 덕분에 한결 마음이 가벼워진 느낌입니다. 종종 들리겠습니다. :)
  • Ophelia_song 2011/06/17 00:34 # 답글

    이런 두고 두고 재미있는 이야기를 보게되서 정말 영광입니다.
  • 2016/11/19 03:34 # 삭제 답글

    쓰는사람 차이인가요. c# 그냥써야겟네요
  • 2017/02/08 02:31 # 삭제 답글

    네 ..잘 읽었습니다
    뭔소린지는 잘 이해가 안 가네요.ㅠ
    다음에 (배경지식 쌓아서)다시 읽어 보도록 하겠습니다(이해가 갈지도 모르니까요)
    2017년 cpu에서 돌리면 별 상관이 없지 않을까요.ㅎ
  • 티모대위 2017/11/03 10:47 # 삭제 답글

    꽤 예전 글인데도, 게다가 저는 하드웨어 엔지니어인데도 금쪽 같은 정보들이 가득하네요. 댓글까지 읽으니 더욱 감동이.... 하드웨어 엔지니어지만 임베디드 소프트웨어에 발을 들이고 있는 참에, 이런 정보는 참 반갑습니다. 임베디드 소프트웨어 입장에서는 현재의 데스크탑과 달리 이런 문제들에 여전히 민감하지요...
    많은 공부가 되었습니다.
댓글 입력 영역