Inlining, Loop Transformations, and Auto-Vectorization TODO
Concept
Inlining is the transformation that replaces a function call with the callee's body; the bigger payoff isn't removing call overhead itself but eliminating the call boundary, which unlocks follow-on optimizations like constant propagation and dead-code elimination. The trade-off is larger code size and more instruction-cache pressure, so compilers decide whether to inline using heuristics based on function size and call frequency. Loop transformations include unrolling, loop-invariant code motion (LICM), loop interchange, fusion and fission, and tiling; their common goal is to improve locality and instruction-level parallelism without breaking data dependencies. Auto-vectorization is the transformation that packs loop iterations with no cross-iteration dependencies into SIMD instructions, but it frequently fails because of possible pointer aliasing, irregular control flow, and the constraint that floating-point associativity must not be changed. So whether vectorization actually happened shouldn't be guessed — it needs to be confirmed from the compiler's optimization report or the generated assembly.
When a hot loop doesn't speed up as expected, the cause is usually not the algorithm but vectorization failing to kick in, or inlining being blocked so that every downstream optimization falls through.
Code & Formula
# 인라이닝·루프 변환·자동 벡터화 — LICM(불변식 끌어올리기)과 루프 언롤링이 연산 횟수를 어떻게 줄이는지 센다.
def naive_scale_shift(xs, a, b):
ops = 0
out = []
for x in xs:
invariant = a * b + 1 # 매 반복 다시 계산됨 (루프 불변식인데 안 끌어올림)
ops += 2
out.append(x + invariant)
ops += 1
return out, ops
def licm_scale_shift(xs, a, b):
ops = 0
invariant = a * b + 1 # 루프 밖으로 한 번만 끌어올림
ops += 2
out = []
for x in xs:
out.append(x + invariant)
ops += 1
return out, ops
def unrolled_sum(xs, factor=4):
# 루프를 factor개씩 묶어 반복 증분/조건 검사 오버헤드를 줄인다 (unrolling)
total, n, i, iterations = 0, len(xs), 0, 0
while i + factor <= n:
total += xs[i] + xs[i + 1] + xs[i + 2] + xs[i + 3]
i += factor
iterations += 1
while i < n:
total += xs[i]
i += 1
iterations += 1
return total, iterations
xs = list(range(1, 21))
r1, ops1 = naive_scale_shift(xs, 3, 5)
r2, ops2 = licm_scale_shift(xs, 3, 5)
assert r1 == r2
total_unrolled, iters = unrolled_sum(xs, factor=4)
assert sum(xs) == total_unrolled
print(f"결과 동일: {r1 == r2}, naive 연산수={ops1}, LICM 연산수={ops2} "
f"(불변식 재계산 {len(xs) - 1}회 절약)")
print(f"합계={total_unrolled}: naive 반복수={len(xs)}, unrolled(factor=4) 반복수={iters} "
f"(루프 오버헤드 ~{len(xs) - iters}회 절약)")
docs/code/algorithms/algorithms-23.py
Exercise
Write a simple array-sum loop and compile it with optimization-report flags on, then compare whether SIMD instructions appear in the assembly before and after telling the compiler the pointers don't alias.
Practical Connection
When looking at the performance of a matching engine or a signature-verification loop written in Go, this leads directly to the habit of checking the compiler's output for the inlining budget and whether bounds-check elimination happened.
Where it lands in Jayverse
- Verex: confirm vectorization on the CLOB matching loop before crediting an algorithm change. Read the compiler's optimization report or the generated assembly for the matching engine's hot loop, and attribute a speedup to vectorization/inlining only when it's confirmed there, not guessed from wall-clock alone.
- Verex: check pointer-aliasing first when a hot loop won't vectorize. For signature-verification or order-matching code, telling the compiler pointers don't alias is often the cheap fix before reaching for an algorithmic rewrite.
- gitboard: surface "was this loop vectorized" as a checked fact. If gitboard ever tracks service performance, pull the vectorization status from the build's optimization report next to latency numbers, instead of assuming it happened.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| the bigger payoff | 더 큰 이득, 진짜 효과 · 겉으로 드러난 이유보다 실제로 더 중요한 이점. "the bigger payoff isn't removing call overhead" |
| call boundary | 함수 호출 경계 · 함수를 부르고 넘어가는 지점 자체를 말할 때. "eliminating the call boundary" |
| cache pressure | 캐시 압박, 부담 · 캐시 공간이 부족해지며 성능에 주는 부담. "more instruction-cache pressure" |
| kick in | (효과가) 발동하다, 작동을 시작하다 · 어떤 최적화나 규칙이 실제로 적용되기 시작할 때. "vectorization failing to kick in" |
| blocked | 차단되다, 막히다 · 어떤 처리가 조건 때문에 진행되지 못할 때. "inlining being blocked" |
| fall through | 무산되다, 실패로 돌아가다 · 뒤이어 일어나야 할 일이 앞 단계 실패로 못 일어날 때. "every downstream optimization falls through" |
| LICM | 루프 불변 코드 이동(Loop-Invariant Code Motion) · 루프 안에서 안 바뀌는 계산을 루프 밖으로 옮기는 컴파일러 최적화. "loop-invariant code motion (LICM), loop interchange" |
| SIMD | 단일명령 다중데이터(Single Instruction, Multiple Data) · 여러 루프 반복을 한 번에 처리하는 벡터화 명령어 집합. "into SIMD instructions, but it frequently fails" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.