스택? 힙? 전공시간에 분명히 배우긴 했는데..

전공자라면 스택과 힙에 대해서는 당연히 공부해 봤을 것입니다. 저 또한 그렇고요. 하지만, 내가 정말 이에 대하여 빠삭하게 이해하고 있는 것일까요? 확신이 들지 않습니다. 스스로에게 질문을 던져봅시다.

스택이 뭐고, 힙은 뭐죠? 

스택은 자료구조 시간에서도 배우죠. Problem Solving, 알고리즘 문제를 풀 때도 자주 활용하고요. 가장 먼저 생각나는 특징을 살펴보자면, LIFO (Last In First Out), 먼저 삽입된 요소가 가장 나중에 추출된다는 특징을 가지고 있습니다.

이렇게 접근하니, 스택은 무언가 요소를 담았다가 뺄 때 사용되는 자료구조와 같이 느껴집니다. 이는 사실일까요? 함수 재귀 호출또한 스택에 쌓이는 방식으로 진행됩니다. 가장 먼저 호출된 함수가 가장 마지막에 리턴되죠.

네, 스택은 자료구조의 한 종류라고 볼 수 있을 것 같습니다.

이제 힙에 대하여 생각해 보겠습니다. 먼저, 왜 스택을 얘기할 때 힙이 함께 떠오르는 것일까요? 이는 아무래도 메모리 구조 때문이겠죠 

바로 위 이미지는 프로그램의 한 인스턴스, 즉 프로세스의 메모리 구조를 보여줍니다. 여기서 text 영역엔 실행되는 코드들이 저장되고, data 영역에는 초기화된, 혹은 초기화되지 않은 전역 변수의 값이 저장됩니다. 그 다음에 존재하는 것이 바로 스택 영역과 힙 영역 입니다.

스택 영역은 간단하게 지역 변수를 저장하고, 힙 영역에서는 동적 변수 메모리 할당에 활용 됩니다. 

사실, 여기서 힙하면 바로 떠오르는것이 있습니다. 바로 트리형태의 자료구조 힙이죠. 스택 메모리와 스택 자료구조가 유사하듯이, 힙 메모리와 트리형태의 힙 자료구조와 관련이 있는 것일까요? 정답은 "아니다" 입니다. 스택과 다르게, 같은 용어를 사용하지만 전혀 다른 개념입니다.

메모리 구조 상의 힙 영역은 동적 변수 할당을 위해 활용되는 공간으로, 전역적으로 접근 가능한 변수나 객체등이 저장되는, 자신만의 라이프 사이클을 갖는 자료들이 저장되는 공간입니다.

여담으로, '힙'이라는 단어는 무질서하게 쌓여 있는 객체 더미 또는 집합을 의미한다고 합니다.

메모리 구조를 왜 그렇게 분리한 것일까요?

당연히 각각이 가지고 있는 특징이 다르고, 그 특징들 모두 유용하기 때문에 분리하여 함께 활용할 것이라고 생각합니다. 그러니, 그 특징이 무엇인지 알아보면 되는 것이죠.

특히, 프로그래밍과 메모리 관리 측면에서 생각해볼 수 있습니다.

먼저, 스택 메모리는 힙 메모리보다 훨씬 빠릅니다. 즉, 메모리를 할당하고 제거하는 속도가 빠르다는 뜻이죠. 이는 스택의 LIFO 라는 특징에서 기인합니다. 함수에 진입할 때 데이터를 밀어넣고, 함수가 종료되면 특별히 관리할 필요없이 데이터를 빼내면 되는 것이죠. 그렇기에, 이는 로컬 변수를 저장하는데 매우 적합합니다. 로컬 변수가 함수가 실행하는 동안에만 존재하면 되니까요.

스택메모리에 저장되는 값에는 무엇이 있을까요?

먼저 return address 가 저장됩니다. 함수가 종료되면 program counter 가 돌아갈 주소가 저장되어야 겠죠. 다음으론 당연히 지역변수가 저장될 것이고요, 그 외에 인자로 넘어온 파라미터 값들도 저장됩니다.

C의 경우  malloc 등을 활용하여 직접 힙에 메모리를 할당하지 않는 이상, 모든 데이터는 지역변수에 저장될 것입니다.

같은 지역변수와 인자를 활용하니까 같은 함수라면 차지하는 메모리 크기는 동일할까요? 그렇다면 이는 컴파일 타임에 결정되는 것일까요?

