itertools 라이브러리와 메모리 구조 살펴보기 / with.기억장치

어제 백준 9742번 (순열) 문제를 풀다가 마주친 새로운 문제.

그것은 바로 “메모리 초과”.

라이브러리로 풀어서 그런걸까?

아니면 permutations로 만든 객체를 리스트로 반환해서 사용해서 그런가?

정답은 후자였다.

일단 itertools 라이브러리의 동작 과정에 대해 먼저 알아보자.

itertools 라이브러리에 대해

itertools 라이브러리는 이름 그대로 반복 가능한 객체를 만들 때 사용하는 라이브러리다.

(여기서 반복 가능한 객체라는건, list나 tuple, string과 같은 자료형을 의미한다. 왜 이 자료형들이 반복 가능한 객체라는걸까?를 또 생각해보면, 얘네들을 반복문에 넣어서 돌리면 (특정한 순서를 정해주지 않는한) 순차적으로 그 안에 있는 값을 반환하지 않는가? 그래서 반복 가능한 객체라고 부르는 거다.)

쨌든 그래서 공식 문서에서 permutations 부분에 해당하는 코드를 보면,

permutations 함수는 yield(제너레이터)를 활용해 반복 가능한 객체를 반환하고 있다.

1. 즉 모든 순열을 한 번에 계산하지 않고,
2. 필요할 때마다 다음 순열을 계산하여 반환하며,
3. 계산 상태를 함수 내부에 유지한다. (== lazy evaluation, 지연평가)

그래서 그냥 permutations로 만든 객체 자체를 바로 프린트하면, 아래 사진과 같이 해당 메모리 주소값만 출력되는거다.

그래서 어떤 특정한 값을 빼내고 싶으면, 앞서 permutations로 생성한 “반복 가능한 객체”를 반복문을 돌려서 찾으려는 특정 값을 빼내면 되는 것이다.

나는 이때까지 permutations를 사용하면 그 객체 자체에 바로 리스트를 씌워줬는데, 이는 잘못된 행동이었다.

모든 순열의 값이 한꺼번에 필요하지 않은 이상 내가 했던 행동은 메모리를 낭비하는 행동이기 때문이다.

왜냐하면 백준 9742번 (순열) 문제처럼 한 번에 하나의 순열의 값만 필요한 경우엔(이 문제에선 특정 값이 해당 순열에 있는지, 없는지를 찾는 문제였다.) for문을 돌려서 그 값만 빼주면 되기 때문이다.

참고로 permutations를 반복문을 돌려써 빼낸 객체는 튜플 형태(e.g. ('A', 'B', 'C'))로 반환이 된다.

따라서 ABC와 같이 연결 된 값을 사용하려면 "".join()을 활용해 해당 값들을 연결해주는 과정이 필요하다.

아니 근데 그럼 라이브러리도 그렇고, 코드에서 생성되는 데이터들은 메모리에 어떻게 쌓이는걸까?

데이터가 메모리에 쌓이는 과정

1. 우리가 처음에 작성한 코드는 하드디스크나 SSD와 같은 보조 저장장치에 저장된다.
2. 그러고 나중에 그 코드를 실행하면 운영체제에서 RAM에게 필요한 데이터와 해당코드를 요청한다.
3. 그러면 CPU가 RAM에서 직접 명령어를 읽고 코드를 실행하는 과정을 거친다.

나는 이 과정을 보고 아래와 같은 의문이 들었다.

