당신이 iOS 프로그래밍을 한다면 거의 마주치지 않을 일에 대한 해결책을 적어놓은 글

[newJunsung]

반갑다.

오전 12팀 HMHZ의 공장장 뉴준성이다.
오늘은 재미없는 이야기에 대해 하고자 한다.
하지만 당신이 Swift라는 언어를 사랑한다면, 한 번쯤 보면 유익한 글이지 않을까 싶다.
아직까지 iOS 프로그래밍을 하면서 앱이 버벅인다거나 이런 경우는 발견하기 쉽지 않을 것이다.
그런데 10만 개 이상의 데이터를 처리하는 PS(쉽게 말하면 코테)의 영역으로 들어가면 발견하게 되는 문제가 있다.
그건 바로 사소한 코드의 수정으로도 문제를 처리하는데 걸리는 시간이 5배 이상 차이가 날 수도 있다는 것이다.
물론 Swift로 서버를 구축한다면 이 글을 언젠가 한 번쯤 읽어봐도 좋을 수도 있다.

• 아래 코드의 일부(652 ms)

let divider = 1_000_000_007
let my1 = [-1, 0, 1]
let mx1 = [1, 1, 0]
let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])

var hive = [[Int]](repeating: [Int](repeating: 0, count: m), count: n)s
// ...
for x in 0..<m {
    for y in 0..<n {
      for i in 0..<3 {
          let newX = x + mx[i]
            let newY = y + my[i]
      hive[newY][newX] += hive[y][x]
      hive[newY][newX] %= divider
    }
  }
}
// ...

• 위 코드의 일부(124 ms)

let divider = 1_000_000_007
let my1 = [-1, 0, 1]
let mx1 = [1, 1, 0]
let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])

var hive = [[Int]](repeating: [Int](repeating: 0, count: m), count: n)
// ...
for x in 0..<m {
    for y in 0..<n {
      for i in 0..<3 {
          let newX = x + mx[i]
            let newY = y + my[i]
      hive[newY][newX] = (hive[newY][newX] + hive[y][x]) % divider
    }
  }
}
// ...

코드는 다르지만, 결과는 동일하다는 것을 코딩을 한 사람들은 알 것이다.
그럼에도 불구하고 시간이 5배 차이가 나는 이유는 무엇일까?
우선 COW에 대해 알아보도록 하자.

COW란? (Copy On Write)

아래의 코드를 확인해보면, h2가 h1을 통해 복제가 되고 있는 것을 확인할 수 있다.
(구조체는 어디까지나 예시다.)

struct Human {
  var age: Int
  var name: String
}

let h1 = Human(age: 20, name: "H1")
var h2 = h1

let h1 = Human(age: 20, name: "H1") 코드가 실행되고 난 이후의 메모리 상황은 일단 아래와 같을 것이다.

그리고 var h2 = h1 코드를 실행하면, COW에 대해 모르는 사람들은 아래와 같은 상황이 될 것이라고 생각하는 경우가 많을 것이다.

그러나 사실 이렇지 않다.
변수에 값을 복제할 때, 새로운 값을 만들어 메모리에 할당하는 것이 아닌 원본 값을 참조한다.
그림으로 보면 아래와 같은 상황이 일어난다는 것이다.

그렇다면 h2의 age 혹은 name이 바뀌게 되면 h1의 값이 바뀐다고 생각하는 사람이 있을 수도 있다.
물론 h1은 상수라 값이 바뀌지 않고, 바뀌면 안된다.

struct Human {
	var age: Int
	var name: String
}

let h1 = Human(age: 20, name: "H1")
var h2 = h1
h2.name = "H2"
h2.age = 58

이 경우에는 h2의 값이 바뀌기 때문에 이 시점에서 메모리를 새로 할당한다.

이러한 과정을 COW(Copy On Write)라고 한다.
COW를 어디에서 사용하는 것이고 왜 사용할까?라는 질문에는 프로세스 생성을 예로 들 수 있다.
fork()를 통해 새로 프로세스를 만든다고 가정했을 때, COW를 하지 않는다면 새로 프로세스를 만들어야 하기 때문에, 오버헤드가 커진다.
따라서 값에 수정이 있기까지 부모 프로세스의 주소를 자식 프로세스가 가리키고 있다면, 프로세서를 생성하는 과정에서의 오버헤드를 않이 줄일 수 있기 때문에, COW를 사용한다고 한다.

Swift에서의 COW

**'Swift와 COW가 그래서 무슨 상관인데?'**에 대한 답변을 할 차례다.
컬렉션 타입(배열, 딕셔너리, 문자열 등)의 경우 구조체임에도 불구하고 힙 영역에 할당이 된다.
왜나하면 컬렉션 타입의 경우, 사이즈가 가변적이기 때문에 스택에 정해진 크기만큼 할당할 수 없기 때문이다.
아래와 같은 코드가 있다고 해보자.

var a = [1, 2, 3, 4] // Line 1
var b = a // Line 2
b.append(5) // Line 3

