[Swift] Protocol에서 Method dispatch

iOS 개발자라면 꼭 시청해야 한다고 생각하는 WWDC 세션인 Understanding Swift Performance의 내용 중

Protocol types 파트에 대해서 공부하며 적은 글입니다.

출처는 알아보기 쉽도록 각 단락마다 적어놓았습니다.

Polymorphism with struct

polymorphic code를 struct로 작성하는 방법은 무엇일까요?

영상에서는 POP(Protocol oriented programming)이라고 답합니다.

그렇다면 protocol을 사용할 때 method dispatch가 어떻게 동작하는지도 알아야 할 것입니다.

이번에는 이전의 예시에서 부모 클래스를 protocol로 바꿨습니다.

각 struct는 protocol을 채택하여 구현했고, 때문에 상속관계가 없어 v-table이 존재하지 않습니다. (SharedLine은 무시해도 됩니다)

이럴 때에는 d.draw의 정확한 구현체를 어떻게 결정해야 할까요?

PWT(Protocol Witness Table)

v-table과 마찬가지로 table기반의 메커니즘인 PWT를 활용하여 해결합니다.

타입당 하나의 PWT가 존재하고, 테이블의 엔트리(?)는 각 구현체와 link 됩니다.

이제 각 타입들이 어떻게 메서드를 찾는지 알아냈는데, 어떻게 각 배열의 원소가 자신의 PWT를 찾는지는 모르는 상태입니다.

이 궁금증을 해결하기 전에, 먼저 다른 궁금증부터 해결해봅시다

Line은 4개의 프로퍼티를 갖고 있어 4 word의 공간이 필요하고, Point는 2 word의 공간이 필요합니다.

두 타입의 크기가 같지 않습니다.

하지만 배열에서는 각 원소들이 같은 크기를 갖고 있어야 합니다. (그래야 메모리에서 offset * size만큼 이동했을 때 원하는 원소를 찾을 수 있어서 그런 것 같다.)

이 문제를 해결하기 위해 Swift에서는 Existential Container라는 자료구조를 도입했습니다.

Existential container

아래 그림은 두 개의 프레젠테이션을 합쳐서 만들었습니다.

existential container란 보시다시피 5 word의 크기를 갖는 컨테이너입니다.

(또한, protocol을 type으로 사용할 때 existential type이라고 부릅니다. 뭔가 관련이 있다고 느껴집니다.)

https://docs.swift.org/swift-book/LanguageGuide/Protocols.html

일단, 처음 3 word를 Value Buffer로 갖습니다.

즉 3 word의 크기만큼만 valueBuffer에 저장될 수 있다는 뜻인데요,

2 word의 크기를 가진 Point는 valueBuffer에 그대로 저장됩니다.

하지만 4 word의 크기를 가진 Line은 Heap 영역에 저장되며, valueBuffer에 그 참조가 저장됩니다.

Line과 Point에는 이렇게 차이 생기는데, existential container은 어떤 방식으로 이 차이를 관리할까요? (이 차이로 인해서 뭐가 달라지는지 정확히 알 수 없지만, 뒤의 내용을 보아 lifetime관리에서 차이가 있는 것으로 보입니다. stack과 heap에서의 데이터 관리 방법이 다르기 때문이죠)

이 질문의 답은 마찬가지로 table기반의 메커니즘인 VWT(Value Witness Table)입니다.

VWT(Value Witness Table)

VWT는 value의 lifetime을 관리하고, 타입마다 해당 테이블이 존재합니다. ( 그럼 Line 객체가 두 개일 때에는 어떻게 할까 하는 의문이 들 수 있는데, existential container가 두 개 생기고, VWT는 하나만 생긴다고 생각하면 될 것 같습니다. )

이 VWT가 어떻게 동작해 value의 lifetime을 관리하는지 알아봅시다.

프로토콜 타입인 지역 변수의 lifetime이 시작할 때, Swift는 VWT에 있는 allocate 함수를 호출합니다.

LineVWT의 경우에는 heap에 메모리를 할당하고 그 메모리의 포인터를 valueBuffer에 저장합니다.

(만약 Pointer의 경우였다면 아무것도 하지 않았을 것 같습니다. stack에 저장될 것이고, 이미 valueBuffer의 위치는 정해져 있으니깐..?)

