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.
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/.