modify-coro.md

autoscale: true slidenumber: true

Swiftのmodifyアクセサとコルーチン

わいわいswiftc #17

@omochimetaru

---

Forum:

[Pitch] Modify Accessors ¹

---

---

動機

• get/setは遅い

---

struct GetSet {
    var storage: String = ""
    
    var property: String {
        get {
            return storage
        }
        set {
            storage = newValue
        }
    }
}

---

---

---

遅い理由

• a.property.appendという式は、下記の手順にコンパイルされる。

var temp = a.property
temp.append(text)
a.property = temp

• 雑に言えば、無駄なコピーが生じているので遅い。

---

• 正確には、コピー自体はCoWが効くのでコストはかからない。

• しかし、getして作ったテンポラリコピーのStringの本体は、a.storageからも参照されているためユニークな参照にならない。

• ユニークな参照ではないので、appendのタイミングで全文コピーが生じる。

• CoWは万能ではなく、コピーのペナルティが顕現する事がある。

---

SILで確認

func main() {
    var a = GetSet()
    a.property.append("str")
}

• $ swiftc -emit-sil c2.swift

---

  %12 = alloc_stack $String                       // users: %18, %15, %22, %17
  // function_ref GetSet.property.getter
  %13 = function_ref @$s2c26GetSetV8propertySSvg : 
    $@convention(method) (@guaranteed GetSet) -> @owned String // user: %14
  %14 = apply %13(%3) : $@convention(method) (@guaranteed GetSet) -> @owned String // user: %15
  store %14 to %12 : $*String                     // id: %15
  // function_ref String.append(_:)
  %16 = function_ref @$sSS6appendyySSF : 
    $@convention(method) (@guaranteed String, @inout String) -> () // user: %17
  %17 = apply %16(%10, %12) : $@convention(method) (@guaranteed String, @inout String) -> ()
  %18 = load %12 : $*String                       // user: %20
  // function_ref GetSet.property.setter
  %19 = function_ref @$s2c26GetSetV8propertySSvs : 
    $@convention(method) (@owned String, @inout GetSet) -> () // user: %20
  %20 = apply %19(%18, %11) : $@convention(method) (@owned String, @inout GetSet) -> ()

---

stored propertyの場合

func main() {
    var a = GetSet()
    a.storage.append("str")
}

  %12 = struct_element_addr %11 : $*GetSet, #GetSet.storage // user: %14
  // function_ref String.append(_:)
  %13 = function_ref @$sSS6appendyySSF : 
    $@convention(method) (@guaranteed String, @inout String) -> () // user: %14
  %14 = apply %13(%10, %12) : $@convention(method) (@guaranteed String, @inout String) -> ()

---

提案

• modifyアクセサ

struct GetModify {
    var storage: String = ""
    
    var property: String {
        get { return storage }
        modify {
            yield &storage
        }
    }
}

---

• modifyアクセサはsetと異なり、関数ではなく、コルーチン

• コルーチンの本文ではyield文が使える

---

コルーチン

---

2016 LLVM Developers’ Meeting: G. Nishanov “LLVM Coroutines” ²

• llvmのcoroの紹介

---

---

modifyコルーチン

• yieldではプロパティの型のinout参照を返す (関数のreturnではできない事)

• 参照を返す事でコピーを回避して高速化する

---

• テンポラリコピーでget/setする代わりに、modifyアクセサを実行、返ってきた参照をそのまま利用し、modifyアクセサを再開する。

// 動作イメージ
let coro = a.property
inout temp = coro.resume()
temp.append("str")
coro.resume()

---

yieldと前後処理

struct GetModify {
    var storage: String = ""
    
    var property: String {
        get { return storage }
        modify {
            print("before yield")
            yield &storage
            print("after yield")
        }
    }
}

var a = GetModify()

print("before append")
a.property.append("str")
print("after append")

/*
before append
before yield
after yield
after append
*/

---

• modifyコルーチンは取得した参照を使用している間は中断していて、使用が終わったら再開してから終了される

---

コルーチンとコンテキスト

struct GetModify {
    var num: Int?
    
    var property: String {
        get { return "" }
        modify {
            var str = num?.description ?? ""
            yield &str
            self.num = Int(str)
        }
    }
}

var a = GetModify()
a.property.append("1")
print(a.num ?? 0) // => 1
a.property.append("2")
print(a.num ?? 0) // => 12
a.property.append("a")
print(a.num ?? 0) // => 0

---

• コルーチンが中断していても、コルーチンが終了するまではコンテキスト(スコープ)が生きているので、ローカル変数への参照を返却できる