다음으로 지역 변수를 초기화하는 대입문에서 값을 복사해 exntential container에 넣습니다. ( 대입문이라는 것은 초기화 구문을 말하는 것 같습니다. let line = Line()과 같은 초기화 구문)

Line의 값은 valueBuffer에 들어가지 않기 때문에 LineVWT는 heap의 할당된 위치에 해당 값들을 넣어줄 것입니다.

(PointerVWT는 valueBuffer에 값들을 넣어주었겠죠)

프로그램이 실행되다가 이제 이 지역변수의 lifetime이 끝날 때가 되었습니다.

Swift는 VWT에서 destruct entry를 호출해서, 값들의 reference count를 감소시킵니다.

(왜 값을 지우지 않고, reference count를 감소시킬까요?)

Line의 경우 reference를 갖고 있지 않아 이 과정이 필요 없습니다.

(그러니깐, reference 타입인 프로퍼티들의 rc를 감소시켜주는 과정이라는 것 같습니다. Line은 모두 value 타입 프로퍼티라서 해당 과정이 필요 없다고 하는 거죠)

정말로 끝에 도달하면, Swift는 table에서 deallocate 함수를 호출합니다.

LineVWT의 경우에는 할당된 heap메모리를 해제합니다.

이러한 방식으로 VWT을 통해서 다른 종류의 value의 lifecycle을 관리합니다.

다시 Existential Container

(여기서부터 계속되는 예제 코드 설명으로 인해 사진이 매우 많을 예정입니다.)

Drawable 타입을 매개변수로 갖는 drawACopy 함수가 있고, Drawble 타입인 val 변수가 있습니다.

이 코드가 컴파일 과정을 거치면 아래와 같은 코드가 만들어지게 됩니다.

(이제부터 ----아래에 있는 코드들은 컴파일러에 의해 만들어진 코드라고 생각하면 됩니다. 줄여서 컴파일된 코드라고 부르겠습니다.)

원래는 swift 코드가 아니지만, 예제에서 pseudocode로 쉽게 표현해주었습니다.

위에서 공부했다시피 5 word의 Existential Container에는 3 word의 valueBuffer, VWT의 레퍼런스, PWT의 레퍼런스가 존재합니다.

drawACopy 함수가 불리면, 매개변수가 함수 구현부로 전달됩니다.

컴파일된 코드를 보면 함수의 매개변수로 existential container를 전달하는 것을 볼 수 있습니다.

함수가 실행되면, 지역 변수(local)를 만들어 매개 변수(val)를 대입해줍니다.

컴파일된 코드를 보면 Swift는 stack에 Existential Container를 생성합니다.

그런 다음, 매개 변수(val: Existentail Container)에서 VWT와 PWT을 읽어와 지역 변수(local: Existentail Container)의 필드를 초기화합니다.

쉬운 이해를 위해 두 가지 프레젠테이션을 합쳤습니다.

VWT(Value Witness Table)에서 (필요하다면) allocate 함수와 copy 함수를 호출합니다. (아래 그림을 보면, Point의 경우에는 heap allocate가 필요하지 않으므로 필요하다면이라는 조건이 붙은 것 같습니다.)

VWT의 allocate&copy 함수의 결과 각 타입마다 다른 형태로 값이 할당됩니다.

이제 local.draw 메서드가 실행되면, Swift는 existential container의 필드에서 PWT를 조회해서, 해당 테이브의 fixed offset에 있는 draw 메서드의 구현체로 jump 합니다.

컴파일된 코드를 다시 보면, VWT가 projectBuffer를 호출합니다.

이게 필요한 이유는 위의 예시를 다시 한번 곱씹어보면 알 수 있습니다.

draw 메서드는 매개변수로 value의 주소(포인터)를 필요로 합니다.

하지만 value의 크기에 따라서 그 주소 값의 위치가 달라집니다.

inline buffer(valueBuffer)에 알맞게 들어가는 Point의 경우에는 existential container의 시작 주소가 value의 주소에 해당할 것입니다.

반면, inline Buffer에 들어가지 않는 large value인 Line의 경우에는 heap에 할당된 메모리의 시작 주소가 이에 해당할 것입니다.

