[Malloc Lab] 7. 성능 개선을 위한 몇가지 최적화 (3) (Best fit)

3. Explicit free list chain 내림차순 정렬 / 그에 맞는 Best fit find_fit함수 구현 (+2점)

 

명시적 가용 리스트 chain은 가장 나중에 추가된 원소가 start점에 위치하는, 우선순위 없는 선입후출인 스택의 구조를 갖고 있었다. 속도는 빠르지만 공간 효율에는 그닥 도움을 주지 못해서 속도점수는 높고 메모리 점수는 낮아 한쪽으로 점수가 치우친 상태인데, 빈 블록을 크기순 내림차순으로 정렬함으로써 이 부분을 개선했다.

 

빈 블록을 보관하는 가용리스트 chain이 크기 내림차순이라면, 가장 큰 블록은 chain의 start에 있을 것이다. 그렇다면 만약 fit을 요구하는 asize가 start보다 크다면 나머지 원소와는 비교하지 않아도 fit이 불가능함을 빠르게 알 수 있다.

또한 내림차순을 list를 순회하면서 처음으로 fit이 불가능한 블록을 만났다면, 그 직전 블록을 할당함으로써 가장 낭비공간이 적은 블록에 fit이 가능한 일종의 best fit이 된다.

 

best fit을 택하는 find_fit 덕에 위쪽 trace의 공간활욜은 100%에 가까운 성능이 나왔다. 하지만 trace 9의 util이 97%에서 77%로 깎여 어느정도 상쇄되고 결과적으로 2점이 올랐다. 같은 realloc testcase인 trace 10은 점수가 유지되는걸 보면 realloc함수의 커스텀이 chain을 끊고 다시 붙이는 과정은 크게 무리를 주는 것 같지는 않고, trace 9의 요구하는 용량들이 best fit 알고리즘과 맞지 않는 것 같다.