[SE-0527] RigidArray & UniqueArray

안녕하세요. 그린입니다 🍏
이번 포스팅에서는 SE-0527 — RigidArray와 UniqueArray에 대해 정리해보겠습니다 🙋🏻

Intro

Proposal: SE-0527

Authors: Karoy Lorentey, Alejandro Alonso

Review Manager: Steve Canon

Status: Implemented (Swift 6.4)

Implementation: swiftlang/swift#87521

Motivation

Swift 5.9에서 noncopyable struct/enum이 들어온 이후로 이를 지원하는 API가 하나둘 추가되어 왔습니다 🙌

표준 라이브러리도 Atomic, Mutex, inline 저장소에 noncopyable 값을 담을 수 있는 InlineArray 같은 타입을 직접 구현했죠.

 

하지만 noncopyable 원소를 지원하는 크기 조절 가능한(resizable) 자료구조는 아직 없었습니다.

 

Swift 개발자라면 동적으로 크기가 변하는 값 목록이 필요할 때 Array를 찾게 마련인데, 안타깝게도 클래식 Array는 noncopyable 값을 지원하지 않아요.

 

noncopyable 원소 지원을 Array에 억지로 끼워 넣는 방법은 두 가지가 있을 수 있어요.

 

1️⃣ Array를 copyable로 유지하면서, mutation 연산이 원소를 복사하는 대신 다른 방식으로 uniqueness를 보장하게 만드는 방법.
예를 들어 mutation이 런타임 에러를 일으키게 하거나, 원소를 어떻게 clone할지 설명하는 새 인자를 추가하는 방식이 있는데, 둘 다 실제로는 받아들이기 힘든 프로그래밍 경험으로 이어집니다.

 

2️⃣ Array를 원소의 copyability에 따라 조건부로 copyable하게 만드는 방법.
이러려면 mutation 연산이 Element가 copyable인 경우에만 copy-on-write 경로로 분기하는 런타임 조건을 추가로 가져야 해요. 여기엔 두 가지 기술적 문제가 있습니다.

Swift 코드는 현재 런타임에 타입 인자가 copyable인지 확인할 방법이 없고, 이런 "conformance" 체크는 모든 배열 mutation에 잠재적 오버헤드를 더하게 됩니다.

 

첫 번째 문제는 해결 가능하지만, 두 번째는 굉장히 가져가기 어려운 문제예요.

 

특히 noncopyable 원소를 허용하는 제네릭 컨텍스트에 큰 영향을 주는데, 그런 컨텍스트에서는 copyability 체크가 런타임 조건이어야만 하거든요.

noncopyable 원소를 허용하는 컨텍스트에서 호출됐다는 이유만으로 append가 storage가 unique하다고 가정할 순 없으니까요.

 

이미 복잡한 Array의 성능 분석을 더 어렵게 만드는 건 noncopyable 타입 도입의 배경이 된 Swift Ownership Manifesto의 목표에 정면으로 반하는 일이에요.

 

목표는 단순히 noncopyable 값을 담는 배열이 아니라, 예측 가능하고 분석하기 쉬운 좋은 성능으로 그걸 해내는 겁니다.

 

이 외에도 Array에는 예측 불가능한 복잡도 급증을 만드는 두 가지 주요 원인이 있어요.

 

1️⃣ copy-on-write 값 시맨틱스 — 공유된 복사본을 실수로 mutate하기 쉽습니다.

그럴 때마다 배열 전체를 새로 할당해야 해서, 평소엔 상수 복잡도인 단순 subscript 재할당 같은 연산도 선형 복잡도 괴물이 될 수 있어요.

 

2️⃣ 동적 자료구조 — 필요할 때마다 암묵적으로 크기를 재조정합니다. 적

절한 크기의 새 버퍼를 할당하고 기존 원소를 복사하거나 옮기는 방식이라, 대부분은 상수 시간/공간에 실행되지만 어쩌다 한 번씩 resize가 트리거되면서 갑자기 선형이 돼요.

기하급수적 성장 패턴 덕분에 append는 평균적으로 amortized O(1)이지만, 실제 최악의 경우 복잡도는 O(count)입니다.

 

