Search
Duplicate
🥕

두 배 더 빠른 퀵정렬 구현 방법

간단소개
Why cmov is faster than branch instruction
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
CS
Algorithm
태그
Scrap
9 more properties
얼마 전 분기없이 작성한 퀵정렬이 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.
Plain Text
Branch Target Buffer를 CMOV는 사용하지 않는단다. 즉 History를 CMOV는 저장을 안한다.
그러면?
1.
cmov는 투기실행을 하지 않는다. (hitory 없음)
2.
cmov는 cmp가 끝날 때 까지 대기한다.
아하. 이러면 branch와 cmov는 써야 할 상황이 갈린다.
Branch Prediction을 사용하는 이유는, 대다수 프로그램에서 한 쪽 방향으로 분기할 확률이 높기 때문이다.
하지만 예측 불가능한 분기, 평균적으로 분기 확률이 50%라면? 분기예측은 자주 실패한다.
분기예측 실패는 분기예측을 하지 않는 것 보다 비용이 크다. 즉 분기를 예측할 수 없다면 분기예측을 하지 않고 cmp를 기다리는게 더 빠르다.
이게 cmov인 것이다. cmp 결과가 관측될 때 까지 그냥 대기한다.
정렬 알고리즘은 편향된 데이터가 아니라면 보통 분기를 예측할 수 없다.
그러니 정렬에서 분기예측을 빼면 랜덤한 데이터에서 분기예측 실패로 인한 파이프라인 플러시 비용을 없앨 수 있다.

결론

1.
편향적 분기가 예상되면 그냥 일반 분기로 작성한다.
2.
예측불가한 분기가 예상되면 비트연산등을 써서 분기를 없애본다. (abs()같은거 디스어셈블리 해보면 분기 없이 비트연산을 쓴다)
3.
비트연산을 사용할 수 없다면 cmov나 setcc같은 Conditional Branch 를 쓴다.