Nimのメモリ管理を理解する⑤ ― ムーブセマンティクスとデストラクタ

この記事はNimのメモリ管理を理解するシリーズの5作目になります。今回は公式ドキュメントのNim Destructors and Move Semanticsを翻訳して、Nimのメモリ管理について更に理解を進めていこうと思います。

---

〜Nimのメモリ管理を理解するシリーズ〜

• Nimのメモリ管理を理解する① ― Nimの新しいGC、ARCについて
• Nimのメモリ管理を理解する② ― Nimのムーブセマンティクス
• Nimのメモリ管理を理解する③ ― GCなしのNim
• Nimのメモリ管理を理解する④ ― ORC - アルゴリズムによるアドバンテージ
• Nimのメモリ管理を理解する⑤ ― ムーブセマンティクスとデストラクタ

---

このドキュメントについて

本書は、従来のGCを用いず、デストラクタとムーブセマンティクスに基づいたNimランタイムを紹介します。この新しいランタイムの利点は、Nim のプログラムがヒープサイズを気にしなくなることと、マルチコアマシンを有効に活用するためのプログラムが書きやすくなることです。また、ファイルやソケットなどのクローズコールを手動で行う必要がなくなるという嬉しい特典もあります。

この文書は、Nimにおけるムーブセマンティクスとデストラクタの動作に関する正確な仕様であることを目的としています。

モチベーションを高めるサンプルコード

ここで説明した言語機構を用いると、カスタムseqは次のように書くことができます。

type
  myseq*[T] = object
    len, cap: int
    data: ptr UncheckedArray[T]

proc `=destroy`*[T](x: var myseq[T]) =
  if x.data != nil:
    for i in 0..<x.len: `=destroy`(x.data[i])
    dealloc(x.data)

proc `=trace`[T](x: var myseq[T]; env: pointer) =
  # `=trace` は、サイクルコレクタ `--mm:orc` が
  # オブジェクトグラフをトレースする方法を理解することを可能にします。
  if x.data != nil:
    for i in 0..<x.len: `=trace`(x.data[i], env)

proc `=copy`*[T](a: var myseq[T]; b: myseq[T]) =
  # 自己割り当てでは何もしない:
  if a.data == b.data: return
  `=destroy`(a)
  wasMoved(a)
  a.len = b.len
  a.cap = b.cap
  if b.data != nil:
    a.data = cast[typeof(a.data)](alloc(a.cap * sizeof(T)))
    for i in 0..<a.len:
      a.data[i] = b.data[i]

proc `=sink`*[T](a: var myseq[T]; b: myseq[T]) =
  # move assignment, optional.
  # Compiler is using `=destroy` and `copyMem` when not provided
  `=destroy`(a)
  wasMoved(a)
  a.len = b.len
  a.cap = b.cap
  a.data = b.data

proc add*[T](x: var myseq[T]; y: sink T) =
  if x.len >= x.cap:
    x.cap = max(x.len + 1, x.cap * 2)
    x.data = cast[typeof(x.data)](realloc(x.data, x.cap * sizeof(T)))
  x.data[x.len] = y
  inc x.len

proc `[]`*[T](x: myseq[T]; i: Natural): lent T =
  assert i < x.len
  x.data[i]

proc `[]=`*[T](x: var myseq[T]; i: Natural; y: sink T) =
  assert i < x.len
  x.data[i] = y

proc createSeq*[T](elems: varargs[T]): myseq[T] =
  result.cap = elems.len
  result.len = elems.len
  result.data = cast[typeof(result.data)](alloc(result.cap * sizeof(T)))
  for i in 0..<result.len: result.data[i] = elems[i]

proc len*[T](x: myseq[T]): int {.inline.} = x.len

ライフタイムを追跡するフック

Nimの標準的な文字列型やseq型（動的配列）、その他の標準的なコレクションのメモリ管理は、いわゆる「Lifetime-tracking hooks」、つまり特定の型拘束演算子によって行われます。
各オブジェクト型T（Tは個別型でもよい）に対して3つの異なるフックがあり、 コンパイラによって暗黙のうちに呼び出されます。
(注意: ここでの「フック」という言葉は、動的結合や実行時の間接参照を意味するものではなく、暗黙の呼び出しは静的に結合され、インライン化される可能性もあります)。

=destroy hook

=destory hookはオブジェクトの関連メモリを解放し、その他の関連するリソースを解放します。変数がスコープ外に出たときや、宣言されたルーチンが戻ろうとするときに、このフックによって破棄されます。

