[Malloc Lab] 5. 성능 개선을 위한 몇가지 최적화

1. CHUNKsize 축소 (+2점)

 

malloc lab에서 다루는 heap의 사이즈는 20MB로 작고, 테스트케이스에서 할당과 free를 요구하는 용량도 작다.

이런 상황에서 extend_heap의 최소용량인 CHUNKsize가 4kB인건 비효율적인 공간 사용이 될 수 있다.

CHUNKsize를 줄여가며 점수를 확인한 결과 2^8 이하일때 최대 점수가 나왔다.

2^7, 2^6 혹은 그 이하를 해도 점수가 더 오르진 않는걸 보면 너무 작은 용량은 테스트케이스에 없는 것 같다.

 

 

2. place 함수 커스텀 (+2점)

 

place함수는 find_fit으로 선택된 빈 블록의 크기과 실제 할당을 요구한 크기의 차 surplus가 Dsize*2 이상이라면 그 나머지를 다시 빈 블록으로 분할하여 재활용한다.

기존의 place함수는 항상 선택된 빈 블록의 앞에 할당하고 나머지 블록을 뒤에 생성했는데, 이는 매 할당마다 작은 조각의 빈 블록이 파편으로 남게 되는 결과를 만든다. 이를 매 place마다 반복하면 아래와 같은 상황이 될 것이다.

 

[1--------할당-------1][0-파편-0][1--------할당-------1][0-파편-0]   (병합 불가능한 여러개의 작은 파편)

 

그렇다면 어떨땐 파편을 앞에 두고, 어떨땐 파편을 뒤에 두는 식으로 place 함수를 짠다면, 저 파편들끼리 확률적으로 붙어 병합될 수 있을 것이다.

 

[1--------할당-------1][0-파편-0][0-파편-0][1--------할당-------1] (파편간 병합 가능)

 

병합 후

 

[1--------할당-------1][0-------파편-------0][1--------할당-------1] (병합하여 하나의 큰 빈 블록으로)

 

이를 구현하기 위해 surplus에 cutline을 설정해서, 남은 빈 파편의 크기 surplus가 cutline 이상이라면 파편을 앞에, 그 이하라면 파편을 뒤에 두는 할당 방식으로 블록을 할당했다.

이러한 place 방식을 따르면, 남은 빈 블록이 cutline 이상의 큰 파편이라면 coalesce 과정에서 prev블록에 (확률적으로 있을 수도) 있는 cutline 이하의 작은 파편과 병합을 시도할 수 있다.

 

테스트케이스에선 커트라인을 64B로 하는 것이 점수가 제일 잘 나왔다.