[TIL] 5주차 - (6) : 코드 재 분석 (realloc&coalesce) 후 최종 결과

오늘은 내가 짰던 realloc의 기존 문제점을 한번 살펴보고, 개선하여 좋아진 성능을 파악해보겠다.

 

---

 

realloc 코드 재 분석

 

나는 내가 스스로 짠 realloc 코드가 최선이라고 생각하고 어쩔 수 없이 copy를 하는 비효율적인 상황 때문에 점수가 낮은 줄 알았다.

 

근데 팀원의 점수가 되게 높길래 팀원의 코드를 보니 realloc 점수가 너무 높아 해당 코드를 분석해보았다.

 

다음 코드가 팀원 분의 코드이다.

 

void *mm_realloc(void *ptr, size_t size)
{
    if (ptr == NULL) {
        return mm_malloc(size);
    }

    if (size == 0) {
        mm_free(ptr);
        return NULL;
    }

    size_t original_size = GET_SIZE(HDRP(ptr));
    size += 2 * WSIZE;   //헤더와 푸터가 붙은 사이즈로 비교하기 위해 DSIZE 만큼 더해줌
    if (original_size >= size) {
        return ptr;
    }

    if (original_size < size) {
        size_t total_size = original_size + GET_SIZE(HDRP(NEXT_BLKP(ptr)));
        block_status_t next = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));

        if (next == FREE_BLK && total_size >= size) {
            PUT(HDRP(NEXT_BLKP(ptr)), PACK(0, ZERO_BLK));
            PUT(FTRP(ptr), PACK(0, ZERO_BLK));
            PUT(HDRP(ptr), PACK(total_size, ALLOC_BLK));
            PUT(FTRP(ptr), PACK(total_size, ALLOC_BLK));

            return ptr;
        }
    }

    // 새로운 블록을 할당하고 데이터를 복사합니다.
    void *new_p = mm_malloc(size);
    if (new_p == NULL) {
        return NULL;
    }
    memcpy(new_p, ptr, size);
    mm_free(ptr);
    return new_p;
}

 

해당 코드를 보면 사실 논리적으로 문제가 있는 부분이 꽤 많은데 util 점수가 높은 것이 이해하기 조금 어려웠다.

 

1. 첫번째 if문은 일단 realloc으로 블록의 크기를 줄이는 요청이 들어오면 그냥 현재 블록 그대로 둔다.

 

이는 내부 단편화가 발생할 우려가 있다.

 

 

 

2. 두번째 if문에서 realloc으로 블록보다 큰 요청이 들어왔지만 그 양을 NEXT의 가용 블록에 삽입할 수 있으면 NEXT를 현재 블록이 아예 차지한다.

 

이 또한 내부 단편화와 남은 잉여 블록의 보존을 고려하지 않았다.

 

 

 

3. 초반부 'size += DSIZE' 를 통해서 요청받은 사이즈에 헤더와 푸터가 붙은 것처럼 연산해준 뒤 1,2번을 수행 하고 , 3번째 상황(memcpy를 통한 완전 복사 재할당)에서 해당 size를 원래대로 되돌려 놓지 않은 상태로 malloc을 요청한다.

 

이 또한 로직적으로 의도한 방식이 아닌 것 같다.

 

근데 문제는 이 3가지를 무시한 코드가 10번 trace에서 무려 86점을 맞은 것.

 

내가 눈치채지 못한 무언가가 있는 것이 아닌가 계속 디버깅과 코드 일부 주석처리를 반복하였고, 해당 코드와 내 코드의 가장 큰 차이로 인해 점수 차이가 발생한다는 것을 깨달았다.

 

 

바로 next-fit의 로직에 존재하는 next_bp 기억 변수를 해당 코드에서 초기화하는지 안하는지의 차이였다.

 

초기화를 하면 이상하게도 10번 케이스에서 점수가 43점을 맞지만, 초기화를 하지 않으면 86점을 받는다.

 

 

 

내가 짠 realloc 코드는 아래와 같다.

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));
            if(next_bp >= ptr && next_bp <= NEXT_BLKP(ptr))
                next_bp = NEXT_BLKP(ptr);
            coalesce(NEXT_BLKP(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;
        PUT(FTRP(ptr) , PACK(0 , 0));
        PUT(FTRP(ptr)+WSIZE , PACK(0 , 0));
        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));
        }
        if(next_bp >= ptr && next_bp <= NEXT_BLKP(ptr))
            next_bp = NEXT_BLKP(ptr);
        return ptr;

    }
	
    //CASE 3
    newptr = mm_malloc(size);
    if (newptr == NULL)
      return NULL;
    memcpy(newptr, oldptr, size);
    mm_free(oldptr);
    return newptr;
}

 

 

CASE1번과 CASE2번에서 모두 next_bp가 적절한 블록포인터 위치에 존재하지 않는 상황에서 예외처리를 진행했으며,

 

외부 단편화를 해소하기 위해 coalesce를 추가해주었다.

 

 

아까 말한 3가지의 잘못된 부분을 다 고려해서 짰기 때문에 로직적으로는 내가 생각한 모든 적절한 처리는 해줬다고 생각했다.

 

근데 이 복잡한 로직이 thru (시간 성능) 측면에서 떨어진 점수를 받았다면 이해했겠지만, 메모리 사용 측면에서 손해라는 것이 이해되지 않았다.

 

 

