Malloc Lab 98점 코드 분석
먼저 코드를 살펴보겠습니다.
https://github.com/prkty/KJ_malloc_lab/blob/main/mm_98_clean.c
해당 깃허브를 통해 전체 코드를 확인하실 수 있습니다.(주석 및 설명 추가)
위의 코드를 분석하면 다음 표와 같습니다.
| 항목 | 설명 |
|---|---|
| 할당자 종류 | 명시적 가용 리스트 방식 중 segregated free list 방식 사용 |
| 리스트 수 | LISTLIMIT = 16개의 크기별 분리 리스트 존재 |
| 삽입 정책 | 정렬된 주소 순으로 삽입 (오름차순 주소 정렬) |
| 분할 정책 | 요청된 크기보다 큰 블록은 분할되며, 일부 조건에서만 분할을 안 함(16바이트 미만일때) |
| 병합 정책 | 인접한 블록이 free이면 병합 (단, 다음 블록이 재할당 태그가 설정되어 있으면 병합하지 않음) |
| 재할당 정책 | REALLOC_BUFFER만큼의 추가 공간을 확보해 자주 재할당하는 블록의 성능 최적화 |
| 태그 사용 | 재할당에 사용되는 블록을 구분하기 위한 Reallocation Tag 사용 |
전체적인 로직은 Segregated List 과 동일합니다. 원래 해당 리스트는 85점 정도가 나옵니다. 그러나 우리가 해당 코드에서 주목해야될 점은 재할당 정책과 태그를 사용한다는 점입니다. 이 방법을 통해 98점이라는 높은 점수를 받을 수 있습니다. 밑에 내용을 참고하여 어떤 식으로 성능을 끌어올리는지 알아봅시다.
Segregated List 성능 향상 방안
기존의 방식
명석님께서 하신 말씀을 차용하여 말하자면, 사실상 묵시적말고 명시적이나 분리 가용 리스트에서는 배치정책인 First Fit, Best Fit, Next Fit 방식이 드라마틱한 효과를 보여주지 않습니다.
그러면 어떻게 3개의 가용 블록 관리 방식에서 제일 효율적이라고 불리우는 분리 가용 리스트의 성능을 끌어 올릴 수 있을까요?
→ 답은
명시적 리스트의 장점을 살려 가용 블럭 관리시에 free 블록만 따로 연결 리스트로 관리하여 삽입/삭제 효율증가시키고, 재할당시 Reallocation Buffer + Tag 를 통해 단편화의 위험성과 메모리 효율성을 증대하는 방법이 있습니다.
기본적인 realloc을 그냥 구현하면?
- 매번 새로운 메모리 블록을
malloc - 데이터를 복사
- 기존 블록을
free
복사 비용이 크고 → 데이터 처리속도가 떨어집니다. → 메모리 조각화(fragmentation)가 심해질 수 있습니다.
| 주요 구성 요소 | 사용된 방식 | 설명 |
|---|---|---|
| 메모리 분할 전략 | Segregated Free Lists | 크기별로 free list를 나누어 탐색 범위를 줄여 속도 향상 |
| 가용 블록 관리 | Explicit Linked List | free 블록만 따로 연결 리스트로 관리하여 삽입/삭제 효율적 |
| 할당 후 블록 분할 | Immediate Splitting | 할당한 블록에서 남는 공간이 충분하면 즉시 나눔 |
| 병합 전략 | Immediate Coalescing | free 시점에 인접 free 블록을 즉시 병합하여 조각화 방지 |
| 재할당 최적화 | Reallocation Buffer + Tag | 미래 realloc에 대비하여 buffer 확보, 확장 가능하게 구성 |
| 가상 주소 정렬 | 8바이트(64비트) 정렬 | CPU에서 요구하는 alignment 기준을 충족 |
Reallocation Buffer
오늘은 Reallocation Buffer에 대해서 발표를 해보고자 합니다.
Reallocation은 realloc을 할 때 비효율적인 메모리 복사, 재할당을 줄이기 위해 특정한 규칙을 적용하는 전략입니다.
기존의 realloc은 요청이 오면 매번 free하고 새 블록을 할당하고 복사합니다. 그러나 해당 방식을 쓰면, 특정한 조건에서 버퍼를 통한 해당 과정을 줄일 수있습니다. 그럼 이제 어떤식으로 구현되는지 알아보겠습니다. 밑에 그림은 흐름 파악용으로 참고하시면 좋을 것 같습니다.
1. Buffer 사용하기
new_size += REALLOC_BUFFER;- realloc할 때 필요한 크기보다 약간 더 크게 메모리를 확보합니다.
- 그럼 다음에 이 블록을 조금 더 키워야 할 때, 굳이 새로 malloc하고 복사하지 않아도 됩니다.
→ realloc이 자주 발생하는 경우 성능 최적화에 매우 큰 효과가 있습니다.
이득
- 미래의 realloc 확장 가능성 대비
- 데이터 복사 줄임
- 처리속도 향상
2. Buffer Tag 사용하기
if (block_buffer < 2 * REALLOC_BUFFER)
SET_RATAG(HDRP(NEXT_BLKP(ptr)));- 만약 현재 블록의 남은 공간이 realloc buffer보다 작다면, 다음 블록에 "내가 곧 확장할 수도 있다"는 Realloc Tag를 설정합니다.
- 이 Realloc Tag가 붙은 free 블록은 다른 사람이 malloc으로 가져가지 못하도록 막습니다.
즉, realloc 확장할 때 쉽게 사용할 수 있도록 예약하는 효과입니다.
이득
- realloc이 자연스럽게 제자리로 확장 가능
- free 블록의 부적절한 사용 방지
- 조각화 감소
3. Next Free Block을 이용한 내부 확장
if (!GET_ALLOC(HDRP(NEXT_BLKP(ptr))) || !GET_SIZE(HDRP(NEXT_BLKP(ptr))))- 현재 블록 바로 옆에 free block이 있으면, 그 블록을 합쳐서 크기를 늘려 realloc을 수행합니다.
- 이걸 통해 realloc 시 데이터 복사 자체를 아예 피할 수 있습니다.
이득
- 복사 비용 제거
- 더 빠른 realloc
Reallocation 프로세스
- 작은 realloc이면 buffer로 해결 → 별도 재할당, 메모리 복사 없이 처리
- 옆 블록이 free면 병합해서 확장 → 메모리 복사 없이 realloc 완료
- buffer 부족 시 tag 설정 → 미래의 realloc 대비
- 어쩔 수 없으면 새 malloc + 데이터 복사 → 마지막 수단
→ 결론적으로, Reallocation은 realloc 시 매번 새 블록 복사하지 않고, 최대한 현재 블록을 이용해 효율적으로 확장하려는 지능적인 최적화 전략입니다.
| 전략 | 설명 | 기대 효과 |
|---|---|---|
| Reallocation Buffer | 크기보다 약간 크게 확보 | future realloc 최적화 |
| Reallocation Tag | 다음 free 블록 예약 | 확장 가능성 보장 |
| Next Free Block 확장 | 옆 free 블록 흡수 | 복사 없이 realloc |
| memcpy fallback | 최후 수단 | 복사 비용 발생 |
[이점]
- 미래의 realloc 확장 대비
- 힙 단편화 감소
- 힙 확장 시스템 호출 감소
- 예측성 향상
위와 같은 장점이 있습니다.
보통의 분리 맞춤은 85점대입니다. 그러나 위의 방법으로 98점까지 끌어 올릴수 있습니다.
여담
그러면 생각해보건데, 이전 블록이 free라면 place만 이동시켜서 할당 시키면 더 최적화를 할 수 있지 않을까 싶긴합니다. 지금은 이전이 free이고 이후가 할당중일 때는 일반적인 realloc 방식과 동일하다.
라고 해서 해봤지만, 성능 저하가 심한 것 같다. 새로 배치하는 것이 더 효율적인 것으로 확인했다.