mimalloc: 현대를 위한 고성능 확장 가능한 메모리 할당기

mimalloc은 malloc/free의 드롭인 대체재로 설계된 오픈소스 메모리 할당기다. MSR RiSE에서 Lean과 Koka를 위해 2020년에 처음 만들어졌고, 지금은 Microsoft 내부 서비스와 외부 프로젝트 전반에서 쓰인다. Bing 같은 서비스의 응답 시간을 개선했고, GitHub에 공개돼 12K+ stars를 기록했다. 최악의 할당 시간과 공간 오버헤드를 제한하고, 내부 단편화와 경합을 줄이는 것이 목표다.

적용 범위도 넓다.

• **NoGIL CPython 3.13+**의 allocator로 쓰인다.
• Unreal Engine에 통합돼 있다.
• 게임 Death Stranding에도 사용된다.
• Rust wrapper는 하루 10만 회 이상 다운로드된다.

코드베이스는 약 12K줄로 작고 내부 자료구조가 명확해 통합이 쉽다. 핵심 구조는 스레드마다 가진 thread-local heap인 theap과 그 안의 64 KiB page다. 각 page는 고정 크기 블록을 size class로 나눠 담고, 대부분의 할당과 해제는 동기화 없이 처리된다. 작은 할당은 free list에서 블록을 바로 꺼내는 빠른 경로를 타며, theap과 small_pages를 특수한 빈 구조로 초기화해 불필요한 분기를 줄인다. x64에서는 불과 두 개의 uncommon branch만 남는다.

해제도 같은 스레드라면 local_free에 push하고, 다른 스레드라면 thread_free에 CAS(compare-and-swap) 로 넣는다. 최신 mimalloc v3의 mi_ptr_page는 온디맨드로 할당되는 메모리 맵을 사용해 전역 free를 덮어쓸 때 들어오는 잘못된 포인터도 더 안전하게 걸러내며, used count로 페이지 전체 해제도 빠르게 판정한다.

페이지마다 free, local_free, thread_free의 3개 free list를 두는 방식은 수천 개의 리스트가 생겨도 충돌 가능성을 낮춘다. 이런 구조 덕분에 mimalloc은 작은 앱부터 500 GiB가 넘는 대규모 서비스까지 폭넓게 대응하고, 캐시 지역성과 확장성을 함께 확보한다. 복잡한 공유 자료구조 대신 독립 리스트를 많이 두고 충돌 확률을 낮추는, 랜덤화식 설계에 가까운 접근이다.