WWDC16 - Understanding Swift Performance

Overview

프로토콜 타입 변수 및 제네릭 타입 변수가 어떻게 저장되고 복사되는지, 메서드 디스패치가 어떻게 동작되는지 알아보자.

Protocol Types

다형성을 만족하는 프로그램: Drawable 프로토콜 타입 배열에 Point, Line 타입을 모두 저장할 수 있기 때문

protocol Drawable { func draw() }

struct Point : Drawable {
		var x, y: Double
		func draw() { … }
}
struct Line : Drawable {
		var x1, y1, x2, y2: Double
		func draw() { … }
}
class SharedLine : Drawable {
		var x1, y1, x2, y2: Double
		func draw() { … }
}

var drawables: [Drawable]
for d in drawables {
		d.draw()
}

하지만 v-table 디스패치를 수행하는데 필요한 공통 상속 관계를 공유하지 않는다.

그렇다면 어떻게 올바른 메서드로 디스패치할까?

Witness table을 사용하는 것이다.

Protocol Witness Table (PWT)

application에 프로토콜을 구현하는 테이블이 타입마다 있고 해당 테이블의 항목은 해당 타입의 메서드 구현에 연결된다.

• Point 클래스는 Drawable 프로토콜에 대한 PWT가 있다.
• Line 클래스는 Drawable 프로토콜에 대한 PWT가 있다.

ok 찾는 방법 알아써.. PWT를 통해서 찾는다구.. 그런데 테이블로 어떻게 이동함요…?

배열의 요소에서 테이블로 이동하는 방법이 뭐냐구!!!!

Line를 저장하려면 4개의 공간이 필요하고 Point를 저장하려면 2개의 공간이 필요하다. (다른 크기)

배열은 요소를 배열의 고정된 크기의 오프셋에 균일하게 저장하려고 한다.

⁉️ How to store Values Uniformly?

💥 Swift는 ‘Existential Container’라는 특별한 storage layout을 사용한다.

The Existential Container

boxing value of protocol types

existential container 안의 첫 3개의 words는 valueBuffer 용도로 예약할 수 있다.

• Point의 경우, 2개의 words만 필요하므로 Inline valueBuffer 적합
• Line의 경우, 4개의 words 필요
  • 힙에 메모리 할당 후, 값을 저장하고 해당 메모리에 대한 포인터를 existential container에 저장 → cost 발생
    

existential container는 이러한 차이에 맞게 관리해야 하는데, 이를 테이블 기반 메커니즘인 Value Witness Table를 통해 관리한다.

Value Witness Table (VWT)

VWT는 value의 생명주기를 관리하며 프로그램에서 타입 마다 VWT를 가진다.

지역 변수의 생명주기에 대한 예시

프로토콜 타입인 지역 변수의 생명주기가 시작될 때, Swift는 해당 테이블 내부에서 allocate 함수를 호출한다.

1. VWT에서 allocate 함수를 호출 힙에 메모리를 할당한 후, 해당 메모리에 대한 포인터를 existential container의 value buffer에 저장한다.

2. copy 함수 호출 : 값 초기화

   지역 변수를 초기화하는 할당 소스의 값을 existential container로 복사

   

3. destruct 함수 호출: 지역 변수 소멸

   타입에 포함될 수 있는 value에 대한 reference count를 줄인다. (Line에는 아무것도 없음)

   

4. deallocate 함수 호출

   value에 대해서 힙에 할당된 메모리가 할당 해제된다.

   

여전히 어떻게 그 테이블(PWT, VWT)에 접근할 수 있는가에 대한 의문이 풀리지 않음

Existential container에 PWT, VWT에 대한 참조가 있다!!!!

그럼 VWT, PWT, Existential Container가 어떤 내용을 담고 있고 어떤 관계를 맺고 있는지는 알았다. 그럼 실제로 protocol 타입 인스턴스에 대해서 existential container가 어떻게 동작하는지 알아보자.

Existential Container가 어떻게 동작하는가?

코드 설명

• Drawable 프로토콜 타입의 지역변수를 생성하고 이를 Point로 초기화
• 해당 변수를 drawACopy 함수 호출 인자로 전달

// Protocol Types
// The Existential Container in action
func drawACopy(local : Drawable) {
		local.draw()
}

let val : Drawable = Point()
drawACopy(val)

위 코드에 대해서 Compiler가 생성한 코드를 pseudocode로 표현한 것

struct ExistContDrawable {
		var valueBuffer: (Int, Int, Int) // three words storage 
		var vwt: ValueWitnessTable // reference
		var pwt: DrawableProtocolWitnessTable //reference
} 

동작 과정

1. generated code를 살펴보면 drawACopy 함수에 argument의 existential container를 전달한다. 함수가 실행되면 지역변수를 생성하고 거기에 argument를 할당한다.

