[Swift] Generic에서 Method Dispatch

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

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

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

Generic

Generic code는 더욱 정적인 형태의 polymorphism을 구현할 수 있도록 도와줍니다. 이것을 parametric polymorphism이라고도 부릅니다. "One type per call context"

(protocol을 이용했을 때에는 struct를 사용하더라도 메서드가 동적으로 결정되는 부분이 있었는데, generic은 그게 아니라는 뜻인 것 같습니다.)

이제부터 위에 한 말이 무슨 뜻인지 알아보겠습니다

Generic으로 만들어진 foo, bar가 있을때, foo를 호출하면 어떤일이 일어날까요?

Swift는 generic type인 T와 호출하는 시점에 사용된 type인 Point를 binding합니다.

이 때 foo의 local이라는 변수의 타입이 Point로 결정됩니다.

또 foo내부에서 bar을 호출하는데, 이 시점에 bar 함수의 generic type인 T와 Point를 binding합니다.

이런 방식으로 타입은 call chain으로 대체되어 내려갑니다.

이것이 바로 위에서 말한 정적인 형태의 polymorphism이나, parametric polymorphism이라는 말로 이 과정을 정의합니다.

이제 Swift에서는 이 과정을 어떻게 구현했는지 살펴봅시다.

local.draw가 어떤 타입의 draw를 호출해야할지 결정하기 위해서 PWT(Protocol Witness Table)과 VWT(Value Witness Table)을 사용합니다.

(PWT는 왜 사용하는지 알겠는데, ❓ VWT는 왜 사용하는지 잘 모르겠습니다..)

하지만 call context에 하나의 타입밖에 없기 때문에 existential container를 사용하지 않습니다.

(❓ 도대체 왜 existential container가 필요없는지 이해할 수 없습니다....)

대신 함수를 호출하는 부분에서 추가적으로 함수의 매개변수에 PWT와 VWT를 전달합니다.

함수가 실행되면 매개변수에 대한 (위 예제에서는) local이라는 지역변수가 생성될 때, Swift는 VWT를 사용해 heap에 필요한 버퍼(메모리)를 할당하고 원본에서(point 매개변수) 복사본으로(local 지역변수) 값을 복사합니다.

또, 비슷한 방식으로 draw 메서드를 실행할 때 PWT를 사용해 table에서 고정된 위치에 있는 draw 메서드를 찾아 해당 구현체로 jump합니다.

(PWT에 여러가지 메서드가 있을텐데, 그중에 draw가 몇 번째인지 아는 정보를 통해 draw 메서드를 찾는다는 뜻입니다. ❓ PWT에서 메서드를 찾을 때 완전탐색을 돌리는 거겠죠? 이 부분에 대해서는 정보가 없습니다..)

여기까지 알아봤는데, 이제 local(지역 변수)에서 existential container없이 어떻게 메모리를 할당할까요?

답은, stack에 valueBuffer를 만들어 할당하는 것입니다.

existentail container에서처럼 valueBuffer은 3word 크기의 공간입니다.

위처럼 3 word내에 들어갈 수 있는 값이라면 inline에 저장되고, 더 크다면 heap에 저장되어 valueBuffer에는 주소값이 저장됩니다.

(발표자님은 "store a pointer to that memory inside of the local existential container"라고 하시는데,, 분명 existential container가 없다고 하셨는데,, 그래서 valueBuffer라고 의역했습니다.)

(❓그런데 결국 valueBuffer, VWT, PWT가 모두 필요하다면 existential container을 없애고 따로따로 갖다쓰는 이유가 뭘까요? 구체적인 기준이 없이 통일성을 해체는 결정을 하지는 않았을 것이니, 더 공부해보며 그 답을 찾아보겠습니다.)

이러한 것들은 VWT의 사용을 위해서 관리됩니다. (And all of this is managed for the use of the value witness table.)