型Tに対するこのフックのプロトタイプは、次のようにする必要があります。

proc `=destroy`(x: var T)

=destroyの一般的なパターンはこのようになります。

proc `=destroy`(x: var T) =
  # まず'x'がどこか他でムーブされていないかチェックする
  if x.field != nil:
    freeResource(x.field)

=sink hook

=sink hookは、オブジェクトをムーブする際に、ムーブ元からリソースを"盗んで"ムーブ先に渡します。オブジェクトをデフォルト値（オブジェクトの状態が開始した値）に戻すことで、ムーブ元のデストラクタがその後リソースを解放しないことが保証されます。オブジェクトxをデフォルト値に戻すことは、wasMoved(x)と記述されます。リソースがムーブ元から渡されない場合、コンパイラは=destroyとcopyMemの組み合わせを代わりに使用します。これは効率的なので、ユーザーが独自の=sink演算子を実装する必要はほとんどなく、=destroyと=copyを提供するだけで十分で、あとはコンパイラが処理してくれます。

型Tに対するこのフックのプロトタイプは、次のようにする必要があります。

proc `=sink`(dest: var T; source: T)

=sinkの一般的なパターンはこのようになります。

proc `=sink`(dest: var T; source: T) =
  `=destroy`(dest)
  wasMoved(dest)
  dest.field = source.field

注：=sinkは自己割り当てをチェックする必要はありません。自己割り当てがどのように扱われるかは、このドキュメントの後の方で説明します。

=copy hook

Nimの通常の代入は概念的には値をコピーします。コピーフックは=sink操作に変換できなかった代入のために呼ばれます。

型Tに対するこのフックのプロトタイプは、次のようにする必要があります。

proc `=copy`(dest: var T; source: T)

=copyの一般的なパターンはこのようになります。

proc `=copy`(dest: var T; source: T) =
  # リソースの自己割り当てを防ぐ
  if dest.field != source.field:
    `=destroy`(dest)
    wasMoved(dest)
    dest.field = duplicateResource(source.field)

=copy関数は{.error.}プラグマでマークすることができます。そうすれば、コピーにつながるような代入はコンパイル時に阻止されます。これは次のようになります。

proc `=copy`(dest: var T; source: T) {.error.}

この時にカスタムエラーメッセージ（例： {.error: "custom error".} ）を指定しても、エラーメッセージがコンパイラーから出力されることはありません。{.error.}プラグマの前に=がないことに注意してください。

=trace hook

カスタムコンテナタイプはNimのサイクルコレクターである--mm:orcを=traceフックでサポートすることができます。もしコンテナが=traceを実装していない場合、コンテナの助けを借りて構築された周期的なデータ構造はメモリやリソースをリークするかもしれませんが、メモリの安全性は損なわれません。

型Tに対するこのフックのプロトタイプは、次のようにする必要があります。

proc `=trace`(dest: var T; env: pointer)

envは、ORCがその内部状態を追跡するために使用され、組み込みの=trace操作の呼び出しに渡されるべきです。

通常、カスタムの=traceが必要になるのは、手動で割り当てたリソースを解放するカスタムの=destroyも使用する場合だけで、手動で割り当てたリソース内のアイテムから循環的に参照される可能性があり、これらの循環的に参照されるリソースを-mm:orcが破壊して収集したい場合のみです。しかし現在のところ、=destroy/=traceのどちらを先に使っても、自動的にもう一方のバージョンを作成し、それがペアの2番目の作成と衝突してしまうという相互利用の問題が生じています。この問題を回避するには、「フック」の2つ目を先に宣言して、自動生成を防止することです。

=destroyを=traceと共に使う一般的なパターンはこのようになります。

type
  Test[T] = object
    size: Natural
    arr: ptr UncheckedArray[T] # 生ポインタ

proc makeTest[T](size: Natural): Test[T] = # custom allocation...
  Test[T](size: size, arr: cast[ptr UncheckedArray[T]](alloc0(sizeof(T) * size)))


proc `=destroy`[T](dest: var Test[T]) =
  if dest.arr != nil:
    for i in 0 ..< dest.size: dest.arr[i].`=destroy`
    dest.arr.dealloc

proc `=trace`[T](dest: var Test[T]; env: pointer) =
  if dest.arr != nil:
    # trace the `T`'s which may be cyclic
    for i in 0 ..< dest.size: `=trace`(dest.arr[i], env)

# 必要であればその他のカスタム"hook"をこの後に実装していく...

注: =traceフック(これは-mm:orcでのみ使用される)は、現在他のフックより実験的で洗練されていません。