이 두 특징 자체가 나쁜 건 아니에요.

오히려 Swift의 프로그래밍 모델을 크게 단순화해주는 바람직한 이점이죠.

하지만 신뢰할 수 있는 고성능이 필요한 컨텍스트에서는 이 특징들이 코드가 런타임에 어떻게 동작할지 분석하고 보장하기 어렵게 만드는 걸림돌이 됩니다.

 

Array에 기능을 계속 덧붙이는 건 답이 아니에요.

필요한 건 Array보다 더 예측 가능한 성능이 필요한 용례에 특화된 추가 배열 구현체입니다

 

그럼 새 배열 타입이 몇 개나 필요할까요?

 

위 두 특징은 기술적으로 서로 독립적이라 개별적으로 켜고 끌 수 있어요.

그러면 이론상 네 가지 조합이 나오는데, 그중 하나는 이미 존재하는 Array입니다.

	Noncopyable	Copy-on-write
Fixed capacity	???	???
Dynamic	???	Array

 

fixed-capacity 자료구조를 쓰는 주된 이유는 암묵적 할당을 피하기 위해서인데, copy-on-write는 그것과 정면으로 충돌해요.

그래서 오른쪽 위 칸은 비워둘 수 있습니다.

	Noncopyable	Copy-on-write
Fixed capacity	???	---
Dynamic	???	Array

Proposed Solution

표준 라이브러리에 RigidArray와 UniqueArray라는 두 새 배열 타입을 추가할 것을 제안합니다.

 

둘 다 진짜 배열 타입으로, append, insert, replace, remove, 임의 재정렬, 정수 오프셋을 통한 빠른 접근 등 익숙한 배열 연산을 제공해요.

둘 다 하나의 힙 할당된 연속 메모리 영역을 저장소로 쓰고, 부분적으로만 초기화될 수 있으며, 초기화된 항목들은 앞쪽에 모여 있어요.

요컨대 기존 Array, ContiguousArray와 마찬가지로 고전적인 가변 크기 배열 자료구조를 구현합니다.

 

이 타입들은 Swift 툴체인의 새 모듈 Containers에 포함돼요. s

wift-collections의 Collections처럼, 이 모듈은 앞으로 ring buffer 같은 자료구조들의 집합이 될 예정입니다 ☺️

 

---

UniqueArray

UniqueArray는 copy-on-write 컨테이너를 피하고 싶지만 메모리를 엄격하게 관리할 필요는 없는, 일반적인 고성능 컨텍스트에 좋은 선택이에요.

 

C++의 std::vector나 Rust의 Vec처럼 단순하고 동적으로 크기가 조정되는 배열 타입입니다.

UniqueArray는 저장소가 항상 유일하게(uniquely) 소유되는 Array variant예요.

UniqueArray를 noncopyable 타입으로 선언해서 정적으로 강제하는데, 그래서 UniqueArray 자신은 한 번에 하나의 변수(저장 프로퍼티, 지역 변수, 함수 인자 등)만 가질 수 있고 그 변수를 통해서만 mutate할 수 있어요.

다른 변수로 옮길 수는 있지만, 이건 원본을 consume해서 사용 불가능/미초기화 상태로 만듭니다.

 

import Containers

struct FileHandle: ~Copyable {
  let fd: UInt32

  init(reading path: String) throws { fd = try open(path, .read) }

  deinit {
    try! close(fd)
  }
}

let foo = try FileHandle(reading: "foo.txt")
let bar = try FileHandle(reading: "bar.md")

var a = UniqueArray()
a.append(foo) // OK, consumes \`foo\`
a.append(bar) // OK, consumes \`bar\`

var b = a // OK, consumes \`a\`, moving the array instance into \`b\`

b.append(try FileHandle(reading: "baz.swift")) // OK
// \`b\`는 이제 foo.txt, bar.md, baz.swift에 대한 열린 핸들을 담고 있음

a.append(try FileHandle(reading: "Info.plist")) // error: \`a\` used after consume (used here)

 