(❓ 이 말은 또 무슨뜻일까요? 크기에 따라 valueBuffer에서 값이 다르게 저장되기 때문에 그 lifecycle을 관리하기 위해서 VWT를 사용한다고 생각했는데, 발표자님은 생각하던 의존관계를 반대로 설명하셨습니다.. 이게 무슨 뜻일까요?)

이렇게 구현한 이유는 빠르기 때문이라고 합니다.

Specialization

정적인 방식의 polymorphism을 통해서 generic의 specialization이라고 불리는 컴파일러 최적화가 가능해집니다.

이렇게 작성되어있던 코드가

specialization을 통해서 위와 같은 코드로 변하게 됩니다.

즉, 컴파일러는 호출 시점의 type(Point)을 가지고 generic type(T)를 대체해서 새로운 버전의 함수 구현체(drawACopyOfAPoint)를 생성합니다.

Swift는 호출 시점의 모든 type(Point, Line)에 해당하는 버전의 함수 구현체를 만들어냅니다.

specialized가 수행된 SIL코드

여기서 잠깐, 컴파일러가 실제로 specialization을 수행한 SIL코드를 들여다봅시다.

출처
https://techblog.zepeto.me/%EB%A7%88%EB%B2%95-%EA%B0%99%EC%9D%80-swift-%EC%A0%9C%EB%84%A4%EB%A6%AD-%EC%9D%B4%EC%95%BC%EA%B8%B0-2c222ae2798

Generic 함수

Generic 함수를 구현한 뒤, 아래 명령어를 통해서 SIL(Swift Intermetiate Language) 파일을 생성할 수 있습니다.

swiftc Generics.swift -O -emit-sil -o Generics.s

생성된 코드를 보면, generic type(T)가 모두 구체적인 타입(Int, Float)으로 바뀐것을 볼 수 있습니다.

또한, 함수명도 `

i_Tg5`, `

f_Tg5`와 같이 타입 이름이 들어간 함수명으로 바뀌었습니다.

### 과도한 코드 생성? 코드 사이즈 증가?

이렇게 모든 타입마다 새로운 함수 구현체를 생성하기 때문에 코드 사이즈가 증가한다고 생각할 수 있습니다.

Swift는 더더더더 적극적인 최적화를 통해서 코드 사이즈를 줄일 수 있습니다.

먼저 inlining, 축약 등 여러가지 기법을 통해서 optimization을 수행합니다.

이제 어떻게 동작하는지 알았으니, 언제 동작하는지 알아보겠습니다.

언제 Specialization이 동작하는가?

두 가지 조건을 기억하시면 됩니다.

첫 번째로, call-site에서 타입을 추론할 수 있어야 합니다.

위 예제에서 함수의 매개변수로 들어가는 point가 바로 위에서 Point라는 타입으로 초기화됐기 때문에 추론이 가능합니다.

두 번째로, specialization 과정에서 사용될 type과 함수의 정의(구현체를 말하는 듯)가 있어야 합니다.

위 예제에서는 모든 것이 한 파일에 정의되어있어서 가능합니다.

만약 위와 같이 type의 정의, 함수의 정의가 다른 파일에 있다면, UsePoint파일의 입장에서는 해당 정의들은 사용할 수 없는 것들일 것입니다. 컴파일러가 두 파일을 따로 컴파일 할 것이기 때문입니다.

하지만 WMO(Whole Module Optimization)옵션을 통해서 모든 파일을 하나의 단위로서 컴파일할 수 있고 최적화도 가능해집니다.

이 WMO는 Xcode 8부터 기본값으로 활성화 되어있어 따로 신경쓰지 않아도 됩니다.

마지막 예제를 보겠습니다.

Struct와 Protocol을 활용해 Pair을 구현한다면 위와 같이 heap 할당이 두번 일어나게 됩니다.

(이렇게 되는 이유가 기억이 안난다면 [Swift] Protocol에서 Method dispatch 를 다시한번 읽어보시면 도움이 될 거에요)

