1. 스택 영역과 힙 영역
프로그램이 OS로 부터 할당받는 대표적인 메모리 공간은 코드(code) 영역, 데이터(data) 영역, 힙(heap) 영역, 스택(stack) 영역으로 구성되어 있다.
그 중 스택 영역과 힙 영역을 비교해보자.
출처: https://velog.io/@tonic523/%ED%9E%99-%EC%98%81%EC%97%AD-vs-%EC%8A%A4%ED%83%9D-%EC%98%81%EC%97%AD-
스택 영역 (정적 메모리)
-
스택 프레임이 쌓이는 메모리 공간
-
미리 할당될 스택 프레임의 크기을 알고 있어야 스택 프레임을 할당할 수 있다.
-
함수, 지역변수, 매개변수 저장
-
함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸
-
-
힙 영역 (동적 메모리)
-
변수의 생성 시기와 소멸시기를 프로그래머가 결정할 수 있는 메모리가 동적으로 할당되는 공간
-
많은 메모리가 필요할 경우 더 큰 공간을 확보하여 이전 요소들을 모두 복사한 후 새로운 데이터를 삽입
-
전역 변수를 다루며 사용자가 직접 관리해야 하는 메모리 영역
-
사용자에 의해 메모리 공간이 동적으로 할당되고 해제
-
2. 동적 배열
크기가 고정되지 않은 배열을 의미하며, 힙 영역에 저장되는 배열이다.
데이터가 선형적으로 이어져 있다는 특징
C++의 vector, 자바의 ArrayList, 파이썬의 리스트가 동적 배열에 해당함
2-1. Operation
-
Array.is_empty()-
리스트가 비어 있으면 True, 아니면 False
-
파이썬에서 빈 리스트는 False → 리스트 자체로 확인 가능
-
-
Array.add_last(element)-
리스트 마지막에 원소 추가
-
list명.append(element)
-
-
Array.insert(index, element)-
리스트의 index 위치에 원소 삽입
-
list명.insert(index, element)
-
-
Array[index]-
인덱스에 위치한 원소 반환(인덱싱)
-
list명[index]
-
-
Array.remove_last()-
리스트의 마지막 원소를 삭제한 후 반환
-
list명.pop()
-
-
Array.remove(index)-
인덱스에 위치한 원소를 삭제하고 반환
-
list명.pop(index)
-
2-2. 데이터의 삽입과 삭제
capacity: 배열이 확보한 메모리 공간
size: 채워진 데이터 크기
-
배열의 마지막에 추가, 삭제 하는 경우 → O(1)
-
capcity > size인 경우: O(1)
-
capcity < size인 경우: O(n)
-
분할 상환 분석 개념을 적용하면 해당 연산은 O(1)
-
참고: 동적 배열은 배열이 가득 차면 배열 크기의 2배만큼 capacity를 다시 잡음
-
- 배열의 중간에 추가, 삭제 하는 경우 → O(n)
2-3. 인덱싱(indexing)
배열에서는 인덱싱을 통해 데이터에 접근.
데이터 개수에 상관 없이 1회의 연산만 필요로 하기 때문에 빅오는 O(1)
3. 지역성의 원리와 캐시
지역성의 원리(principle of locality) → CPU와 메인 메모리 사이에 캐시(cache)를 두게 됨
메인 메모리에 있는 변수는 연산을 하기 전과 후에 반드시 레지스터를 거쳐야한다.
만약 캐시가 없다면 CPU에서 데이터 요청하면 메모리에서 레지스터로 데이터를 가져오고 이를 ALU(산술 논리 장치)로 전송한 후 다시 결과 값을 레지스터에 저장하고 또 다시 메모리에 저장하는 행위를 반복하여 비효율적일 수 있다.
CPU와 메인 메모리 사이에 성능이 빠른 메모리를 두는 것으로 비효율성을 줄이고자 하였고 이 때 사이에 들어가는 메모리가 캐시 메모리이다.
캐시는 메인 메모리에서 CPU가 요청한 변수 뿐만 아니라 주변 변수까지 한번에 가져오게 되는데, 이 때 메모리에서 선형적으로 이어져있다는 배열의 특징을 고려하면 더욱 성능 향상을 기대할 수 있다.
즉, 공간 지역성을 고려한다면 캐시히트가 발생했을 때 성능 향상을 기대해볼 수 있고 선형적으로 이어져 있는 배열은 캐시 히트가 발생하기 좋은 최적의 조건을 가진다.
-
용어 정리
-
레지스터: 메인 메모리에서 가져온 데이터를 일시적으로 저장할 수 있는 CPU의 메모리 공간
-
산술 논리 장치(Arithmetic Logic Unit, ALU): CPU 연산 장치
-
캐시 미스(cache miss): CPU가 요청한 데이터가 캐시에 없는 경우
-
캐시 히트(cache hit): CPU가 요청한 데이터가 캐시에 있는 경우
-
3-1. 지역성의 원리(principle of locality)
-
시간 지역성(temporal locality): 한번 접근한 변수는 계속해서 접근할 가능성이 높은 것
-
공간 지역성(spatial locality): 접근한 변수는 이전에 접근한 변수 근처에 있을 가능성이 높은 것
3-2. 캐시 메모리 (cache memory)
주기억장치에서 자주 사용하는 프로그램과 데이터를 저장해두어 속도를 빠르게 하는 메모리
주기억 장치와 CPU 사이에 위치한다.
