O(1)인데 왜 느려질까 (메모리 성능의 진짜 문제)

앞에서 malloc이 내부적으로 메모리를 어떻게 관리하는지 정리했다.

• free된 블록은 다시 재사용하고
• 크기별로 bin에 넣어두고
• 필요하면 쪼개고(splitting)
• 다시 합치기도(coalescing) 한다

여기까지 보면 자연스럽게 이런 생각이 든다.

“이 정도면 꽤 단순한데? 대부분 빠른 거 아닌가?”

실제로도 맞다.
대부분의 malloc/free는 빠르다.
그런데 문제는 “대부분”이라는 말에 있다.

실제 시스템에서는 평균적으로 빠른 것보다,
가끔 느려지는 순간이 있는지가 더 중요할 때가 많다.

그리고 메모리 문제는 딱 그 지점에서 터진다.

O(1)이라는 말부터 조금 다르게 봐야 한다

처음에 많이 헷갈리는 부분이 이거다.

O(1)이면 빠르다는 뜻 아닌가?

보통은 그렇게 받아들이기 쉬운데, 정확히는 그렇지 않다.

O(1)은
“항상 빠르다”는 뜻이 아니라
입력 크기에 따라 시간이 늘어나지 않는다는 뜻에 가깝다.

즉,

• 데이터가 10개든
• 1000개든
• 100만 개든

실행 단계 수가 크게 늘지 않으면 O(1)이라고 부른다.

그런데 여기서 중요한 건,
O(1)이라고 해도 실제 시간은 얼마든지 달라질 수 있다는 점이다.

같은 O(1)이라도

• CPU 캐시에 걸리면 빠를 수 있고
• 메모리를 다시 뒤져야 하면 느릴 수 있고
• 아예 커널까지 들어가면 훨씬 느려질 수 있다

즉, O(1)은 성장 방식을 말하는 거지,
“무조건 빠르다”는 보장은 아니다.

평소의 malloc은 왜 빠를까

평소 malloc이 빠른 이유는 생각보다 단순하다.

필요한 크기의 free 블록이 이미 준비돼 있으면,
그걸 그냥 꺼내서 주면 끝이다.

예를 들면 이런 식이다.

32B bin → [32][32][32]

여기서 malloc(32)가 오면
32B bin에서 하나 꺼내면 된다.

이건 거의 추가 작업이 없다.
OS에 새로 요청할 필요도 없고,
큰 탐색도 필요 없다.

그래서 malloc이 보통은 빠르다.

그런데 항상 이렇게 이상적으로 돌아가지는 않는다

문제는 요청이 항상 allocator가 기대한 모습으로 들어오지 않는다는 데 있다.

예를 들어 32바이트가 필요한데
32B bin이 비어 있고, 64B 블록만 남아 있다고 해보자.

그럼 단순히 꺼내서 줄 수 없다.
이제부터는 추가 작업이 생긴다.

• 더 큰 블록을 찾아야 하고
• 필요하면 쪼개야 하고
• 그 과정에서 내부 상태도 바꿔야 한다

즉, “빠른 경로”에서 벗어난다.

이 순간부터는 같은 malloc이라도 비용이 달라진다.

splitting은 단순해 보여도 계속 쌓이면 문제가 된다

앞에서 본 것처럼 splitting은
큰 블록을 쪼개서 필요한 만큼만 쓰는 과정이다.

예를 들면:

[ 64B free ]
↓
[ 32B 사용 ][ 32B free ]

이 자체는 별일 아닌 것처럼 보인다.
실제로도 한 번만 보면 큰 비용은 아니다.

그런데 이런 일이 계속 반복되면
메모리 상태가 점점 잘게 쪼개진다.

그리고 이 조각난 상태가 누적되면
나중에는 “총 free 메모리는 충분한데, 쓸 수 있는 큰 블록은 없는” 상황이 생긴다.

이게 fragmentation이다.

즉, splitting 자체가 문제라기보다는
splitting이 계속 누적된 결과가 문제를 만든다.

free도 그냥 끝나는 게 아니다

free도 단순해 보이지만, 항상 “표시만 하고 끝”나는 건 아니다.

인접한 free 블록이 있으면
allocator는 그걸 다시 합쳐서 큰 블록으로 만들려고 한다.

