아 오늘 오후엔 일 좀 하려 했는데 자꾸 도발 걸리네.


이번엔 파이프라인과 분기에 대해서 알아보자. (pipeline - 링크)


현대의 CPU들은 명령어를 읽고 해석하고 수행하는 일련의 과정들을 파이프라인으로 세분화해서 처리해. 아키텍처에 따라 파이프라인을 몇단계로 어떻게 나누는가에 따라 다르지만 지금 정리하고자 하는 내용들은 크게 다르지 않으니까, 지금 내가 쓰고 있는 cortex-m3 기준으로 설명할게.


cortex-m3의 파이프라인은 3단계로 구성되어있어. Fetch - Decode - Execute. (링크)


* Fetch - 메모리에서 명령어를 읽어온다.

* Decode - 읽어온 명령어를 해석한다.

* Execute - 해석한 명령어를 실행한다.


간단하게 표현하자면, 컨베이어 벨트에 3명의 작업자가 분업을 하고 있는 상황을 떠올리면 될거야.


                  Fetch   Decode   Execute

   │  instrA       A

   │  instrB       B        A

PC │  instrC       C        B        A

   │  instrD       D        C        B

   ↓  instrE       E        D        C



그림으로 표현하면 위와 같아.


자 그럼 여기서 분기문이 파이프라인에 주는 영향을 보자. instrA가 instrD로의 분기라면 어떻게 될까?


                  Fetch   Decode   Execute

   │  br D        br D

   │  instrB       B      br D

PC │  instrC       C        B       br D

   │  instrD       D              (stalled)

   │  instrE       E        D     (stalled)

   ↓  instrF       F        E        D



다음 인스트럭션 B와 C를 Fetch하고 Decode해놨는데 분기(branch)하면서 의미가 없어졌지? 그럼 분기 후 명령어들을 다시 Fetch, Decode, Execute를 하기 위해 정지(stalled)될 수 밖에 없고, 그래서 파이프라인의 단계가 많은 아키텍처일수록 분기로 인한 성능 손실이 발생해. (pipeline stall - 링크). 물론 이를 해결하기 위해 branch prediction이라던지 speculative execution같은 것도 있긴 하지만 일단 여기서 설명하기에는 너무 방대하므로 링크로 대체할게. (branch prediction 링크, speculative execution 링크)

위와 같은 무조건 분기도 있지만 조건 분기도 있어. 다음과 같은 코드를 보자.

if(condition) {
  true_statements;
}
else {
  false_statements;
}


요 코드를 컴파일하면 컴파일러가 생성가능한 코드는 다음과 같이 크게 두 가지야. (pseudo code로 표현. 물론 컴파일러와 환경에 따라 table based branch라던지 다른 분기 구조를 가질 수 있음)


condition이 참일때 브랜치

condition이 거짓일 때 브랜치

  branch if(condition == true) to T

  false_statements

  ret

T:

  true_statements

  ret

  branch if(condition == false) to F

  true_statements

  ret

F:

  false_statements

  ret 


수행되는 결과는 둘 모두 같아. 그런데 자세히 보자.


첫번째의 경우는 condition이 true면 분기를 하니까 pipeline이 stall테고,

두번쨰의 경우는 condition이 false면 분기를 하니까 pipeline이 stall되겠지?


그럼 똑같은 코드라 해도 컴파일러가 어떤 분기 구조를 택하는가에 따라 소요되는 클럭싸이클이 달라질 거라는걸 쉽게 예상할 수 있을거야.



자, 이제 그분이 콤마 연산자를 이용해 최적화를 했다고 주장하시는 코드를 한번 보자(링크). 그 분께서 고안하셨대 키키

비교를 위해 디스어셈블 결과도 같이 넣었어. 여기(링크)서 확인하면 될거야.



int test_plain(unsigned int p)

{

  if((p & 0x000000ff)) return 0;

  if((p & 0x0000ff00)) return 1;

  if((p & 0x00ff0000)) return 2;

  if((p & 0xff000000)) return 3;

  return -1;

}