우선, 같은 함수가 재귀적으로, 혹은 여러번 실행될 때 차지하는 스택 메모리 공간의 크기는 동일하며, 이는 컴파일 타임에 결정된다고 합니다. 그렇게 되면, 빠르고 효율적인 메모리 할당이 가능합니다. 스택 포인터를 조정하는 한번의 작업만으로 메모리 할당이 가능하죠.  또한, 스택 오버플로우가 실제 물리 메모리상에 발생하기 전에 이를 감지할 수 있습니다. 

똑똑하신 분들은 조건절에서 변수를 선언할 수 있는 경우에 대하여 의문을 품으셨을 것 같습니다. 그 경우, 컴파일러는 각각의 분기절에 최대 메모리 할당량을 확인하고, 그 중 가장 최악의 경우에 맞게 미리 스택 메모리를 할당합니다. 

void exampleFunction(int x) {
    int a = 5;  // Always allocated
    if (x > 0) {
        int b = 10;  // Space is reserved even if `x > 0` is false
    } else {
        long long c = 10L;  // Space is also reserved for `c`, but `b` and `c` are mutually exclusive
    }
}

위와 같은 코드가 있을 때에 컴파일러는 long long 타입에 맞게 스택 사이즈를 할당한다고 이해할 수 있습니다. 

스택 메모리의 빠르고 효울적인 메모리 할당에 대하여 조금 더 자세하게 알고싶어요

"스택 포인터를 조정하는 한번의 작업만으로 메모리 할당이 가능해서 빠르다". 이 말이 어느정도 이해는 됐으나, 조금 더 자세히 알아보고 싶어졌습니다.

이를 위해선 스택 메모리를 할당받고 반납하는 과정에 대하여 조금 더 상세히 파악해 보아야 할 것 같습니다.

스택 영역의 메모리 할당은 stack pointer 를 top 을 가르키도록 이동시키는 과정입니다. 함수가 호출되었을 때, 포인터는 함수 프레임에 필요한 공간만큼 아래쪽으로(대부분의 아키텍쳐에서는 아래방향) 이동시킵니다. 

여기서 함수 프레임이란 스택 프레임, 콜 프레임이라고도 불리는, 특정한 함수 호출을 위해 할당되는 메모리 블럭입니다. 위에서 살펴본 것고 같이 이 프레임에는 지역 변수, 파라미터, return address, 리턴 후 복구되어야 할 레지스터 값 등이 포함됩니다.

아무튼 한 함수에 스택 메모리가 얼마나 할당될지 알기 때문에 메모리 할당은 단순히 현재 stack pointer 에서 함수 프레임의 사이즈를 빼는 것으로 완료됩니다. 반대로 함수가 리턴할 때는 이를 더해주겠죠.

이에 비해 힙 메모리는 메모리 공간을 할당받고 반납하기 위해선 특정한 알고리즘이 필요합니다. 이는 fragmentation 과 같은 문제를 방지하기 위함이죠. 그렇기 때문에 스택 메모리 할당이 빠를 수 밖에 없는 것입니다.

그런데, 컴파일 언어가 아닌 파이썬 같은 인터프리터 언어는 이를 어떻게 처리하는 걸까요?

굉장히 답변이 길어질 수 있는 질문인 것 같습니다. 하지만 이 또한 공부해봅시다. 다음은 파이썬 한정 설명이며, 다른 인터프리터 언어는 다르게 동작할 수 있음을 미리 밝힙니다.

우선 결론부터 말하자면, 파이썬은 함수에 맞게 고정된 스택 사이즈 값을 가지고 있지 않습니다. 각 함수 호출은 새로운 프레임 객체를 생성하고, 이 프레임의 사이즈는 동적으로 점점 커지는 방식으로 동작합니다. 이 프레임 객체가 실행 환경, 지역변수, 실행할 bytecode, 콜 스택 위치 등을 가지고 있는 것이죠.

파이썬의 함수가 호출되면, 인터프리터는 그 때 함수를 bytecode 로 컴파일하고, 이를 새로운 프레임 내에서 실행합니다. 이 프레임의 크기와 구조는 런타임 요구사항에 의존하는 것이지, 컴파일과는 전혀 관련이 없습니다.

