[TIL] 5주차 - (4) : realloc() 함수 개선

오늘은 realloc() 함수를 개선해 보겠다.

 

 

realloc 함수 문제 인식

 

현재 realloc() 코드를 보자.

 

void *mm_realloc(void *ptr, size_t size)
{
    void *oldptr = ptr;
    void *newptr;
    size_t copySize;


    newptr = mm_malloc(size);
    if (newptr == NULL)
      return NULL;
    copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
    if (size < copySize)
      copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

 

현재 코드는 무조건 할당되어 있는 ptr 포인터의 위치의 블록을 free()하면서

동시에 해당 값들을 malloc()함수로 재 할당한 위치로 복사한다.

 

이 복사 로직은 데이터가 많을수록 시간 성능에 좋지 않은 무식한 방법이다.

 

 

하지만 이 방식은 두가지 상황에서 성능을 개선할 수 있다.

 

1. realloc으로 블록을 축소하려는 상황

 

2. realloc으로 블록 확장을 할때, 다음 블록이 가용 블록인 상황

 

1번은 헤더와 푸터를 요청받은 size에 맞게 초기화해주는 방식으로 성능을 개선할 수 있으며

 

2번은 다음 블록이 가용 블록이고 충분히 확장할 만한 크기라면 확장해주어 요청을 해결할 수 있다.

 

 

 

개선 코드

 

개선된 코드를 보자.

 

void *mm_realloc(void *ptr, size_t size)
{
    void *oldptr = ptr;
    void *newptr;
    size_t this_size = GET_SIZE(HDRP(ptr));
    size_t copySize,asize,bsize,csize;
    
    
    /* CASE 1 */
    if (this_size - DSIZE >= size){
        if (size <= DSIZE){
            asize = 2*DSIZE;
        }
        else{
            asize = DSIZE * ((size+(DSIZE) + (DSIZE-1)) / DSIZE);
        }

        if((this_size - asize) >= (2*DSIZE)) {
            PUT(HDRP(ptr) , PACK(asize , 1));
            PUT(FTRP(ptr) , PACK(asize , 1));
            PUT(HDRP(NEXT_BLKP(ptr)) , PACK(this_size - asize , 0));
            PUT(FTRP(NEXT_BLKP(ptr)) , PACK(this_size - asize , 0));
            coalesce(NEXT_BLKP(ptr));
        }
        next_bp = ptr;
        return ptr;
    }


    /* CASE 2 */
    asize = DSIZE * ((size+(DSIZE) + (DSIZE-1)) / DSIZE);
    csize = GET_SIZE(HDRP(NEXT_BLKP(ptr))) + this_size;

    if(csize >= asize && !GET_ALLOC(HDRP(NEXT_BLKP(ptr)))){
        bsize = csize - asize;
        if(bsize >= DSIZE){
            PUT(HDRP(ptr) , PACK(asize , 1));
            PUT(FTRP(ptr) , PACK(asize , 1));
            PUT(HDRP(NEXT_BLKP(ptr)) , PACK(bsize , 0));
            PUT(FTRP(NEXT_BLKP(ptr)) , PACK(bsize , 0));
        }
        else{
            PUT(HDRP(ptr) , PACK(csize , 1));
            PUT(FTRP(ptr) , PACK(csize , 1));
        }
        next_bp = ptr;
        return ptr;

    }
	
    
    /* CASE 3 */
    newptr = mm_malloc(size);
    if (newptr == NULL)
      return NULL;
    copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
    if (size < copySize)
      copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

 

코드는 크게 세 영역으로 나눌 수 있으며,

 

각각 개선 1번 , 개선 2번 , 이후 복사 로직으로 배치했다.

 

 

 

1번 if문 블럭 코드의 flow는 다음과 같다.

 

먼저 요청받은 재할당 size가 최소 영역 블록보다 작은지 확인하고 작다면 최소 할당 블럭 크기인 2*DSIZE를 제공한다.

 

그렇지 않다면 8의 배수에 맞춘 사이즈를 제공한다.

 

그 후 place() 함수에서 진행한 블럭의 header 와 footer를 수정하는 로직을 추가한 뒤 coalesce()로 가용 블럭을 병합한다.

 

 

 

2번 if문 블럭 코드의 flow는 선언한 변수가 많아 이해하기 좀 까다롭다.

 

그림을 통해 이해하고 설명을 확인해보자.

 

 

 

먼저 C size를 A size보다 크고 가용 가능한지 체크한다. 그 상황이라면 2번 케이스로 개선할 수 있는 경우이다.

 

bsize가 만약 최소 블럭 단위보다 크다면 해당 영역은 가용 블럭으로 세팅해주고, 그렇지 않다면 C size 전부를 할당해주는 방식이다.

 

 

 

 

3번 블럭 코드는 원래 복사하여 옮겼던 방식과 일치한다. 위 두 케이스를 제외하고는 이 방식대로 진행하기로 한다.

 

 

 

개선 성능 비교

 

실제로 이 코드가 실 점수에 큰 영향을 미치진 않았지만 (1점 증가) 시간 성능이 눈에 띄게 개선되었다.

 

next-fit 에 realloc() 개선 함수 적용  전 VS 후

 

Total 시간과 realloc test인 10번 Trace의 시간을 보면 성능이 증가 했음을 알 수 있지만

 

next-fit 방식은 realloc() 상황에서 조금씩 생기는 잉여 가용 블록들이 데이터 효율성을 저하시키는 듯 했다. 

 

게다가 리뉴얼한 realloc의 2번 케이스는 next-fit 로직에서 잘 발생하지 않는 상황일 것이다.

 

하지만 대부분의 상황에서 리뉴얼한 방식이 데이터 효율성 저하 대비 시간 성능이 크게 증가할 것으로 예상했다.

 

 

 

custom-best-fit-V2 에 realloc() 개선 함수 적용  전 VS 후

 

성능 개선에서 가장 큰 차이를 보인건 뜻밖에도 내가 만들었던 custom_best_fit_v2 이다.

 

custom_best_fit_v2는 next-bp 기억 변수와 best-bp 기억 변수 두개를 사용하는 방식으로, next-fit의 장점과 best-fit의 장점을 모두 사용해보기 위해 직접 만들어봤다.

 

먼저 next_bp로 기억되어 있는 부분부터 끝까지 next-fit으로 할당하는 건 next-fit의 방식을 채택했다.

 

하지만 이 구간에서 빈 블록이 탐색되지 않았다면 다시 돌아와 best-fit을 next_bp 포인터 전까지 수행한다.

 

 

이 방식을 사용한 이유는

 

충분히 많은 블록들을 완전탐색 방식의 best-fit으로 진행하면 초반엔 수행시간 대비 메모리 사용 효율의 의미가 없어지기 때문에

 

Chunk heap을 1회 순환하여 next-fit으로 블록들을 할당한 뒤 best-fit으로 탐색하기 위해 사용했다.

 

 

이전 포스팅에서 말했듯이, next-fit의 무지성 삽입이 반복된 상황에서 best-fit으로 정교한 삽입을 함으로써 성능을 개선할 수 있을까 해서 구현해보았다.

 

이 방식에서 9번과 10번의 realloc trace에서 시간 성능이 개선되면서 총 소요시간이 0.04초 가량 감소했고, 최종 점수가 1점 올랐다.

 

 

 

실제로 이 전후 비교는 빌드를 할때 마다 바뀌는 게 아니라 확실히 눈에 띄게 개선된 사항이다.

 

결국 하루종일 코드를 수정한 결과에 대한 보람을 직접 확인할 수 있었다.