[TIL] 5주차 - (3) : 동적 메모리 할당 기법 개선하기

 
이번 포스팅에는 지난 (2) 의 코드를 개선할 방안을 나열한 뒤 각각 구현한 코드를 실행해 보고 해당 결과를 확인해보겠다.

---

 

교재 코드의 할당 구동 절차

 
1. init()으로 런타임 heap의 틀을 구색
 
2. 처음에 크기가 큰 heap을 할당 (CHUNKSIZE heap)
 
3. 할당과 반환 작업
 
4. 3번 진행 중에 크기에 맞는 가용 블럭이 없다면 2번 순서에서 진행한 heap을 재 할당
 
 

---

 
 

개선 방안 제시

 

1. first fit으로 가용블럭을 탐색하고 있는 코드

현재 코드는 first-fit으로 가용 블럭을 탐색하고 있다.
 
이 경우 heap의 초반부에 작은 블럭들이 편향되는 단점이 있으므로 next-fit과 best-fit으로 탐색하는 코드도 테스트 해 볼수 있다.
 
 
 

2. 즉시연결 (free 하자마자 연결탐색) 방식을 채택한 코드

이 빈 블록 병합 방법은 지연 연결을 사용할 수도 있다.
 
만약 테스트케이스에서 작은 node를 할당과 반환을 반복하는 경우가 많다면 지연 연결이 더 효율적일 수 있다.
 
 
 

3. Footer는 가용블럭일 때만 의미 있음

footer는 한 워드 크기만 차지하지만, 만약 많은 수의 블록들이 존재한다면 불필요한 Footer를 삭제하는 것이
n개의 W크기의 블록을 회수할 수 있다.
 
하지만 footer의 존재여부를 파악하는 방법을 생각하기 쉽지 않다.
 
 
할당되었지만 footer위치에 우연히 할당 코드가 0으로 되어있을 수 있기 때문이다.
 
따라서 footer를 제거하려면 다른 방법으로 할당 여부를 파악해야 할 것이다.
 
예를 들면 이전 블럭이 할당되었는지 파악하는 로직을 없애고, 지연 연결 방식을 채택하여 오름차순으로 다음 블럭만 파악해서 연결하는 방법이 있을 수 있을 것 같다.
 
 
 

4. 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;
}

 
현재 realloc() 함수이다.
 
이 realloc() 함수의 문제점은 realloc()함수를 호출 했을 때, 해당 포인터가 그 자리에서 확장해도 문제가 없을 경우를 고려하지 않고 무조건 free()와 재 할당을 수행한다는 점이다.
 
하지만 할당된 블록이 제자리에서 할당 범위 확장이 가능한 경우는 next-fit의 탐색 로직 상 거의 없다.
 
따라서 고려해볼만한 사항은 realloc() 함수로 할당 영역을 줄이는 경우이다.
 
위 코드는 realloc으로 할당 범위를 줄이더라도 cpy를 통해 새로 할당 후 free() 연산을 수행하고 있다.
 
이는 그저 header와 footer의 데이터를 수정해 주는 것으로 구현을 간단히 할 수 있을 것 같다.
 
 

---

 

1-1.  next-fit 성능 테스트

 
일단 next-fit과 best-fit을 구현하여 성능을 테스트 해 보았다.
 
아래는 next-fit의 코드이다.

static void *next_bp;


static void *next_fit(size_t asize){

    void *bp;

    for(bp = next_bp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))){
            next_bp = bp;
            return bp;
        }
    }

    for(bp = heap_listp; bp < next_bp; bp = NEXT_BLKP(bp)){
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))){
            next_bp = bp;
            return bp;
        }
    }

    return NULL;
}

 
 
일단 init()함수에서 heap_listp 변수를 +(2*WSIZE)할 때, `next_bp = heap_listp` 코드를 추가하여 static 변수 next_bp
 
를 초기화한 뒤에 탐색 시에 이전 탐색했던 블럭부터 탐색하는 용도로 사용한다.
 
 
에필로그 블록에 도달하면 SIZE가 0이되므로 첫번째 for문의 조건에 도달하며,
 