noncopyable 자신인 덕분에 UniqueArray는 위 예시의 파일 핸들처럼 noncopyable 원소도 자연스럽게 담을 수 있어요.

 

원소를 다루는 배열 연산들은 소유권을 신중하게 고려해서 설계되었고, consuming이나 borrowing 키워드로 원소 소유권과 어떻게 상호작용하는지 표시되어 있습니다.

제대로 된 동적 크기 조정 컨테이너답게, UniqueArray도 기하급수적 성장 곡선에 의존해서 (amortized) 성능을 확보해요.

resize가 필요할 때 이전 capacity에 상수 배율을 곱하는 방식이지, 단순히 그 연산에 필요한 만큼만 선형으로 키우지 않습니다.

이 키워지는 비율은 내부 구현 세부사항이라 환경/플랫폼/Swift 릴리스에 따라 바뀔 수 있고, 사용자가 설정할 수 없습니다.

 

---

RigidArray

핵심 시스템 프로그래밍, 메모리 제약이 있는 임베디드 플랫폼, 실시간 컨텍스트 같은 가장 low-level인 용례에는 UniqueArray만으로는 충분하지 않아요.

고정 capacity를 갖는 noncopyable 배열 타입이 필요합니다.

 

가용 메모리가 킬로바이트 단위인 환경을 위한 Swift 코드를 작성한다고 생각해보면, 모든 할당이 소스에 명시적으로 드러나서 정확히 계산하고 예산을 세울 수 있어야 해요.

이런 컨텍스트에서는 알아서 resize하거나 복사하는 컨테이너 타입이 들어설 자리가 없죠.

 

RigidArray는 이런 용례를 위한 타입이고, 이름 그대로 유연하지 않고 rigid(경직된)한 성격을 반영합니다.

 

RigidArray 인스턴스는 항상 특정 capacity로 할당되고, 그 안에서만 동작해야 해요.

 

그래서 더 이상 새 항목을 담을 수 없는 "가득 찬" 상태가 될 수 있고, 가득 찬 RigidArray에 값을 추가하려 하면 런타임 트랩이 발생합니다.

 

var c = RigidArray(capacity: 2)
print(c.isFull)       // => false
print(c.freeCapacity) // => 2

c.append(23)
print(c.isFull)       // => false
print(c.freeCapacity) // => 1

c.append(42)
print(c.isFull)       // => true
print(c.freeCapacity) // => 0

c.append(7) // runtime error: RigidArray capacity overflow

 

이걸 복구 가능한 에러가 아니라 precondition 위반으로 다루면, RigidArray가 UniqueArray와 같은 기본 연산을 제공하면서도 향후 이 둘을 ownership-aware RangeReplaceableCollection 같은 추상화 아래로 통합할 길을 열어둘 수 있어요.

 

또한 연산들이 어떤 식으로든 실패를 복구 가능하게 보고하도록 억지로 복잡하게 만들 필요도 없어지고요.

 

실제로 RigidArray 저장소를 오버플로우시키는 건 프로그래머의 실수처럼 느껴져요.

타입을 잘못 사용했다는 신호지, 일상적인 문제가 아닙니다.

빈 Array에서 마지막 항목을 지우려 하면 트랩이 나는 것처럼, 가득 찬 RigidArray에 항목을 추가하려는 것도 자연스럽게 트랩으로 이어집니다.

RigidArray는 스스로 resize하지 않지만, capacity가 타입의 일부는 아니에요.

 

rigid array 인스턴스는 사실 reallocate 연산을 명시적으로 호출해서 임의로 저장소를 키우거나 줄일 수 있습니다.

 

var d = RigidArray(capacity: 2)
d.append(10)
d.append(20)
print(d.isFull)       // => true
print(d.freeCapacity) // => 0

d.reallocate(capacity: 10)
print(d.isFull)       // => false
print(d.freeCapacity) // => 8

d.append(30) // OK!

 

배열은 요청한 만큼 정확히 저장소를 할당해요 (더 많지도 적지도 않게).

이 연산 덕분에 RigidArray로 임의의 커스텀 resize 로직을 갖는 wrapper 배열 타입도 만들 수 있어요.

