WEEK 7. 탐험 준비 - C malloc 구현

크래프톤 정글 기간에 쓴 글을 2026-08-21에 다시 정리했다.

이번 주 목표

주가 시작할 때 세운 목표다.

이번 주에 하기로 한 것은 세 가지다.

1. CSAPP 9.9장(동적 메모리 할당) 전체 학습
2. 직접 malloc 구현하기
3. B+ 트리를 활용한 팀 프로젝트 기획

어디까지 어떻게 시도했는가

CSAPP 9.9장

9.9.1부터 9.9.12까지 학습했다.
동적 메모리 할당기의 설계 원칙부터 implicit free list, 경계 태그, 가용 블록 탐색 전략까지 순서대로 읽어나갔다.

이번 malloc 구현과 맞물려서 이론이 실제 코드로 어떻게 연결되는지 직접 확인할 수 있었던 점이 컸다.

malloc 구현 — implicit + next-fit

처음에는 implicit free list와 first-fit 조합으로 구현했다. 그런데 성능 점수가 56%에 그쳤다.

점수를 올리려고 두 가지를 바꿨다.

• 탐색 방식을 first-fit에서 next-fit으로
• realloc에서 memcpy를 쓰는 대신 제자리 확장과 힙 끝 확장 방식을 도입

결과는 86점이었다. 팀 4명 중 3등이었지만, next-fit 하나로 30점 가까이 오르는 것을 보면서 탐색 전략이 성능에 얼마나 큰 영향을 미치는지 체감했다.

구현이 끝난 뒤에는 팀원들과 각자 코드를 리뷰하는 시간을 가졌다.

B+ 트리 프로젝트 — League of Legends 랭킹 서비스

내가 먼저 「B+ 트리를 활용한 게임 데이터 서비스」를 제안했다. op.gg처럼 게임 데이터를 B+ 트리 인덱스로 탐색하는 구조다.

팀은 개발 조와 자료조사 조로 나뉘었다. 역할은 핀볼 게임을 해서 정했다 — 요즘 우리 반이 핀볼에 빠져 있어서다.
나는 자료조사 조로 합류해 B+ 트리의 개념을 조사했다. 선형 탐색 → B 트리 → B+ 트리의 차이, 그리고 실제 서비스 적용 사례를 정리했다.

Riot API로 데이터를 수집하는 과정이 험난했다.

시도	한 일	결과
1차	Challenger~Silver 수집 (2~3시간)	상위 랭크는 전부, 나머지는 500개씩 다시 하기로
2차	재수집 (약 2시간)	Riot이 닉네임을 닉네임#태그로 바꾼 걸 놓쳐 전부 unknown
3차	닉네임#태그 형식으로 재시도	데이터 용량이 너무 커서 내 컴퓨터에서 계속 오류
4차	raw로 받아온 뒤 후처리하는 방식으로	Challenger~Emerald 500개, Platinum~Iron 100개. 새벽 4시 30분까지

결국 프로젝트가 영어 외의 문자를 파싱하지 못하는 문제가 있었다. 게다가 발표하는 컴퓨터가 dev 브랜치를 pull 받지 못해서, 발표할 때는 데이터가 전부 더미인 상태로 진행되었다.
이후 비영어 문자를 null로 변환하는 처리를 추가했더니 서버에서 바로 열렸다.

험난했지만 API 수집 전반에 대해 많은 것을 배웠다.

새롭게 배운 점

first-fit과 next-fit은 무엇이 다른가

둘 다 빈 블록을 앞에서부터 훑는다는 점은 같다. 다른 것은 어디서부터 훑느냐다.

graph LR
    B1["블록 1"] --> B2["블록 2"] --> B3["블록 3"] --> B4["블록 4"] --> B5["블록 5"]

• first-fit — 요청이 올 때마다 늘 블록 1부터 다시 본다
• next-fit — 지난번에 찾은 자리부터 이어서 본다. 블록 3에서 찾았으면 다음엔 블록 4부터

앞쪽에는 작은 조각이 쌓인다. 큰 블록을 쪼개 쓰고 남은 자투리들이 앞에 모이기 때문이다.
first-fit은 요청이 올 때마다 그 자투리들을 처음부터 다시 지나쳐야 한다. 쓸 수 없는 걸 알면서도 매번 훑는 셈이고, 요청이 많아질수록 그 헛걸음이 그대로 쌓인다.

next-fit은 지난번에 멈춘 곳부터 이어 보기 때문에 그 반복을 건너뛴다. 탐색이 빨라진 만큼 처리량이 오르고, 그것이 점수로 나타났다.

이번 주 아쉬웠던 점

malloc 구현 방식 — implicit + first/next-fit으로만 해본 것이 아쉽다.
best-fit이나 explicit free list, segregated list 같은 방식도 직접 구현해봤으면 얼마나 달랐을지 궁금하다.

시간 관리 — Riot API 수집에서 시간을 제대로 못 썼다.
API를 처음 써보다 보니 예상치 못한 변수들(닉네임 형식 변경, 용량 문제, 인코딩 이슈)에 대응하는 데 너무 많은 시간이 들었다.

역할 — 자료조사 조보다 구현 조에 있었으면 어땠을까 하는 아쉬움이 남는다.
물론 각자의 자리에서 열심히 했다. 다음 협업에서는 기능을 나눠 다 같이 구현에 참여하는 방식으로 해보고 싶다.

다음 주 계획

다음 주의 핵심은 네트워크 프로그래밍이다. C 언어로 웹 서버와 프록시를 직접 만들어보는 것이 목표다.

1. CSAPP 11장 학습
2. 소켓을 이용한 간단한 클라이언트/서버 구현
3. HTTP 프로토콜 이해 → tiny 웹 서버 완성
4. 숙제 문제 11.6c, 7, 9, 10, 11 중 세 문제 이상 풀기
5. 프록시 과제 도전 — 순차 처리 → 병렬 처리 → 캐시 순서로

수요 코딩회에서는 이전에 만든 B+ 트리 인덱스를 활용해 미니 DBMS API 서버를 구현한다.
스레드 풀(Thread Pool)을 구성해 SQL 요청을 병렬로 처리하는 구조까지 만드는 것이 목표다.

목표 흐름 — 소켓 이해 → 에코 서버 → tiny 웹 서버 → 숙제 문제 → 프록시 도전