아무튼, 그렇게 동적으로 자라나는 프레임을 객체를 관리하는 것은 앞서 봤던 stack pointer 를 옮기는 방식보다 시간이 오래 걸릴 것은 분명합니다. 결국 이러한 차이가 파이썬이 C, C++ 보다 상대적으로 느리게 만드는 요인중 하나일 것입니다.

물론 이 외에도 파이썬이 C계열 언어보다 느린 이유는 Dynamic Type Checking, Memory Management Overhead (with garbage collector), Inteprted execution 등 다양하게 존재합니다. 이는 추후에 기회가 된다면 다른 포스트에서 다뤄보도록 하겠습니다.

스택 메모리, 힙 메모리도 결국엔 모두 Abstraction 입니다 

이번 포스팅을 작성하면서, 특히 파이썬과 C계열 언어의 동작방식 차이를 이해하면서 제가 지금껏 프로세스의 메모리 구조에 대하여 잘 못이해하고 있었다는 것을 깨달았습니다. 다음 한 문장에 이 깨달음이 어느정도 함축되어 있습니다.

"스택 메모리이던, 힙 메모리이던, OS 관점에선 그냥 프로세스에 할당되는 가상 메모리의 일부일 뿐이며, 물리 메모리 상에서 이는 동일한 것이다."

가상 메모리가 무엇인지 모르겠다면, 이 포스팅을 확인해 보시기 바랍니다.

다만, 여기서도 언어별 차이가 존재합니다. Unix 계열의 OS 터미널에서 ulimit -s 를 입력하면 8176 과 같이 숫자가 출력되는데, 이것은 OS에서 제한하는 스택 사이즈의 상한 KB 입니다. 즉, 이 경우 한 프로세스가 8MB 이상의 스택 메모리를 할당받을 수 없다는 것이죠. 

하지만, 이 제한은 C 계열 언어의 스택 메모리 할당에만 국한됩니다. 즉, 파이썬으로 작성된 프로그램이 PVM 에 의하여 실행될 때에는 이 값에 영향을 받지 않습니다. 왜냐하면, 파이썬의 스택 메모리는 전통적인 메모리 관리 기준으로는 힙 메모리를 활용하는 것과 같기 때문이죠.

즉, 이 경우에는 실행되는 프로세스가 8MB 가 넘어가는 스택 메모리를 할당받을 수 있을 것입니다. 물론, 깊은 재귀 반복이 일어나면 이 또한 에러를 표시하겠지만, 이는 가상의 스택 메모리 사이즈, 즉 파이썬 언어 환경에서 설정된 deep recursion 제한에 의한 것일 겁니다.

다음은 파이썬에서 recursion limit 을 확인하고, 설정하는 방법을 보여줍니다.

import sys

# Get the current recursion limit
current_limit = sys.getrecursionlimit()
print(f"Current recursion limit: {current_limit}")

# Set a new recursion limit
sys.setrecursionlimit(1500)
print(f"New recursion limit set to: {sys.getrecursionlimit()}")

그런데 이런 언어별 차이는 어디서 왔을까요? 아무래도, 리눅스 커널 역시 C언어로 작성되어 있기 때문에 OS 자체에서 스택 메모리라는 개념을 가지고 이를 제한할 수 있는 것 같습니다.

다만, 새로운 high-level 언어가 개발되고 메모리 관리 방식도 다양화 되면서 더 이상 이 제한에 따를 필요가 없었던 것이겠죠.

마무리

이번 포스팅에서 다룬 내용을 가볍게 정리해 보겠습니다. 처음 스택과 힙에 대하여 복습하고자 하였고, 자연스럽게 메모리 구조에 대한 탐구로 이어졌습니다. 스택 메모리와 힙 메모리가 왜 구분되어 있는지, 이어서 스택 메모리가 빠른 이유를 알아 보았습니다. 파이썬과 같은 인터프리티드 언어는 스택 메모리를 어떻게 할당받고 사용하는지에 대한 의문에서 결국 이 메모리들도 Abstraction 이라는 사실을 배웠고, 이 또한 언어별로 차이가 존재한다는 것을 확인하였습니다.

여기서 더 공부할 것이 있다면, 메모리를 할당받는 방식, 즉 커널이 스택/힙에 대한 메모리 요청(커널 입장에선 같은 것임)을 어떻게 처리하는지에 대한 복습을 해보면 좋을 것 같아는 생각이 들었습니다.

참고 문헌

[1] Stack and Heap Memory: https://courses.engr.illinois.edu/cs225/fa2022/resources/stack-heap/