사실 UniqueArray 자체가 그렇게 구현되어 있습니다.

 

Detailed Design

타입 선언

@frozen
public struct RigidArray: ~Copyable {}

extension RigidArray: Sendable where Element: Sendable & ~Copyable {}

@frozen
public struct UniqueArray: ~Copyable {}

extension UniqueArray: Sendable where Element: Sendable & ~Copyable {}

 

둘 다 갖는 API — 기본

capacity, freeCapacity, span/mutableSpan, isTriviallyIdentical(to:), 그리고 OutputSpan을 통해 저장소를 직접 편집하는 edit(_:), capacity를 조정하는 reallocate(capacity:)와 reserveCapacity(_:)가 공통으로 제공됩니다.

 

copyable 원소에 대해서는 clone() / clone(capacity:)로 깊은 복사도 가능해요.

 

extension [Rigid|Unique]Array where Element: ~Copyable {
  public var capacity: Int { get }
  public var freeCapacity: Int { get }
  public var span: Span { get }
  public var mutableSpan: MutableSpan { mutating get }
  public func isTriviallyIdentical(to: borrowing Self) -> Bool

  public mutating func edit(
    _ body: (inout OutputSpan) throws(E) -> R
  ) throws(E) -> R

  public mutating func reallocate(capacity newCapacity: Int)
  public mutating func reserveCapacity(_ n: Int)
}

extension [Rigid|Unique]Array where Element: Copyable {
  public func clone() -> Self
  public func clone(capacity: Int) -> Self
}

 

둘 다 갖는 API — 이니셜라이저

extension [Rigid|Unique]Array where Element: ~Copyable {
  public init()
  public init(capacity: Int)

  public init(
    capacity: Int,
    initializingWith initializer: (inout OutputSpan) throws(E) -> Void
  ) throws(E)
}

extension [Rigid|Unique]Array where Element: Copyable {
  public init(repeating repeatedValue: Element, count: Int)

  public init(
    capacity: Int? = nil,
    copying span: Span
  )
}

 

둘 다 갖는 API — 컬렉션 기반

배열의 위치를 나타내는 Index는 정수 오프셋(typealias Index = Int)이고, isEmpty, count, startIndex, endIndex, indices, subscript, swapAt, index(after:)/index(before:), formIndex 계열, distance(from:to:) 등 기존 Collection API와 결을 맞춘 연산들이 제공됩니다.

 

성능을 위해 대부분의 인덱스 관련 연산은 인덱스 유효성을 미리 검증하지 않고, 실제로 접근할 때 검증을 미룹니다.

 

extension [Rigid|Unique]Array where Element: ~Copyable {
  public typealias Index = Int

  public var isEmpty: Bool { get }
  public var count: Int { get }
  public var startIndex: Int { get }
  public var endIndex: Int { get }
  public var indices: Range { get }

  public subscript(position: Int) -> Element {
    borrow
    mutate
  }

  public mutating func swapAt(_ i: Int, _ j: Int)

  public func index(after index: Int) -> Int
  public func index(before index: Int) -> Int
  public func formIndex(after index: inout Int)
  public func formIndex(before index: inout Int)
  public func index(_ index: Int, offsetBy n: Int) -> Int
  public func distance(from start: Index, to end: Index) -> Int

  public func formIndex(
    _ index: inout Index,
    offsetBy n: inout Int,
    limitedBy limit: Index
  )
}

 

둘 다 갖는 API — Append

단일 원소 append(_:) 외에, OutputSpan을 직접 채우는 append(addingCount:initializingWith:), 버퍼나 OutputSpan을 이동시키는 append(moving:), copyable 원소를 위한 버퍼/span/시퀀스 복사 append(copying:) 계열이 있습니다.

capacity가 부족하면 RigidArray는 런타임 에러, UniqueArray는 기하급수적으로 storage를 늘려요.

extension [Rigid|Unique]Array where Element: ~Copyable {
  public mutating func append(_ item: consuming Element)

  public mutating func append(
    addingCount newItemCount: Int,
    initializingWith initializer: (inout OutputSpan) throws(E) -> Void
  ) throws(E)