만약 에필로그 블록에 도달하면 다시 첫 블록부터 탐색을 다시 진행한다.
 
 
탐색은 한바퀴를 넘기지 않도록 next_bp까지만 진행한다.
 
 
이 next_bp를 구현하면서 고려해야 할 것이 있다.
 
바로 coalesce() 함수이다.
 
할당 과정에서 next_bp가 결정 된 뒤 해당 bp가 free()를 통해 반환되면서 coalesce()에서 해당 블록이 병합된다면,
next_bp가 가리키는 곳이 bp가 아니게 될 수 있다.
 
따라서 coalesce()에서 bp가 변경되는 로직에서 next_bp도 같이 수정해줌으로써 문제를 해결할 수 있을 것이다.
 

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));
        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));
        next_bp = PREV_BLKP(bp);
        bp = PREV_BLKP(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));
        next_bp = PREV_BLKP(bp);
        bp = PREV_BLKP(bp);
    }

    return bp;
}

 
next-fit을 사용함으로써 first-fit 구현 시의 점수였던 69점에서 -> 83점으로 올랐다.
 
 
모든 상황에서 next-fit이 first-fit보다 우수하다는 것은 아니지만
 
테스트 상황에서의 해당 지표를 통해 더 개선된 코드가 되었음을 확인했다.
 
 

---

 
 

1-2. best-fit 성능 테스트

 
책에서는 특정 연구 결과에 의하면 next-fit < first-fit < best-fit 순으로 높은 메모리 이용도를 가진다고 소개했지만, 해당
 
테스트에서는 next-fit이 first-fit 보다 좋은 성능을 냈다.
 
이는 first-fit과 next-fit의 각 장단점이 있기에
 
테스트마다 주로 요구되는 메모리의 크기와 반환의 빈도가 다르기 때문일 것이다.
 
 
아무튼 이번엔 완전 탐색 후 가장 적합한 크기의 블록에 할당하는 best-fit의 성능을 체크해 보자.
 
아래는 best-fit의 코드이다.
 

static void *best_fit(size_t asize){

    void *bp;
    void *best_bp = NULL;
    size_t besize = 0;
    for(bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))){
            if (best_bp == NULL){
                besize = (GET_SIZE(HDRP(bp)) - asize);
                best_bp = bp;
            }
            if (besize > (GET_SIZE(HDRP(bp)) - asize)){
                besize = (GET_SIZE(HDRP(bp)) - asize);
                best_bp = bp;
            }
        }
    }
    return best_bp;
}

 
besize 변수를 함수내에 선언하여 가용 가능한 블록을 탐색한 경우 해당 블록이 얼마나 현재 요구와 크기가 비슷한 지를 체크
 
한 뒤, 가장 요구와 적합한 블록을 할당한다.
 
 
해당 함수는 best_bp를 무조건 반환하도록 되어있는데, 이는 탐색에 실패할 경우 NULL을 반환하기 때문이다.
 
이 함수는 완전 탐색이기 때문에 first-fit과 동일하게 heap_listp를 통해 순회하며 다른 함수의 특정 코드를 변경할 필요도 없다.
 
 
성능을 체크해보니 의외로 낮은 점수인 '66점'이 나왔다.
 
 
first-fit 보다도 낮은 성능을 보이는데,
 
그 이유는 해당 테스트에서는 완전 탐색에서 소모하는 시간 성능가 적절한 블럭에 할당하는 것에 비해 더 많은 영향을 끼쳤기 때문일 것 같다.
 
 

1-3. best-fit customizing

 
해당 로직들을 적용해 보면서 문득
 
'블럭 트래픽이 많이 발생하는 구간에만 best-fit 로직을 적용하는 것으로 코드를 개선해 볼 수 있지 않을까?'
 
라는 생각이 들어서, 두가지 방법을 사용해서 세가지 탐색 방법을 섞어 보았다.
 
 

