Mimalloc: Free List Sharding in Action 논문 요약
미말록(Mimalloc) 이란?
마이크로소프트에서 개발한 성능 좋은 Memory Allocator.
다른 최신 Memory Allocator은 할당시간/메모리사용량/스레드 스케일링의 성능향상이 주된 목표이지만, mimalloc은 메모리 참조 지역성을 향상시키는데 포커스를 맞추었다.
미말록 장점 요약)
Free List 내에서 메모리 사이즈별로 큰 하나의 저장공간을 사용하는 대신, mimalloc page라고 불리우는 (약 64KB) 작은 페이지로 분할시켜두었다. 이는 할당된 메모리의 지역성을 유지시켜준다.
Bump Pointer 형식이 아닌 페이지별로 고정된 블록 사이즈를 가지는 Free List 방식을 사용한다. Free List 방식에 비하여 평균 2% 속도가 개선되고 메모리 할당 로직이 단순해지는 이점이 있다.
다른 최신 Memory Allocator와 같이, 쓰레드별로 로컬 힙을 사용하여 경합없이 할당이 가능하다.
다른 스레드에서 메모리 해제 시, 분리된 thread free list 를 두어 특정 상황(fast path)에서는 atomic 연산 없이 메모리 해제가 가능하도록 하였다.
분리된 free list 는 스레드 경합을 줄여주고 local free list로 한번씩 자동으로 옮겨진다.
할당/회수하는 코드 경로를 최적화해서 코어 라이브러리 코드라인수도 3500 밖에 되지 않는다.
코드에서 락을 사용하는 부분은 없고 atomic 연산만 사용한다.
메모리 해제 호출 횟수를 카운트하여 일정 횟수가 넘으면 큰 객체를 해제하는것으로 판단하여 지연 해제 리스트(deferred_free)에 넣어두고 무거운 동작을 매번 하지 않도록 지연시켰다.
지연 해제 리스트는 메모리가 압박을 받고 있고 추가 free list를 요구하는 시점에 콜백함수를 호출하여 부하를 감소시켰다. 이는 slow path라고 불리우는
malloc_generic이 호출되는 시점이다.그러나 slow path가 주기적으로 호출되지 않을 경우 한번에 큰 부하가 생길 수 있으므로 일반 free list에 메모리 할당시 일부 객체를 local free list에도 넣어두어 일정 횟수 이후에 slow path가 호출되도록 보장하였다.
미말록 힙 구조 (출처: Mimalloc: Free List Sharding in Action)