  public mutating func append(
    moving items: UnsafeMutableBufferPointer
  )

  public mutating func append(
    moving items: inout OutputSpan
  )
}

extension [Rigid|Unique]Array where Element: Copyable {
  public mutating func append(
    copying newElements: UnsafeBufferPointer
  )
  public mutating func append(
    copying newElements: UnsafeMutableBufferPointer
  )
  public mutating func append(copying newElements: Span)
  public mutating func append(copying newElements: some Sequence)
}

 

둘 다 갖는 API — Insert

지정한 위치에 원소를 끼워 넣는 insert(_:at:)부터, OutputSpan을 채우는 버전, 버퍼/span을 이동/복사하는 버전까지 append와 짝을 이루는 형태로 제공됩니다.

지정 위치 이후 원소들은 뒤로 밀려서 공간을 만듭니다.

extension [Rigid|Unique]Array where Element: ~Copyable {
  public mutating func insert(_ item: consuming Element, at index: Int)

  public mutating func insert(
    addingCount newItemCount: Int,
    at index: Int,
    initializingWith initializer: (inout OutputSpan) throws(E) -> Void
  ) throws(E)

  public mutating func insert(
    moving items: UnsafeMutableBufferPointer,
    at index: Int
  )

  public mutating func insert(
    moving items: inout OutputSpan,
    at index: Int
  )
}

extension [Rigid|Unique]Array where Element: Copyable {
  public mutating func insert(
    copying newElements: UnsafeBufferPointer, at index: Int
  )
  public mutating func insert(
    copying newElements: UnsafeMutableBufferPointer,
    at index: Int
  )
  public mutating func insert(
    copying newElements: Span, at index: Int
  )
  public mutating func insert(
    copying newElements: some Collection, at index: Int
  )
}

 

둘 다 갖는 API — Remove

extension [Rigid|Unique]Array where Element: ~Copyable {
  public mutating func popLast() -> Element?
  public mutating func removeLast() -> Element
  public mutating func removeLast(_ k: Int)
  public mutating func remove(at index: Int) -> Element
  public mutating func removeSubrange(_ bounds: Range)
  public mutating func removeSubrange(_ bounds: some RangeExpression)
}

 

둘 다 갖는 API — Replace

지정한 범위를 새 항목으로 교체하는 replaceSubrange 계열이에요.

remove 후 insert하는 것과 같은 효과지만, 원소를 두 번 옮기지 않아서 상수 배 더 빠릅니다.

extension [Rigid|Unique]Array where Element: ~Copyable {
  public mutating func replaceSubrange(
    _ subrange: Range,
    addingCount newItemCount: Int,
    initializingWith initializer: (inout OutputSpan) throws(E) -> Void
  ) throws(E) -> Void

  public mutating func replaceSubrange(
    _ subrange: Range,
    moving newElements: UnsafeMutableBufferPointer
  )

  public mutating func replaceSubrange(
    _ subrange: Range,
    moving items: inout OutputSpan
  )
}

extension [Rigid|Unique]Array where Element: Copyable {
  public mutating func replaceSubrange(
    _ subrange: Range,
    copying newElements: UnsafeBufferPointer
  )
  public mutating func replaceSubrange(
    _ subrange: Range,
    copying newElements: UnsafeMutableBufferPointer
  )
  public mutating func replaceSubrange(
    _ subrange: Range,
    copying newElements: Span
  )
  public mutating func replaceSubrange(
    _ subrange: Range,
    copying newElements: consuming some Collection
  )
}

 

둘 다 갖는 API — Conformance

두 타입 모두 Equatable, Hashable, CustomStringConvertible, CustomDebugStringConvertible을 채택하고, SE-0516에서 제안된 BorrowingSequence도 채택해서 그 프로포절의 SpanIterator를 iterator로 씁니다.

extension [Rigid|Unique]Array: Equatable where Element: Equatable & ~Copyable {
  public static func ==(left: borrowing Self, right: borrowing Self) -> Bool
}