• 아니 어차피 RAM에서 코드를 불러올거면 그냥 RAM에다 한꺼번에 저장하지, 왜 보조 기억 장치에다 저장하고 RAM에서 불러오는걸까?
  • RAM의 특성을 생각해봐라. RAM은 휘발성 메모리이기에 전원이 꺼지면 모든 데이터가 사라진다. 기껏 열심히 코드를 다 작성해서 신난 마음에 컴퓨터 전원을 끄고 잠에 들었다. 그러고 다음날 아침에 일어났는데, 모든게 사라져있다고 해보자. 이… 얼마나 침통하겠는가.
  • 그리고 보조기억장치는 저장된 위치에 따라 그 곳에 접근하는 데 걸리는 시간이 각각 다르다. 반면에 RAM은 어느 위치에 저장된 데이터든지간에, 접근(읽기 및 쓰기)하는 데 동일한 시간이 걸린다. 그래서 이름도 ‘random access memory’라고 명명한거다. 참고
  • 그러니 프로그램 파일은 보조기억장치(HDD나 SSD)에 보관해놓고, 그 때 그 때 필요한 것만(사용할 것만) 보조기억장치에서 “복사”한 다음, 실행 속도도 빠르고 어떤 데이터든 동일한 속도로 갖고오는 RAM에다 데이터를 적재해서, 최종적으로 CPU에서 실행하는거다.
• 아니 그럼 보조기억장치말고, 그냥 상남자처럼 ROM에다가 바로 저장하면 되지 않을까? 이러면 RAM도 필요없고, ROM은 비휘발성 메모리니까(전원이 꺼져도 데이터가 남아있으니까) 여기에 그냥 모든 코드를 저장하면 되지 않을까 ㅇㅅㅇ
  • 이것도 안된다. 왜냐? ROM의 약자를 생각해봐라. “Read-Only”-Memory이지 않는가. 내딴에는 ‘음~ 완벽해’ 하면서 ROM에다 저장해놨다고 해보자. 근데 막상 실행해보니까 이상하게 동작되는 버그가 났어. 근데 모든걸 ROM에다 저장해놨으면 코드 수정을 할 수 있겠는가? Read only니까 할 수 없을 것이다. 뭐 물론 ROM의 종류에 따라 다르겠지만.. 참고
  • 결론적으로 ROM은 BIOS나 펌웨어 같이 “고정된 데이터의 영구 저장”을 위해 설계된 메모리다. 그렇기에 여러개의 프로그램 파일을 저장할만큼 용량이 그렇게 크지도 않다. 따라서 프로그램 파일은 보조기억장치에 저장을 해놓고, 필요시마다 RAM에다 적재해서 쓰는거다.
    (그리고 애초에 왜 이렇게 역할을 나눠놓았겠는가.. 역할을 나눈데는 다 이유가 있는거다. 하다못해 회사에서도 특정 한 사람에게 과도하게 업무를 주면 과부하가 걸리지 않는가. 시스템도 똑같다. 그러니 너는 이 일을 담당해 ㅇㅇ 하면서 회로 설계하고, 제작해서 사용하는거다.)
  • 또한 ROM은 속도나 데이터를 읽는 과정이 RAM보다 느리고 복잡하다. 왜냐면 RAM은 “고속 회로”와 “저전압 트랜지스터”로 이뤄져있다. 트랜지스터의 전압이 낮을수록 스위칭 속도가 빨라지기에 RAM의 데이터 처리 속도 또한 빠른거다.
  • 반면 ROM은 다이오트나 트랜지스터의 매트릭스 구조로 이뤄져있다. flash 기반 메모리도 RAM보다는 빠르지 못하다. 왜냐면 비휘발성 메모리 특성상, 복잡한 회로 구조를 가져야 하기 때문이다.
  • 전압이 낮을수록 스위칭 속도가 빨라지는 이유는, 트랜지스터가 스위칭을 할 때마다 게이트 커패시턴스를 충전하거나 방전해야하는데, 저전압일 경우 이 때 필요한 전하량(전기량)이 줄어든다. 전하량이 줄면 물리적으로 상태 전환에 필요한 시간 또한 단축되기에 스위칭 속도도 빨라지는거다.
  • 참고로 트랜지스터는 게이트와 소스, 드레인 이렇게 총 세개의 단자를 갖는데 게이트 단자에는 작은 커패시턴스(==게이트 커패시턴스)가 있어서 여기서 전하를 저장할 수 있다고 한다.
• ㅇㅋ, 왜 프로그램 파일을 보조기억장치에 저장해놓고 있다가 실행되면 RAM에다 적재하는지 알겠다.

그럼 RAM에 “어떻게” 적재가 되는가?

