struct Struct {
let aaa: Int
let bbb: String
}
class Class {
let aaa: Int
let bbb: String
}
위와 같은 형식의 구조체와 클래스의 인스턴스를 무수히 반복하여 처리한다고 했을 때
구조체가 성능면에서 더 우세하다는 건 알고 있을 것이다.
그렇다면 mutating function 이 자주 사용되는 Struct라면 어떨까?!
// 이런 경우라면?! struct Struct { let aaa: Int let bbb: String mutating func change() { aaa += 1 } }
스택오버플로의 답변에 따르면 mutating function이 사용된 경우 구조체의 인스턴스는 메모리 상에서 새 인스터스로 교체된다고 한다.
아무리 Value Type으로 처리된다고 해도 그렇게 막 생성되면 클래스 쪽이 더 성능 빠른거 아니야?
마침 프로그래머스 코딩 문제를 풀던 도중 테스트해보기 딱 좋은 상황이 나왔다.
바로 테스트해보자
struct PriorityQueue {
private var nodes: [Node] = []
var count: Int {
return nodes.count
}
// mutating
mutating func enqueue(_ element: Node) {
nodes.append(element)
let lastIndex = count - 1
shiftUp(child: lastIndex)
}
// mutating
mutating func dequeue() -> Node {
nodes.swapAt(0, count - 1)
defer { shiftDown(parent: 0) }
return nodes.removeLast()
}
private func parentIndex(of child: Int) -> Int {
return (child - 1) / 2
}
private func leftChildIndex(of parent: Int) -> Int {
return (parent * 2) + 1
}
private func rightChildIndex(of parent: Int) -> Int {
return parent * 2
}
// mutating
mutating private func shiftUp(child: Int) {
var child = child
var parent = parentIndex(of: child)
while child > 0 && nodes[child] < nodes[parent] {
nodes.swapAt(child, parent)
child = parent
parent = parentIndex(of: child)
}
}
// mutating
mutating private func shiftDown(parent: Int) {
var parent = parent
while true {
let left = leftChildIndex(of: parent)
let right = rightChildIndex(of: parent)
var candidate = parent
if right < nodes.count && nodes[right] < nodes[candidate] {
candidate = right
} else if left < nodes.count && nodes[left] < nodes[candidate] {
candidate = left
} else {
return
}
nodes.swapAt(parent, candidate)
parent = candidate
}
}
}
class PriorityQueue {
private var nodes: [Node] = []
var count: Int {
return nodes.count
}
// no mutating
func enqueue(_ element: Node) {
nodes.append(element)
let lastIndex = count - 1
shiftUp(child: lastIndex)
}
// no mutating
func dequeue() -> Node {
nodes.swapAt(0, count - 1)
defer { shiftDown(parent: 0) }
return nodes.removeLast()
}
private func parentIndex(of child: Int) -> Int {
return (child - 1) / 2
}
private func leftChildIndex(of parent: Int) -> Int {
return (parent * 2) + 1
}
private func rightChildIndex(of parent: Int) -> Int {
return parent * 2
}
// no mutating
private func shiftUp(child: Int) {
var child = child
var parent = parentIndex(of: child)
while child > 0 && nodes[child] < nodes[parent] {
nodes.swapAt(child, parent)
child = parent
parent = parentIndex(of: child)
}
}
// no mutating
private func shiftDown(parent: Int) {
var parent = parent
while true {
let left = leftChildIndex(of: parent)
let right = rightChildIndex(of: parent)
var candidate = parent
if right < nodes.count && nodes[right] < nodes[candidate] {
candidate = right
} else if left < nodes.count && nodes[left] < nodes[candidate] {
candidate = left
} else {
return
}
nodes.swapAt(parent, candidate)
parent = candidate
}
}
}
위 코드와 같이 구조체에서의 우선순위 큐는 enqueue, dequeue를 할 때마다 mutating func이 호출되고 매번 새 인스턴스로 교체될 것이다.
이제 그럼 성능 결과표를 확인해보자.
구조체 버전 우선순위 큐 결과
테스트 1 〉 통과 (0.13ms, 16.4MB)
테스트 2 〉 통과 (0.16ms, 16.6MB)
테스트 3 〉 통과 (0.23ms, 16.4MB)
테스트 4 〉 통과 (0.87ms, 16.6MB)
테스트 5 〉 통과 (3.31ms, 16.9MB)
테스트 6 〉 통과 (8.42ms, 17.8MB)
테스트 7 〉 통과 (105.29ms, 26.3MB)
테스트 8 〉 통과 (111.49ms, 30.1MB)
테스트 9 〉 통과 (123.81ms, 29.8MB)
클래스 버전 우선순위 큐 결과
테스트 1 〉 통과 (0.14ms, 16.3MB)
테스트 2 〉 통과 (0.16ms, 16.3MB)
테스트 3 〉 통과 (0.23ms, 16.5MB)
테스트 4 〉 통과 (0.91ms, 16.4MB)
테스트 5 〉 통과 (3.50ms, 17.1MB)
테스트 6 〉 통과 (9.50ms, 17.9MB)
테스트 7 〉 통과 (98.33ms, 26.1MB)
테스트 8 〉 통과 (104.48ms, 30.4MB)
테스트 9 〉 통과 (138.00ms, 29.5MB)
특별하게 차이나는 결과는 나오지 않았다.
가장 오래 걸린 '테스트 9'로 비교해 보자면
'테스트 9'의 테스트 케이스 복잡도가 어느정도인지는 공개되지 않았지만
문제의 제약사항으로 볼 때 총 노드만 2만개 정도이니 어마어마하게 반복됐을 거라고 추정된다.
아무리 mutating func을 자주 호출한다해도 Value Type인 구조체의 속도가 더 빨랐습니다.
(구조체가 Static dispatch 접근이고 ARC도 안하고 메모리상 스택에서 오버해드 없이 빼오니 여러모로 Value Type이 짱!)
그래도 구조체 쪽이 새 인스턴스가 자주 발생하다보니 Reference Type의 클래스 쪽이 메모리 잡아먹는건 덜했습니다.