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'로 비교해 보자면

시간은 0.15초 차이로 구조체 버전이 더 빨랐고

메모리는 0.3MB 차이로 클래스 버전이 더 우세했다.

'테스트 9'의 테스트 케이스 복잡도가 어느정도인지는 공개되지 않았지만
문제의 제약사항으로 볼 때 총 노드만 2만개 정도이니 어마어마하게 반복됐을 거라고 추정된다.

결론

아무리 mutating func을 자주 호출한다해도 Value Type인 구조체의 속도가 더 빨랐습니다.
(구조체가 Static dispatch 접근이고 ARC도 안하고 메모리상 스택에서 오버해드 없이 빼오니 여러모로 Value Type이 짱!)
그래도 구조체 쪽이 새 인스턴스가 자주 발생하다보니 Reference Type의 클래스 쪽이 메모리 잡아먹는건 덜했습니다.

본 실험은 Swift로 테스트 되었습니다. 다른 언어나 다른 접근 방식에서는 다를 수도 있음