[WEEK07] Trace 데이터 분석 기반 Segregated-fit Size Class 최적화

😨 문제 발생

명시적 가용 리스트에서 분리 가용 리스트 방식으로 전환해서 프로그램을 실행했더니 다음과 같은 결과가 나왔다.

Explicit free list	Segregated free list

9, 10번 trace는 realloc 성능을 평가하는 것이라서 제외했다.

분리 맞춤을 사용하면 할당 시간을 줄이고 메모리 이용도를 개선할 수 있다고 알고 있었는데, 분리 맞춤으로 전환했음에도 불구하고 성능 점수는 명시적 가용 리스트를 사용한 점수에서 변하지 않았다. util과 secs 및 Kops를 비교해 보면, 오히려 분리 맞춤을 사용한 이후의 성능이 소폭 감소했다는 것을 확인할 수 있다.

---

🤔 원인 찾기

static int get_index(size_t size) {
    size_t a = 1;
    size_t b = 2;
    if (size <= a) return 0;
    for (int i = 0; i < SEGSIZE; i++) { // SEGSIZE = 20
        if (a < size && size <= b) return i;
        a <<= 1;
        b <<= 1;
    }
    return SEGSIZE-1;
}

기존의 get_index 함수는 2의 제곱 만큼의 크기 별로 클래스를 나누는 기능을 수행했다. 예를 들어 {1, 2}는 0번째 크기 클래스, {3, 4}는 1번째 크기 클래스, {5-8}은 2번째 크기 클래스를 할당받게 된다.

 

아래는 trace 파일들에서 실제로 할당되는 크기들을 모두 카운트해서 size class별로 구분해서 나타낸 그래프다.

실제로는 특정한 크기 클래스만 집중적으로 사용되고 있기 때문에 불균형하다는 것을 확인할 수 있다.

{9-16} 크기에 할당된 3번 size class를 보자. 실제로는 9부터 16까지 고르게 할당을 요청받은 것이 아니라, 16에만 집중적으로 요청되고 있다는 것을 확인할 수 있다.

 

정리하자면, 일부 구간에 요청 몰리기 때문에 모든 가용 리스트가 사용되지 못하고 낭비가 발생할 수 있다는 문제점이 있다.

---

😎 해결하기!

특정 size class만 집중적으로 사용되면서 성능이 감소했다고 판단했다. 이를 해결하기 위해 덜 사용되는 크기 클래스는 합치고, 자주 할당 요청을 받는 크기는 따로 크기 클래스를 할당하는 방식으로 get_index 함수를 구현했다.

static int get_index(size_t size) {
    if (size <= 15) return 0;
    else if (size == 16) return 1;
    else if (size <= 64) return 2;
    else if (size <= 72) return 3;
    else if (size <= 112) return 4;
    else if (size <= 128) return 5;
    else if (size <= 256) return 6;
    else if (size <= 512) return 7;
    else if (size <= 4071) return 8;
    else if (size == 4072) return 9;
    else if (size <= 4094) return 10;
    else if (size == 4095) return 11;
    else if (size <= (1<<13)) return 12;
    else if (size <= (1<<14)) return 13;
    else if (size <= (1<<15)) return 14;
    else if (size <= (1<<16)) return 15;
    else if (size <= (1<<17)) return 16;
    else if (size <= (1<<18)) return 17;
    else if (size <= (1<<19)) return 18;
    else return 19;
}

Before	After

예상했던 대로 size class를 나누는 로직을 바꾼 이후에 모든 trace에 대해 성능이 더 좋아진 것을 확인할 수 있다.

항목	trace 기반 get_index 함수	지수 기반 get_index 함수
기반 논리	데이터 기반 하드 코딩	2ⁱ 기준 크기 분할
주요 요청 크기 정밀도	✅ 높음 (요청 많은 크기 집중 처리)	❌ 낮음 (빈출 크기를 정확히 나누지 못함)
균형성 (분할 간 거리)	❌ 불균형 (요청 많은 크기에 집중)	✅ 균형적 (1~2, 2~4, ..., 2048~4096, ...)
요청 데이터 대응력	✅ 매우 높음 (trace 최적화)	❌ 낮음 (일반적 로직, trace 미반영)
SEGSIZE 활용도	✅ 대부분 클래스가 자주 사용됨	⚠️ 일부 구간에 요청 몰림, 낭비 가능
재사용성 / 이식성	❌ 낮음 (trace 데이터 의존 높음)	✅ 높음 (일반 상황에 적용 가능)
성능 최적화 효과	✅ 높음 (find_fit 성공률 ↑)	⚠️ 비교적 낮음

 

기존의 2의 제곱 기반 get_index 함수에 비해 trace를 기반으로 get_index 함수를 구현함으로써 성능을 최적화할 수 있었다.

 

다만 새로 작성한 함수는 성능 점수를 최대로 키우기 위해서 주어진 trace 데이터만을 바탕으로 함수를 구현한 것이기 때문에 재사용성이나 이식성이 낮아 다른 데이터에 대해서 사용하기는 어려울 것으로 보인다.