위 코드를 generic을 활용해 바꿔봅시다.

이제 내부적으로 어떻게 동작하는지 살펴봅시다.

타입이 런타임에 바뀌지 않을 것이므로, Swift가 생성한 코드에서는 타입 내부에 저장공간이 할당됩니다.

heap 할당이 불필요하게 됩니다.

(분명 아까는 valueBuffer에 저장된다고 했는데, 최적화를 통해서 이렇게 저장이 가능한가봅니다.)

이렇게 heterogeneous한 타입이 할당되는것이 불가능하기 때문에 specialization이 가능하다고 합니다.

왼쪽과 같이 unspecialized상태의 코드는 valueBuffer, VWT, PWT가 모두 필요했습니다.

하지만 specializeation을 통해서 각 타입에 맞는 함수를 생성할 수 있습니다.

(그렇지만 아까의 의문은 아직도 해결할 수 없었습니다. valueBuffer, VWT, PWT, 또 existentail container모두 컴파일 시점에 생성되는 것들입니다. 또한 최적화도 컴파일 시점에 일어나죠.)

(같은 protocol + generic 이라도 최적화 될 수 있는게 있을 것이고, 최적화가 불가능한 것이 있을것인데, 굳이 generic에 대해서만 existential container를 생성하지 않는지 모르겠다는 것 입니다.)

(아마 프로토콜과 제네릭의 추상화 단위가 값, 타입으로 다른것이 영향이 있을 것 같은데 이 부분에 대해서는 조금 더 공부해봐야겠습니다.)

성능

struct에서 generic을 사용했을 때 specilization이 된다?

아무것도 걱정할 필요 없습니다. 최고의 성능을 보여줍니다.

class에서 generic을 사용했을 때 specialization이 된다고 하더라도

일반적으로 class를 사용했을 때와 다르지 않은 성능을 보여줍니다.

specialization이 불가능할 경우에는, 메서드를 실행할 때 PWT에서 찾아 실행해야 하기 때문에 조금의 비용이 발생합니다.

값이 크다면 heap할당이 필요하고, 만약 값에 레퍼런스 타입이 있다면 reference counting도 해야합니다.

indirect storage & COW 와 같은 기술로 비용을 줄일 수 있는 방법이 있습니다.

최종 정리

동적으로 런타임시 타입이 많이 변하지 않는 것에 대해서 적절한 추상화를 해야합니다.

이를 통해 정적인 타입 검사가 가능해지고, 컴파일러가 컴파일타임에 프로그램이 올바른지 검사할 수 있고, 코드를 빠르게 하기 위해 최적화를 수행하게 도와줄 수 있습니다.

struct나 enum과 같은 값타입으로 엔티티를 표현한다면 value sementic을 얻을 수 있습니다. (?) 그렇게 value sementic을 얻으면 의도치 않은 상태의 공유를 피할 수 있고, 매우 최적화된 코드를 얻을 수 있습니다.

만약 identity나 OOP스타일의 polymorphism이 필요해서 class를 사용해야 한다면, 앞에서 설명한 방법을 통해서 reference counting을 줄일 수 있습니다. (어떤 방법인지 다시 찾아보고오기)

코드의 일부분이 더 정적인 형태의 polymorphism을 사용해 표현될 수 있다면, generic과 value type을 조합하면 더 빠른 코드를 얻을 수 있다. 하지만 구현을 공유할 수도 있습니다.(오버엔지니어링을 뜻하는것인가?)

앞의 예제인 drawable의 배열과 같은 동적인 polymorphism이 필요하다면, protocol type과 value type을 조합해 class보다 빠른 코드를 구현할 수 있습니다. 하지만 value sementic이기 때문에 상태를 공유할 수 없다.

generic 이나 protocol type 내부에 large value의 복사로 인해 heap allocation의 문제가 생겼다면, indirect storage & COW를 통해 비용을 줄일 수 있습니다.