Swift 컴파일러의 표현식 타입 검사 성능과 진단 개선을 위한 최근 변경 사항, main 브랜치의 업데이트, 다음 단계 작업 및 장기 계획을 개관한다. 제약 해결, 오버로딩, 살베이지 모드, 테스트 확장, 알고리즘 및 자료구조 최적화를 다룬다.
과거에는 언어의 개선 계획을 논의하기 위해 여러 “선언문(manifesto)”와 “로드맵”을 공개해 왔습니다. 이 글 또한 넓은 의미의 로드맵이지만, 초점은 사용자에게 보이는 언어 변화가 아니라 구현 자체에 맞춰져 있습니다(다만 글의 맨 마지막에 몇 가지 잠재적인 언어 변화도 간략히 언급합니다).
구체적으로는 Swift 컴파일러에서 표현식 타입 검사(expression type checking)를 개선하기 위해 진행 중인 작업을 다룹니다. 여기에는 Swift 6.2에 이미 포함된 변경 사항, 현재 main 개발 브랜치에 있는 변경 사항, 다음으로 계획 중인 작업, 그리고 보다 장기적인 구상까지 포함됩니다.
개별 개선점에 들어가기 전에, 아직 한 곳에 요약된 적이 없는 이 컴파일러 구현 부분에 대한 다소 긴 설명부터 시작하겠습니다.
이 모든 것은 악명 높은 the compiler is unable to type-check this expression in reasonable time 오류와 관련이 있습니다. 이 오류는 올바른 코드와 잘못된 코드 모두에서 나타날 수 있으며, 여러 우회책은 썩 만족스럽지 않습니다. 표현식을 더 작은 조각으로 나누거나, 타입 표기를 추가하거나, 다른 리팩터링을 시도하면 때로는 올바른 코드가 타입 검사를 통과하기도 하고, 잘못된 코드인 경우에는 실행 가능한 진단 메시지가 드러나기도 합니다. 그러나 이는 흐름을 끊고, 숙련된 Swift 프로그래머에게조차 답답한 시행착오식 “산탄총 디버깅” 과정이 됩니다. 게다가 컴파일러는 그 표현식이 올바른지 아닌지도 심지어 알려주지 않습니다!
Swift는 동일한 스코프 내에서 여러 선언이 같은 이름을 공유할 수 있는 오버로딩을 지원합니다. Swift의 오버로딩은 인자 레이블에 의한 것과 타입에 의한 두 가지 형태가 있습니다. 전자의 경우 호출 지점에서 인자 레이블이 명시되므로 궁극적으로 이름 조회(name lookup)로 처리됩니다. 인자 레이블 조회는 타입 체커에 알고리즘적 복잡도를 야기하지 않으므로 더 이상 논의하지 않겠습니다. 반면 타입 기반 오버로딩은 올바른 오버로드를 선택하기 전에 표현식의 타입을 추론해야 하므로 더 어려운 문제입니다. 따라서 본문에서 “오버로딩”이라고 할 때는 매개변수나 결과 타입에 기반한 오버로딩을 특별히 의미합니다.
Swift 컴파일러는 표현식 타입 검사를 제약 해결 문제로 변환하여 오버로드 결정을 수행합니다. 컴파일러는 기본적으로 단일 표현식만을 한 번에 살피며(다중 문 클로저 등 일부 예외가 있음), 각 표현식을 차례대로 타입 검사합니다.
먼저 구문 트리의 각 하위 표현식의 미지 타입을 나타내기 위해 타입 변수(type variable)를 도입합니다. 다음으로 타입 변수 간의 관계를 기술하기 위한 제약(constraint)을 생성합니다. 제약의 예로는 “타입 X는 타입 Y의 서브타입이다”, “타입 X는 함수 타입 Y에 인자 Z를 적용한 결과 타입이다”, 그리고 오버로딩 해소에 결정적으로 중요한 “분리(disjunction) 제약”이 있습니다. 분리 제약은 “타입 X는 Y1이거나, Y2이거나, Y3이거나 … Yn이다”의 형태를 가지며, 여기서 각 Yn은 같은 이름을 가진 오버로드 선언의 타입입니다.
타입 변수와 제약을 준비한 뒤에는, 제약 집합과 모순되지 않도록 각 타입 변수에 구체 타입을 할당하려 시도함으로써 제약 시스템을 “해결”합니다. 이런 할당의 집합을 해(solution)라고 부릅니다. 제약 해결 과정은 0개, 1개, 혹은 다수의 해를 산출할 수 있습니다. 해가 없다면 표현식은 오류입니다. 해가 하나라면 끝입니다. 해가 여러 개라면, 먼저 해들 간에 “더 나은” 것이 분명한지 순위를 매기려 시도합니다. 이 순위 매김으로 승자를 가리지 못하면 모호성(ambiguity) 오류를 보고합니다.
제약 해결에서의 알고리즘적 복잡도는 분리 제약(disjunction constraints)에서 비롯됩니다. 최악의 경우에는 각 분리 선택지의 조합을 전부 시도하는 것 외에는 더 나은 접근이 없기 때문입니다.
이는 스도쿠를 푸는 것과 비슷합니다. 빈 칸에 숫자를 하나 적고, 결과가 유효한 보드인지 확인합니다. 유효하면 다음 칸을 채우고, 계속 진행합니다. 반면 막히면 과거에 채운 칸을 지우고(백트래킹) 다른 곳에 숫자를 놓아 봅니다. 운이 좋아 매 단계에서 완벽한 추측을 하면 백트래킹 없이 보드를 채울 수 있습니다. 반대로 운이 나쁘면 가능한 모든 경로를 시도하게 되어 매우 오랜 시간이 걸릴 수 있습니다.
Swift 타입 체커의 제약 해결에 대한 자세한 개요는 swift/docs/TypeChecker.md at main · swiftlang/swift · GitHub을 참고하세요. 왜 오버로드 해소가 본질적으로 어려운지, 그리고 알려진 모든 접근이 최악의 경우 지수 시간임을 설명하는 내용은 How does compiler compile SwiftUI code? - #4 by Slava_Pestov 및 Lambda Expressions vs. Anonymous Methods, Part Five | Microsoft Learn를 참고하세요.
reasonable time은 무엇을 뜻하나?분리 제약을 포함한 제약 해결은 최악의 경우 지수 시간이 걸리므로, 타입 체커는 타입 검사에 과도한 시간이 필요한 짧은 프로그램도 항상 존재하게 됩니다. 따라서 타입 체커는 수행하는 총 작업량에 상한을 두고, 그 한계에 도달하면 실패해야 합니다.
Swift 타입 체커는 두 가지 한계를 둡니다:
과거에는 벽시계(wall-clock) 시간 제한도 있었지만, 머신에 따라 비결정적이라 기본적으로 비활성화되었습니다. 연산 횟수를 세는 방식이 더 낫고, 실제로 대부분의 “너무 복잡한” 표현식도 일반적인 머신에서 4초를 넘지 않습니다.
일반 타입 검사에서는 제약이 실패하면 즉시 중단하고 백트래킹하지만, 이것만으로는 정확한 오류 메시지가 나오지 않습니다.
실패 이후 더 나은 진단을 위해, 검색 공간을 확대한 채로 해결 과정을 다시 시작합니다. 이를 “살베이지(salvage) 모드”라고 합니다. 살베이지 모드에서는 제약 해결 실패를 다르게 처리합니다. 실패한 제약이 성공한 것처럼 계속 진행하되, 동시에 수정(fix)을 기록합니다.
예를 들어, 어떤 표현식이 Int가 Sequence에 준수하지 않아 타입 검사가 실패했다고 합시다. 첫 시도에서는 해당 적합성 제약이 실패합니다. 그런 다음 살베이지 모드로 타입 검사를 다시 시작합니다. 문제가 된 제약이 다시 나타나면, 이번에는 Int가 Sequence에 준수한다고 “가정”하면서도 수정(fix)을 기록하고, 나머지 제약 해결을 계속합니다.
살베이지 모드로 제약 시스템 해결을 마치면, 모은 수정들을 분석해 진단 메시지를 생성합니다. 마지막으로, 살베이지 모드마저 실패했는데도 어떤 수정도 기록되지 않았다면, failed to produce diagnostic 오류를 출력합니다.
진단 아키텍처에 대한 자세한 내용은 New Diagnostic Architecture Overview | Swift.org를 참고하세요.
최악의 동작은 피할 수 없지만, 복잡한 오버로드 집합이 있어도 모든 표현식의 타입 검사가 반드시 지수 시간이 걸려야 하는 것은 아닙니다. 실제로 오늘날에도 대부분의 표현식은 꽤 빠르게 타입 검사를 통과합니다. 또한 단일 “어려운” 표현식에 대해서는 빠르게 해결할 수 있는 휴리스틱을 고안하는 것도 가능합니다. 극단적으로는 그 특정 문제 인스턴스에 대한 지식을 해결기에 하드코딩할 수도 있습니다(물론 그렇게 하지는 않을 겁니다).
따라서 주요 목표는, 너무 많은 특수 케이스를 하드코딩하지 않으면서도 대부분의 현실적인 문제 인스턴스를 빠르게 해결할 수 있는 충분히 일반적인 휴리스틱을 고안하는 것입니다. 이상적으로는 지수 시간 동작이 실제로는 잘 발생하지 않을 병적인 예제들에서만 나타나도록 하는 것이죠. 이를 달성하는 주된 방법은 바로 분리 제약 선택지를 올바른 순서로 시도하는 것입니다. 이는 어느 분리 제약을 다음에 시도할지와, 해당 분리 제약 내에서 어떤 선택지를 다음으로 시도할지 모두를 포함합니다. 또한 모순으로 이어질 선택지는 고려하지 않도록 회피할 수 있습니다. 이렇게 하면 올바른 해를 더 빨리 찾고, 긴 “막다른 길”을 탐색하는 데 쓰는 시간을 줄일 수 있습니다.
부차적인 목표로는, 제약 해결기에서 사용하는 보조 자료구조와 알고리즘을 개선하여, 어떤 표현식에서는 불가피하게 전수 탐색이 필요하더라도 같은 검색 공간을 고려하는 데 드는 CPU 시간을 줄이는 것입니다.
또한 두 가지 비목표를 언급해 둘 만합니다:
언어에서 오버로딩을 제거하는 것. 분리 제약이 없다면 제약 시스템은 거의 항상 아주 빠르게 해결할 수 있습니다. 그러나 이는 언어에 너무나 큰 변화를 가져오고 기존 API를 대거 깨뜨리므로, 지금 시점에서는 새로운 언어 모드로조차 시도하기 어렵습니다.
양방향 추론(bidirectional inference)을 제거하는 것. 다른 C 계열 언어들처럼 잎 노드에서 시작하여 엄격한 바텀업 방식으로 표현식을 타입 검사하는 언어 설계도 상상할 수 있습니다. 이것 역시 문제를 본질적으로 사소하게 만드는 대폭 단순화입니다. 하지만 그렇게 하려면 다형 리터럴, 선행 점(leading-dot) 멤버 문법, 타입이 추론되는 클로저, 제네릭의 일부 등 언어 기능을 포기해야 합니다. 이들 기능은 Swift를 오늘날처럼 표현력 있는 언어로 만들어 주는 요소들입니다.
Swift 6.2에서는 다양한 대형 프로젝트와, 개별적으로 느린 표현식(올바른 것과 잘못된 것 모두)에 대해 타입 체커를 프로파일링하는 데 시간을 들였습니다. 이를 통해 백트래킹 구현, 연결 요소 계산 같은 여러 그래프 알고리즘, 기타 잡다한 알고리즘에서 병목이 드러났습니다.
첫 번째 예는 작은 개선을 확인할 수 있는 잘못된 표현식입니다. 아래 코드의 마지막 줄을 보시면, 이 예시는 이 블로그 글에 등장합니다:
let address = "127.0.0.1"
let username = "steve"
let password = "1234"
let channel = 11
let url = "http://" + username
+ ":" + password
+ "@" + address
+ "/api/" + channel
+ "/picture"
이 표현식은 +에 Int와 String을 전달하는 오버로드가 없으므로 잘못되었습니다. 제 머신에서 Swift 6.1은 unable to type-check 오류를 내는 데 10초가 걸렸고, Swift 6.2에서는 같은 오류를 6초에 냅니다. 물론 이는 바람직한 최종 상태가 아니며, 의미 있는 진단을 내야 합니다. 하지만 이 예시는 타입 체커가 동일한 작업량을 더 적은 시간에 처리할 수 있게 되었음을 잘 보여줍니다.
좀 더 현실적인 예로, 오버로딩과 제네릭을 많이 사용하는 프로젝트를 측정했을 때 전체 타입 검사 시간이 Swift 6.1의 42초에서 Swift 6.2에서는 34초로 개선되었습니다.
최근 main 개발 스냅샷에는 @xedin님이 수년간 작업해 온 대규모 변경이 포함되어 있습니다. 더 많은 정보를 수집해 어떤 분리 제약을 다음에 시도할지 결정함으로써, 분리 제약 선택을 개선하는 내용입니다. Swift 6.2의 목표 지향적 최적화가 문제의 근본 복잡도를 줄이지 않으면서 점진적 이득을 준 데 비해, 이번 분리 제약 선택 개선은 그동안 타입 검사할 수 없었던 많은 표현식을 신속히 해결할 수 있게 해 줍니다. 또한 기존에 상한선 바로 아래라 느렸지만 타입 검사는 통과하던 표현식들도 대폭 빨라집니다.
이번 변경은 해결 시작 전에 전체 표현식을 훑어 특정 하위 표현식을 “사전 해결(pre-solving)”하려던 낡은 최적화를 대체합니다. 그런 편법은 실제로 매우 부서지기 쉬워, 표현식에 작은 변화만 있어도 전체 요령이 무력화되곤 했습니다.
최적화된 분리 제약 선택 알고리즘은 제약 해결기 내부에서 동작하여 더 견고하고 예측 가능해졌습니다. 가장 큰 효과는 수치 연산자와 리터럴이 포함된 표현식에서 나타납니다. 다음은 전형적인 예입니다. Swift 6.2 컴파일러는 아래 표현식을 타입 검사할 수 없었지만, main의 컴파일러는 이를 4ms에 성공적으로 타입 검사합니다:
func test(n: Int) -> Int {
return n == 0 ? 0 : (0..<n).reduce(0) { x, y in
(x > 0 && y % 2 == 0) ? (((x + y) - (x + y)) / (y - x)) + ((x + y) / (y - x)) : x
}
}
앞서의 잘못된 예( +를 String과 Int에 적용)는 여전히 거부되지만, 새 알고리즘에서는 한계에 도달하는 데 2초밖에 걸리지 않습니다.
마지막으로 Swift 6.2 요약에서 언급했던 동일 프로젝트에서, 새 알고리즘은 전체 타입 검사 시간을 12초로 더 줄였습니다.
(출시 버전의 Swift에서 타입 검사되던 표현식이 main 개발 스냅샷에서 실패한다면 GitHub 이슈를 등록해 주세요.)
최근 main 개발 스냅샷에는 제약 해결기에서 지수적인 공간 사용을 유발하던 원인을 제거하는 최적화도 포함되었습니다. 이 최적화는 아직 기본적으로 비활성화되어 있으나, 곧 활성화되길 기대합니다. (지금 테스트해 보고 싶다면 main 스냅샷에서 프런트엔드 플래그 -solver-enable-prepared-overloads로 켤 수 있습니다.)
작동 방식은 다음과 같습니다. 기존에는 제네릭 오버로드의 분리 선택지를 시도할 때마다, 해당 오버로드의 제네릭 매개변수와 where 절 요구사항에 대응하는 새로운 타입 변수와 제약을 생성했습니다. 동일한 오버로드를 다른 선택지들과의 조합으로 여러 번 시도해야 하면, 같은 타입 변수와 제약이 매번 다시 생성되었습니다. 이 타입 변수와 제약은 제약 해결기의 아레나에 할당됩니다. 이번 공간 최적화는 해당 구조물을 분리 선택지를 처음 시도할 때 한 번만 할당합니다.
많은 표현식에서 이로 인해 제약 해결기 아레나 사용량이 급감합니다. 일부 경우에는 지수적 공간 문제를 다항 공간 문제로 바꾸기까지 합니다(시간은 여전히 지수일 수 있더라도). 더 나아가 공간이 줄면 시간도 줄어들므로, 핵심 이득은 역시 전체 타입 검사 시간의 감소입니다. 미래에는 이러한 구조물을 사전 생성하는 것이 분리 선택지 알고리즘의 추가 개선도 가능케 할 것입니다.
앞서 +를 String과 Int에 적용하던 잘못된 예에서, 아레나 공간 최적화는 한계에 도달하는 시간을 1.7초로 더 줄였습니다(이는 Swift 6.1 대비 5배 이상 개선입니다).
마지막으로 같은 테스트 프로젝트에서, 이 최적화는 전체 타입 검사 시간을 12초에서 10초로 줄였습니다(이는 Swift 6.1 대비 4배 이상 개선입니다).
향후 성능 회귀를 방지하고, 문제 해결의 진척을 추적하기 위해, 테스트 케이스를 추가했습니다. 이들은 Swift 프로젝트의 GitHub 이슈에 보고된 느린 표현식들을 축약해 만든 것입니다.
일부 테스트 케이스는 scale-test 도구를 사용합니다. 이 도구는 표현식의 공통 요소(예: + 1 + 1 + 1 ...)를 반복해 각 인스턴스의 성능을 측정하고, 결과 문제가 다항 시간인지 지수 시간인지 추정합니다. 이는 겉으로는 “빠르게” 보이나 조금만 길어져도 느려지는 미묘한 문제를 잡아내는 데 도움이 됩니다.
이 테스트 케이스는 Swift 저장소의 validation-test/Sema/type_checker_perf 디렉터리에 있습니다. 최근 추가된 테스트 케이스는 Sema: Collected expression checking performance test cases from GitHub issues by slavapestov · Pull Request #84450 · swiftlang/swift · GitHub, 추가 케이스는 Even more type checker perf tests by slavapestov · Pull Request #84890 · swiftlang/swift · GitHub에서 확인할 수 있습니다. 앞으로도 타입 체커 성능 테스트 모음을 계속 확장할 계획입니다.
주의: 아래 모든 내용은 계획의 진척에 따라 변경될 수 있습니다.
어떤 제약 시스템을 해결 중이라고 합시다. 이제 남은 제약이 하나뿐인데, 타입 변수 T0를 Optional<Int>로 변환하는 제약입니다. 이 시점에서 진행하려면 T0에 묶을(concrete) 구체 타입을 “추측”해야 합니다. T0가 그대로 Optional<Int>일 수도 있지만, Int도 유효한 선택지입니다. Int는 Optional<Int>로 변환되기 때문입니다. 제약 해결기의 바인딩(bindings) 서브시스템은 미해결 변환 제약을 고려해 각 타입 변수의 가능한 바인딩을 추적하고, 궁극적으로 다양한 바인딩을 시도해 해를 찾는 일을 담당합니다.
바인딩을 위한 장부 관리(book-keeping)는 꽤 복잡하며, 제약이 해결되고 새로운 제약이 도입될 때마다 점진적으로 갱신되어야 합니다. 또 다른 복잡성은 다음에 시도할 바인딩을 고르려면 모든 타입 변수와 그들의 가능한 바인딩을 고려하고, 휴리스틱에 따라 순위를 매겨야 한다는 점입니다.
현재 이 순위 매김 과정은 실제로 모든 타입 변수와 모든 바인딩을 고려한 뒤, 결국 단 하나의 타입 변수와 단 하나의 바인딩만 선택합니다. 그리고 이 작업을 바인딩되지 않은 모든 타입 변수에 대해 반복합니다. 이는 제곱 시간(Quadratic time) 알고리즘을 낳습니다.
따라서 복잡한 오버로드가 많지 않은 제약 시스템에서도, 바인딩 때문에 알고리즘 복잡도가 관찰될 수 있습니다. 대부분의 표현식은 많은 타입 변수를 포함하지 않습니다. 흔한 것은 다수의 분리 선택지입니다. 하지만 많은 타입 변수가 생성되는 대표적 상황이 하나 있는데, 바로 요소 수가 많은 배열/딕셔너리 리터럴입니다.
우리는 가능한 바인딩을 추적하는 자료구조를 전면 개편할 계획입니다. 구현 내의 중복 장부(BindingSet과 PotentialBindings)를 제거하고, 다음 바인딩 선택 작업을 현재처럼 타입 변수 수에 선형이 아닌 상수 시간 또는 로그 시간에 수행할 수 있도록 하려 합니다. 이렇게 하면 큰 배열/딕셔너리 리터럴의 타입 검사가 급격히 빨라질 것입니다.
제약 해결 과정에서 새로운 바인딩이 생길 수 있으므로, 바인딩 집합이 “완전한지”를 판단하는 것이 중요합니다. 현재 이 판단은 매우 보수적이어서, 종종 분리 선택지 경로를 상당히 진행한 뒤에야 바인딩을 시도합니다. 바인딩 집합이 완전한 시점을 더 정확히 계산할 수 있다면 바인딩을 더 빨리 시도할 수 있고, 이는 많은 일반적인 표현식의 알고리즘 복잡도를 줄이는 데 도움이 됩니다.
바인딩 로직의 또 다른 개선은, 상충하는 바인딩을 고려해 더 빨리 모순에 도달할 수 있게 하는 것입니다. 현재는 타입 변수 T0가 예를 들어 Optional<Int>와 Optional<String>으로의 두 변환 제약을 동시에 받는 경우, T0의 가능한 모든 구체 타입을 시도할 때까지 모순에 도달하지 못합니다. 하지만 이 경우 Optional<Int>와 Optional<String> 모두로 변환되는 구체 타입은 존재하지 않으므로, 더 빨리 모순을 발견해 막다른 길 탐색을 피할 수 있어야 합니다.
이러한 바인딩 로직 개선은 앞서 말한 긴 컬렉션 리터럴을 포함해, 많은 표현식을 가속할 것입니다. 또한 +를 String과 Int에 적용하던 잘못된 예에서도, 마침내 실행 가능한 진단을 빠르게 생성할 수 있을 것입니다.
새 분리 선택 알고리즘이 많은 옛 성능 편법을 대체했지만, 여전히 일부 편법이 남아 있습니다. 이러한 편법은 일반적으로 적용 범위가 좁아, 표현식에 작은 변화만 생겨도 성능 절벽을 만들고, “하중을 지탱하는” 의미상의 효과까지 가지고 있어 언어 모델을 복잡하게 만듭니다. 이들은 시간이 지나면서 일반화하거나 기존 최적화에 흡수시킬 계획입니다.
이 중 일부는 극단적 에지 케이스에서 소스 호환성을 깨뜨릴 수 있지만, 작은 불편을 감수할 가치가 있다고 봅니다. 성능 개선뿐만 아니라 언어 의미를 더 쉽게 추론하게 만들고, 진단도 개선할 수 있습니다.
더 구체적으로, 제거하고자 하는 편법의 몇 가지 무작위 예는 다음과 같습니다:
Array와 Dictionary 타입의 서브스크립트는 아주 예전 Swift 1.0 시절의 좁은 최적화(inferCollectionSubscriptResultType())로 특별 취급됩니다. 어떤 경우에는 이상한 오버로드 해소 동작을 유발하며, 사용자 정의 타입의 서브스크립트에는 일반화되지 않습니다.simplifyAppliedOverloadsImpl()). 이는 제네릭 반환 타입을 전혀 다루지 못하고, 이상한 에지 케이스 동작이 있습니다.tryOptimizeGenericDisjunction()). 이는 세 번째 오버로드가 추가되면 명백한 성능 절벽이 됩니다. 비록 그 오버로드가 표현식에서 쓰이지 않더라도 말이죠.제약 해결 알고리즘의 한 단계는 제약 그래프를 구성합니다. 여기서 정점은 타입 변수이고, 간선은 같은 제약에 등장하는 타입 변수 쌍을 연결합니다. 중요한 최적화는 그래프에 연결 요소가 2개 이상인 상황을 감지하는 것입니다. 이 경우 각 구성 요소는 독립적으로 해결할 수 있습니다. 각 구성 요소에서 얻은 “부분 해”를 병합해 전체 제약 시스템의 해를 구성합니다.
많은 상황에서 이는 지수적 동작을 피할 수 있게 해 줍니다. 그러나 다른 상황에서는 부분 해가 매우 많이 생성되어, 이들을 나타내는 자료구조를 만들고 병합하는 알고리즘이 표현식 타입 검사 시간의 대부분을 차지하게 됩니다.
Swift 6.2에서 백트래킹 가속을 위해 도입한 “트레일(trail)” 자료구조를 기반으로, 이런 병적인 경우에 부분 해로 인한 오버헤드를 줄이려 합니다. 이러한 문제가 특히 자주 나타나는 표현식으로는, 큰 컬렉션 리터럴의 각 요소가 자체적으로 복잡한 표현식인 경우가 있습니다.
엄밀히 말해 성능 문제는 아니지만, 살베이지 모드가 어떤 수정도 기록하지 못해 failed to produce diagnostic 오류를 내는 경우를 더 줄이고자 합니다.
사실 오늘날 살베이지 모드에는 또 다른 이상한 상황이 있습니다. 일반 타입 검사가 실패했는데 살베이지 모드는 “성공”해 표현식을 받아들이는 알려진 사례들이 있습니다. 이는 성능 문제이기도 합니다. 왜냐하면 올바른 표현식임에도 해를 찾기 전에 사실상 두 번 타입 검사를 해야 하기 때문입니다.
이는 의도된 설계도 아니며, 언어의 잘 이해되지 않고 테스트도 부족한 구석과 맞닿아 있습니다. 이러한 상황을 바로잡으면 병적인 경우의 성능을 개선하는 동시에, 언어의 에지 케이스를 정비하고 테스트 커버리지를 개선할 수 있습니다. 궁극적으로 살베이지가 이런 식으로 성공하는 경우에는, 해결기가 조용히 진행하는 대신 또 다른 “폴백 진단”을 내도록 할 계획입니다.
마지막으로, 일반 타입 검사가 다수의 유효한 해를 낳아도, 오늘날 우리는 모호성 진단을 생성하기 전에 여전히 살베이지 모드에 들어갑니다. 이는 불필요하며, 이를 고치면 특정 잘못된 모호한 표현식의 진단 속도를 높일 수 있습니다. 또한 설계상 더 많은 일을 해야 하는 살베이지 모드가, 일반 타입 검사에서 이미 얻은 정보로 실행 가능한 진단을 낼 수 있었는데도, “unable to type-check” 오류로 실패할 확률을 줄여 줍니다.
이제 다소 미완성이나, 타입 검사 성능을 대폭 개선할 잠재력을 지닌 좀 더 탐색적인 아이디어로 글을 마무리하겠습니다.
지금까지는 (대부분) 소스 호환 가능한 변경만 다뤘고, 실제로도 여기에 주로 집중해 왔습니다. 그러나 오버로딩이나 양방향 추론을 완전히 제거하는 급진적 해법은 배제하되, 다가오는 기능이나 언어 모드와 함께 도입할 수 있는 보다 표적화된 언어 변경은 고려하고 있습니다.
== 연산자를 생각해 봅시다. 이 연산자는 오버로드가 매우 많지만, 그 대부분은 Equatable 프로토콜의 == 요구사항을 구현(witness)하는 것입니다. 원칙적으로는 이를 하나씩 시도하지 않고도, ==가 포함된 어떤 표현식에 대해서든 우리가 생성하는 제약 시스템을 단순화할 수 있습니다.
우리는 프로토콜 요구사항을 충족(witness)하는 오버로드를 오버로드 집합에서 가지치기(prune)해 숨기는 방식을 검토할 계획입니다. 이는 ==뿐 아니라 많은(하지만 전부는 아님) 연산자에 대해 오버로드 집합을 단순화할 것입니다.
이는 해 순위 매김 규칙을 변경해야 합니다. 현재는 항상 구체 오버로드를 선호하지만, 많은 경우 제네릭한 Equatable.== 오버로드를 선호해야 합니다. 이런 이유로, 병적인 케이스에서는 약간의 소스 파괴가 있을 수 있으나, 실제 프로그램에 지장을 주지 않도록 단계적으로 도입할 가능성도 있습니다.
흔한 오해는 정수나 문자열 같은 다형 리터럴이 스스로 오버로드를 도입한다는 것입니다. 즉, 각 ExpressibleBy* 프로토콜에 준수하는 모든 구체 타입이 리터럴에 분리 선택지를 추가한다는 오해입니다. 이는 정확하지 않습니다. 예를 들어 "hello world" 같은 리터럴은 주변 코드에서 구체 타입이 알려져 있으면 그 타입으로 타입 검사되고, 실패하면 기본 타입(이 경우 String)을 통해 타입 검사됩니다. 따라서 일종의 분리처럼 동작하긴 하지만, 이 경우 선택지는 두 개뿐이며, 기본값 자체가 전혀 시도되지 않는 경우도 흔합니다.
그러나 123 같은 정수 리터럴에는 실제로 기본 타입이 두 개(Int, Double)가 있어, 결과 분리는 세 개의 선택지를 갖습니다. 오늘날 정수와 부동소수점 리터럴이 섞인 표현식이 특히 까다로운 이유가 여기에 있습니다. 따라서 부동소수점 리터럴은 소수점을 반드시 표기하도록 하는 언어 변경을 고려할 가치가 있을지 모릅니다.
앞서 설명한 다양한 리팩터링과 정비가 더 진척되면, 오늘날 SAT 해결기에서 흔히 쓰이는 더 발전된 제약 해결 기법을 도입할 수 있을 것입니다. “SAT”(부울식 충족 가능성)는 연산자 오버로딩과 관련된 문제입니다. (오버로드 해소와 마찬가지로 최악의 경우 지수 시간이 걸리지만, 오버로드 해소와 달리 각 변수의 “도메인”은 참/거짓 값입니다. “제약” 대신 문제 인스턴스는 “그리고/또는/부정”으로 구성된 부울식으로 표현됩니다.) SAT 해결기 가속에 쓰이는 많은 기법이 제약 해결에도 적용 가능합니다.
**비연대기적 백트래킹(non-chronological backtracking)**을 지원하는 해결기는 모순을 감지하면 한 번에 하나 이상의 분리 선택지를 건너뛰어 되돌아갈 수 있습니다. 이는 상위의 어떤 제약이 이미 만족 불가능하므로 필연적으로 실패할 막다른 길의 추가 탐색을 피합니다.
또 다른 기술은 **절 학습(clause learning)**입니다. “순진한” 제약 해결 접근은 모순을 발견해 백트래킹할 때 모든 상태 변경을 버립니다. 절 학습을 가진 해결기에서는, 대략 말해, 알고리즘이 진행 중 사실을 “학습”하여 백트래킹의 결과로 새 제약을 기록합니다. 이렇게 하면 동일한 상황이 다시 발생할 때, “학습된” 제약 덕분에 모순을 더 빨리 감지할 수 있습니다.
(SAT 해결기에 대해 더 알고 싶다면, 최근 본 이 블로그 글이 좋은 요약을 제공합니다: SATisfying Solutions to Difficult Problems! - Vaibhav Sagar. 입문서로는 Schóning과 Torán의 “The Satisfiability Problem”이 무난합니다. 깊이 있는 정리는 Knuth Volume 4B에 실려 있습니다. 마지막으로, Beneš와 Brachthäuser의 최근 학술 논문 The simple essence of overloading은 문제를 이진 결정 다이어그램으로 환원하는 흥미로운 오버로딩 해법을 제시합니다. 여기의 일부 아이디어는 Swift 타입 검사에도 적용될 수 있습니다.)
Swift 타입 체커에는 개선할 수 있는 흥미로운 지점이 상당히 많으며, 이 영역의 진척에 따라 더 많은 업데이트를 공유할 수 있기를 기대합니다.