예를 들면:

[ 32B free ][ 32B free ]
↓
[ 64B free ]

이게 coalescing이다.

이 과정이 필요한 이유는 분명하다.
쪼개진 메모리를 다시 큰 블록으로 복구해야,
나중에 큰 요청이 들어왔을 때 대응할 수 있기 때문이다.

그런데 이 합치는 과정도 결국 일이다.

• 앞 블록이 free인지 확인해야 하고
• 뒤 블록도 확인해야 하고
• 실제로 합쳤으면 관리 구조도 갱신해야 한다

즉, free도 언제나 “공짜”는 아니다.

진짜로 느려지는 순간은 따로 있다

여기까지는 그래도 allocator 내부에서 해결하는 문제다.
그런데 정말 눈에 띄게 느려지는 순간은 대개 그 바깥에서 생긴다.

대표적인 게 mmap이다.

malloc이 내부에서 더 이상 줄 블록을 찾지 못하면
결국 OS에 새 메모리를 요청해야 한다.
이때 자주 나오는 방식이 mmap이다.

이 순간부터는 단순한 라이브러리 함수 호출이 아니라,

• 시스템 콜이 발생하고
• 커널로 들어가고
• 새로운 매핑이 만들어지고
• 페이지 단위 관리가 개입된다

즉, 비용이 확 달라진다.

평소에는 아주 빠르게 끝나던 malloc이
갑자기 훨씬 무거운 경로를 타게 되는 것이다.

그래서 “대부분 빠른데, 가끔 느리다”가 된다

이제 그림이 좀 보인다.

평소에는:

• bin에서 바로 꺼내고
• 내부에서 재사용하고
• 추가 작업이 거의 없다

이 상태라서 빠르다.

그런데 특정 순간에는:

• 적당한 블록이 없고
• 더 큰 블록을 찾아야 하고
• splitting이 생기고
• free 과정에서 coalescing이 생기고
• 심하면 mmap까지 간다

즉, 같은 malloc/free라도
항상 같은 비용으로 끝나는 게 아니다.

이게 메모리 성능을 이해할 때 중요한 포인트다.

평균보다 더 중요한 건 “가끔 느린 순간”이다

실제 서비스에서는 평균이 괜찮아도 문제가 생길 수 있다.

예를 들어 요청 1000개 중 999개는 빨라도,
1개가 유난히 느리면 사용자는 그 느린 요청을 체감한다.

그리고 운영에서는 이런 “가끔 느린 순간”이 더 문제다.

메모리 allocator도 마찬가지다.

평소에는 잘 돌아가지만,
특정 타이밍에만 느린 경로를 타면
그 순간 latency spike가 생긴다.

그래서 성능 분석에서는 단순히
“평균적으로 빠르냐”보다

언제 느린 경로로 빠지는가

를 보는 게 훨씬 중요하다.

결국 O(1)과 실제 성능은 다른 이야기다

정리하면 이렇다.

malloc이 O(1)에 가깝다고 말하는 건
대부분의 일반적인 경로가 단순하기 때문이다.

하지만 실제 시스템에서는:

• bin miss
• splitting
• coalescing
• mmap
• cache miss
• page fault

같은 것들이 개입하면서
“복잡도”와는 다른 차원의 성능 문제가 생긴다.

즉, O(1)이라는 말만으로는 실제 체감 성능을 설명할 수 없다.

그래서 성능 엔지니어링에서는
알고리즘 복잡도도 보지만,
결국엔 실제 latency를 같이 봐야 한다.

여기까지 오면 다음 질문이 생긴다

이제 자연스럽게 이런 궁금증이 생긴다.

free를 했는데 왜 메모리 사용량은 그대로일까?
RSS는 뭘까?
page cache랑 anonymous memory는 뭐가 다를까?

이건 allocator 내부 동작만으로는 설명이 안 되고,
운영체제가 메모리를 어떻게 보느냐까지 같이 봐야 한다.

그 부분은 다음 글에서 이어서 정리하면 자연스럽다.

한 줄 정리

malloc은 대부분 빠르지만, 실제 성능 문제는 bin miss, splitting, coalescing, mmap처럼 가끔 느린 경로로 빠지는 순간에 생긴다.