---

その他のコルーチン

---

Generator

• Pitchに載っている例

extension Array: MutableGenerator {
  func generateMutably() {
    for i in 0..<count { 
      yield &self[i]
    }
  }
}

for &x in myArray {
  x += 1
}

---

• OwnershipManifesto³に載っている例

mutating generator iterateMutable() -> inout Element {
  var i = startIndex, e = endIndex
  while i != e {
    yield &self[i]
    self.formIndex(after: &i)
  }
}

for inout employee in company.employees {
  employee.respected = true
}

---

Async/Await

• Asnyc/Awaitプロポーザルドラフト⁴がコルーチンの導入を提案している

---

---

---

func loadWebResource(_ path: String) async -> Resource
func decodeImage(_ r1: Resource, _ r2: Resource) async -> Image
func dewarpAndCleanupImage(_ i : Image) async -> Image

func processImageData1() async -> Image {
  let dataResource  = await loadWebResource("dataprofile.txt")
  let imageResource = await loadWebResource("imagedata.dat")
  let imageTmp      = await decodeImage(dataResource, imageResource)
  let imageResult   = await dewarpAndCleanupImage(imageTmp)
  return imageResult
}

---

---

modifyの中止(abort)

---

modifyの中止

• コルーチンの実行中に呼び出し側で例外が発生した場合、コルーチンが中止され、yieldより後続の処理に戻らない

func storeText(to str: inout String) throws { ... }

var a = GetModify()
try storeText(to: &a.property)

---

• yieldより前に書いたdeferは中止した場合でも実行される

---

extension Array {
  var first: Element? {
    get { isEmpty ? nil : self[0] }
    modify {
      var tmp: Optional<Element> = nil
      if isEmpty {
        tmp = nil
        yield &tmp
        if let newValue = tmp {
          self.append(newValue)
        }
      } else {
        // put array into temporarily invalid state
        tmp = _storage.move()

        // code to restore valid state put in defer
        defer {
          if let newValue = tmp {
            _storage.initialize(to: newValue)
          } else {
            _storage.moveInitialize(from: _storage + 1, count: self.count - 1)
            self.count -= 1
          }
        }
        
        // yield that moved value to the caller
        yield &tmp
    }
  }
}

---

modifyの実装

---

llvm.coro

• SILにもコルーチンが実装される

• LLVM-IRにおいて、コルーチンを実現する通常のコードにLowerする

• llvm.coro系命令

---

2つのLowering

• Switched-Resume Lowering: 最初にC++向けに作られた実装

• Returned-Continuation Lowering: Swift向けに作られた実装

---

Switched-Resume Lowering

---

Returned-Continuation Lowering

• 2018 LLVM Developers’ Meeting: J. McCall “Coroutine Representations and ABIs in LLVM”⁵

• yieldごとに関数を分けて、「次の関数」を返り値と一緒に返す

• コミット⁶

---

LLVM-IR 詳細

• Coroutines in LLVM⁷

---

modifyを試す

---

• modifyは_modifyキーワードで実装済み

• 標準ライブラリで既に使用している

---

• Array.swift⁸

extension Array: RandomAccessCollection, MutableCollection {
  @inlinable
  public subscript(index: Int) -> Element {
    get {
      // This call may be hoisted or eliminated by the optimizer.  If
      // there is an inout violation, this value may be stale so needs to be
      // checked again below.
      let wasNativeTypeChecked = _hoistableIsNativeTypeChecked()

      // Make sure the index is in range and wasNativeTypeChecked is
      // still valid.
      let token = _checkSubscript(
        index, wasNativeTypeChecked: wasNativeTypeChecked)

      return _getElement(
        index, wasNativeTypeChecked: wasNativeTypeChecked,
        matchingSubscriptCheck: token)
    }
    _modify {
      _makeMutableAndUnique() // makes the array native, too
      _checkSubscript_native(index)
      let address = _buffer.subscriptBaseAddress + index
      yield &address.pointee
    }
  }
}

---

SIL

struct GetModify {
    var storage: String = ""
    
