allocator의 종류와 특징
동적할당에 대해 어느 정도 안다고 가정한다.
allocator는 동적할당의 실질적인 동작을 구현해주는 구성요소다.
GC 언어들은 자신만의 메모리 청크를 미리 올려두고 쓰지만, C/C++같은 non-GC 언어들은 동적할당(malloc/new)을 할때 내부적으로 allocator 구현에 의해 동작한다.
근데 동적할당은 생각보다 고려할게 많다. 반복적으로 할당/해제되는 것에 대해서 실제 메모리 배치를 compact하게 유지할 필요가 있기 때문이다.
게다가 멀티스레드 환경에서 최적화를 하는 것도 골칫거리다.
기본 Allocator
따로 별다른 설정을 하지 않는다면, 운영체제에서 기본으로 적용되는 allocator들이 있다.
windows에서는 HeapAlloc이 있고, MacOS에는 libmalloc이 있다.
Linux에서는 ptmalloc 기반의 구현을 사용한다. 버전 1/2/3까지 있더라.
문제
일반적인 사용사례에서는 기본 allocator를 써도 충분하지만, 경우에 따라서는 단점이나 한계가 있을 수 있다.
- 멀티스레드 환경에서의 할당에서는 실행속도가 충분히 효율적이지 못하다.
- 메모리 단편화가 발생할 수 있다.
- 힙 사용량 프로파일링이 불가능하다.
이유
allocator들도 사실 내부적으로 스레드 간 동기화를 위한 Mutex나 Spinlock을 사용하곤 하는데, 그런 동기화 최적화 수준에서 성능차가 많이 벌어지는 것 같더라.
그리고 메모리 낭비를 최소화하기 위한 목적에서 보수적으로 구조를 잡다보니 할당성능이 떨어지는 부분도 있다.
적절한 커스텀 allocator들을 사용한다면 이 문제들을 부분적으로 해결하거나 보완해볼 수 있다.
하지만
다 trade-off는 존재한다.
일반적으로... 실행속도를 얻으면 메모리를 잃거나, 정지시간이 발생한다.
그래서 빠르다고 무작정 박을게 아니고, 특징과 장단점을 잘 파악하고 적용해야 한다.
그리고 표준 allocator들도 놀고만 있는건 아니라서, 지금도 계속 발전중에 있음을 염두에 둬야한다. 예전 벤치마크와 현재는 다를 수 있다.
jemalloc
custom allocator 중에서 가장 유명한 것 중 하나다.
이것도 동시성 환경에서의 빠른 성능과 메모리 단편화 해결, 프로파일링 기능 등을 제공한다.
벤치마크를 봤을때 tcmalloc과 비슷하거나 조금 더 빠른 수준인 것 같다.
기본 allocator보다는 최대 2배 정도 더 빠르다.
2005년에 FreeBSD에서 기본 allocator로 시작했고, Linux, MacOS 등에서도 사용 가능하다. Windows는 뭔가 잘 안됐던 것으로 기억한다.
클래스
jemalloc은 내부적으로 3가지 클래스를 나눠서 할당 영역을 관리한다.
small - 8B ~
large - 4KiB ~
huge - 4MiB ~
arena
가장 큰 메모리 단위를 arena라고 하는데, 동시성 수준에서의 최적화와 약간의 메모리 풀링을 위해 존재한다. 그래서 코어 갯수에 비례해서 arena 개수가 정해진다.
arena에는 실제 메모리를 참조하는 여러가지 정보들이 존재한다.
스레드마다 최소 한개씩의 arena가 주어지고, arena끼리는 거의 독립적으로 동작하기 때문에 동기화 비용을 최소화할 수 있다.
스레드 캐싱
멀티스레드 환경에서의 최적화를 위해 스레드 캐싱 개념을 적용했다.
스레드마다 32KB 정도의 캐시를 두고, 캐시에 사용 가능한 메모리가 있다면 arena에 접근할 필요도 없이 바로 할당해서 쓸 수 있도록 하는 것이다.
이를 통해 빈번한 할당에서의 성능최적화를 얻을 수 있었다.
하지만 우습게도, 이 캐시를 정리하기 위해서 캐시 영역에 대해 내부적으로 Incremental GC를 돌린다.
메모리 단편화
내가 알기로는 메모리 단편화 문제가 가장 적다. tcmalloc보다도 적은 것으로 알고 있다.
jemalloc은 buddy allocation이라고 하는 방법을 통해서, 단편화될 수 있는 메모리를 실시간으로 분할하거나 merge해서 공간을 확보하는 방법을 사용한다.
세부 알고리즘은 꽤 복잡한데, 대충 설명하자면 메모리 할당이 일어날때 가장 작은 메모리 블록을 찾아서 넣는 것이다. 딱 맞는 작은 블록이 없다면 큰 블록을 쪼개서 쓰고, 해제되면 다시 merge한다.
메모리 반환
곧 아래에서 설명할 tcmalloc과 다르게 해제된 메모리는 웬만해서 바로 OS에 반환한다.
단점
jemalloc이 모든 부분에서 완벽했다면 모든 환경에서 기본 allocator로 사용했을 것이다.
이건 실행성능을 최적화하기 위해서 memory footprint를 희생한 측면이 있다. 여기저기 캐시 박고, 메모리 들고서 재사용하고, 그런 것들이 있기 때문이다.
그래서 기본 allocator들에 비해서는, 실제 사용량보다 많은 메모리를 점유할 수도 있다. 내가 봤던 벤치마크에서는 2배 정도 더 먹기도 했다.
tcmalloc
구글에서 만든 allocator다.
C/C++에도 종종 쓰고, Go에서는 기본 allocator로 사용하고 있다.
크롬 같은 구글 구현체들은 대부분 tcmalloc을 쓴다.
동시성 환경에서의 빠른 성능과 메모리 단편화 해결, 프로파일링 기능 등을 제공한다.
극단적인 멀티스레드 환경에서는 최대 2배의 성능향상을 보이고, 일반적인 환경에서도 10-20% 정도는 빨라지는 것 같다.
3 레이어
tcmalloc은 3가지 레이어로 나눠서 메모리 할당을 관리한다.
백엔드, 미들엔드, 프론트엔드다.
백엔드는 OS에서 직접 메모리를 할당해오고, 미들엔드는 할당해온 메모리를 적절히 관리한다.
그리고 프론트엔드는 모아놓은 메모리를 빠르게 프로그램에 나눠준다.
클래스
효율적인 메모리 배치를 위해 메모리 크기를 60가지의 클래스로 매우 세분화해서 관리한다. 이것으로 메모리 파편화 문제를 줄인다.
스레드 캐싱
tcmalloc도 위에서 설명한 jemalloc처럼 스레드 캐싱 매커니즘을 사용한다.
원리는 jemalloc과 비슷하다.
메모리 반환
이건 사실상 GC 런타임을 위에 올린거나 다름없어서, 메모리를 할당해제하더라도 OS에 그걸 바로 반환하지 않는다.
해제 후에도 그 메모리 풀을 활용해서 할당성능은 좋을 수 있지만, 메모리 사용량 측면에서는 jemalloc보다 비효율적일 수 있다.
단점
이것도 실행속도를 얻기 위해 footprint를 희생하는 케이스다.
캐시도 캐시고, GC 런타임처럼 자체 메모리 풀을 들고서 반환하지 않은 채로 쓰기 때문이디.
그래서 기본 allocator에 비해서 2-3배의 공간을 더 점유할 수 있다...
그 외...
windows에서만 제공되는 nedalloc, 그리고 mimalloc, Hoard, concur 등등 다양한 구현체가 존재한다.
하지만 jemalloc이나 tcmalloc만큼 실행성능이 크게 좋지는 못하더라.
게다가 환경에 따라서는 오히려 표준 allocator보다 느리기도 하다.
참조
https://jemalloc.net/
https://yscho03.tistory.com/m/299
https://stackoverflow.com/questions/8224347/malloc-vs-heapalloc
https://blackwinghq.com/blog/posts/playing-with-libmalloc/
https://jemalloc.net/
https://engineering.fb.com/2011/01/03/core-infra/scalable-memory-allocation-using-jemalloc/
https://stackoverflow.com/questions/18033518/what-are-the-windows-and-linux-native-os-system-calls-made-from-malloc
https://www.slideshare.net/JangHoon1/jemalloc-92835449
https://stackoverflow.com/questions/13027475/cpu-and-memory-usage-of-jemalloc-as-compared-to-glibc-malloc
https://goog-perftools.sourceforge.net/doc/tcmalloc.html
https://stackoverflow.com/questions/7852731/c-memory-allocation-mechanism-performance-comparison-tcmalloc-vs-jemalloc
https://stackoverflow.com/questions/9866145/what-are-the-differences-between-and-reasons-to-choose-tcmalloc-jemalloc-and-m
https://medium.com/daangn/memory-allocator-for-mongodb-1953f9cee06c
https://en.m.wikipedia.org/wiki/Buddy_memory_allocation