⁉️ 지난번에는

단순한 추상 자료형 기반 구현에서도,
작은 설계 선택들이 함수 호출 오버헤드와 불필요한 메모리 접근을 만들 수 있기 때문에
최적화가 필요하다는 사실을 알게되었고,
이번에는 그러한 최적화 하는 방법에 대해 알아보려고 한다.

🛠️ 프로그램 성능 최적화

🔄 루프 비효율성 제거하기

📌 루프 비효율성이란?

루프 안에서 불필요하게 반복되는 연산, 메모리 접근, 함수 호출로 인하여
프로그램의 성능이 떨어지는 형상을 말한다.
단계별로 최적화를 진행해보자.

---

💡 process 1

for (i = 0; i < vec_length(v); i++) {
    data_t val;
    get_vec_element(v, i, &val);
    *dest = *dest OP val;
}

🚨 problem

for (i = 0; i < **vec_length(v)**; i++)
테스트 조건이 루프의 매 실행마다 평가되어야 하기 때문에
함수 호출 오버헤드가 발생할 가능성이 있다.

💬 solution

long length = vec_length(v)
for (i = 0; i < length; i++) {
    data_t val;
    get_vec_element(v, i, &val);
    *dest = *dest OP val;
}

long length = vec_length(v)
벡터의 길이는 변하지 않으므로 루프 밖에서 한번만 계산하고 이를 이용한다.
여러 번 수행하지만 계산 결과가 변하지 않는 코드를 찾아내서
루프 밖으로 빼는 최적화 방법을 '코드 이동(Code Motion)' 이라고 한다.

✅ result

---

💡 process 1-2

다음은 또 다른 루프 비효율성 문제의 예시이다.

void lower1(char *s){
   long i;
   for (i = 0; i < strlen(s); i++)
     if (s[i] >= ’A’ && s[i] <= ’Z’)
   s[i] -= (’A’ - ’a’);}
}

🚨 problem

for (i = 0; i < **strlen(s)**; i++)
strlen(s)는 널 문자('\0')를 만날 때까지 전부 스캔 → O(n)
루프는 n번 반복되므로, 전체 시간은 O(n²) 로 증가
즉, 문자열의 길이가 2배가 되면 전체 시간은 4배로 증가

💬 solution

long i;
  long len = vec_length(v);

  *dest = IDENT;
  for (i = 0; i < length; i++) ...

• 최적화 컴파일러도 부작용(side effect) 가능성을 완전히 배제 못 하면
  이런 호출을 자동 이동하지 못할 수 있음 → 프로그래머가 직접 코드 이동 필요
• 루프 불변식 이동(Code Motion): vec_length(v) 결과를 한 번만 계산해 len에 저장
• 루프는 더 이상 O(n²)가 아니라 O(n)

✅ result

💭 놓치기 쉬운 부분

이 예시는 프로그램 작성에서 흔히 발생하는 문제를 보여주는데 겉보기엔 사소한 코드 한 줄이
숨겨진 점근적 비효율성(asymptotic inefficiency) 을 가질 수 있다는 것이다.
예를 들어, 소문자 변환(lowercase) 함수가 프로그램 성능의 병목이 될 거라고는 보통 생각하지 않는다.
하지만 실제 배포 후에는 이 함수가 백만 글자 이상의 문자열에도 적용될 수 있다.
그러면 이 “무해해 보이던” 코드가 순식간에 심각한 성능 병목이 된다.

숙련된 프로그래머의 역할 중 하나는 이런 점근적 비효율성을 아예 코드에 넣지 않는 것이다.

---

📞 프로시저 호출 줄이기

📌 프로시저 호출 비용이란?

루프 안에서 매번 함수 호출이 일어나면,
함수 호출 준비(인자 전달, 레지스터 저장), 호출 후 복귀 시 레지스터 복원 및 정리 와 같은 오버헤드가 누적된다.
특히 짧은 연산이지만 호출이 빈번하면 전체 성능을 크게 저하시킬 수 있다.

💡 process 2

void combine2(vec_ptr v, data_t *dest)
{
  long i;
  long length = vec_length(v);

  *dest = IDENT;
  for (i = 0; i < length; i++) {
    data_t val;
    get_vec_element(v, i, &val);
    *dest = *dest OP val;
    }
   }

🚨 problem

get_vec_element(v, i, &val)
get_vec_element 는 매번 다음 벡터 원소를 가져오기 위해 매 루프 실행마다 함수 호출
또한, 매번 벡터를 참조할 때마다 경계값을 체크하는 비효율적인 동작