그래서, 이 projectBuffer 함수는 타입에 의존하게 되는 이 상황을 추상화를 통해 해결한 것입니다.

함수의 실행이 끝나면, Swift는 VWT에서 destruct 함수를 실행해 (만약 값이 reference type이라면) reference count를 감소시키고, (buffer에 할당됐다면) buffer 메모리를 해제(deallocate)합니다.

stack에 생성된 existential container 또한 삭제되고, 모든 것이 종료됩니다.

중간 정리

이렇게 struct와 protocol을 사용하여 dynamic behavior, dynamic polymorphism을 얻을 수 있습니다.

class를 사용하게 되면 v-table과 추가적인 reference counting에 의한 오버헤드가 발생하는데, 그에 비해서 struct와 protocol을 사용하는 것이 조금 더 낫다고 합니다.

(사실 v-table과 pwt가 큰 차이가 나는 것 같다고 느껴지진 않습니다. 그리고 큰 값에 대해서는 heap에 할당되는 것은 마찬가지인데 크게 다를까 싶습니다..

* Existential Container는 각 프로토콜 변수마다 생성됩니다.

* 프로토콜 변수가 사용될 때에는 내부적으로 변수 자체를 주고받는 것이 아니라 existential container를 주고받습니다.

* VWT과 PWT는 Heap에 할당됩니다. existential container에는 그 포인터가 저장됩니다.

* VWT와 PWT는 각 타입마다 한 개가 생성됩니다. 따라서 컴파일 타임에 생성될 수 있습니다.

* VWT는 내부의 함수를 통해 변수의 lifecycle을 관리합니다.

* PWT는 각 메서드 구현체의 주소를 갖고 있습니다.

각 개념들이 나타나게 된 계기(내 생각)

struct의 상속 불가능함을 극복하기 위한 protocol

protocol을 사용하면 어떤 메서드를 실행해야 할지 모르기 때문에, 메서드 결정을 위한 protocol witness table

같은 protocol 타입을 한 배열에 저장하기 위해서는 모두 같은 크기여야 하기 때문에, 일정한 크기(uniformly)를 맞춰주기 위한 existential container와 valueBuffer

변수의 크기에 따라서 서로 다른 관리방법에 대처하기 위한 value witness table

---

프로토콜 타입이 저장 프로퍼티일 경우의 예시를 보겠습니다.

first, second라는 프로퍼티는 Drawble 타입입니다.

이를 저장할 때에는 Pair의 구조체 영역 안에 두 개의 existential container를 생성합니다.

그리고 Pair의 인자로 Line과 Point가 들어왔으니, 위에서 여러 번 했듯이 Line은 heap에 할당, Point는 valueBuffer에 할당합니다.

(이 부분이 이해가 안 가신다면, 위의 existential container를 반복해서 읽어보시면 이해가 가실 겁니다.)

코드를 조금 변경해서 Line 두 개를 할당했다고 해봅시다. 그럼 두 번의 heap allocation이 일어납니다.

### Cost of Large Value

다른 예제로 이동해서 large value의 비용에 대해서 알아보겠습니다.

위 코드를 실행시키면 내부적으로 어떻게 메모리가 할당될까요?

바로 이렇게, 두 개의 existential container에서 두 번의 heap allocation이 발생한 pair 객체가 있고,

Pair가 value type이므로 값 복사가 일어나, 두 번의 heap allocation이 추가돼, 총 네 번의 heap allocation이 발생합니다.

이 상황을 해결하기 위해서 Line을 struct가 아닌 class로 바꾸면 어떻게 될까요?

class의 reference는 1 word의 크기를 갖기 때문에 valueBuffer내부에 저장될 수 있게 됩니다.

또한, Pair를 복사하게 되면, reference만 복사하면 되기 때문에 heap allocation이 발생하지 않고 같은 주소를 가리키게 됩니다.

복사를 할 때 우리가 지불해야 하는 비용은 이전과 달리 reference count를 증가시키는 연산뿐입니다.

하지만 이렇게 Line을 class로 구현하게 되면 의도치 않게 상태를 공유한다는 문제가 생깁니다. (원본을 공유한다는 뜻입니다.)

first를 복사한 second에서 x1의 값을 바꾸면, first의 x1값도 바뀌게 됩니다. 우리가 원하는 것은 오른쪽과 같은 상황인데 말이죠

이렇게 value sementic을 원하지만 값 복사에 대한 비용이 많이 들지 않을 때, COW(Copy-on-Write)라는 기술로 해결할 수 있습니다.

바로, class에 값을 쓰기 전에 그것의 reference count를 확인하는 방법인데요.

같은 인스턴스에 1개 이상의 reference가 생기면, reference count는 1보다 커지게 됩니다.

이때, 해당 인스턴스의 값을 바꾸기 전에, 인스턴스를 복사해서, 새로운 인스턴스에 값을 바꾸는 방식이 바로 COW입니다.

코드로 한번 살펴봅시다.

Line 내부에 프로퍼티들을 직접 저장하는 것 대신에, LineStorage라는 class를 만들어 Line의 프로퍼티로는 LineStorage 참조 하나만 갖고 있도록 합니다.

값을 읽을 때에는 LineStorage에 접근해서 그 안에 있는 값들을 읽으면 됩니다.

이제 우리가 값을 바꾸려 할 때에는, 먼저 storage의 reference count를 검사합니다.

만약 1보다 크다면 두 개의 Line 객체가 같은 LineStorage를 참조하고 있는 것입니다. 따라서 현재 storage값을 인자로 새로운 LineStorage를 생성해서(현재 값을 복사한다는 뜻), 새로운 storage 내부의 값을 변경합니다.

방금 설명한 내용을 그림을 통해서 확인해봅시다.

pair객체를 생성하게 되면, heap에 할당된 Line객체(정확히 말하자면 LineStorage(class type))의 reference count는 3이 됩니다. (aLine에서 하나, pair의 first, second에서 각각 하나씩 해서 3)

이제 copy 객체를 생성하게 되면, reference count가 2 증가하게 됩니다.

heap allocation을 4번 반복했던 이전에 비해서 3번의 비용이 감소했습니다.

이제 다시 copy의 값을 변경하게 되면, LineStorage가 새로 할당되고, 그 값을 바꾸게 됩니다.

이렇게 large value를 가진 protocol 타입을 최적화해볼 수 있습니다.

## performance관점에서 최종 정리

작은 값을 가진 Protocol 타입은 stack에 저장되고, 생성된 객체에는 reference counting이 없어 비용이 매우 저렴합니다.

또한 PWT(Protocol Witness Table)을 활용한 Dynamic dispatch에 의한 비용만 지불하면, 값싸게 polymorphism을 구현할 수 있습니다.

3 word를 초과하는 값을 가진 Protocol 타입은, 프로퍼티가 heap에 할당되는 비용이 발생합니다.

하지만 객체 자체는 값 타입이기 때문에 reference counting이 없고, 위와 마찬가지로 PWT에 의한 Dynamic dispatch를 활용할 수 있습니다.

(만약 프로퍼티가 값타입이 아닌 레퍼런스 타입이라면 그에 따르는 reference counting이 발생할 수 있습니다. 오해 금지)

Large value를 indirect storage에 저장해 COW를 구현한다면, 값 비싼 heap할당을 의무적으로 할 필요가 없어져(값을 변경할 때만 heap allocation) 조금의 비용을 아낄 수 있습니다.

class를 사용할 때와 얼마나 차이 날까 싶지만, 여러 가지 상황을 모두 종합해보면 위 경우가 조금 더 효율적인 것을 확인할 수 있습니다.

class는 항상 heap allocation이 발생하지만, 이렇게 하면 값을 변경할 때만 heap 할당을 하기 때문에 조금은 줄일 수 있기 때문입니다.

 

이렇게 해서 protocol을 활용해 구현했을 때의 내부 동작과 문제점, 성능을 개선할 수 있는 방법에 대해서 알아봤습니다.

마냥 struct를 이용하면 값싸게 구현 가능할 것으로 생각했는데, 다형성(polymorphism)을 위해서는 어느 정도 trade-off가 필요한 것을 깨달았습니다.

혹시 잘못된 개념이 있다면, 댓글 부탁드립니다!