int test_mo_fuckers(unsigned int p)

{

  int r = -1;

  if((r = 0, (p & 0x000000ff)) ||

     (r = 1, (p & 0x0000ff00)) ||

     (r = 2, (p & 0x00ff0000)) ||

     (r = 3, (p & 0xff000000))) return r;

  return -1;

} 
test_plain(unsigned int):
  xorl    x, x
  testb   %dil, %dil
  jne     .L2
  testl   $65280, i
  movl    $1, x
  jne     .L2
  testl   $16711680, i
  movl    $2, x
  je      .L8
.L2:
  rep ret
.L8:
  andl    $-16777216, i
  cmpl    $1, i
  sbbl    x, x
  orl     $3, x
  ret 		 test_mo_fuckers(unsigned int):
  testb   %dil, %dil
  jne     .L12
  testl   $65280, i
  je      .L17
  movl    $1, x
  ret
.L12:
  xorl    x, x
  ret
.L17:
  testl   $16711680, i
  jne     .L14
  andl    $-16777216, i
  jne     .L15
  movl    $-1, x
  ret
.L14:
  movl    $2, x
  ret
.L15:
  movl    $3, x
  ret 



코드가 똑같진 않지만 대략 연관성 있는 애들끼리 같은 색으로 묶었어.


자. 현명한 프겔러들이라면 이 두 코드의 소요클럭이 다를 때, 어떻게 해석해야 맞는 해석일까? 내가 생각하는 그럴듯한 해석은 '아, 분기가 다르게 구성돼서 파이프라인 스톨 땜에 소요 클럭이 달라졌을 것 같네.'인데, 프겔러들은 어떻게 생각해?


컴파일러 입장에서는 condition이 true일 때가 많을지 false일 때가 많을지 알 수 없을 때 지멋대로 분기가 구성될 때가 많아. 그럼 컴파일러에게 condition이 true일 때가 더 자주 있는지 false일 때가 더 자주 있는지 알려줄 수 있다면 효율적인 코드를 생성하는데 도움이 되겠지?

이 분기 힌트를 어떻게 주는가는 컴파일러마다 다 다른데, boost를 쓰면 cross-platform하게 BOOST_LIKELY(x)나 BOOST_UNLIKELY(x)를 사용할 수 있고(링크), gcc를 쓴다면 리눅스 커널에서처럼 직접 likely(), unlikely()를 디파인해서 쓸 수 있어(링크).


어차피 저 코드는 모든 분기가 같은 확률이라 걍 내 멋대로 분기힌트를 줬는데 생성된 코드를 한번 보자. (링크)



int test_plain(unsigned int p)

{

  if(unlikely(p & 0x000000ff)) return 0;

  if(unlikely(p & 0x0000ff00)) return 1;

  if(unlikely(p & 0x00ff0000)) return 2;

  if(unlikely(p & 0xff000000)) return 3;

  return -1;

}

 int test_mo_fuckers(unsigned int p)

{

  int r = -1;

  if((r = 0, unlikely(p & 0x000000ff)) ||

     (r = 1, unlikely(p & 0x0000ff00)) ||

     (r = 2, unlikely(p & 0x00ff0000)) ||

     (r = 3, likely(p & 0xff000000))) return r;

  return -1;

}

test_plain(unsigned int):

  testb   %dil, %dil

  jne     .L3

  testl   $65280, i

  jne     .L4

  testl   $16711680, i

  jne     .L5

  andl    $-16777216, i

  cmpl    $1, i

  sbbl    x, x

  orl     $3, x

  ret

.L3:

  xorl    x, x // return 0

  ret

.L4:

  movl    $1, x // return 1

  ret

.L5:

  movl    $2, x // return 2

  ret

test_mo_fuckers(unsigned int):

  testb   %dil, %dil

  jne     .L11

  testl   $65280, i

  jne     .L12

  testl   $16711680, i

  jne     .L13

  andl    $-16777216, i

  movl    $3, x

  je      .L16

  rep ret

.L16:

  movl    $-1, x // return -1

  ret

