GCC와 clang이 정수 합산 루프를 어떻게 최적화하는지 살펴보며, 특히 clang이 닫힌형 공식을 찾아 O(n) 코드를 O(1) 계산으로 바꾸는 놀라운 순간을 다룹니다.
내가 썼고, LLM이 교정했습니다.
자세한 내용은 마지막에 있습니다.
가끔씩 컴파일러는 정말 영리한 묘기로 저를 놀라게 합니다. 처음 이 최적화를 봤을 때는 거의 믿기 어려웠습니다. 저는 루프 최적화를 보고 있었고, 주어진 값까지의 모든 수를 더하는 이런 단순한 함수를 작성했습니다.
여기까지는 꽤 괜찮습니다. GCC는 몇 가지 사전 검사를 수행한 뒤, lea를 사용해 효율적으로 수를 더하는 루프로 들어갑니다(이건 전에 본 적이 있습니다). 하지만 루프를 자세히 보면 조금 이상한 점이 보입니다.
.L3:
lea edx, [rdx+1+rax*2] ; result = result + 1 + x*2
add eax, 2 ; x += 2
cmp edi, eax ; x != value
jne .L3 ; keep looping
컴파일러는 우리가 x와x + 1을 더하게 된다는 사실을 이용해 한 번에 두 수를 처리할 수 있음을 영리하게 알아냈습니다. 이것은 x*2 + 1을 더하는 것과 같습니다. 정말 교활하죠1!
최적화 수준을 -O3로 올리면 컴파일러가 병렬 덧셈을 사용해 루프를 벡터화하려고 더 열심히 일하는 것을 볼 수 있습니다. 정말 영리합니다.
이것은 모두 GCC에 대한 이야기입니다. 이제 우리의 코드에 대해 clang이 무엇을 하는지 봅시다.
여기서 저는 거의 의자에서 떨어질 뻔했습니다. 루프가 없습니다! Clang은 value가 양수인지 확인하고, 그렇다면 다음을 수행합니다.
lea eax, [rdi - 1] ; eax = value - 1
lea ecx, [rdi - 2] ; ecx = value - 2
imul rcx, rax ; rcx = (value - 1) * (value - 2)
shr rcx ; rcx >>= 1
lea eax, [rdi + rcx] ; eax = value + rcx
dec eax ; --eax
ret
도대체 무슨 일이 벌어지고 있는지 처음에는 전혀 분명하지 않았습니다. 수학을 조금 되짚어 보면, 이것은 다음과 같습니다.
v + ((v - 1)(v - 2) / 2) - 1;
괄호를 전개하면:
v + (v² - 2v - v + 2) / 2 - 1
조금 정리하면:
(v² - 3v + 2) / 2 + (v - 1)
(v - 1)에 2 / 2를 곱하면:
(v² - 3v + 2) / 2 + (2v - 2)/2
이들을 합치고 소거하면:
(v² - v) / 2
이를 단순화하고 인수분해하면 v(v - 1) / 2가 되는데, 이것이 바로 “정수의 합”에 대한 닫힌형 해입니다! 정말 놀랍습니다2. 우리가 작성한 O(n) 알고리즘이 O(1) 알고리즘으로 바뀐 것입니다!
컴파일러와 20년 넘게 작업해 왔음에도, 여전히 저를 놀라게 하고 즐겁게 한다는 점이 정말 좋습니다. 컴파일러를 훌륭하게 만들기 위해 쏟아부어진 수년간의 경험과 노고는 정말로 겸허하게 만들고, 또 영감을 줍니다.
이 시리즈도 거의 끝나갑니다. 할 말은 훨씬 더 많지만 그건 다음 기회로 미뤄야겠습니다. 내일은 조금 다를 것입니다. 그때 뵙겠습니다!
이 글과 함께하는 영상을 보세요.
이 글은 Advent of Compiler Optimisations 2025의 24일차 글입니다. 이 시리즈는 25일 동안 컴파일러가 우리의 코드를 어떻게 변환하는지 살펴봅니다.
← 조금 다르게 바꿔 보기 | 감사합니다 →
이 글은 인간(Matt Godbolt)이 작성했고, LLM과 인간이 검토하고 교정했습니다.
Patreon이나 GitHub에서 Compiler Explorer를 후원하시거나, Compiler Explorer Shop에서 CE 상품을 구매해 주세요.
초기 코드의 일부 검사는 홀수/짝수를 확인하고 그에 맞게 처리합니다.↩
컴파일러는 왜 이 정확한 시퀀스를 생성하고, 조금 더 직관적인 시퀀스는 생성하지 않을까요? 제 생각에는 부분적으로는 다른 경우에 오버플로가 날 수 있는 상황을 피하기 위해서이고, 또한 clang이 유도 변수를 추적하고 추론하는 방식의 부수 효과이기도 한 것 같습니다. 하지만 확실히는 모르겠습니다.↩
2025년 12월 24일 CST 06:00:00에 게시됨.
Matt Godbolt는 시카고에 살고 있는 C++ 개발자입니다. 그는 Hudson River Trading에서 아주 재미있지만 비밀인 일들을 하고 있습니다. 그는 Two's Complement 팟캐스트의 공동 진행자입니다. Mastodon이나 Bluesky에서 그를 팔로우하세요.
Copyright 2007-2026 Matt Godbolt. 별도로 명시되지 않는 한, 모든 콘텐츠는 Creative Commons Attribution-Noncommercial 3.0 Unported License에 따라 라이선스됩니다. 이 블로그는 Malcolm Rowe의 MalcBlogSystem으로 구동됩니다. 참고: 이것은 제 개인 웹사이트입니다. 이 페이지들에 표현된 견해는 오직 제 개인의 것이며 제 고용주의 견해가 아닙니다.