extension [Rigid|Unique]Array: Hashable where Element: Hashable & ~Copyable {
  public func hash(into hasher: inout Hasher)
}

extension [Rigid|Unique]Array: CustomStringConvertible where Element: ~Copyable {
  public var description: String { get }
}

extension [Rigid|Unique]Array: CustomDebugStringConvertible where Element: ~Copyable {
  public var debugDescription: String { get }
}

extension [Rigid|Unique]Array: BorrowingSequence where Element: ~Copyable {
  @lifetime(borrow self)
  public func makeBorrowingIterator() -> SpanIterator
}

CustomStringConvertible과 CustomDebugStringConvertible 채택은 SE-0499가 구현된 뒤에야 정식으로 배포될 수 있어요.

그 전까지는 (지금으로선 다소 소박한) description/debugDescription 구현을 우선 제공합니다.

 

RigidArray 전용 API

isFull 프로퍼티, 시퀀스/컬렉션을 복사해서 초기화하는 이니셜라이저, capacity가 부족하면 항목을 그대로 돌려주는 pushLast(_:), 저장 capacity는 유지한 채 모든 원소를 지우는 removeAll()이 있어요.

extension RigidArray where Element: ~Copyable {
  public var isFull: Bool { get }

  public init(
    capacity: Int,
    copying contents: some Sequence
  )

  public init(
    capacity: Int? = nil,
    copying contents: some Collection
  )

  public mutating func pushLast(_ item: consuming Element) -> Element?

  public mutating func removeAll()
}

 

UniqueArray 전용 API

초기 capacity를 지정하는 이니셜라이저와, capacity를 유지할지 선택할 수 있는 removeAll(keepingCapacity:)가 있습니다.

extension UniqueArray where Element: ~Copyable {
  public init(
    capacity: Int? = nil,
    copying contents: some Sequence
  )

  public init(minimumCapacity: Int)

  public mutating func removeAll(keepingCapacity keepCapacity: Bool = false)
}

 

---

Source Compatibility

RigidArray와 UniqueArray는 표준 라이브러리의 새 타입이라 추가는 소스 호환적인 변경이에요.

swift-collections에서 이 타입들을 import하고 있거나 같은 이름으로 커스텀 타입을 정의한 개발자라도, 표준 라이브러리 타입 이름에 대한 shadowing 규칙 덕분에 기존 import/커스텀 타입은 그대로 동작합니다.

 

---

ABI Compatibility

이 제안은 표준 라이브러리 ABI에 순수하게 추가만 하는 변경이라 기존 바이너리를 깨지 않아요.

두 타입은 frozen으로 제안되는데, 이는 향후 표현 방식 변경을 막습니다 (capacity 축소를 구현하려고 예약된 capacity를 추적하고 싶을 수 있는 UniqueArray에 특히 관련이 있어요).

 

---

Implications on Adoption

RigidArray와 UniqueArray는 표준 라이브러리의 새 타입이므로, 적어도 이 타입들이 도입된 버전의 Swift를 써야 해요.

swift-collections에서 이 타입들을 쓰던 개발자라면, 패키지 소스의 하위 배포 특성 때문에 계속 그 버전을 쓰는 게 더 나을 수도 있습니다.

---

Future Directions

Clonable

이 제안은 UniqueBox 제안처럼 RigidArray와 UniqueArray 모두에 clone()/clone(capacity:)를 도입해요.

다만 지금은 Element: Copyable을 요구해서 UniqueArray<UniqueArray<Int>> 같은 중첩 2차원 배열은 불가능한데, UniqueBox 제안에서 언급했듯 이런 기능을 가능하게 할 Clonable 프로토콜의 여지가 있어요.

public protocol Cloneable: ~Copyable {
  func clone() -> Self
}

 

다른 표준 자료구조의 Rigid/Unique variant

이 제안이 도입하는 Rigid/Unique 접두어는 비슷한 동작을 하는 컨테이너 타입들의 일반적인 네이밍 패턴으로 자리잡길 의도한 것이에요.

