오늘 하루 요약

✏️ 오늘의 한 일

• CSAPP Segregated Free List

🌈오늘의 성장!

CSAPP Segregated Free LIst

Segregated Free List + Best Fit: 처리량과 효율 모두 잡은 최적의 할당기

최근 구현한 메모리 할당기는 Segregated Free List + Best Fit 전략을 기반으로 합니다. 놀랍게도 이 전략은 기존 방식보다 훨씬 뛰어난 처리량(Throughput) 을 보여주었습니다. 아래는 성능 테스트 결과와 분석입니다.

---

✅ 최종 성능 지표

Perf index = 45 (util) + 40 (thru) = 85/100

• Utilization (공간 효율): 74%
• Throughput (처리량): 48,654 Kops
• Trace 4~8 처리량: 모두 8만 Kops 이상 기록
• 특이점: Trace 10에서도 처리량이 무려 94,993 Kops (Best Fit으로는 이례적인 속도)

---

💡 전략 설명

• Segregated Free List: 블록 크기를 기준으로 여러 개의 리스트(클래스)를 두고, 각 리스트에는 비슷한 크기의 가용 블록만 저장합니다.
• Best Fit: 각 리스트 내에서 요청 크기에 가장 근접한(낭비가 가장 적은) 블록을 선택합니다.

---

📌 핵심 코드

find_fit() - Segregated + Best Fit 전략

static void *find_fit(size_t asize)
{
    int index = get_list_index(asize);
    void *bp;
    void *best_bp = NULL;
    size_t min_diff = (size_t)-1;

    for (int i = index; i < NUM_CLASSES; i++)
    {
        for (bp = segregated_lists[i]; bp != NULL; bp = GET_SUCC(bp))
        {
            size_t csize = GET_SIZE(HDRP(bp));
            if (csize >= asize && (csize - asize) < min_diff)
            {
                min_diff = csize - asize;
                best_bp = bp;
                if (min_diff == 0) return bp;
            }
        }
        if (best_bp != NULL) return best_bp;
    }
    return NULL;
}

---

📈 분석: 왜 이렇게 빠를까?

1. Best Fit의 단점 완화

Best Fit은 보통 리스트 전체 탐색 때문에 느립니다. 하지만 Segregated List를 사용하면 탐색 리스트의 크기 자체가 작아지기 때문에, Best Fit의 약점이 거의 사라집니다.

2. 탐색 범위 감소

• Single List는 수천 개 블록을 순차 탐색해야 함.
• Segregated List는 보통 1~2개 클래스 내에서 수십 개 블록만 탐색하면 끝남.

3. 적합 블록이 빠르게 발견됨

• 동일한 크기 또는 가까운 크기의 블록이 정확한 클래스에만 존재.
• 즉, Best Fit이 찾는 ‘딱 맞는’ 블록이 빨리 등장할 가능성이 매우 큼.

---

🔁 비교: 다른 전략들과의 차이

전략	평균 처리량(Kops)	평균 공간 효율(%)
Single List + First Fit	약 4,500	~90
Single List + Best Fit	약 900	~90
Segregated List + First Fit	약 15,538	73
Segregated List + Best Fit	48,654	74

🚀 Best Fit이라고 무조건 느리다는 고정관념은 Segregated List를 만나면 완전히 무너집니다!

---

🧠 정리

• Segregated Free List의 탐색 범위 감소 장점과 Best Fit의 효율적 공간 활용이 최고의 시너지를 보였습니다.
• 이전까지 Best Fit은 “느리지만 효율적”이라는 평가였지만, 이제는 “빠르고 효율적”인 전략이 될 수 있습니다.

---

⛏ 오늘의 삽질

ㅠ-ㅠ