1. 스택에 ExistContDrawable 를 할당한다. (struct이니까 당연하겠지)

   func drawACopy(val: ExistContDrawable) {
   		var local = ExistContDrawable()

   

2. val의 vwt, pwt 필드를 읽고 local의 필드를 초기화한다.

   func drawACopy(val: ExistContDrawable) {
   		var local = ExistContDrawable()
   		let vwt = val.vwt
   		let pwt = val.pwt
   		local.type = type
   		local.pwt = pwt

3. 필요할 경우, buffer를 할당하고 값을 복사하기 위해 VWT 함수 호출

   • Point는 valueBuffer 크기 만으로 충분해서 동적할당이 필요하지 않음

   

   

   • Line의 경우 buffer를 할당하고 값을 복사하는 동적 할당

   

4. draw 함수가 실행될 때,

   1. local의 pwt를 통해 PWT를 조회
   2. draw 메서드 주소를 조회하고
   3. 구현으로 점프하여 실행

   

6. 이때, pwt.draw(vwt.projectBuffer(&local)) vwt는 projectBuffer를 호출

projectBuffer 역할

draw 메서드는 value를 input으로 받는다. (Point, Line의 저장속성)

• 값이 인라인 버퍼에 맞는 (3 words 이하) 작은 값이면 existential container의 시작 주소
• 인라인 버퍼에 맞지 않는 큰 값인 경우 힙에 할당된 메모리 주소

1. 메서드 실행 후, 함수의 끝 → 매개변수에 대해 생성된 local이 scope를 벗어남

   값을 destruct하기 위해 VWT에 있는 함수 호출하여,

   • reference counting 감소하고 할당된 경우 buffer 할당 해제

2. 함수 실행 완료되면, 스택 제거, local 도 제거

🔥 struct도 Protocol과 결합하여 동적 동작, 동적 다형성을 얻을 수 있다는 것!

그 전 클래스 디스패치와 비교하면, v-table을 거치고 reference counting을 통한 overhead이 발생하는 것이 비슷하다.

Protocol Type Stored Properties

2개의 프로토콜 타입의 저장 속성을 포함한 쌍

struct Pair {
		init(_ f: Drawable, _ s: Drawable) {
				first = f ; second = s
		}
		var first: Drawable
		var second: Drawable
}
var pair = Pair(Line(), Point())

구조체는 struct에 인라인 형태로 저장됨

• 구조체에 2개의 existential container를 저장한다.
  • Line은 Heap에 buffer 할당
  • Point는 container의 value buffer에 값 저장

프로그램에서 다른 유형의 값 저장 가능 → 다형성 만족

pair.second = Line()

Expensive Copies of Large Values

let aLine = Line(1.0, 1.0, 1.0, 3.0)
let pair = Pair(aLine, aLine)
let copy = pair

• existential container에 대해서 value buffer가 아닌 heap에 buffer를 할당하여 저장 → heap에 2개 할당
  
• copy할 때, 추가로 heap에 2개 할당

총 heap에 4개 할당: expensive cost

What’s better?

방안 1. 두번째 필드에 대해서 첫번째 참조를 복사하면 heap을 할당하지 않고 reference counting만 증가해도 된다.

but, value semantics가 아닌 reference semantics여서 변경사항을 공유한다. 이건 의도된 것과 다르다!!!

→ copy-on-write 방식 사용: write하기 전에 인스턴스를 복사하여 해당 복사본에 쓴다.

Indirect Storage with Copy-on-Write

LineStorage 클래스 생성 (Line 구조체의 모든 필드를 포함하는 클래스)

Line 구조체는 LineStorage 참조

• 값을 읽고 싶을 때, 해당 저장소 내부의 값을 읽는다.

class LineStorage { var x1, y1, x2, y2: Double }

struct Line : Drawable {
		var storage : LineStorage
		
		init() { storage = LineStorage(Point(), Point()) }
		func draw() { … }
		
		mutating func move() {
				if !isUniquelyReferencedNonObjc(&storage) {
						storage = LineStorage(storage)
				}
				storage.start = ...
		}
}

값을 수정하거나 변경하려면 참조 횟수를 확인

• !isUniquelyReferencedNonObjc(&storage)
  • reference가 unique하지 않다. (reference count가 2이상이다.) 다른 인스턴스가 참조를 공유하는 상태이므로 수정하기 위해서 복사본 만들어 변경
    

Indirect Storage를 활용한 Copy 과정

let aLine = Line(1.0, 1.0, 1.0, 3.0)
let pair = Pair(aLine, aLine)
let copy = pair

힙에 있는 reference count를 5로 증가 → heap에 5개 할당하는 것보다 훨씬 저렴

---

지금까지 protocol type 변수가 어떻게 복사되고 저장되고, 메서드 디스패치가 작동하는지에 대한 이해를 바탕으로 프로토콜 타입의 성능에 대해서 알아보겠다.

Performance of Protocol Types

정리해보면서 성능 평가를 해보자.

Protocol Type - Small Value

existential container의 valueBuffer에 들어갈 수 있는 작은 값을 가진 프로토콜 타입

• 힙 할당이 필요 없음
• 구조체에 참조가 없으면 reference counting도 없다.

→ 따라서 매우 빠르다.

• VWT, PWT를 활용한 동적 디스패치로 동적 다형성 동작을 허용할 수 있다.

속도도 빠른데, 다형성도 만족한다고?!!!

Protocol Type - Large Value

• 변수를 초기화하거나 할당할 때 마다 힙 할당 발생
• 참조가 포함된 경우 reference counting 발생

하지만 Indirect Storage를 활용한 copy 매커니즘을 사용하면, 힙 할당 비용을 더 저렴한 reference counting 비용으로 교환 가능

• heap allocation cost → reference counting cost

이랬는데????

요래 됐거등예….!

클래스와 비교해보자

클래스

• 초기화시 할당
• reference counting 발생

중간 정리

1. protocol type은 동적인 형태의 다형성을 제공한다.
   • 프로토콜과 함께 여러 value type들을 사용할 수 있다.
   • 프로토콜 타입 배열 내부에 여러 구조체 타입을 저장할 수 있다.
2. PWT, VWT, existential container를 활용해서 가능하다!!!!
3. 큰 값을 복사할 때, 힙 할당 비용이 발생하는데 이를 copy-on-wrtie 방식으로 해결
   • 힙 할당 비용을 reference counting 비용과 trade-off

Generic Code

제네릭 타입 변수는 어떻게 저장되고 복사되는지 그리고 메서드 디스패치가 어떻게 작동되는지 알아보자.

특징

1. 제네릭 코드는 parametric polymorphism이라는 정적 형태의 다형성 지원

2. One type per call context

   func foo<T: Drawable>(local : T) {
   		bar(local)
   }
   func bar<T: Drawable>(local: T) { … }
   
   let point = Point()
   foo(point)

   1. foo 함수가 실행될 때, Swift는 일반 타입 T를 호출 측에서 사용되는 타입(Point)로 바인딩 → foo 호출 컨텍스트에서 T를 Point로 바인딩

      !

   2. bar 함수 호출에 도달하면 local 변수는 Point를 갖음

   3. bar 함수 호출 컨테스트에서 T가 Point 타입으로 바인딩

3. Type substituted down the call chain

   호출 체인에 따라 타입이 대체된다.

Implementation of Generic Methods

// Drawing a copy using a generic method
protocol Drawable {
		func draw()
}
func drawACopy<T: Drawable>(local : T) {
		local.draw()
}

let line = Line()
drawACopy(line)
// ...
let point = Point()
drawACopy(point)

• 프로토콜 타입과 마찬가지로 하나의 shared implementation이 있다.
• Protocol/Value Witness Table를 사용한다.
• 호출 컨텍스트 당 하나의 유형이 있기 때문에 existential container를 사용하지 않는다.
  • 대신, Point의 VWT와 PWT를 함수에 대한 추가 argument를 전달 가능
• 함수를 실행하는 동안, local 생성할 때 VWT를 사용하여 잠재적으로 필요한 버퍼를 heap에 할당하고 해당 버퍼에 대하여 복사한다.
• 메서드를 실행할 때, PWT를 사용하여 draw 메서드 구현으로 이동

Existential container가 없는데 변수에 필요한 메모리를 어디에 어떻게 할당할까??

바로 stack에 valueBuffer를 할당한다.

Storage of Local Variables

valueBuffer는 3 words이다.

• 작은 구조체인 경우, valueBuffer에 그 값을 모두 저장
• 큰 구조체인 경우, 힙에 저장하고 그 포인터를 stack에 저장

이 값을 저장하고 관리하는 것은 Value Witness Table에 의해 관리된다.

정적 형태의 다형성은 Specialization of Generics인 컴파일 최적화를 가능하게 한다.

Specialization of Generics

func drawACopy<T : Drawable>(local : T) {
		local.draw()
}
drawACopy(Point(…)

static polymorphism이므로 call-site에 한가지 타입이 있다.

해당 타입을 사용하여 함수의 제네릭 파라미터를 대체하고 해당 타입에 특정한 버전의 함수를 생성한다.

타입이 무엇이냐에 따라 함수 내부의 코드가 다르다. → 최적화 대상

이처럼 타입별로 함수의 버전을 생성한다. (version per type in use)

타입 별로 코드를 생성하니까 코드 양이 많이 늘지 않을까라는 걱정이 들 수 있다.

→ static typing 정보는 공격적인 컴파일러 최적화 대상이어서 코드 크기를 잠재적으로 줄일 수 있다.

최적화 과정

func drawACopyOfAPoint(local : Point) {
		local.draw()
}
func drawACopyOfALine(local : Line) {
		local.draw()
}

drawACopyOfAPoint(Point(…))
drawACopyOfALine(Line(…))

⬇️

let local = Point()
local.draw()
drawACopyOfALine(Line(…))

⬇️

Point().draw()
Line().draw()

코드가 한줄로 줄어들 수 있고 draw 함수의 구현으로 대체해서 더 최적화 가능

어떤 경우에 Specialization이 일어날까?

specialization이 일어나기 위한 조건

• call-site에서 타입 추론
• specialization에 사용되는 함수에 대한 정의 필요

프로그램 1.

// main.swift
struct Point {...}
let point = Point()
drawACopy(point)

프로그램 1은 하나의 파일에 정의되어 있어 전체 모듈 최적화 기회를 크게 향상할 수 있다.

프로그램 2.

// Point.swift
struct Point {
		...
}

// UsePoint.swift
let point = Point()
drawACopy(point)

프로그램 2는 컴파일러가 2개의 파일을 별도로 컴파일하므로 drawACopy 에서 Point의 정의를 사용할 수 없다.

Solution

프로그램 2의 경우 Whole Module Optimization (WMO)를 사용하면 된다.

WMO는 두 파일을 하나의 단위로 함께 컴파일할 수 있어 최적화할 수 있다.

Generic Stored Properties

struct Pair {
		init(_ f: Drawable, _ s: Drawable) {
				first = f ; second = s
		}
		var first: Drawable
		var second: Drawable
}
var pair1 = Pair(Point(), Point())
var pair2 = Pair(Line(), Line())

이렇게 Pair에 대해서 first, second 필드가 동일한 타입으로만 할당된다면 제네릭 타입으로 수정할 수 있을 것이다! 요렇게

struct Pair<T: Drawable> {
		init(_ f: T, _ s: T) {
			first = f ; second = s
		}
		var first: T
		var second: T
}
var pair = Pair(Line(), Line())

저장 속성이 제네릭 타입으로 구현된 것을 알 수 있다.

타입은 런타임 중에 변경될 수 없다!

위 코드를 실행할 때, Pair가 둘러싸는 인라인 형태로 할당된다. → 추가 힙 할당 필요 없음

다른 타입을 저장할 수 없음 (~~pair.first = Point()~~)

Performance of Generic Code

• specialized code와 unspecialized code가 작동 방식

Struct Type 과 비교

Specialized generic은 구조체 유형을 사용하는 것과 동일한 성능 특성을 갖는다.

• 값을 복사할 때 힙 할당이 필요하지 않다는 점
• 구조체에 참조가 포함되어 있지 않으면 참조 계산이 없다는 점
• 정적 메서드 디스패치: 컴파일러 최적화 가능, runtime(실행시간) 줄임

Class Type과 비교

Specialized generic 인자로 클래스 유형을 사용하면 클래스와 유사한 특징을 가짐

• Heap allocation
• reference counting
• dynamic dispatch through V-table

Unspecialized Generics—Small Value

• No heap allocation - 스택에 할당된 valueBuffer에 할당될 수 있기 때문
• 값에 참조 포함 없으면 No reference counting
• Dynamic Dispatch through Protocol Witness Table

Unspecialized Generics—Large Value

• Heap allocation - Indirect stroage 사용
• 값에 참조가 포함되어 있으면 reference counting
• Dynamic Dispatch through Protocol Witness Table

Summary.

Choose fitting abstraction with the least dynamic runtime type requirements

애플리케이션 엔티티에 적합한 추상화를 선택할 때, 동적 런타임 타입 요구사항이 가장 적은 abstraction을 선택해라

→ static type checking이 가능하고 컴파일 타임에 코드가 올바른지 확인 가능, 최적화를 위한 정보를 제공받을 수 있으므로 더 빠른 코드를 얻을 수 있다.

• struct types: value semantics 공유가 없는 의미 체계를 얻고 최적화된 코드를 얻을 수 있다.
  
• class types: identity or OOP style polymorphism 클래스를 사용하는 경우 reference counting 비용을 줄여라
  
• Generics: static polymorphism static 다형성을 사용하여 code를 작성하면 value type을 제네릭 코드와 결합한채 코드를 공유할 수 있고 빠른 코드도 얻을 수 있다.
  
• Protocol types: dynamic polymorphism Protocol type를 활용하면 클래스를 사용하는 것보다 value semantics를 유지한 채 빠른 코드를 얻을 수 있다.
  

Use indirect storage to deal with large values

프로토콜 혹은 제네릭 타입에서 큰 값을 복사할 때 발생하는 힙 할당 비용에 대해서 copy-on-write 방식으로 해결할 수 있었다.

Related.