애초에 컴퓨터는 우리가 작성한 코드의 변수명 그 자체를 그대로 이해하지 못한다.

컴퓨터 입장에서는 16진수 메모리 주소로 변환해서 저장해서 사용하는거다.

프로세스가 실행되면 운영체제는 해당 프로세스에 대해 가상 주소 공간을 만들고, 이 공간은 일반적으로 코드 영역, 데이터 영역, 힙, 스택으로 나뉜다.

실제로는 필요한 부분만 RAM에 페이지 단위로 적재되며, 이 때 RAM은 이러한 논리적 구조를 그대로 반영하지 않는다.

가장 먼저 Stack에는 지역 변수와 함수 호출 정보 같은 함수의 컨텍스트가 저장된다.

1. 그럼 여기서 질문, 왜 저런 타입들을 Stack에다 저장하는걸까?

Stack은 마치 젠가를 쌓는 것처럼, 아래에서부터 위로 쌓이는 데이터 형식을 말한다.

그렇기에 스택의 위에 있는 데이터일 수록 메모리 주소는 줄어든다(작아진다).

또한 데이터가 빠져나가는 순서도 제일 늦게 들어온게 먼저 나가고, 젤 첨에 들어온게 가장 늦게 나가는 Last In First Out의 형태다.

함수의 컨텍스트들은 해당 함수에서만 유효하기 때문에, 해당 함수의 실행이 종료되면 자연스럽게 메모리에서 사라져야 된다.

이는 메모리 할당과 해제가 빨라야 된다는걸 의미한다.

그럼 이를 만족하는 자료구조는 무엇일까?

Stack이다. 그래서 함수가 호출 되면 Stack에 Frame의 형태로 저장이 되는거다.

왜 Stack이 메모리 할당과 해제가 빠르냐고 묻는다면, 스택은 단순히 스택 포인터를 이동하는 것(push, pop)만으로도 할당과 해제를 빠르게 처리할 수 있기 때문이다.

예를 들어 강아지 객체를 생성하기 위해 사전에 강아지 함수를 만들어 놓았다고 해보자.

그러고 나서 강아지 함수를 사용하고 싶어서 이 함수를 호출하면, RAM의 Stack 메모리 영역에 강아지 함수의 스택 프레임이 쌓이게 된다.

그리고 CPU는 *스택 포인터를 활용해 강아지 함수가 어딨는지 찾는다. *現스택의 가장 위에 있는 메모리 주소를 가리키고 있는 연산자(레지스터).

그러고 해당 함수의 실행이 종료되면, 해당 스택 프레임은 자동으로 해제된다.

2. Heap에는 왜 동적 객체를 저장하는가?

Heap에는 함수의 실행이 종료돼도 살아남아야 하는 객체나 반복 가능한 객체가 저장된다.

왜냐면 Heap의 크기는 가변적이기 때문이다. 필요할 때 필요한 크기만큼 할당을 받고, 필요 없을 때는 해제하는 메모리 풀에 가깝다.

Stack의 메모리 할당은 컴파일 시간과 관련이 있어 사용자가 그 크기를 정할 수 없지만,

Heap의 메모리 할당은 실행 시간에 따라 달라지기에 Heap에다가 동적 객체를 담는거다.

그래서 Heap의 메모리 관리는 코드를 짜는 프로그래머나 가비지컬렉터의 책임인 것이다.

근데 아래와 같은 코드가 있다고 해보자.

void A() {
  int* a = (int*)malloc(3 * sizeof(int));
  a[0] = 1;
  a[1] = 2;
  a[2] = 3;
  free(a);
}

함수를 호출 했을 때 해당 함수의 컨텍스트가 Stack에 프레임으로 저장된다고 하지 않았는가?

근데 저기서 변수 a는 함수 A의 지역변수이면서 동적으로 할당 된 객체이다. (malloc으로 선언했으니까)

그럼 얘는 Heap에 저장될까? Stack에 저장될까?

정답은 포인터 변수 a 자체는 Stack에 위치하게 되는거고,

a의 value(a[0], a[1], a[2])는 Heap에 저장된다.

