얼마 전 분기없이 작성한 퀵정렬이 80% 가량의 성능향상을 가져온다는 글을 보았다. https://arxiv.org/abs/1604.06697

기본적인 아이디어는 branch를 쓰지 않고, setcc와 cmov같은 Conditional Move를 사용한다는 것이다.

그런데 생각을 해보면.. Branch와 Conditional Move가 뭐가 다를까?

1. 어차피 setcc와 cmov도 비교(cmp) 가 끝날 때 까지 파이프라인 stall이 걸린다.
2. cmov는 History가 기록되지 않는가?
3. cmov는 투기적 실행을 하지 않는가?

인텔 메뉴얼을 살펴보자. (Intel 64 and IA-32 Architecture Optimization Reference Manual, 2016. Order Number: 248966-032.)

• It reduces the possibility of mispredictions.
• It reduces the number of required branch target buffer (BTB) entries.
Conditional branches that are never taken do not consume BTB resources.

Branch Target Buffer를 CMOV는 사용하지 않는단다. 즉 History를 CMOV는 저장을 안한다.

그러면?

1. cmov는 투기실행을 하지 않는다. (hitory 없음)
2. cmov는 cmp가 끝날 때 까지 대기한다.

아하. 이러면 branch와 cmov는 써야 할 상황이 갈린다.

Branch Prediction을 사용하는 이유는, 대다수 프로그램에서 한 쪽 방향으로 분기할 확률이 높기 때문이다.

하지만 예측 불가능한 분기, 평균적으로 분기 확률이 50%라면? 분기예측은 자주 실패한다.

분기예측 실패는 분기예측을 하지 않는 것 보다 비용이 크다. 즉 분기를 예측할 수 없다면 분기예측을 하지 않고 cmp를 기다리는게 더 빠르다.

이게 cmov인 것이다. cmp 결과가 관측될 때 까지 그냥 대기한다.

정렬 알고리즘은 편향된 데이터가 아니라면 보통 분기를 예측할 수 없다.

그러니 정렬에서 분기예측을 빼면 랜덤한 데이터에서 분기예측 실패로 인한 파이프라인 플러시 비용을 없앨 수 있다.