Go 언어 - 배열

검프·2021년 3월 21일

Cache Saturday Night Ultimate Go array golang memory

Go 언어 학습

목록 보기

4/9

The Ultimate Go Study Guide의 내용을 참고하여 작성했습니다.

배열

CPU 캐시 (수정 예정)

CPU 코어는 메인 메모리(RAM)에 접근하기 전에 CPU 캐시 $^{CPU\ Cache}$ 에 접근합니다. 캐시에는 데이터와 명령어가 저장되며 프로세서 $^{Processor}$ 가까이 위치하면서 빈번하게 사용하는 데이터를 저장합니다. 캐시의 속도는 L1 > L2 > L3 > 메인 메모리 순서로 빠릅니다. 따라서 성능이 중요한 경우 메인 메모리에 대한 접근을 줄이고 캐시를 사용할 수 있도록 해야합니다. 그럼 캐시 미스 $^{Cache\ miss}$ 를 최소화하려면 어떻게 코딩해야 할까요?

프로세서는 프리페처 $^{Prefetcher}$ 를 가지고 있다. 프리페처는 어떤 데이터가 필요할지 예상한다. 데이터 단위 $^{granularity}$ 는 사용하는 기계에 따라 다르다. 대체로 프로그래밍 모델은 바이트를 사용한다. 한 번에 바이트를 읽고 쓸 수 있다. 그러나, 캐싱 시스템의 관점에서 보면 데이터 단위는 1바이트가 아니다. 캐싱 시스템의 관점에서 데이터의 단위는 64바이트고 이걸 캐시 라인 $^{Cache\ line}$ 이라고 부른다. 모든 메모리는 64바이트의 캐시 라인으로 구성되어 있다. 캐싱 메커니즘 $^{Caching\ mechanism}$ 은 복잡하지만 프리페처는 모든 지연 시간을 없애려 한다. 프리페처가 예측 가능한 데이터 접근 패턴을 파악 할 수 있어야 한다. 즉, 예측 가능한 데이터 접근 패턴을 생성하는 코드를 작성해야 한다.

쉬운 방법의 하나는 메모리의 연속 할당을 만들고 이것을 순회하는 것이다. 배열 데이터 구조는 연속 할당과 순회를 할 수 있게 해준다. 하드웨어 관점에서 배열은 가장 중요한 데이터 구조이며 Go 관점에서 슬라이스가 그러하다. C++의 vector와 마찬가지로 슬라이스는 배열 기반 자료구조이다. 사이즈가 어떻든 배열을 할당하면, 모든 원소는 각각 다른 원소로부터 같은 거리를 갖게 된다. 배열을 순회하는 건 캐시 라인을 한줄 한줄 순회하는 것과 같다. 프리페처는 접근 패턴을 고르고 모든 지연 시간을 숨긴다.

예를 들어, 큰 nxn 행렬이 있다고 하자. 연결 리스트 순회 $^{LinkedList\ Traverse}$ , 열 순회 $^{Column\ Traverse}$ , 행 순회 $^{Row\ Traverse}$ 를 했을 때 각 순회의 성능을 측정해보자. 당연하게도 행 순회가 가장 높은 성능을 가진다. 행 순회는 행렬의 캐시 라인을 순회하면서 예측 가능한 접근 패턴을 만든다. 이와 달리 열 순회는 캐시 라인을 순회하지 않는다. 메모리 임의 접근 패턴을 가지고 있다. 이게 성능이 제일 느린 이유다. 연결 리스트 순회의 성능이 왜 중간인지 설명하지 않았다. 단순히 열 순회만큼 성능이 안 좋을 거라고 생각해 볼 수 있다. 자세한 이해를 위해 또 다른 캐시인 TLB - 변환 색인 버퍼 $^{Translation\ Lookaside\ Buffer}$ 를 알아보자. 변환 색인 버퍼는 물리적 메모리에 있는 운영 체제의 페이지 $^{Page}$ 와 오프셋 $^{Offset}$ 을 유지한다.

변환 색인 버퍼 (수정 예정)

캐싱 시스템은 하드웨어로 한 번에 64바이트씩 데이터를 옮긴다. 데이터 단위는 기계 별로 다르듯이, 운영 체제는 4k(운영 체제의 기존 페이지 크기) 바이트씩 페이징 함으로써 메모리를 관리한다.

관리되는 모든 페이지는 가상 메모리 주소(소프트웨어는 가상 주소를 물리적 메모리를 사용하고 공유하는 샌드박스에서 실행한다)를 갖게 되는데, 올바른 페이지에 매핑되고 물리적 메모리로 오프셋 하기 위해 사용된다.

변환 색인 버퍼의 미스는 캐시 미스보다 나쁠 수 있다. 연결 리스트 순회가 중간 성능인 이유는 다수의 노드가 같은 페이지에 있기 때문이다. 캐시 라인은 예측 가능한 거리를 요구하지 않기 때문에 캐시 미스가 발생 할 수 있지만, 많은 변환 색인 버퍼의 미스는 발생하지 않을 수 있다. 열 순회에서는 캐시 미스뿐만 아니라 엑세스할 때마다 변환 색인 버퍼의 캐시 미스가 발생 할 수 있다.

즉, 데이터 지향 설계가 중요하다. 효율적인 알고리즘을 작성하는 것에 그치지 않고, 어떻게 데이터에 접근하는 것이 알고리즘보다 성능에 좋은 영향을 미칠지 고려해야 한다.