    var property: String {
        get {
            return storage
        }
        _modify {
            yield &storage
        }
    }
}

func main() {
    var a = GetModify()
    a.property.append("str")
}

---

// GetModify.property.modify
sil hidden @$s2c59GetModifyV8propertySSvM : 
  $@yield_once @convention(method) (@inout GetModify) -> @yields @inout String {
// %0                                             // users: %2, %1
bb0(%0 : $*GetModify):
  debug_value_addr %0 : $*GetModify, var, name "self", argno 1 // id: %1
  %2 = begin_access [modify] [static] %0 : $*GetModify // users: %5, %8, %3
  %3 = struct_element_addr %2 : $*GetModify, #GetModify.storage // user: %4
  yield %3 : $*String, resume bb1, unwind bb2     // id: %4

bb1:                                              // Preds: bb0
  end_access %2 : $*GetModify                     // id: %5
  %6 = tuple ()                                   // user: %7
  return %6 : $()                                 // id: %7

bb2:                                              // Preds: bb0
  end_access %2 : $*GetModify                     // id: %8
  unwind                                          // id: %9
} // end sil function '$s2c59GetModifyV8propertySSvM'

---

  %12 = function_ref @$s2c59GetModifyV8propertySSvM : 
    $@yield_once @convention(method) (@inout GetModify) 
    -> @yields @inout String // user: %13
  (%13, %14) = begin_apply %12(%11) : 
    $@yield_once @convention(method) (@inout GetModify) -> @yields @inout String // users: %16, %17
  // function_ref String.append(_:)
  %15 = function_ref @$sSS6appendyySSF : 
    $@convention(method) (@guaranteed String, @inout String) -> () // user: %16
  %16 = apply %15(%10, %13) : $@convention(method) (@guaranteed String, @inout String) -> ()
  end_apply %14                                   // id: %17

---

中止の処理

func main() {
    var a = GetModify()
    try! storeText(to: &a.property)
}

---

  // function_ref GetModify.property.modify
  %6 = function_ref @$s2c59GetModifyV8propertySSvM : 
    $@yield_once @convention(method) (@inout GetModify) 
    -> @yields @inout String // user: %7
  (%7, %8) = begin_apply %6(%5) : 
    $@yield_once @convention(method) (@inout GetModify) -> @yields @inout String // users: %10, %12, %19
  // function_ref storeText(to:)
  %9 = function_ref @$s2c59storeText2toySSz_tKF : 
    $@convention(thin) (@inout String) -> @error Error // user: %10
  try_apply %9(%7) : $@convention(thin) (@inout String) -> @error Error, normal bb1, error bb2 // id: %10

bb1(%11 : $()):                                   // Preds: bb0
  end_apply %8                                    // id: %12
  ...

// %18                                            // user: %27
bb2(%18 : $Error):                                // Preds: bb0
  abort_apply %8                                  // id: %19

---

LLVM (コルーチン変換前)

• 謎のオプションを与えるとコルーチンをLowerしていないLLVMが出る

• $ swiftc -emit-ir -Xfrontend -disable-swift-specific-llvm-optzns c5.swift

• これをやるとLLVM-IRは出せるがバイナリは生成できない(必須変換)

---

; Function Attrs: noinline
define hidden swiftcc { i8*, %TSS* } 
  @"$s2c59GetModifyV8propertySSvM"(
    i8* noalias dereferenceable(32), 
    %T2c59GetModifyV* nocapture swiftself dereferenceable(16)) #1 {
entry:
  %2 = call token @llvm.coro.id.retcon.once(
    i32 32, i32 8, i8* %0, 
    i8* bitcast (void (i8*, i1)* @"$s2c59GetModifyVIetMl_TC" to i8*), 
    i8* bitcast (i8* (i64)* @malloc to i8*), 
    i8* bitcast (void (i8*)* @free to i8*))
  %3 = call i8* @llvm.coro.begin(token %2, i8* null)
  %.storage = getelementptr inbounds %T2c59GetModifyV, %T2c59GetModifyV* %1, i32 0, i32 0
  %4 = call i1 (...) @llvm.coro.suspend.retcon.i1(%TSS* %.storage)
  br i1 %4, label %6, label %5

; <label>:5:                                      ; preds = %entry
  br label %coro.end

; <label>:6:                                      ; preds = %entry
  br label %coro.end

coro.end:                                         ; preds = %5, %6
  %7 = call i1 @llvm.coro.end(i8* %3, i1 false)
  unreachable
}

---

• llvm.coro系命令が出てくる
• シグネチャではselfに加えて、謎の32バイトのメモリを引数に受けている
• coro.suspendの返り値としてi1を使い、resume/abortを区別している

