jun-wiki
으윽… 벌써 금요일, 그것도 8월 중순을 지나 하순…
시간 더럽게 빠르다
여름 옷밖에 없어 가을 옷을 사거나 해야 할 듯하다
아무튼, 오늘은 제대로 된 동적 메모리 할당을 위해서 매크로 구현을 시작했다
매크로
매크로란 일종의 함수다
단, 실제 함수랑 다르니 주의해서 쓰자
자세한 건 웹서핑하셈 ㅇㅇ
(대충 인수들은 괄호로 안묶어주면 원하는대로 작동안할 수 있다는 내용)
상수
먼저 염두에 두어야 할 것은 지금 하는건 동적 메모리 할당기를 모의로 구현한다는 거다
실제 32비트나 64비트 기종에 맞추어 하는게 아니란 사실이다
그러니 몇 바이트 워드로 만들지 우리가 정해야 한다
그렇기에 #define으로 이와 관련해 상수를 정해주고 시작한다
#define ALIGNMENT 8 /* 페이로드 정렬규칙 */
#define WSIZE 4 /* 메타데이터 워드의 폭 */
#define DSIZE 8 /* 더블워드 */
#define CHUNKSIZE (1<<12) /* 힙 확장할때 쓸 양 (4096) */
#define MIN_BLOCK (2*DSIZE) /* 최소 블록 크기 지정 */
페이로드는 유저가 쓸 실질적 공간이다
이렇게 미리 정해줘야 규격에 맞는 동적 할당기 설계가 가능하다
매크로 하는 거
이제 필요한 매크로들과 이들의 역할을 알아보자
사실 오늘은 여기까지만 해도 개인적으로는 만족일 정도로 중요하다 생각한다
매크로랑 기본 상수만 잘 알아두어도 훨 실제 구현하기 편해지니 말이다 emoji
#define PACK(size, alloc) ((size) | (alloc))
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp)) - DSIZE))
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
/*
* PACK = alloc에 0또는 1 넣어서 하위 3비트에 함께저장
* GET,PUT = p에서 WSIZE 읽기/쓰기
* GET_SIZE,ALLOC = 헤더/푸터의 워드 값에서 크기와 할당 비트만 추출
* HDRP = 현재 블록의 헤더 주소
* FTRP = 현재 블록의 푸터 주소
* NEXT_BLKP = 다음 블록의 bp
* PREV_BLKP = 이전 블록의 bp (이전 블록 할당이면 불가)
* ALIGN = 임의 크기 size를 8바이트 배수에 맞추기 [예) ALIGN(13) = 16]
* SIZE_T_SIZE = ?
*/
이렇게 만들었다
ALIGN하고 SIZE_T_SIZE는 원래 있는거다
SIZE_T_SIZE는 아직도 어디다 쓰는지 모르겠다…
나중에 알게 되면 쓰겠다
1차시도
플래그 기록하는 거 또 헷갈림
정해진 크기로 정렬 했기에 최하비트가 빈다는 건 머리로는 이해하지만 코드에 적용을 못시킴
헤더에 저장 된 블록 크기 size가 정렬의 배수니까 0이 되는 하위 비트에 저장하는거란 거
다시한번 기억하고 | 연산자 갖다가 박아서 해결봄
1차시도 결과
흐음… 70점 나왔다
Results for mm malloc:
trace valid util ops secs Kops
0 yes 99% 5694 0.003270 1741
1 yes 99% 5848 0.003095 1889
2 yes 99% 6648 0.004667 1424
3 yes 100% 5380 0.003370 1596
4 yes 66% 14400 0.000040360902
5 yes 92% 4800 0.003151 1523
6 yes 92% 4800 0.002949 1628
7 yes 55% 12000 0.054986 218
8 yes 51% 24000 0.193120 124
9 yes 27% 14401 0.019199 750
10 yes 30% 14401 0.000356 40418
Total 74% 112372 0.288203 390
Perf index = 44 (util) + 26 (thru) = 70/100
보면 알 수 있듯이 7번 부터 점수가 꼴아박는다
묵시적 할당 리스트의 한계인가 보다
2차시도때는 책읽으면서 마음에 들었던 방식인 분리 가용 리스트 방식을 해볼 것이다
2차 시도는 분리 맞춤으로 하고 3차 시도는 간단한 분리 저장장치 방식으로
뭐, 반대일수도 있고
2차시도
이번에 들어가기 앞서 약간의 최적화를 위해 가용 블록에 푸터 없애기를 도입해보았다
대신 이럴 경우 푸터에 들어갈 값인 직전 블록 할당 상태를 헤더의 하위 3비트 안에 넣어야 한다
ㅅㅂ 개열심히 수정했는데 딱히 이득 못봤다;;
Results for mm malloc:
trace valid util ops secs Kops
0 yes 99% 5694 0.003318 1716
1 yes 99% 5848 0.003127 1870
2 yes 99% 6648 0.004664 1425
3 yes 100% 5380 0.003526 1526
4 yes 66% 14400 0.000046311688
5 yes 92% 4800 0.003189 1505
6 yes 92% 4800 0.002971 1616
7 yes 55% 12000 0.055878 215
8 yes 51% 24000 0.188125 128
9 yes 27% 14401 0.018276 788
10 yes 30% 14401 0.000355 40566
Total 74% 112372 0.283475 396
Perf index = 44 (util) + 26 (thru) = 71/100
혹시 first fit 문제일 수 있으니 next fit으로 수정해보자
3차시도
기존의 find fit (first fit 방식) 코드다
static void *find_fit(size_t asize) { void *bp; for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) { if (!GET_ALLOC(HDRP(bp)) && (GET_SIZE(HDRP(bp)) >= asize)) { return bp; } } return NULL; }걍 쭈욱 읽으면서 찾는 방식으로 보편적이다
이건 나중에 분할 리스트로 관리할때 쓸 생각이다 ㅇㅇ
그리고 이게
새로만든 find fit (next fit 방식) 코드다 ```c static void *find_fit(size_t asize) { char *bp;
// rover부터 힙 끝까지
for (bp = rover; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp)) >= asize) {
rover = bp; // 발견 지점 기억(선택)
return bp;
}
}
// 못 찾으면 리스트 처음부터 rover 직전까지
for (bp = heap_listp; bp < rover; bp = NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp)) >= asize) {
rover = bp;
return bp;
}
}
return NULL; } ``` 여기 외에도 `init`에 `rover` 설정하고 `place`(배치), `coalesce`(병합)에도 블록 포인터 위치 바뀔때마다 같이 변화하도록 설정했다
결과는…
…
Results for mm malloc:
trace valid util ops secs Kops
0 yes 91% 5694 0.000813 7004
1 yes 91% 5848 0.000524 11162
2 yes 96% 6648 0.001564 4251
3 yes 96% 5380 0.001576 3415
4 yes 66% 14400 0.000052275862
5 yes 90% 4800 0.001947 2465
6 yes 88% 4800 0.001837 2613
7 yes 55% 12000 0.005564 2157
8 yes 51% 24000 0.005111 4696
9 yes 27% 14401 0.019045 756
10 yes 43% 14401 0.000339 42443
Total 72% 112372 0.038372 2928
Perf index = 43 (util) + 40 (thru) = 83/100
와! 대략 10점이나 올랐다! emoji
솔직히 기대 안했다
점수 안떨어지면 다행이라 여겼는데 의외로 효과를 거둔 모양이다
| Trace | 1st Result (secs / Kops / util) | 2nd Result (secs / Kops / util) |
|---|---|---|
| 0 | 0.006920 / 823 / 99% | 0.000813 / 7004 / 91% |
| 1 | 0.006400 / 914 / 99% | 0.000524 / 11162 / 91% |
| 2 | 0.007588 / 876 / 99% | 0.001564 / 4251 / 96% |
| 3 | 0.004955 / 1086 / 100% | 0.001576 / 3415 / 96% |
| 4 | 0.000053 / — / 66% | 0.000052 / — / 66% |
| 5 | 0.004048 / 1186 / 92% | 0.001947 / 2465 / 90% |
| 6 | 0.003949 / 1215 / 92% | 0.001837 / 2613 / 88% |
| 7 | 0.078912 / 152 / 55% | 0.005564 / 2157 / 55% |
| 8 | 0.245567 / 98 / 51% | 0.005111 / 4696 / 51% |
| 9 | 0.021916 / 657 / 27% | 0.019045 / 756 / 27% |
| 10 | 0.000398 / 36211 / 30% | 0.000339 / 42443 / 43% |
| Total | 0.380706 / 295 / 74% | 0.038372 / 2928 / 72% |
| Perf Index | 71/100 (44 util + 26 thru) | 83/100 (43 util + 40 thru) |
마지막 줄만 보면 됨 ㅇㅇ
표로 비교해보자
으음… util이 메모리 효율이고 thru가 속도라고 아는데…
next fit이 더 속도가 높나 보다
초반 trace의 경우 first fit 우월했지만 이후의 과정에서 next fit 이 더 빠른것 같다
하긴 ㄹㅇ 구렸으면 책에서 next fit소개 안했겠지 ㅇㅇ
생각보다 탐색 기법 바꾸는게 유의미한 변화를 부르는 터라 다음 단계인 best fit도 구현해보겠다
속도보다는 메모리 효율 치중된 형태다
4차시도
거지 같은 거
코드가 길어지다 보니까
자잘한거 수정하다가도 방심하니 코드 터진다…
static void *find_fit(size_t asize) {
void *bp;
void *best = NULL;
size_t bp_size = GET_SIZE(HDRP(bp));
size_t best_size = __SIZE_MAX__;
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp))
&& (bp_size >= asize)
&& (bp_size <= best_size)) {
if (best == NULL) best = bp;
if (bp_size == asize) return bp;
best = bp;
}
}
if (best) return best;
else return NULL;
}
문제 생기는 곳이 아무래도 if문에다가 무호흡으로 && 써서 그런 거 같아서 좀 더 직관적으로 수정했다
효율은… 더 구려졌을지도 모르지만 작동 안하는 것보다는 낫다
static void *find_fit(size_t asize) {
void *bp;
void *best = NULL;
size_t best_size = __SIZE_MAX__;
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp))) {
size_t csize = GET_SIZE(HDRP(bp)); // 매 반복마다 갱신
if (csize >= asize) {
if (csize == asize) return bp; // 완벽 적합 → 즉시 반환
if (csize < best_size) {
best = bp;
best_size = csize; // 같이 갱신
}
}
}
}
return best; // 없으면 NULL
}
이렇게 하니 작동된다 emoji
bp_size 갱신을 루프 안으로 옮기고
best를 갱신할때 size 같이 갱신하게 했다
Results for mm malloc:
trace valid util ops secs Kops
0 yes 99% 5694 0.003553 1603
1 yes 99% 5848 0.003498 1672
2 yes 99% 6648 0.004987 1333
3 yes 100% 5380 0.003696 1455
4 yes 66% 14400 0.000051282353
5 yes 96% 4800 0.006708 716
6 yes 95% 4800 0.006430 746
7 yes 55% 12000 0.053784 223
8 yes 51% 24000 0.186176 129
9 yes 31% 14401 0.018497 779
10 yes 30% 14401 0.000476 30286
Total 75% 112372 0.287857 390
Perf index = 45 (util) + 26 (thru) = 71/100
결과는…
으음… 예상한대로 좀 아쉽다…
유틸은 확실히 올라갔지만 속도가 확연히 떨어졌으니 말이다
…
아니네 뭐야
유틸도 거의 그대로네 쓰레기 같은 거 ㅅㅂ
best fit은… 서비스 종료다…