Malloc Lab 회고

Malloc Lab을 진행하면서 나는 92점이라는 점수를 받았다. 이 점수는 분리 가용 리스트(Segregated Free List)를 최초로 적용했을 때는 86점 수준이었으며, 이후 realloc 개선과 자잘한 최적화를 통해 92점까지 올릴 수 있었다. 하지만 이 점수가 내 코드의 한계인지, 더 높은 점수를 받을 수 있는 여지가 있는지 확인하고 싶었다. 그래서 다양한 개선 방안을 탐색하고, 실제로 적용하기 위해 시도했던 모든 과정을 공유하고자 이 주제를 선정하게 되었다.

🔍 분리 가용 리스트 적용 직후

아래는 분리 가용 리스트를 적용한 직후 얻은 점수이다.

분리가용 리스트 구현 직후 점수

🔧 최적화 이후 결과

realloc의 로직을 개선하고, 최적화를 반복적으로 적용하였다. 그 결과 아래와 같이 성능은 상당히 개선되었다

최적화 수행 후 점수

📈 요청 크기 히스토그램 분석

성능 최적화를 위해 먼저 어떤 크기의 malloc 요청이 많이 발생하는지 파악할 필요가 있었다. 이를 위해 아래와 같은 방식으로 mm.c 파일에 히스토그램 로직을 삽입했다.

1단계: 요청 크기 기록용 배열 추가

mm.c 파일 상단에 다음과 같이 전역 변수와 범위 정의를 추가했다.

#define MAX_HISTOGRAM_SIZE 1024  // 1KB까지의 요청 크기만 기록 (원하면 늘릴 수 있음)
static int size_histogram[MAX_HISTOGRAM_SIZE];

2단계: mm_malloc 내부에 기록 코드 삽입

mm_malloc 함수 내부에서 size를 기록하는 부분을 추가했다:

void *mm_malloc(size_t size)
{
    if (size < MAX_HISTOGRAM_SIZE) {
        size_histogram[size]++;
    }
    ...

이렇게 하면 매번 mm_malloc(size)가 호출될 때마다 해당 size 요청 횟수가 기록된다.

3단계: 기록된 히스토그램 출력 함수 추가

void print_malloc_histogram()
{
    printf("\n[malloc size histogram]\n");
    for (int i = 0; i < MAX_HISTOGRAM_SIZE; i++) {
        if (size_histogram[i] > 0) {
            printf("Size %3d bytes: %d times\n", i, size_histogram[i]);
        }
    }
    printf("[end of histogram]\n\n");
}

결과

[malloc size histogram]
Size   9 bytes: 48 times
Size  16 bytes: 384 times
Size  24 bytes: 12 times
Size  48 bytes: 48 times
Size  64 bytes: 492 times
Size 112 bytes: 1500 times
Size 128 bytes: 1680 times
Size 160 bytes: 72 times
Size 448 bytes: 2688 times
Size 456 bytes: 240 times
Size 512 bytes: 3096 times
[end of histogram]

출력 결과를 보면 사이즈가 112, 128, 448, 512 인 구간에 1000회 이상의 요청이 몰려 있는 것을 확인할 수 있었다.

get_class 최적화 전략

초기에는 아래처럼 2배 단위로 클래스 분류를 수행하였다.

static int get_class(size_t size){
    int class = 0;
    size >>= 4; // 최소 16부터 시작 (DSIZE)
    while (size > 1 && class < SEGREGATED_SIZE - 1) {
        size >>= 1;
        class++;
    }
    return class;
}

하지만 요청이 집중되는 크기에 대해 이 방식은 공간 낭비와 탐색 오버헤드를 초래할 수 있었다. 이에 따라 수작업 기반의 튜닝을 적용하였다.

수작업 튜닝 기반 분류

#define SEGREGATED_SIZE (16)


static int get_class(size_t size){
    if (size <= 16) return 0;
    if (size <= 32) return 1;
    if (size <= 48) return 2;
    if (size <= 64) return 3;
    if (size <= 96) return 4;
    if (size <= 112) return 5;
    if (size <= 128) return 6;
    if (size <= 160) return 7;
    if (size <= 256) return 8;
    if (size <= 384) return 9;
    if (size <= 448) return 10;
    if (size <= 512) return 11;
    if (size <= 1024) return 12;
    if (size <= 2048) return 13;
    if (size <= 4096) return 14;
    return 15; // 그 외 초대형 블록
}

이렇게 하여 요청이 집중되는 112, 128, 448, 512 바이트를 개별 클래스로 직접 분류하였다.

무식한 방법이긴 하지만 이렇게 하면 특정 사이즈의 요청을 빠르게 처리할 수 있지 않을까? 하는 생각이 들었다.

결과는 위와 같았다. 점수는 같았지만 총 실행 시간이 엄청난 차이가 있었다.

항목	적용 전	적용 후	변화
Util (메모리 효율)	52 점	52 점	동일
Thru (처리량)	40 점	40 점	동일
Total	92 점	92 점	동일
총 실행 시간	0.093752초	0.002696초	34배 빨라짐
Trace 8 Kops	262 → 84418	극적인 향상	중요한 개선 가능성 있음

Trace 8 분석 결과

• binary2-bal.rep에서 112 바이트, 128 바이트 요청이 집중적으로 발생
• 중반부에는 해당 요청이 해제되고
• 후반부에는 새로운 크기의 할당 요청이 이어짐

따라서 특정 크기의 블록 요청에 맞춘 분리 리스트 구성은 속도 향상에는 분명히 도움이 되었으나, 메모리 효율 개선에는 영향이 없었기 때문에 점수 향상으로 이어지지 않았다.

🚧 나는 왜 92점을 넘지 못했는가?

내가 최종적으로 얻은 점수는 92점이었고, 그 이상의 점수는 다양한 개선을 시도하더라도 넘기 어려웠다. 그 이유는 다음과 같이 분석했다.

1. 환경의 차이 (64-bit 시스템)
   • 포인터와 메타데이터가 2배 크기이기 때문에, 할당 가능한 유효 메모리가 줄어들며
   • 벤치마크는 힙 확장 한도를 넘기면 즉시 오류 처리한다.
2. 리스트 개수 증가로 인한 오버헤드
   • 클래스 수가 많아지면 루트 포인터만으로도 큰 메모리 공간이 소모된다.
   • 예를 들어, 16개 클래스는 160바이트 추가 헤더 공간을 요구한다.
3. 진정한 성능 개선은 32-bit에서 검증 필요
   • 더 많은 실험을 위해선 memlib 수정 또는 32-bit 환경 도커 테스트가 필요할 것이다.

결론

점수는 같았지만, 실행 시간은 수십 배 빨라졌고, 특정 트레이스에 대한 처리량이 극적으로 향상되었다. 이런 무식해 보일 수 있는 시도들이 실제로 성능에 영향을 줄 수 있음을 확인하였다. 다만, Malloc Lab의 점수 체계는 속도보다 메모리 효율에 높은 비중을 두기 때문에 점수 향상을 위해서는 효율을 해치지 않으면서도 속도까지 잡는 정교한 전략이 필요함을 느꼈다.