ムーブセマンティクス

「ムーブ」は最適化されたコピー操作と見なすことができます。コピー操作の元リソースがその後使用されない場合、コピーはムーブに置き換えることができます。ここでは、lastReadOf(x)という表記を用いて、xがその後使用されないことを表現しています。この特性は静的な制御フロー解析によって計算されますが、system.moveを明示的に使用することによっても強制することもできます。

Swap

自己割り当てをチェックする必要があり、また=copyと=sinkの内部で以前のオブジェクトを破壊する必要があることは、system.swapをそれ自身の組み込みプリミティブとして扱い、関係するオブジェクトのすべてのフィールドをcopyMemまたは同等のメカニズムで交換することを強く示唆するものです。言い換えると、swap(a, b)はlet tmp = move(b); b = move(a); a = move(tmp)のように単なる交換としては実装されていません。

このことは、さらなる結果をもたらします。

• 同じオブジェクトを指すポインタを含むオブジェクトは、Nimのモデルではサポートされていません。そうしなければ、スワップされたオブジェクトは一貫性のない状態になってしまいます。
• Seqsは実装上reallocを使用することができます。

Sinkパラメーター

コレクションに変数を移動させるには、通常sinkパラメータを使用します。sinkパラメータに渡されたリソースは、その後で使われてはいけません。これは制御フローグラフの静的解析によって保証されます。もし、そのリソースが最後に使われたリソースであることが証明できない場合は、代わりにコピーが作成され、このコピーがsinkパラメータに渡されます。

sinkパラメータはproc本体の中で一度消費されるかもしれませんが、全く消費される必要はありません。この理由は、proc put(t: var Table; k: sink Key, v: sink Value)のようなシグネチャは、それ以上のオーバーロードなしに使えるべきで、kがすでにテーブルに存在する場合、putはkの所有権をとらないかもしれないからです。sinkパラメータは、線形型システムではなく、アフィン型システムを可能にします。

採用された静的解析は限定的で、ローカル変数のみを対象としますが、オブジェクトとタプルフィールドは別個の存在として扱われる。

proc consume(x: sink Obj) = discard "no implementation"

proc main =
  let tup = (Obj(), Obj())
  consume tup[0]
  # tup[0]は消費されたが、tup[1]はまだ生存している
  echo tup[1]

時には、明示的に値を最終位置にムーブさせることが必要な場合もあります。

proc main =
  var dest, src: array[10, string]
  # ...
  for i in 0..high(dest):
    dest[i] = move(src[i])

実装は、さらに多くのムーブの最適化を実装することは許されていますが、必須ではありません（現在では手動での最適化は不要になっています）。

Sinkパラメーターによる推論

現在の実装では、sinkパラメータ推論を限定的に行うことができます。しかしコマンドラインで--sinkInference:onを指定するかpushプラグマによって有効にする必要があります。

あるセクションでコードの推論を有効にするには、{.push sinkInference: on.}...{.pop.}のブロックを使うことでできます。

.nosinksプラグマを使用すると、特定のルーチンでこの推論を無効にすることができます。

proc addX(x: T; child: T) {.nosinks.} =
  x.s.add child

推論アルゴリズムの詳細については、現在ドキュメント化はされていません。

リライトルール

注：許可される実装方法は2種類あります。

• 生成される「最終」セクションは、ルーチン本体全体を包む1つのセクションとすることができます。
• 生成された「最終」セクションは、スコープを囲むようにラップされます。

現在の実装では、戦略(2)に従っています。つまり、スコープの終端でリソースが破壊されます。

var x: T; stmts
---------------             (destroy-var)
var x: T; try stmts
finally: `=destroy`(x)


g(f(...))
------------------------    (nested-function-call)
g(let tmp;
bitwiseCopy tmp, f(...);
tmp)
finally: `=destroy`(tmp)


x = f(...)
------------------------    (function-sink)
`=sink`(x, f(...))


x = lastReadOf z
------------------          (move-optimization)
`=sink`(x, z)
wasMoved(z)


v = v
------------------   (self-assignment-removal)
discard "nop"


x = y
------------------          (copy)
`=copy`(x, y)


f_sink(g())
-----------------------     (call-to-sink)
f_sink(g())


f_sink(notLastReadOf y)
--------------------------     (copy-to-sink)
(let tmp; `=copy`(tmp, y);
f_sink(tmp))


f_sink(lastReadOf y)
-----------------------     (move-to-sink)
f_sink(y)
wasMoved(y)