.L11:

  xorl    x, x // return 0

  ret

.L12:

  movl    $1, x // return 1

  ret

.L13:

  movl    $2, x // return 2

  ret



흐미 성님 분기힌트만 줬는데 두 코드 분기 구조가 비슷해져부렀소. 콤마연산자를 활용해서 깨알같이 최적화 했는데 이게 어찌된 일이오.

는 무슨 씨발 그냥 저게 최적화가 아닌거지 뭐.


내가 여기까지 썼다면 예상되는 저 새끼의 반응은 '두 코드 생성되는 결과 다르네!! 셀프디스 축하요!!' 요 지랄로 예상한다. 그래서 가져왔어.

이유는 모르겠지만 c++로 컴파일 안하고 c로 컴파일하니까 두 코드가 똑같더라고? 직접 확인해봐. (링크)


생성되는 코드가 같은데 도대체가 뭘 최적화했다고 생각하시는지는 소인은 짬밥이 부족해서인지 잘 모르겠소만, 어쨌든 해보니까 소요 클럭이 다르대더라고??


근데 이 새끼가 뭐라고 해석했는지 한번 살펴보자.


하위 16비트만을 비트 연산할때와 상위 16비트를 계산할때 크게 벌어진다는 것,

   즉 super pipeline 단계중, execute 단계에서의 세분화가

   word -> byte ( -> bit ? 는 아니겠지 코어 제조 비용이 급증할테니 ㅋㅋ ) 단위로 분기되어 쪼개져 있다는거지.

   고로 상위 16bit word의 ( & 0xFFFF0000 ) 연산이 시행되는 시점에서 아얘 0 이면 바로 빠져 나왔고,

   그 결과 분기까지의 절차적 거리가 동일하기 때문에 ( 어차피 return 말곤 할게 없음 ),

   두 가지 케이스 ( 0x00FF0000 과 0x00000000 의 입력조건 )의 클럭수가 같게 나오는거지.


따라서 비트 연산도 상위 워드는 상위 워드끼리, 하위 워드는 하위 워드끼리 모아줘야

컴파일러의 short circuit 상의 최적화 뿐만 아니라

제대로 super pipeline 상의 short circuit 의 효과를 볼 수 있다는 것.

return code 를 하나로 묶냐 아니냐 에 따라 short circuit 효율 자체가 크게 좌우될 수 있다는 것.


콤마 연산으로 상태를 마킹하고 ( overwrite 만 하기 때문에 writeback+readout 비용은 없음 )

비용이 비싼 연산 앞에 묻어가는 트릭을 말씀드렸슴돠~


하 시발... 워드 바이트 비트로 쪼개지기는 무슨 씨발 네 박자 개소리 위에 쉴새없이 비트를 쪼개는 병신새끼...



여기서 잠깐 정상적인 가설 검증의 루트를 살펴 보자.


1. 가설을 세운다.

2. 관측 한다.

3. 관측 결과가 가설과 안맞으면 1.로 돌아가 새 가설을 세운다.

4. 가설 검증 성공!!


이 가설 검증 루트를 통해 '도대체 저새끼는 왜 저지랄을 떠는가?'에 대한 가설을 세워보기로 했어.


가설1 : 저새끼의 가설 검증 루트가 남들과 다르다. 저 새끼의 가설 검증 루트는 다음과 같을 것이다.

  1. 관측한다.

  2. 가설을 세운다.

  3. 나님은 항상 옳으시다!!

  4. 가설 검증 성공!!!



프갤러들아 내 가설이 맞는지 틀린지 다 함께 저 새끼의 행동을 관측해보자.



3줄 요약

* 분기를 하면 pipeline stall 때문에 성능이 저하될 수 있다.

* major 분기를 알 수 있다면 컴파일러에게 분기 힌트를 줘서 효율적인 코드를 생성하게 할 수 있다.

* 근데 사실 이런 테크닉이 realtime 쪽으로 팔 거 아니면 별 쓸데 없음요 ㅋ 그냥 상식삼아 알아두면 돼.