💬 solution

• 내부 루프에서 함수 호출 사용하지 않고 시작 주소를 한번만 조사하자
• 프로시저 호출 줄이기: 시작 주소 계산을 한 번만 계산해 *data에 저장

✅ result

🤔 성능 개선

놀랍게도 성능 개선은 거의 이루어지지 않았다.

실제로는 정수 연산에 대한 클럭 사이클은 더 길어졌다.
이는 우리가 최적화한 부분 이외에서 성능을 제약하는 병목을 형성하고 있다는 말이다.
이외에도 원인은 바뀐 구조로 인한 파이프라인 변경, 또는 컴파일러의 보수적인 해결 방식 등도 있을 수 있다.

---

🗑️ 불필요한 메모리 참조 제거

📌 메모리 참조 비용이란?

메모리 접근은 CPU 레지스터 연산에 비해 배우 느리고, 같은 값을 여러 번 참조하는 경우,
메모리에서 읽었을때 저장해 두지 않는다면 계속해서 읽어야 한다.
특히 이러한 연산이 아무리 짧은 연산일지라도 호출이 빈번하면 전체 성능을 크게 저하시킬 수 있다.

💡 process 3

🔄 명령어 해석

1. 메모리 (%rbx)에 저장되어 있는 dest 주소를 %xmm0 레지스터에 저장 (초기화)
2. 메모리 (%rdx)에 저장되어 있는 다음 data값을 %xmm0와 누적 연산하고 %xmmo에 갱신
3. %xmm0값을 메모리 (%rbx)에 저장
4. 포인터 이동으로 rdx 주소가 다음 data 값을 가르킬 수 있도록 계산
5. 종료 조건 확인

🚨 problem

불필요한 메모리 접근

💬 solution

• 컴파일러가 루프 전개(Loop Unrolling)와 레지스터 활용 최적화를 적용할 수 있게 코드 구조 단순화
• 메모리 접근을 최소화하고, CPU 레지스터에서 연산 처리.

🔄 명령어 해석

1. 메모리의 %rdx (= data[i])를 읽어서 %xmm0(acc)와 곱하고 결과를 %xmm0에 저장.
2. 포인터 이동으로 rdx 주소가 다음 data 값을 가르킬 수 있도록 계산
3. 종료 조건 확인

✅ result

• 메모리 왕복 최소화

---

📍 결론

지금까지는 코드 구조 개선과 불필요한 연산 제거를 통해 루프 효율성을 높이는 방법을 살펴보았다.
하지만 이러한 최적화는 주로 언어와 컴파일러 수준에서 가능한 범위에 국한된다.
더 높은 성능 향상을 위해서는 프로세서 내부 구조(microarchitecture)를 고려한 최적화가 필요하다.

---

🔄 프로세서 내부 최적화

이제 우리는 코드 자체의 단순한 개선을 넘어, 현대 프로세서의 동작 방식을 이해하고
프로세서의 마이크로구조 즉, 하부 시스템 설계를 활용하는 최적화 전략을 살펴보려고 한다.

하지만 더 높은 성능을 위해서는 마이크로아키텍처(microarchitecture),
즉 프로세서가 명령을 실행하는 하부 시스템 설계를 활용한 최적화가 필요하다.

모든 성능을 끌어내기 위해서는 프로그램 분석 + 해당 프로세서에 맞춘 코드 생성이 필요하다.
다만, 범용적인 최적화 원칙은 대부분의 머신에 적용 가능하다.

🔍 현대 마이크로프로세서의 특징

• 수많은 트랜지스터를 하나의 칩에 집적 가능
• 프로그램 성능 극대화를 위한 복잡한 하드웨어 설계
• 코드 레벨에서는 명령이 순차적으로 실행되는 것처럼 보임
• 실제 하드웨어에서는 여러 명령이 동시에 실행됨
  → 명령 수준 병렬성(Instruction-Level Parallelism, ILP)

💡 일부 설계에서는 한 번에 100개 이상의 명령이 "비행 중(in flight)" 상태일 수 있음.

✅ 최신 프로세서 특징

1. 인스트럭션 수준 병렬성

2. 병렬 실행의 성능 제한 요인(한계)
- Latency Bound (지연 한계)
: 명령어들이 순차적으로만 실행되어야 할 때 발생.

• 예: 한 명령의 결과가 다음 명령의 입력이 되는 경우 → 앞의 연산이 끝나야 다음 연산 시작 가능.
• 데이터 의존성이 클수록 병렬 실행 효과 감소.