그래서 10번 realloc checking trace의 테스트케이스를 확인해보았다.

 

확인해보니 테스트케이스는 특별한 상황이 반복되는 경우였다.

a 0 4092
a 1 16
r 0 4097
a 2 16
f 1
r 0 4102
a 3 16
f 2
r 0 4107
a 4 16
f 3
r 0 4112
a 5 16
f 4

 

큰 값 (4092) 이 할당된 0번 포인터에 존재하는 블록을 재할당하면서 동시에 작은 값 (16)의 서로 다른 할당 요청과 반복 요청을 반복하고 있다.

 

이 요청의 플로우를 내 코드에 적용해보면 초반에 CASE 3 경우가 한번 요청되고(재할당하려고 보니 옆에 1번 포인터 16값이 들어있음) 그 큰 범위를 비워 둔 뒤 CASE 2번을 계속해서 반복하고 있다.

 

또 다른 특징은 realloc하는 큰 블록과 16씩 계속 할당과 반환을 반복되는 영역이 구분되어 수행되고 있다.

 

 

이렇게 하면 첫번째 코드가 왜 점수가 높냐 분석해보니,

 

재할당을 요청할 것을 대비하여 블록을 요구보다 충분히 크게 할당함으로써, 다음 realloc 요청시 해당 요청을 무시한다.

 

 

따라서 첫번째 코드는 이 테스트 케이스에 맞춰 높은 성능을 내도록 짜져있는 것 같다.

 

하지만 나는 잉여 가용영역을 realloc 후 재 설정하고 있기 때문에 next_bp가 올바른 자리로 배치하기 위해 초기화 코드를 작성해야 한다.

if(next_bp >= ptr && next_bp <= FTRP(ptr))

next_bp = NEXT_BLKP(ptr);

 

이 코드로 인해 내 생각엔 작은 할당(16)이 next_bp에 의해 다른 구역에서 진행되다가 

 

next_bp를 재할당하는 이 블록쪽으로 당겨와서 수행하면서 재할당할 자리가 없게 되고

 

그래서 이 큰 할당 블록을 재할당하기 위해 3번 케이스인 memcpy를 수행해서 메모리 효율성이 떨어지는 것으로 분석된다.

 

내가 짠 realloc으로 돌린 trace 점수표(왼) / 제일 처음 코드로 돌린 trace 점수표(오)

---

 

결론

 

과연 비록 모든 경우에서는 비효율적이더라도 점수를 받는 이 해당 케이스에 맞추어 코드를 짜는 것이 더 올바른 방법인지,

 

아니면 모든 케이스를 예외처리하는 코드가 더 올바른 것인지 판단하는 것이 쉽지 않았다.

 

 

원래는 모든 경우를 고려한 것이 더 올바른 것이라고 생각했지만,

 

next-fit 또한 보통의 경우 우수하기에 사용하지만 특정 케이스에서는 제일 안좋은 효율을 낼 수 있듯이

 

특정 요구를 분석하여 특정 할당 패턴에 맞는 할당기를 제작하는 것이 더 올바른 것이 아닌가 하는 생각이 들었다.

 

 

하지만 위에서 처음 짠 코드에서는 next_bp를 고려하지 않아 실제로 오류를 발생할 수 있는 여지가 있으므로

 

그냥 내가 짠 코드로 적당히 점수를 내는 것으로 만족하기로 했다.

 

---

 

coalesce 로직 업데이트 후 점수 상승

 

coalesce() 함수에 next_bp를 재 조정해주는 코드를 추가해야 한다는 것을 깨닫고 적당히 추가해 준 뒤 가만히 놔뒀었는데

 

특정 상황에서만 next_bp를 초기화하도록 로직을 수정했더니 util 점수가 무려 2점 올랐다.

 

해당 코드는 다음과 같다.

static void *coalesce(void *bp){
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));

    if (prev_alloc && next_alloc) {
        return bp;
    }

    else if(prev_alloc && !next_alloc){
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
        if (next_bp >= HDRP(bp) && next_bp <= FTRP(bp))
            next_bp = bp;
    }

    else if(!prev_alloc && next_alloc){
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp) , PACK(size,0));
        PUT(HDRP(PREV_BLKP(bp)) , PACK(size, 0));
        bp = PREV_BLKP(bp);
        if (next_bp >= HDRP(bp) && next_bp <= FTRP(bp))
            next_bp = bp;
        
    }

    else {
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)) , PACK(size,0));
        PUT(FTRP(NEXT_BLKP(bp)) , PACK(size,0));
        bp = PREV_BLKP(bp);
        if (next_bp >= HDRP(bp) && next_bp <= FTRP(bp))
            next_bp = bp;
    }

    return bp;
}

 

각 if와 else 문 안에 작은 if문이 들어있는 것을 확인할 수 있다.

 

이는 이전에는 고려하지 않고 무조건 coalesce 함수가 요청되면 해당 if문으로 들어갔을 때

 

블록이 합쳐지면서 next_bp가 블록포인트 위치를 잘못 건들이는 경우가 발생할 수도 있었다.

 

하지만 그런 상황은 해당 if문 조건에서만 발생하므로 코드를 수정해주었다.

 

그리고 최종 util 점수가 44점에서 46점으로 상승했다.