1 . best-fit + next-fit

 
이 방법은 트래픽이 많은 구간에서 best-fit으로 탐색하여 가장 적절한 블록에 할당함으로써 트래픽을 개선한 뒤,
 
뒤 부분은 자리가 있다면 바로 할당하는 방식으로 시간 소요는 best-fit보다 줄이려고 했다.
 
 
해당 코드는 다음과 같다.

static void *custom_best_fit(size_t asize){

    void *bp;
    void *best_bp = NULL;
    size_t besize = 0;

    for(bp = heap_listp; bp < next_bp; bp = NEXT_BLKP(bp)){
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))){
            if (best_bp == NULL){
                besize = (GET_SIZE(HDRP(bp)) - asize);
                best_bp = bp;
            }
            if (besize > (GET_SIZE(HDRP(bp)) - asize)){
                besize = (GET_SIZE(HDRP(bp)) - asize);
                best_bp = bp;
            }
        }
    }
    if (best_bp != NULL){
        next_bp = best_bp;
        return best_bp;
    }

    for(bp = next_bp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))){
            next_bp = bp;
            return bp;
        }
    }

    return NULL;


}

 
먼저 초반부에 적절한 블럭이 탐색되었다면 해당 블럭을 할당 받는 것으로 마무리를 하지만
 
그렇지 않을 경우 이후에는 next-fit 로직을 따른다.
 
 
해당 로직의 결과는 '69점'을 맞았다.
 
물론 best-fit보다는 개선되었다고 할 수 있지만, 아직 개선의 여지가 많아 보였다.
 
 
 
 

2. next-fit + best-fit

위의 best-fit을 한 후 뒤에서 next-fit 로직을 사용하는 custom best-fit을 짜고나서 왜 데이터 할당 효율성이 눈에 띄게 차이나지 않는 건지 생각을 해보았다.
 
근데 블록 traffic이 있는 부분보다 없는 부분이 경우의 수가 더 많을테니까
그 구간을 더 정교하게 할당하는 것이 데이터 배정에 더 효율적일 것 같다는 생각이 들었다.
 
그래서 이번엔 반대로 next-fit의 next-bp부터는 그냥 무조건 할당을 하고, 적절한 가용 블록이 없다면
next_bp까지 정교한 best-fit 할당을 해보자는 생각이 들었다.
 
그 코드가 아래와 같다.
 

static void *custom_best_fit_2(size_t asize){

    void *bp;
    void *best_bp = NULL;
    size_t besize = 0;

    for(bp = next_bp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))){
            next_bp = bp;
            return bp;
        }
    }

    for(bp = heap_listp; bp < next_bp; bp = NEXT_BLKP(bp)){
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))){
            if (best_bp == NULL){
                besize = (GET_SIZE(HDRP(bp)) - asize);
                best_bp = bp;
            }
            if (besize > (GET_SIZE(HDRP(bp)) - asize)){
                besize = (GET_SIZE(HDRP(bp)) - asize);
                best_bp = bp;
            }
        }
    }

    return best_bp;
}

 
그냥 간단히 생각하면 next_bp를 기억하는 메커니즘을 통해 next_bp 이후 블럭은 first-fit으로 할당하고
 
이후 없다면 heap_listp로 돌아와 next_bp까지 best-fit으로 할당하는 방식이다.
 
 
이 방식이 놀랍게도 미세하지만 next-fit보다 더 높은 효율성을 보였다.
 
이 방식은 현재 최고점수인 '84점' 을 받을 수 있었다.
 
 
 

---

 
 

2. 지연 연결 활용

 
두번째로 개선할 방안은 바로 즉시연결 방법을 지연 연결 방법으로 전환하는 것이다.
 
이 방법은 작은 데이터 할당을 빠르게 요청하고, 할당하는 작업을 반복하는 경우 효율적인 방법이다.
 
 
프로그램 상 어떤 테스트 방식으로 점수를 채점하는지 알 수 없기도 하고, 이 방식이 얼마나 효율적인지 테스트하기 위해서
 