배열 선언과 초기화

배열 $^{Array}$ 은 var 변수명 [배열길이]타입의 형태로 정의합니다. 아래 예제는 길이가 5인 문자열 배열을 선언합니다.

var fruits [5]string

이렇게 선언하면 제로값 $^{Zero\ value}$ 으로 초기화됩니다. 문자열은 포인터와 길이를 표현하는 두 워드 $^{Word}$ 로 이루어져 있으므로 아래 그림과 같이 초기화됩니다. 배열의 0번째 원소는 문자열 배열에 대한 포인터와 길이 정보 5를 갖습니다.

배열 원소 할당 비용

배열의 특정 원소에 문자열을 할당할 경우 2 바이트 $^{Byte}$ 의 복사 비용이 발생합니다. 즉, 문자열 리터럴 $^{Literal}$ "Apple"과 fruits[0]은 같은 문자열을 가르킵니다.

fruits[0] = "Apple"
fruits[1] = "Orange"
fruits[2] = "Banana"
fruits[3] = "Grape"
fruits[4] = "Plum"

여기서 상수와 리터럴에 대해서 언급해 보려고합니다. 상수는 한 번 할당된 값을 변경할 수 없는 변수입니다. 고언어에서는 이들은 불변 $^{Immutable}$ 하며 문자열, 불, 숫자 타입 등을 상수 타입으로 사용할 수 있습니다. 리터럴은 소스코드 상의 고정된 값 자체를 이야기합니다.

// b, n, s는 상수
// true, 1, "Apple", []string{"Apple", "Orange", "Banana"}, Person{Name: "Gump"}는 리터럴

const b = true
const n = 1
const s = "Apple"

var arr = []string{"Apple", "Orange", "Banana"}
var me = Person{Name: "Gump"}

배열 순회 방법

for문과 range 키워드를 사용하여 배열의 각 인덱스 원소를 순회할 수 있습니다. 첫 번째 반복에서 fruit은 문자열 "Apple"을 가르키게되어 위 이미지 <1>의 배열을 가르키는 3개의 참조를 갖게됩니다.

for i, fruit := range fruits {
    fmt.Println(i, fruit)
}

<출력>
0 Apple
1 Orange
2 Banana
3 Grape
4 Plum

전통적인 방법으로 배열을 순회할 수도 있습니다.

numbers := [4]int{10, 20, 30, 40}
for i := 0; i < len(numbers); i++ {
	fmt.Println(i, numbers[i])
}

<출력>
0 10
1 20
2 30
3 40

배열 크기와 배열 타입

아래와 같이 제로값으로 초기화된 크기가 5인 배열을 특정 값으로 초기화된 크기가 4인 배열에 할당하려고 할 경우 컴파일러는 컴파일 에러를 냅니다. 타입의 크기가 다르기 때문에 할당할 수 없다는 내용입니다. 배열의 크기는 타입명에 표시되며 모든 배열은 컴파일 타임 $^{Compile\ time}$ 에 크기가 정해집니다.

var five [5]int
four := [4]int{10, 20, 30, 40}
five = four

<컴파일 에러>
cannot use four (type [4]int) as type [5]int in assignment

연속된 메모리 할당

특정 값들로 초기화 배열의 각 원소는 연속된 순서로 메모리에 할당Contiguous memory allocations됩니다. 아래 예제를 보면, 배열을 순회하면서 각 원소의 메모리 주소를 출력하고 있습니다. 출력 결과를 확인해보면 연속된 메모리 블록으로 이루어진 것이 확인됩니다. 문자열은 2개의 워드로 이루어졌고 각 원소의 메모리 주소는 정확히 2바이트 간격입니다. 아래 예제에서 변수 **v는 스택에 할당되며 항상 같은 메모리 주소**를 갖습니다.

six := [6]string{"Annie", "Betty", "Charley", "Doug", "Edward", "Hoanh"}

fmt.Printf("\n=> Contiguous memory allocations\n")
for i, v := range six {
	fmt.Printf("Value[%s]\tAddress[%p] IndexAddr[%p]\n", v, &v, &six[i])
}

<출력>
=> Contiguous memory allocations
Value[Annie]	Address[0xc000096220] IndexAddr[0xc0000ba120]
Value[Betty]	Address[0xc000096220] IndexAddr[0xc0000ba130]
Value[Charley]  Address[0xc000096220] IndexAddr[0xc0000ba140]
Value[Doug]	Address[0xc000096220] IndexAddr[0xc0000ba150]
Value[Edward]	Address[0xc000096220] IndexAddr[0xc0000ba160]
Value[Hoanh]	Address[0xc000096220] IndexAddr[0xc0000ba170]

Go언어 배열의 단점

Go언에서 배열은 몇 가지 단점을 갖고 있습니다. 첫 번째는 크기를 변경할 수 없다는 점입니다. 기존 배열에 추가적인 원소를 할당하고 싶을때 더 큰 변수를 생성한 뒤에 기존 배열에 담긴 원소들을 모두 복사해야합니다. 두 번째, 함수의 매개변수로 배열을 전달할 때 배열의 복사본이 전달됩니다. 함수 안에서 배열의 값을 변경하고 리턴하면 변경 사항이 사라집니다. 세 번째, 큰 배열을 함수에 전달할 경우 메모리 복사가 발생하기 때문에 성능이 떨어지는 문제가 있습니다. 이런 문제는 슬라이스를 사용하여 해결할 수 있습니다.