결론적으로 변수 a는 Stack에 저장되어 Heap에 저장된 리스트 객체의 주소값을 가리키는 것이다.

3. 정적 데이터(static)나 전역변수는 데이터 영역에 저장된다.

main함수나 다른 사용자 함수들 말고, 스코프 바깥에서 선언한 변수들을 전역 변수라 칭한다.

즉 스코프 바깥에서 선언 된 변수들(==전역변수)은 데이터 영역에 저장된다.

그럼 함수 안에서 쓴건 다 스택 또는 힙에 저장되는가?

ㄴㄴ. 함수 안에서 선언했더라도 static으로 선언했으면 데이터 영역에 저장된다.

static이란 “정적인” 또는 “고정된” 이란 의미를 갖고 있다.

따라서 데이터 영역에 저장되는 변수들은 메모리 주소값이 항상 동일한 값을 가진다.

static int y = 10;  // static으로 선언했으며 전역 변수니 데이터 영역에 저장됨

void function1() {
    y = 20;  // y를 20으로 변경
}
void function2() {
    printf("%d\n", y);  // 20 출력 (function1에서 변경된 값 유지)
}

고로 함수의 실행이 끝나면 그 값이 사라지는 stack영역과 달리

다른 함수에서도 해당 변수 값을 유지하며 사용할 수 있다.

4. 프로그램 코드는 코드 영역에 저장된다.

결론

그래서 코드 메모리 쪽으로 갈 수록 주소값이 낮아지고, 스택 메모리로 갈 수록 주소값이 높아지는거다.

왜냐면 주소값이 낮다는건 커널과 가깝다는거고, 주소값이 높다는건 사용자 공간에 가깝다는거기 때문이다. « 운영체제에 따라 다를 수 있다.

고로 파이썬에서 itertools 라이브러리의 permutations 함수를 불러와서 사용하면, itertools 라이브러리안에 있는 코드는 코드 메모리 영역에서 한 번만 로드가 된다.

from itertools import permutations
result = permutations([1, 2, 3])
for i in result:
    print(i)

1. 이를 실행하면 Stack에 permutations 함수를 사용하는 프레임이 생성된다.
2. [1, 2, 3] 객체는 Heap에 생성된다.
3. permutations 함수의 실행이 종료되면 해당 스택 프레임은 제거된다.
4. permutations로 생성한 객체는 iterator한 값이기에 Heap에 저장이 된다.
5. result 변수는 네임스페이스에 저장이 되고, 이 안의 값은 Heap에 있는 permutations의 iterator한 반환값의 주소값을 가리킨다.

아니 잠깐, 전역변수는 데이터 메모리에 저장이 된다고 하지않았는가? 근데 왜 result 변수가 네임스페이스에 저장이 된다고 하는거지?

파이썬에서 데이터 저장 위치

파이썬에서는 전역 변수를 포함한 모든 변수가 네임스페이스에 저장된다. 네임스페이스는 딕셔너리로 구현이 되어있으며, 딕셔너리는 동적 객체니까 Heap에 저장이 된다.

(엄밀히 말하면 C에선 딕셔너리 자료형 자체가 없기 때문에 malloc을 활용해서 동적 객체를 생성 후 이를 딕셔너리처럼 활용해야한다. 구현 방법)

따라서 result 변수는 네임스페이스에 저장이 되고 이 네임스페이스도 Heap에 저장이 되는거다. 즉 파이썬에선 C언어와 달리 전역변수가 별도의 데이터 메모리 영역에 저장되지 않고, 거의 모든 데이터가 Heap에 저장이 된다.

그래서 파이썬이 다른 언어들에 비해 메모리 사용량이 많다고 하는것이다.

참고

C에서 그냥 전역에 struct로 선언한 구조체의 경우엔 그냥 선언만 하고 사용하지 않았기에 이 때는 그 어디의 메모리 공간에도 저장되지 않는다.

main 함수나 다른 곳에서 이제 malloc으로 불러오든 어떻게 불러왔을 때 스택에 저장될지 힙에 저장될지 데이터에 저장될지 정해지는거다.