swift-collections 패키지는 이미 같은 시맨틱스의 ring buffer인 RigidDeque, UniqueDeque를 정의하고 있고, ownership-aware한 Set/Dictionary 프로토타입도 같은 접두어로 제공합니다. RigidDeque, UniqueDeque, RigidSet, UniqueSet, RigidDictionary, UniqueDictionary 모두 표준 라이브러리에 추가될 잠재적 후보들이에요.

 

Container 프로토콜

이 제안이 두 배열 타입에 BorrowingSequence 채택을 더하긴 하지만, 그 위에 컨테이너 프로토콜을 제안할 준비는 아직 안 됐어요.

swift-collections에서 이런 추상화를 위한 설계 접근을 탐색 중입니다.

 

리터럴 초기화

제안된 배열 타입들은 원소가 copyable이든 아니든 ExpressibleByArrayLiteral을 채택하지 않아요.

기존 프로토콜은 variadic 이니셜라이저를 통한 Array 인스턴스 구성 위에 만들어져 있어서 일반화하기 쉽지 않고, RigidArray/UniqueArray 초기화가 임시 Array 인스턴스를 거치도록 강제하면 이 타입들의 성능 목표를 만족시킬 수 없어요.

대신 target 타입 저장 버퍼 위의 OutputSpan 인스턴스를 채우는 방식으로 배열 리터럴 초기화를 재구성하는 방법을 하나 생각해볼 수 있어요.

protocol ArrayLiterable: ~Copyable {
  associatedtype ArrayLiteralElement: ~Copyable

  init(
    arrayLiteralCount count: Int, 
    initializingWith initializer: (inout OutputSpan) throws(E) -> Void
  ) throws(E)
}

 

이 방식이라면 타입 컨텍스트 T에서 [a, b, c, d] 같은 배열 초기화 표현이 대략 이렇게 확장될 거예요.

T(arrayLiteralCount: 4) { target in
  target.append(a)
  target.append(b)
  target.append(c)
  target.append(d)
}

(T가 연속된 저장소를 갖는다고 가정한 것이고, 불연속적인 target 저장소를 초기화하도록 허용하는 건 항목을 반환하는 함수들의 inline array를 다루는 등 조금 더 까다로워요.)

이 방향이든 다른 방향이든, 후속 작업의 주제가 될 것으로 예상합니다.

 

Alternatives Considered

Allocator 인자와 비슷한 설정 값들

새 배열 타입을 제안하는 김에, 커스텀 allocator로 이 자료구조들을 할당할 수 있게 하는 방법도 고려했어요.

public struct UniqueArray: ~Copyable {}

allocator 제네릭 인자를 추가하는 건 C++이나 Rust의 컨테이너 타입과 비슷한 방식이에요. 이러려면 커스텀 allocator가 채택할 Allocator 프로토콜과, 표준 라이브러리 기본으로 제공되는 SystemAllocator 같은 것이 필요합니다.

 

protocol Allocator {
  func allocate(_: T.Type) -> UnsafeMutablePointer
  func deallocate(_: UnsafeMutablePointer)
  ...
}

 

하지만 이런 타입 인자는 함수 시그니처를 훨씬 번거롭게 만들어요.

func foo(_ x: borrowing UniqueArray)
// error: generic type 'UniqueArray' specialized with too few type parameters (got 1, but expected 2)

C++과 Rust는 제네릭 타입 매개변수에 기본값을 허용해서 이 문제를 풀지만, Swift에는 아직 그런 언어 기능이 없어요.

설령 있다 해도 foo(_:)가 시스템 allocator를 쓰도록 과도하게 제약해버리는 더 나쁜 문제가 생겨요.

unique array를 그냥 borrow하는 함수는 어떤 allocator를 쓰는지 신경 쓸 이유가 없거든요 (어차피 mutate할 방법도 없으니까요). 결국 foo도 제네릭이 되어야 합니다.

 

func foo(_ x: borrowing UniqueArray<Int, some Allocator>)

배열을 consume하거나 mutate하려는 함수라면 이 allocator 인자를 이름 붙여서 코드베이스 전체에 전파해야 하는 경우가 잦아, 인터페이스 정의를 오염시키고 코드를 흐릴 수 있어요.