- Throughput Bound (처리량 한계)

• CPU의 기능 유닛 개수와 처리 속도가 프로그램 성능을 제한.
• 병렬로 실행할 수 있는 최대 명령어 수가 한계치에 도달하면 즉 CPU의 "순수 계산 용량" 한계에 다다르면 성능이 더 이상 올라가지 않는다.

---

🛠️ 전체 동작 (Overall Operation)

현대 프로세서는 초스칼라(Superscalar) + Out-of-Order 실행 방식 사용

• 초스칼라: 한 클럭 사이클에 여러 연산 실행 가능
• Out-of-Order: 명령 실행 순서가 코드 순서와 다를 수 있음
  

📌 주요 구성

1. 명령 제어 유닛(ICU, Instruction Control Unit)
   • 메모리에서 명령을 읽어와 원시 연산 집합(primitive operations) 생성
   • 명령 캐시(Instruction Cache) 사용 → 가장 많이 쓰이는 명령 빠르게 접근 가능
   • 분기 예측(Branch Prediction) 사용 → 다음 명령 미리 실행
     • 예측이 맞으면 그대로 진행, 틀리면 롤백 후 재실행
2. 실행 유닛(EU, Execution Unit)
   • ICU가 전달한 연산 실행
   • 산술 연산, 메모리 로드/스토어, 분기 수행

⚙️ 현대 프로세서의 명령 실행과 기능 유닛

🔹 명령 디코딩과 마이크로-연산 (Micro-operations)

• x86 구현 예시:
  • 레지스터만 사용하는 명령
    예: addq %rax, %rdx → 단일 연산으로 디코딩.
  • 메모리 참조 포함 명령
    예: addq %rax, 8(%rdx) → 3개의 마이크로-연산으로 분할됨:
    1. load : 메모리에서 값을 읽어옴.
    2. add : 읽은 값을 %rax와 더함.
    3. store : 결과를 메모리에 저장.

🔹 실행 유닛 (Execution Units, EU)

• 명령어들을 받아 실제 연산을 수행하는 장치.
• 다양한 functional units 로 구성 → 각 유닛이 특정 연산에 특화.
• Load/Store 유닛:
  • Load: 메모리 → 레지스터, 주소 계산 가능.
  • Store: 레지스터 → 메모리, 주소 계산 가능.
  • Load/Store는 데이터 캐시 사용.

🔹 분기 예측 (Branch Prediction)과 투기 실행 (Speculative Execution)

• 분기 예측: 분기가 taken / not taken 될지, 그리고 분기 목표 주소 예측.
• 투기 실행: 분기 결과 확정 전, 예측된 경로의 명령을 미리 실행.
• 예측 실패 시 → 잘못 실행된 결과 폐기(Flush), 올바른 경로로 재시작.
• misprediction → 성능 손실 발생.

🔹 기능 유닛의 역할 (Functional Units)

• Haswell 기준 8개의 기능 유닛(0~7번) 예시:
  0. 정수 연산, 부동소수 곱셈, 정수/부동 나눗셈, 분기
  1. 정수 연산, 부동소수 덧셈, 정수 곱셈, 부동소수 곱셈
  2. Load, 주소 계산
  3. Load, 주소 계산
  4. Store
  5. 정수 연산
  6. 정수 연산, 분기
  7. Store 주소 계산

🔹 리타이어먼트 유닛 (Retirement Unit)과 레지스터 파일

• Retirement Unit:
  • 순차 실행의 의미 보장
  • First-in First-out 큐에서 명령이 완료될 때까지 대기
  • 분기 예측이 맞았는지 확인 후, 명령 retire → 레지스터 업데이트
• 레지스터 파일: 정수, 부동소수, SIMD(SSE/AVX) 레지스터 저장

🔹 레지스터 리네이밍 (Register Renaming)

• 목적: 명령 간 오퍼랜드 의존성 해소 + 데이터 전달 최적화
• 과정:
  1. 레지스터 r를 갱신하는 명령 디코딩 시, 고유 태그 t 생성.
  2. 매핑 테이블에 (r, t) 저장.
  3. 이후 r 사용 시 → 태그 t 기반으로 실제 값 추적.
  4. 해당 태그 결과 (v, t)가 생성되면, 이를 기다리는 명령들이 즉시 사용.
• 장점:
  • 중간 결과를 메모리/레지스터에 쓰지 않고도 직접 전달(Forwarding).
  • 대기 없이 연산 연속 수행 가능.
  • 분기 확정 전에도 투기 실행 가능.