オブジェクトと配列の構築

オブジェクトと配列の構築は、関数がsinkパラメータを持つ関数呼び出しとして扱われます。

デストラクタの除去

wasMoved(x);の後に=destroy(x)を実行すると、互いに相殺します。実装では、効率とコードサイズを改善するために、これを利用することが推奨されます。現在の実装では、この最適化が行われています。

自己割り当て

wasMovedと組み合わせた=sinkは、自己割り当てに対応できますが、あまり良くはありません。

x = xという単純なケースを=sink(x, x); wasMoved(x)にすると、xの値が失われてしまうからです。解決策としては、以下のような単純な自己割り当てがあります。

• シンボル: x = x
• フィールドアクセス: x.f = x.f
• コンパイル時にインデックスが分かっている配列、シーケンス、文字列のアクセス： x[0] = x[0]

これらは、何もしない空の文に変換されます。コンパイラはこれ以上のケースを自由に最適化することができます。

複雑なケースはx = f(x)の変形のように見えますが、ここではx = select(rand() < 0.5, x, y)を考えてみます。

proc select(cond: bool; a, b: sink string): string =
  if cond:
    result = a # aはresultへムーブされる
  else:
    result = b # bはresultへムーブされる

proc main =
  var x = "abc"
  var y = "xyz"
  # 自己割り当てができる
  x = select(true, x, y)

これは以下のように変換されます。

proc select(cond: bool; a, b: sink string): string =
  try:
    if cond:
      `=sink`(result, a)
      wasMoved(a)
    else:
      `=sink`(result, b)
      wasMoved(b)
  finally:
    `=destroy`(b)
    `=destroy`(a)

proc main =
  var
    x: string
    y: string
  try:
    `=sink`(x, "abc")
    `=sink`(y, "xyz")
    `=sink`(x, select(true,
      let blitTmp = x
      wasMoved(x)
      blitTmp,
      let blitTmp = y
      wasMoved(y)
      blitTmp))
    echo [x]
  finally:
    `=destroy`(y)
    `=destroy`(x)

このように、この変換は自己割り当てに対して上手く機能します。

借用の型

proc p(x: sink T)はproc pがxの所有権を持つことを意味します。さらに生成/コピー <-> 破壊のペアを排除するために、関数の戻り値の型を貸し出したことを明示するためにlent Tとしてアノテートすることができます。

sinkとlentアノテーションによって、（すべてではないにしても）ほとんどの余計なコピーと破壊を取り除くことができます。

lent Tはvar Tと同様に隠れポインタです。ポインタがその起源より長生きしないことは、コンパイラによって証明されています。lent T型やvar T型の式には，デストラクタ呼び出しは注入されません．

type
  Tree = object
    kids: seq[Tree]

proc construct(kids: sink seq[Tree]): Tree =
  result = Tree(kids: kids)
  # 以下のように変換されます
  `=sink`(result.kids, kids); wasMoved(kids)
  `=destroy`(kids)

proc `[]`*(x: Tree; i: int): lent Tree =
  result = x.kids[i]
  # 'x'からの借用は以下のように変換されます
  result = addr x.kids[i]
  # これは'lent'(借用)を意味し、その正体は'var T'のように隠されたポインタです。
  # 'var'と異なるのは、これはオブジェクトを書き換えるためには使えないということです。

iterator children*(t: Tree): lent Tree =
  for x in t.kids: yield x

proc main =
  # 全てはムーブに変換されます
  let t = construct(@[construct(@[]), construct(@[])])
  echo t[0] # アクセサはリソースのコピーは作成しない

.cursorアノテーション

--mm:arc|orcモードではNimのref型は同じランタイムの「フック」によって実装され、参照カウントを行ないます。このため、周期的な構造はすぐに解放することができません(--mm:orcには サイクルコレクタが付属しています)。.cursorアノテーションを使えば、宣言的にサイクルを分割することができます。

type
  Node = ref object
    left: Node # 所有権を表すref型
    right {.cursor.}: Node # 所有権を表さないref型

しかし、これは単なるC++のweak_ptrではないことに注意してください。rightのフィールドは参照カウントに関与しない、実行時チェックのない生のポインタであることを意味します。

自動参照カウントには、リンクされた構造体を反復処理するときにオーバーヘッドが発生するという欠点もあります。このオーバーヘッドを回避するために、.cursorアノテーションを使用することもできます。

var it {.cursor.} = listRoot
while it != nil:
  use(it)
  it = it.next

