벤치마크만으로는 놓칠 수 있는 성능 회귀를 잡기 위해, CPU 명령어 수처럼 더 일관된 지표로 컴파일러가 루프를 상수 시간으로 최적화했는지를 자동으로 검사하는 방법을 소개합니다. Numba/LLVM 예제와 Rust에서의 주의점, 그리고 SQLite 쿼리 성능 테스트 응용까지 다룹니다.
David Lattimore의 최근 글에서(https://davidlattimore.github.io/posts/2025/09/02/rustforge-wild-performance-tricks.html) 그는 여러 가지 Rust 성능 트릭을 보여주는데, 그중 하나는 겉보기에는 루프처럼 보이지만 실제로는 고정된 수의 명령어로 최적화되는 기법입니다. 겉보기엔 O(n) 루프가 상수 연산으로 바뀐다면 성능에 아주 유리하죠!
하지만 이런 트릭에는 문제가 있습니다. 컴파일러가 앞으로도 계속 그렇게 최적화해 줄지 어떻게 알 수 있을까요? 컴파일러의 다음 릴리스가 나오면 어떻게 될까요? 성능 회귀를 어떻게 잡아낼 수 있을까요?
한 가지 해법은 벤치마크입니다. 코드의 속도를 측정하고 눈에 띄게 느려지면 뭔가 잘못된 겁니다. 속도가 중요하다면 이는 유용하고 중요합니다. 하지만 벤치마크는 국소성이 떨어져서, 회귀가 정확히 어디에서 발생했는지 즉시 짚어주지 못할 때가 있습니다.
이 글에서는 또 다른 접근을 다룹니다. 컴파일러가 정말로 그 루프를 없애는 최적화를 수행했을 때만 통과하는 테스트입니다.
주요 예시는 LLVM 위에 구축된 Numba 컴파일러를 사용합니다. 뒤에서 Rust 관련 사항도 언급하겠습니다.
다음 함수는 루프처럼 보이지만, 실제로는 고정된 수의 명령어로 최적화되어야 합니다:
from numba import jit
# Functions decorated with @jit are compiled to machine code
# the first time they are called.
@jit
def range_sum(n):
result = 0
for i in range(1, n + 1):
result += i
return result
assert range_sum(4) == 10 # = 4 + 3 + 2 + 1
반면, 다음 함수는 O(n) 루프로 남습니다:
from math import log
@jit
def range_sum_of_logs(n):
result = 0
for i in range(1, n + 1):
result += log(i)
return result
assert range_sum_of_logs(3) == log(3) + log(2) + log(1)
range_sum()이 상수 시간으로 최적화되었음을 어떻게 증명할까요? 서로 다른 입력 크기로 실행해 보고 실행 시간을 비교하면 됩니다. 문제는 실행 시간이 노이즈가 많다는 점입니다:
from time import time
results = []
for i in range(1_000):
start = time()
range_sum_of_logs(100_000)
results.append(time() - start)
print(
"Maximum elapsed time was "
f"{max(results) / min(results):.4}× the minimum"
)
Maximum elapsed time was 1.594× the minimum
이 노이즈 문제를 줄이기 위해 함수를 여러 번 실행하고 평균 실행 시간을 구할 수 있습니다:
from time import time
def timeit(f, *args, **kwargs):
start = time()
for _ in range(1000):
f(*args, *kwargs)
return (time() - start) / 1000
이제 좀 더 신뢰할 수 있는 속도 측정치가 생겼으니, 입력 크기에 따라 range_sum()의 속도가 어떻게 변하는지 볼 수 있습니다. 예고한 대로, 입력 크기와 무관하게 range_sum()은 대략 같은 시간이 걸립니다:
print("range_sum(10_000): ", timeit(range_sum, 10_000))
print("range_sum(100_000):", timeit(range_sum, 100_000))
range_sum(10_000): 1.3136863708496095e-07
range_sum(100_000): 1.4185905456542968e-07
반대로, range_sum_of_logs()는 입력이 10배 커지면 실행 시간도 10배 느려집니다. 즉, O(n)입니다:
print("range_sum_of_logs(10_000): ",
timeit(range_sum_of_logs, 10_000))
print("range_sum_of_logs(100_000):",
timeit(range_sum_of_logs, 100_000))
range_sum_of_logs(10_000): 0.00010006403923034668
range_sum_of_logs(100_000): 0.0009971213340759276
실행 시간을 지표로 사용하는 방법은 통하지만, 노이즈를 줄이려면 함수를 여러 번 돌려야 합니다. 실행 간 일관성이 더 높으면서도 코드가 상수 시간인지 아닌지를 알려주는 다른 측정값이 필요합니다.
컴파일러가 코드를 상수 시간으로 최적화했다면, 실행 시 기계어 명령어 수도 상수일 것입니다. 따라서 함수를 실행할 때 사용된 CPU 명령어 수를 측정해 입력 크기별로 충분히 비슷하다면, 컴파일러가 상수 시간 코드를 생성했다고 볼 수 있습니다.
물론 CPU 명령어 수가 항상 속도를 말해주지는 않습니다. 분기 예측 실패와 명령어 수준 병렬성 같은 효과(제 출간 예정인 책에서 다룹니다: https://pythonspeed.com/products/practicesperformance/) 때문에, 더 많은 명령어를 사용하는 함수가 오히려 더 빠를 수도 있습니다. 그러나 그것은 서로 다른 구현 간 비교에서의 이야기입니다. 여기서는 단일 구현을 대상으로 입력 크기와 무관하게 상수 시간으로 실행되는지를 보려는 것입니다. 이 목적에는 런타임 CPU 명령어 수가 충분합니다.
Linux에서는 perf 서브시스템으로 이를 측정할 수 있습니다. 여기서는 py-perf-event 패키지를 사용해 접근하겠습니다. 크로스 플랫폼 대안으로는 pypapi 패키지가 있습니다.
from py_perf_event import measure, Hardware
def count_instructions(f, *args, **kwargs):
# While loop is needed to workaround rare issue where
# result is 0, typically this will only run once.
while True:
result = measure(
[Hardware.INSTRUCTIONS], f, *args, **kwargs
)
if result[0] != 0:
break
return result[0]
이 측정치는 실행 시간보다 훨씬 덜 시끄럽습니다. 개별적으로 실행해 보면 알 수 있습니다:
print(count_instructions(range_sum_of_logs, 100_000))
print(count_instructions(range_sum_of_logs, 100_000))
print(count_instructions(range_sum_of_logs, 100_000))
6138911
6138911
6138911
실행에 따라 차이가 전혀 없거나, 차이가 무시해도 될 만큼 아주 미미합니다. 즉, 실행 시간을 측정할 때처럼 여러 번 반복할 필요 없이 한 번만 실행해도 됩니다.
이제 입력 크기와 무관하게 함수가 상수 시간인지 여부를 신뢰성 있게 빠르게 확인할 수 있습니다:
def is_constant_time(function, small_arg, large_arg):
"""Return if the function does constant time work.
Make sure `large_arg` is 10× as big as `small_arg`.
"""
small_instrs = count_instructions(function, small_arg)
large_instrs = count_instructions(function, large_arg)
# We allow for noise of up to 50%, given the requirement
# that the larger input be 900% larger than the smaller
# one.
return (large_instrs / small_instrs) < 1.5
print(
"Is range_sum() constant time?",
is_constant_time(range_sum, 10_000, 100_000),
)
print(
"Is range_sum_of_logs constant time?",
is_constant_time(range_sum_of_logs, 10_000, 100_000),
)
Is range_sum() constant time? True
Is range_sum_of_logs constant time? False
이 검사는 테스트 스위트에 손쉽게 통합할 수 있습니다.
Rust에서는 Linux에서 CPU 명령어 수를 perf-event2 크레이트로 측정할 수 있습니다. 다만 신경 쓸 점이 몇 가지 더 있습니다.
첫째, 함수 인자를 하드코딩하면 컴파일러에 더 많은 정보를 제공하게 되어, 실제 사용 환경에서는 일어나지 않을 최적화가 일어날 수도 있습니다. 위의 Numba 예제에서는 입력이 Python에서 오기 때문에 문제가 되지 않았습니다. 해결책은 컴파일러로부터 정보를 숨기는 std::hint::black_box()를 사용하는 것입니다. 자세한 내용은 문서를 참고하세요.
또 다른 문제는 Rust 테스트가 기본적으로 최적화 없이 컴파일된다는 점입니다. 최적화를 켜더라도 디버그 어서션의 존재 때문에 최적화가 줄어들 수 있습니다. Numba 예제에서는 Numba가 기본적으로 항상 최적화를 켜고 컴파일하므로 문제가 되지 않았습니다. 이를 해결하려면 다음과 같이 테스트를 작성할 수 있습니다:
#[cfg(test)]
mod tests {
#[cfg(not(debug_assertions))]
#[test]
fn myfunc_is_constant_time() {
// ... Write the test here ...
}
}
기본적으로 이 테스트는 건너뛰어집니다. 하지만 cargo test --profile=release로 테스트를 실행하면 이 추가 테스트가 최적화된 코드에 대해 실행됩니다.
유사한 기법은 다른 맥락에서도 사용할 수 있습니다. 이 글은 SQLite 위에 구축된 Axiom 오브젝트 데이터베이스/ORM의 몇 가지 테스트 접근에서 영감을 받았습니다. SQLite 쿼리를 실행할 때, 실행된 SQLite 바이트코드 명령어 수를 측정할 수 있는데, 이는 실행 시간 측정보다 훨씬 일관됩니다(예를 들어 Python에서는 이 API를 사용할 수 있습니다).
Axiom은 이 기능을 사용해 쿼리 성능이 기대대로 동작하는지 테스트합니다. 예를 들어 같은 쿼리를 여러 테이블 크기에서 실행해, 쿼리가 효율적인지 여부를 검사하는 테스트를 작성할 수 있습니다. 쿼리가 비효율적이라 선형 스캔이 일어나면, 실행된 바이트코드 수는 테이블 크기에 비례해 선형으로 증가합니다. 반면 쿼리가 인덱스를 사용할 수 있다면, 실행된 바이트코드 수는 선형적이지 않으며, 데이터베이스 테이블 크기와 무관하게 꽤 작은 수에 머물 것입니다.
좀 더 넓게 보자면, 약간의 창의성을 발휘하면 벤치마크에만 의존하지 않고도 많은 성능 보장을 테스트할 수 있습니다.