---

  %2 = alloca [32 x i8], align 8
  ...
  %10 = getelementptr inbounds [32 x i8], [32 x i8]* %2, i32 0, i32 0
  call void @llvm.lifetime.start.p0i8(i64 32, i8* %10)
  %11 = call i8* @llvm.coro.prepare.retcon(
    i8* bitcast ({ i8*, %TSS* } (i8*, %T2c59GetModifyV*)* @"$s2c59GetModifyV8propertySSvM" to i8*))
  %12 = bitcast i8* %11 to { i8*, %TSS* } (i8*, %T2c59GetModifyV*)*
  %13 = call swiftcc { i8*, %TSS* } %12(
    i8* noalias dereferenceable(32) %10, 
    %T2c59GetModifyV* nocapture swiftself dereferenceable(16) %0)
  %14 = extractvalue { i8*, %TSS* } %13, 0
  %15 = extractvalue { i8*, %TSS* } %13, 1
  call swiftcc void @"$sSS6appendyySSF"(
    i64 %8, %swift.bridge* %9, %TSS* nocapture swiftself dereferenceable(16) %15)
  %16 = bitcast i8* %14 to void (i8*, i1)*
  call swiftcc void %16(i8* noalias dereferenceable(32) %10, i1 false)
  call void @llvm.lifetime.end.p0i8(i64 32, i8* %10)

---

• coro.prepare.retconが関数ポインタ(%11, %12)を返す
• それを呼び出すと、また関数ポインタ(%13, %14)を返す
• それを呼び出す(%14, %16)ときにresumeを意味するfalseを渡す

---

LLVM

• 普通にやるとコルーチンがLowerされたものが出る。

• $ swiftc -emit-ir c5.swift

---

%"$s2c59GetModifyV8propertySSvM.Frame" = type {}

; Function Attrs: noinline
define hidden swiftcc { i8*, %TSS* } @"$s2c59GetModifyV8propertySSvM"(
    i8* noalias dereferenceable(32), %T2c59GetModifyV* nocapture swiftself dereferenceable(16)) #1 {
entry:
  %.storage = getelementptr inbounds %T2c59GetModifyV, %T2c59GetModifyV* %1, i32 0, i32 0
  %2 = insertvalue { i8*, %TSS* } 
    { i8* bitcast (void (i8*, i1)* @"$s2c59GetModifyV8propertySSvM.resume.0" to i8*), %TSS* undef }, 
    %TSS* %.storage, 1
  ret { i8*, %TSS* } %2
}

define internal swiftcc void @"$s2c59GetModifyV8propertySSvM.resume.0"(
    i8* noalias nonnull dereferenceable(32), i1) #0 {
entryresume.0:
  %FramePtr = bitcast i8* %0 to %"$s2c59GetModifyV8propertySSvM.Frame"*
  %vFrame = bitcast %"$s2c59GetModifyV8propertySSvM.Frame"* %FramePtr to i8*
  ret void
}

---

• 関数resume.0が生成され、アクセサはこれとストレージポインタを返す
• resume.0の実装から、32バイトのメモリはフレームメモリへのポインタだとわかる
• resume.0の第2引数はresumeフラグ

---

  %2 = alloca [32 x i8], align 8
  ...
  %10 = getelementptr inbounds [32 x i8], [32 x i8]* %2, i32 0, i32 0
  call void @llvm.lifetime.start.p0i8(i64 32, i8* %10)
  %11 = call swiftcc { i8*, %TSS* } @"$s2c59GetModifyV8propertySSvM"(
    i8* noalias dereferenceable(32) %10, %T2c59GetModifyV* nocapture swiftself dereferenceable(16) %0)
  %12 = extractvalue { i8*, %TSS* } %11, 0
  %13 = extractvalue { i8*, %TSS* } %11, 1
  call swiftcc void @"$sSS6appendyySSF"(
    i64 %8, %swift.bridge* %9, %TSS* nocapture swiftself dereferenceable(16) %13)
  %14 = bitcast i8* %12 to void (i8*, i1)*
  call swiftcc void %14(i8* noalias dereferenceable(32) %10, i1 false)
  call void @llvm.lifetime.end.p0i8(i64 32, i8* %10)

---

• アクセサを呼ぶと関数ポインタとストレージポインタが返ってくる
• 関数ポインタにresumeフラグを渡して呼んで終わり

---

Footnotes

1. https://forums.swift.org/t/modify-accessors/31872 ↩

2. https://youtu.be/Ztr8QvMhqmQ ↩

3. OwnershipManifesto ↩

4. Async/Await for Swift ↩

5. https://youtu.be/wyAbV8AM9PM ↩

6. https://github.com/apple/swift-llvm/commit/eb7e7fd4f6c0d4c4c97879d9439d82f7eadde324 ↩

7. Coroutines in LLVM ↩

8. stdlib/public/core/Array.swift ↩

rendered: https://speakerdeck.com/omochi/swiftfalsemodifyakusesatokorutin

引用リストがgistだと表示壊れて消えちゃうな。