1번 째 줄을 실행하면 메모리(힙)에 아래와 같이 저장이 될 것이다. (참고. 변수 a는 스택 메모리에 있다.)

앞서 배운 COW 개념을 적용했을 때, 2 번째 줄을 실행하면 아래와 같은 상황이 된다.

마지막으로 3 번째 줄을 실행하면, b는 새로운 메모리를 할당받으며 초기화가 진행될 것이다.

결국 아래와 같은 상황이 될 것이다.

컬렉션 타입에서 할당 연산 시의 COW (추측)

여기서부터는 추측의 영역이다.
다차원 배열에서 할당 연산(+=, -=, *=, /= 등.)을 할 경우의 상황을 살펴보자.
아래의 코드에서 i와 j가 둘 다 0일 때 Line 1 연산을 할 경우, 메모리는 아래와 같은 상황이 될 것 같다.

var a = [[Int]](repeating: [Int](repeating: 0, count: 4), count: 2)
for i in 0..<(a.count - 1) {
    a[i][0] = 1
    for j in 0..<(a[i].count - 1) {
        a[i][j + 1] += a[i][j] // Line 1
    }
}

위의 이미지 같은 상황에서 기존의 값을 보유하는 변수를 하나 만들고, 거기서 더하기 연산을 할 것 같다.
그런데 앞서 말했다시피 컬렉션 타입은 힙 영역에 할당되고 COW가 적용되기 때문에 아래와 같은 상황이 될 것이다.

여기서 a[0][j + 1] = a[0][j + 1] + Temp[j]이 일어나서 a[0]은 다시 초기화가 진행된다.

마무리로 Temp는 제 역할을 다 했기 때문에 소멸된다는 것이 내 추측이다.

즉, 할당 연산 시에는 매 번 COW로 인한 초기화가 일어난다는게 내 추측이다.
그리고 놀랍게도, 내 추측은 사실이었다.
아래의 코드를 콘솔에서 실행시키고 출력된 결과를 확인하면 메모리 주소가 바뀌는 것을 확인할 수 있다!

코드

func printAddress(of object: UnsafeRawPointer) {
    print(object)
}

var a = [[Int]](repeating: [Int](repeating: 0, count: 4), count: 2)
for i in 0..<(a.count) {
    a[i][0] = 1
    for j in 0..<(a[i].count - 1) {
        a[i][j + 1] += a[i][j]
        print("--a[\\(i)]의 배열주소--------")
        printAddress(of: a[i])
        print("----------------------------")
    }
}

실행 결과

컴파일(뇌피셜)

결론적으로 이 코드를 컴파일하면 아래와 비슷할 것 같다.

// 컴파일 전
var a = [[Int]](repeating: [Int](repeating: 0, count: 4), count: 2)
for i in 0..<(a.count - 1) {
    a[i][0] = 1
    for j in 0..<(a[i].count - 1) {
        a[i][j + 1] += a[i][j] // Line 1
    }
}
// 컴파일 후
var a = [[Int]](repeating: [Int](repeating: 0, count: 4), count: 2)
for i in 0..<(a.count - 1) {
    a[i][0] = 1
    for j in 0..<(a[i].count - 1) {
        var temp = a[i]
        a[i][j + 1] = a[i][j + 1] + temp[j]
    }
}

마무리

그럼 할당연산을 하지 않고 어떻게 해결해야 할까? (Swift로 PS를 안하면 된다.)
내가 내린 결론은 += 연산자 대신 + 연산자를 쓰는 것이다.
아래와 같이 쓰는 것보단,

var a = [[Int]](repeating: [Int](repeating: 0, count: 4), count: 2)
for i in 0..<(a.count - 1) {
    for j in 0..<(a[i].count - 1) {
        a[i][j + 1] += a[i][j]
    }
}

이렇게 쓰는 것을 추천하고 싶다.

var a = [[Int]](repeating: [Int](repeating: 0, count: 4), count: 2)
for i in 0..<(a.count - 1) {
    for j in 0..<(a[i].count - 1) {
        a[i][j + 1] = a[i][j + 1] + a[i][j]
    }
}

마찬가지로, 위 코드를 컴파일하면 이런 결과가 나올 것 같다.
(메모리 주소에서 값을 갈아끼우는 개념으로 생각하면 된다.)

var a = [[Int]](repeating: [Int](repeating: 0, count: 4), count: 2)
for i in 0..<(a.count - 1) {
    for j in 0..<(a[i].count - 1) {
        let temp = a[i][j]
        a[i][j + 1] = a[i][j + 1] + temp
    }
}

여기까지 열심히 읽은 사람들을 위해 몇 가지 TMI를 알려주겠다.

1. 나는 코테문제를 풀지 않는다.
2. 그리고 놀랍게도 이건 블로그 글을 퍼와서 약간 수정한거다.
3. 근데 블로그의 주인한테 허락을 받았다.
4. 근데 블로그 주인이 바로 나다.