코드를 짜 보았다.
 
 
코드를 보기 전에 지연 연결 활용을 간단히 정리하면
 
블럭을 free()로 반환할 때, coalesce()함수를 호출하여 가용 블럭들을 병합하는 것이 아니라
 
할당을 요청할 때 만약 적당한 블록을 찾지 못하면 extend_heap으로 힙을 할당 받지 않고 가용 블럭 병합을 진행하는 것이다.
 
따라서 실행 순서는 다음과 같다.
 
 1. 사용자가 요청한 크기의 블럭을 탐색하는 과정에서 NULL이 반환됬다.
 
 2. coalesce_delay_v() 으로 지연 연결 함수를 호출한다.
 
 3. 가용 블럭을 모두 병합한 뒤, first-fit을 호출한다.
 
 4.그 이후에도 NULL을 호출 시 extend_heap()으로 CHUNKSIZE heap을 새로 할당받는다.
 
 
이 모든 과정이 malloc 메인 함수에 들어가기 때문에 매우 복잡할 것 같지만,
 
사실 1번처럼 NULL이 반환 되었을 때만 해당 플로우를 거치기 때문에 시간 성능에는 큰 문제를 일으키지 않았던 것 같다.
 
코드는 다음과 같다.

void *mm_malloc(size_t size)
{
    size_t asize;
    size_t extendsize;
    char *bp;
    if (size == 0){
        return NULL;
    }
    if (size <= DSIZE){
        asize = 2*DSIZE;
    }
    else{
        asize = DSIZE * ((size+(DSIZE) + (DSIZE-1)) / DSIZE);
    }

    if ((bp = custom_best_fit_2(asize)) != NULL){
        place(bp, asize);
        return bp;
    }

    coalesce_delay_v();
    
    //delay merging block
    if ((bp = first_fit(asize)) != NULL){
        place(bp,asize);
        return bp;
    }
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL){
        return NULL;
    }
    place(bp, asize);
    return bp;
}


void mm_free(void *bp)
{
    size_t size = GET_SIZE(HDRP(bp));
    PUT(HDRP(bp) , PACK(size,0));
    PUT(FTRP(bp) , PACK(size,0));
    // coalesce(bp);
}


static void *coalesce_delay_v(void){
    void *bp;
    for(bp = heap_listp; GET_SIZE(HDRP(NEXT_BLKP(bp)))>0; bp = NEXT_BLKP(bp)){
        if (!GET_ALLOC(HDRP(bp))){
            while(!GET_ALLOC(HDRP(NEXT_BLKP(bp)))){
                size_t size = GET_SIZE(HDRP(bp)) + GET_SIZE(HDRP(NEXT_BLKP(bp)));
                PUT(HDRP(bp), PACK(size, 0));
                PUT(FTRP(bp), PACK(size, 0));
            }
            next_bp = bp;
        }
    }
}

 
기존의 mm_malloc() 함수에는 coalesce_delay_v()를 호출 하고 first-fit()을 호출하는 로직이 추가되었고,
free()에서는 coalesce()를 호출하는 코드가 주석 처리 되었다.
 
그리고 제일 마지막 coalesce_delay_v() 함수에서 보듯이, 첫 bp부터 마지막까지 완전탐색으로 병합을 한다.
 
for 문 안에서는 while 문을 통해서 만약 한 bp로 병합을 계속 해야 한다면 반복을 하도록 구현해 보았다.
 
 
 
그리고 최종적으로 지금까지 가장 성능이 좋았던 custom v2 fit 방식에 지연 연결 방식을 도입한 후
 
가장 좋은 점수인 85점을 받을 수 있었다.
 

 
 

---

 

마무리

 
남은 이번주 주차동안 realloc() 함수의 변환과 이후 segregation 방식이 성능이 좋다고 하는 것을 들어서
교재의 더 좋은 방법들을 읽어보고 해당 개선 점들을 개선해 나갈 예정이다.
 
그 구현에 관해서는 이후에 포스팅 하겠다.