이런 타입 인자 오염은 C++ 개발자들의 흔한 불만이기도 하죠. 게

다가 Allocator 추상화는 구현체가 copyable이어야 하는지, allocate/deallocate가 mutating으로 표시돼서 동시 사용과 호환이 안 되는 건 아닌지, 애초에 Swift 개발자들이 allocator를 어떻게 구현해야 하는지 같은 질문도 남겨요.

무엇보다 allocator는 unsafe 포인터를 다루기 때문에 Swift 메모리 안전성 스토리에 눈에 띄는 구멍이 될 수 있습니다.

 

RigidArray/UniqueArray가 Array와 저장 표현을 공유하게 하기

UniqueArray는 사실 RigidArray 인스턴스를 감싼 얇은 wrapper 타입이라 서로 𝛩(1) 복잡도로 변환 가능해요.

 

클래식 Array도 이 상호 변환 가능한 패밀리에 들어오면 좋겠지만, Array의 저장 표현은 ABI의 일부라 변경할 수 없어요.

RigidArray/UniqueArray가 tail-allocated 저장소를 갖는 특정 제네릭 클래스를 중심으로 지어진 그 표현을 그대로 빌려오는 건 부적절할 거예요.

같은 표현을 쓰면 새 low-level 타입에 불필요한 성능 오버헤드가 생겨서 경쟁 시스템 프로그래밍 언어의 비슷한 타입들과 경쟁력이 떨어질 수 있습니다.

그래서 Array와 새 타입 사이의 변환은 새로 할당한 저장소로 원소를 복사/이동하는 선형 시간 연산이 필요하고, 실제로는 큰 문제가 되지 않을 것으로 봅니다.

 

Array를 noncopyable 원소를 지원하도록 일반화하기

copy-on-write 값 시맨틱스가 Array와 다른 표준 Collection 타입들, 그리고 Swift 자체의 핵심 특징이라고 생각해요.

Array를 조건부로 noncopyable하게 만들거나 copy-on-write 동작을 조건화하는 건 Swift Ownership Manifesto의 목표에 오히려 반하고, 실제로도 실용적이지 않다고 봅니다.

 

그리고 그런 작업을 하더라도 이 문서가 제안하는 전용 fixed-capacity/guaranteed-noncopyable 배열 variant의 필요성이 사라지진 않아요.

Element가 copyable이라는 이유만으로 개발자에게 동적으로 크기가 조정되는 copy-on-write Array를 강제하는 건 적절하지 않으니까요. Array가 언젠가 noncopyable 콘텐츠를 지원하게 되든 안 되든, 정수용 RigidArray나 float용 UniqueArray에 대한 실질적이고 시급한 수요가 있습니다. 다만 이 제안이 그런 미래 작업을 막는 건 전혀 아니에요.

 

이 타입들을 기본 Swift 모듈로 옮기기

이 타입들이 Swift 개발자의 기본 네임스페이스에 들어가야 한다고는 생각하지 않아요.

 

Array는 여전히 모두의 첫 번째 선택이어야 하니까요.

이 배열 타입들의 추가가 Array를 대체하는 게 아니라, 더 제약된 환경에서 작업할 때 쓸 수 있는 대안적인 도구일 뿐입니다.

 

---

Conclusion

SE-0527은 표준 라이브러리에 RigidArray와 UniqueArray라는 두 개의 noncopyable 지원 배열 타입을 가져다줘요.

copy-on-write와 암묵적 resize라는 Array의 두 특징을 각각 유연하게 켜고 끌 수 있게 설계된 셈인데, RigidArray는 고정 capacity로 예측 가능한 성능을, UniqueArray는 기하급수적 성장 곡선으로 편리한 동적 크기 조정을 제공합니다.

둘 다 noncopyable 원소를 자연스럽게 담을 수 있어서, 그동안 Array로는 손댈 수 없었던 고성능·저수준 영역에서 Swift가 훨씬 쓸모 있어질 것 같습니다 🙌

 

---

References

swift-evolution/proposals/0527-rigidarray-uniquearray.md at main · swiftlang/swift-evolution