実際、.cursorはより一般的にオブジェクトの構築/破壊のペアを防ぐので、他の文脈でも有用です。代替の解決策は生のポインタ（ptr）を使うことですが、これはより面倒で、また、Nimの進化にとってより危険です。後で、コンパイラは.cursorアノテーションが安全であることを証明しますが、ptrについては、コンパイラは起こりうる問題について何もできません。

Cursor推論 / コピーの省略

現在の実装では、.cursor推論も実行されます。カーソル推論はコピーの省略の一種です。

どのように、そして、いつ、それを行うことができるかを知るために、この質問について考えてみましょう。dest = srcにおいて、本当に完全なコピーを"実体化"しなければならないのはどのような場合でしょうか？それはdestやsrcがその後に変更される場合のみです。destがローカル変数であれば、解析は簡単です。また、srcが形式パラメータに由来する位置であれば、それが変更されることはないでしょう。言い換えれば、コンパイル時にコピーオンライトの解析を行うのです。

つまり、「借用」ビューは、明示的なポインタ間接参照なしに自然に書くことができるのです。

proc main(tab: Table[string, string]) =
  let v = tab["key"] # 'tab'がその後変更されないので、カーソルと推論される
  # 'v'へのコピーも'v'の破棄も行わない(=借用)
  use(v)
  useItAgain(v)

フックリフティング

タプル型(A, B, ...)のフックは、関係する型A, B, ...のフックをタプル型にリフティングすることで生成されます。すなわち、コピーx = yはx[0] = y[0]; x[1] = y[1]; ...のように実装され、同様に=sinkと=destroyも実装されます。

オブジェクトや配列のような他の値ベースの複合型も同様に処理されます。しかし、objectについては、コンパイラが生成したフックをオーバーライドすることができます。これは、より効率的なデータ構造の探索を行うため、あるいは深い再帰を避けるために重要です。

フックの生成

フックを上書きする機能は、phase ordering problemにつながります。

type
  Foo[T] = object

proc main =
  var f: Foo[int]
  # エラー: 'f'のデストラクタはこのスコープでアクセスされる前に呼び出されてしまう

proc `=destroy`[T](f: var Foo[T]) =
  discard

その解決策は、使用する前にproc =destroyTを定義することです。コンパイラはすべての型に対して、戦略的な場所に暗黙のフックを生成し、明示的に提供されたフックが「遅すぎた」場合に、確実に検出できるようにします。これらの戦略的な場所は、書き換えルールから導き出されたもので、以下の通りです。

let/var x = ...(var/letバインディング)では、typeof(x)のためのフックが生成され る。
x = ... (代入) では，typeof(x)のためにフックが生成される．
f(...)(関数呼び出し) では、typeof(f(...))のためにフックが生成される。
すべてのsinkパラメータx: sink Tに対して、typeof(x)のためのフックが生成される。

nodestroyプラグマ

実験的な nodestroyプラグマはフックの挿入を抑制します。これは深い再帰を避けるために、オブジェクトの探索を特殊化するために使用することができます。

type Node = ref object
  x, y: int32
  left, right: Node

type Tree = object
  root: Node

proc `=destroy`(t: var Tree) {.nodestroy.} =
  # スタックオーバーフローを起こさないように明示的なスタックを使用する:
  var s: seq[Node] = @[t.root]
  while s.len > 0:
    let x = s.pop
    if x.left != nil: s.add(x.left)
    if x.right != nil: s.add(x.right)
    # 明示的にメモリを開放する:
    dispose(x)
  # .nodestroyのおかげで's'のデストラクタも暗黙的に呼ばれなくなったので、
  # 自分自身で'=destroy'を呼び出さなければならないことに注意してください。
  `=destroy`(s)

この例からわかるように、この解決策では十分とは言えず、最終的にはより良い解決策に置き換える必要があります。

コピーオンライト

文字列リテラルは「コピーオンライト」として実装されています。文字列リテラルを変数に代入しても、そのリテラルのコピーは作成されません。その代わり、変数は単にそのリテラルを指すようになります。リテラルは、それを指している異なる変数間で共有されます。コピー操作は、最初の書き込みが行われるまで延期されます。

var x = "abc"  # コピーしない
var y = x      # コピーしない
y[0] = 'h'     # コピーする

アドレスが変更可能な変数にに使用されるかどうかはわからないため、addr xに対する抽象化は失敗します。prepareMutationは"address of"操作の前に呼び出される必要があります。

var x = "abc"
var y = x

prepareMutation(y)
moveMem(addr y[0], addr x[0], 3)
assert y == "abc"