코드에 한 줄만 더 추가해도 프로그램은 느려지기는커녕 오히려 4배 빨라질 수 있다. 도시 전설처럼 들리겠지만, 2026년 7월 12일 한 프로그래머인 purplesyringa가 블로그에 직접 검증한 이 사례를 기록했다.
그는 당시 데이터 압축 프로그램을 만들고 있었다. 그 안에는 아주 짧은 반복문이 하나 있었는데, 핵심 코드는 단 한 줄뿐이었다 — 반복해서 테이블에서 다음 값을 찾아보고, 찾은 것을 저장하는 것이 전부였다. 깔끔하고 명료한 한 줄이었다. 하지만 프로그램을 돌려보면 속이 터질 만큼 느렸다. 그는 각종 일반적인 최적화를 시도해 봤지만 별 효과가 없었다. 결국 그는 자신조차도 황당하다고 느낀 짓을 했다. 완전히 쓸데없어 보이는 if 판단을 추가한 것이다 — “새로 찾은 값이 현재 값과 같은지”를 판단해서, 다르면 갱신하고 같으면 건너뛰는 것이었다.
이 if 문의 “헛소리” 수준은 대략 이런 느낌이다. 주머니에 만 원이 있다는 걸 이미 알면서도, 그래도 손을 집어넣어 진짜 있는지 확인한 뒤에야 문밖으로 나가는 것. 넣든 안 넣든 주머니엔 여전히 만 원이다. 하지만 신기하게도 이것을 추가하자 프로그램은 320마이크로초 걸리던 것이 80마이크로초로 줄어, 무려 4배 빨라졌다.
필자도 이 사례를 처음 읽었을 때 농담 같다고 생각했다. 하지만 이것은 마법이 아니다. 그 이면에는 현대 컴퓨터가 어떻게 답을 “추측”하는지에 관한 이야기가 숨어 있다.
공장 생산 라인의 병목
이 이야기를 이해하려면 먼저 CPU가 어떻게 일하는지 알아야 한다.
CPU를 공장 생산 라인으로 상상해 보자. 라인의 작업자들은 이전 제품이 완전히 조립될 때까지 다음 제품을 시작하지 않는다 — 그렇게 하면 너무 느리다. 그들은 작업을 아주 작은 단계로 쪼갠다. 절단, 연마, 도장, 검수…… 각 공정이 서로 다른 제품을 동시에 처리한다. 이렇게 하면 전체 라인의 처리 속도는 “가장 느린 공정 하나”에 좌우되지, “하나를 다 끝내고 다음 것을 한다”는 방식이 아니다. 이것이 바로 현대 CPU의 “명령어 수준 병렬성” — 여러 명령어를 동시에 처리해 효율을 크게 높이는 방식이다.
하지만 생산 라인에는 치명적인 약점이 하나 있다. 다음 제품이 무엇인지가 이전 제품을 다 가공하고 나서야 알 수 있다면, 전체 라인이 멈춰버린다는 것이다. 작업자들은 그냥 기다릴 수밖에 없다.
purplesyringa의 코드에서는 상황이 바로 그랬다. 그의 반복문은 j = next_j[i][j] — 현재 값 j로 테이블을 조회해 다음 j를 찾고, 그 새 j로 다음 라운드를 조회하는 식이었다. 매 라운드가 직전 라운드의 결과에 의존했다. CPU 안의 라인 작업자들은 초조하게 이전 공정의 출하를 기다렸고, 이전 공정도 그 위 공정을 기다렸다…… 전체 라인은 편도로 막힌 정체의 긴 행렬이 되어버렸다. 이것이 이른바 “데이터 의존성 체인”이 만드는 지연 병목이다.
”길을 추측”하는 내비게이션 시스템
하지만 현대 CPU에는 바로 이 상황을 상대할 수 있는 특기가 하나 있다. 그것을 “분기 예측기”라고 부른다.
여전히 공장 비유를 써보자. 라인 위에 검수 공정이 하나 있는데, 작업자가 검사 결과에 따라 제품을 A 통로로 보낼지 B 통로로 보낼지 결정한다. 그가 매번 검수가 끝날 때까지 통로를 고르지 않고 기다린다면 라인은 다시 막힌다. 그래서 공장에는 “경험 기록 시스템”이 설치된다 — 이 검수 공정에 부딪힐 때마다 시스템은 과거 99번의 선택을 바탕으로 추측한다. 이번에도 아마 A일 거라고. 작업자는 미리 제품을 A 통로로 밀어 넣는다. 맞추면 라인은 끊김 없이 매끄럽게 흐르고, 틀리면 이미 A 통로로 밀어 넣은 반제품을 거둬들이고 B 통로로 다시 시작한다.
CPU의 분기 예측기가 바로 이 시스템이다. 프로그램이 과거에 각 “갈림길”에서 내린 선택을 기록해 두고, 복잡한 회로를 통해 다음 번 향방을 예측한다. 현대 CPU의 분기 예측 정확도는 보통 95% 이상 — 대부분의 인간이 내리는 결정보다 정확도가 높다.
purplesyringa의 통찰은 이랐다. 그의 코드에는 뚜렷한 “갈림길”(if-else 같은 것)이 없었지만, 데이터 의존성 체인 자체가 보이지 않는 “대기”였다. 그에게 번뜩이는 생각이 들었다. 명시적인 갈림길을 하나 넣어서 분기 예측기를 끌어들이면 어떨까?
그 “헛소리” if 문의 진짜 역할
그가 추가한 if 문의 논리는 이랬다. 조회 결과가 현재 값과 다른지 판단해서, 같으면 아무것도 하지 않고 다르면 갱신한다. 대부분의 경우 조회된 값이 현재 값과 실제로 같기 때문에, CPU의 분기 예측기는 재빨리 “학습”한다. 이 if 문의 몸통은 거의 절대 실행되지 않는다는 것을.
그러자 CPU는 대담하게 추측한다. 다음 라운드에서도 if 몸통을 건너뛴다고. 건너뛴다고 추측하면, 직전 라운드의 결과를 기다릴 필요가 없다 — 그냥 j가 변하지 않았다고 가정하고 앞으로 달려간다. 라인이 다시 움직이기 시작한다. 여러 라운드의 반복문을 병렬로 처리할 수 있게 된다.
가끔 조회 결과가 정말 다를 때면, 분기 예측기는 자신이 틀렸음을 알고 이미 잘못 들어간 반제품을 지우고, 올바른 j 값으로 그 라운드를 다시 돈다. 이 과정을 “분기 예측 실패 페널티”라고 한다. 하지만 틀리는 비율이 극히 낮아서, 이 비용은 내내 가만히 기다리는 비용에 비하면 아주 작다.
결과적으로 완전히 쓸데없어 보이던 if 문 하나가 분기 예측기에 “추측할 수 있다”는 신호를 주었다. 그것은 본래 직렬로만 실행할 수 있었던 의존성 체인을, 투기적으로 병렬 실행할 수 있는 라인으로 바꾸어버렸다.
컴파일러의 “선의”가 부른 참사
이야기는 여기까지가 반쪽짜리다. 더 골치 아픈 상대가 하나 더 있다. 바로 컴파일러다.
컴파일러는 프로그래머가 쓴 인간이 읽을 수 있는 코드를 CPU가 실행할 수 있는 기계 명령어로 번역하는 프로그램이다. 현대 컴파일러는 매우 똑똑하다 — 똑똑해서 “무용 코드”를 자동으로 알아채고 그냥 지워버린다. 컴파일러 눈에는 purplesyringa가 넣은 그 if 문이 “A가 A와 같지 않을 때만 A를 갱신한다”고 말하는 것이니 당연히 헛소리다. 컴파일러는 비웃으며 이를 최적화해 없앤다.
프로그래머는 CPU의 분기 예측기를 속이려 했지만, 컴파일러가 먼저 속이는 도구를 압수해 버린 셈이다.
여기가 바로 글 제목에 나온 “보수적 결정”의 의미다 — 그리고 필자가 이 사례에서 가장 씹을 게 많은 부분이라고 생각하는 지점이다. 컴파일러는 “프로그램의 의미를 바꾸지 않는다”는 원칙을 엄격히 지킨다 — 네가 쓴 것이 논리적으로 쓸모없으면, 나는 번역해 주지 않는다. 하지만 컴파일러가 모르는 사실이 있다. 어떤 코드의 진짜 가치는 하드웨어 계층에 숨어 있다는 것, 즉 CPU에게 투기적으로 실행할 수 있는 신호를 주고 있다는 것이다.
사실 이것은 삼자 간의 줄다리기다. CPU는 공격적이다. 죽어라 추측하고, 어떻게든 일을 미리 해치운다. 컴파일러는 보수적이다. 의미를 엄격히 지켜, 더 하지도 덜 하지도 않는다. 그리고 프로그래머는 그 중간에 서서, CPU의 공격성을 이용하고 싶으면서도 컴파일러의 보수성을 속여야 한다.
”여긴 건드리지 마”라는 봉인
purplesyringa가 찾아낸 방법은 C 언어의 volatile이라는 키워드를 쓰는 것이었다. 이 단어는 C 언어에서 컴파일러에게 “여긴 건드리지 마”라는 봉인을 붙이는 것과 같다 — 컴파일러에게 이렇게 말하는 것이다. 이 데이터는 네가 모르는 사이에 바뀔 수 있으니 최적화하지 말고 매번 성실하게 읽으라고.
이 봉인을 붙인 뒤로 컴파일러는 if 조건이 “영원히 성립하지 않는” 헛소리라고 더 이상 생각하지 않게 되었고, 그래서 if 문을 유지했다. if가 살아남으면 분기 예측기가 추측할 거리가 생기고, 라인은 다시 병렬로 돌아가기 시작한다.
나중에 Lobsters 커뮤니티의 토론에서 다른 프로그래머인 ibookstein은 C++20의 [[unlikely]] 표기(컴파일러에게 “이 분기는 거의 안 지나간다”고 명시적으로 알려주는 것)를 써도 비슷한 효과가 난다는 것을 발견했다. 하지만 purplesyringa는 volatile 봉인 방식이 생성하는 기계어 품질이 더 좋고, 특정 컴파일러에만 국한되지도 않는다고 지적했다.
더 큰 개념: 값 투기(value speculation)
Lobsters 토론 스레드에서 누군가 이 기법에는 정식 명칭이 있다고 지적했다 — “값 투기(value speculation)“다. 핵심 아이디어는 이렇다. 어떤 값의 취득에 대해 “대개 맞히는” 휴리스틱이 있을 때, 분기 예측기를 이용해 투기적으로 실행함으로써 데이터 의존성 체인을 깨뜨릴 수 있다.
이 개념은 더 이른 연구와 블로그(Paul Khuong, Per Vognsen 등의 작업)까지 거슬러 올라간다. mazzo.li의 고전적인 글에서는 같은 기법이 연결 리스트 순회를 가속하는 데 쓰였다. 연결 리스트를 순회할 때 다음 노드의 주소는 현재 노드가 가진 포인터에 달려 있는데, 이것도 역시 데이터 의존성 체인이다. 하지만 “다음 노드는 메모리상에서 현재 노드 바로 옆에 있다”고 추측한다면, CPU가 미리 가져오게(prefetch) 할 수 있고, 처리량을 14GB/s에서 45GB/s로 끌어올릴 수 있다(데이터가 CPU 캐시에 있을 때).
purplesyringa의 if 기법과 값 투기는 본질적으로 같은 것이다. 비싼 대기를 싼 추측으로 대체하는 것.
당신을 가로막는 것들
이 이야기에서 가장 흥미로운 점은, “네가 생각하는 것 vs 실제”의 충돌이 세 겹으로 겹쳐 있다는 것이다.
첫 번째 층. 인간의 직관은 “코드가 적을수록 빨리 돈다”고 생각한다. 하지만 이 사례에서는 한 줄을 더 넣자 오히려 빨라졌다 — 그 줄의 기능이 연산이 아니라 신호를 보내는 것이기 때문이다.
두 번째 층. 컴파일러는 “논리적으로 쓸모없는 코드는 지워야 한다”고 생각한다. 하지만 어떤 코드의 쓸모는 논리 의미 계층이 아니라 하드웨어 동작 계층에 숨어 있다.
세 번째 층. 우리는 보통 “틀리면 대가를 치르니 차라리 추측하지 않는 게 낫다”고 생각한다. 하지만 현대 CPU의 설계 철학은 정반대다. 대담하게 추측해, 맞히면 이득, 틀려도 어차피 처음부터 다시 하면 그만이다. 맞힐 확률이 충분히 높기만 하면, 전체적으로는 이득이다.
이 이야기에는 거창한 결말은 없다. 그저 한 프로그래머가 압축 알고리즘을 최적화하던 중 우연히 부딪힌 반직관적인 사실 하나일 뿐이다. 하지만 이 작은 if 문을 통해, 당신은 현대 컴퓨터 저수준에 숨겨진 정교한 진실 하나를 보게 된다. CPU는 도박꾼이고, 컴파일러는 변호사이며, 가장 훌륭한 프로그래머는 언제 법조인을 속여 도박꾼에게 정보를 넘겨야 하는지 아는 사람이다.
참고 출처
- Purplesyringa 블로그: Quadrupling code performance with a “useless” if (2026년 7월 12일, 원문에 완전한 기술 세부사항, 코드 예제, 성능 데이터가 기록됨)
- Lobsters 커뮤니티 토론 (s/1an425): 104점, 14개 댓글, ibookstein이 발견한
[[unlikely]]대안과 mikejsavage가 지적한 “값 투기” 개념 링크 포함 - mazzo.li: Beating the L1 cache with value speculation (2021년 7월, 연결 리스트 순회에서 값 투기 기법의 활용을 자세히 소개하며 성능 비교 도표 첨부)