Деструкторы Nim и семантика перемещения

О документе

Этот документ описывает среду выполнения Nim ARC/ORC, которая больше не использует классические алгоритмы сборки мусора, а основана на деструкторах и семантике перемещения. Преимуществами являются то, что программы Nim становятся невосприимчивыми к размерам кучи и программы легче писать для эффективного использования многоядерных машин. В качестве приятного бонуса, файлы, сокеты и подобное могут быть написаны так, чтобы больше не требовать явного вызова close.

Этот документ призван быть точным описанием того, как работают семантика перемещения и деструкторы в Nim.

Пример

С помощью механизмов языка, описанных здесь, можно написать пользовательскую seq так:

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

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

proc `=wasMoved`*[T](x: var myseq[T]) =
  x.data = nil

proc `=trace`[T](x: var myseq[T]; env: pointer) =
  # `=trace` allows the cycle collector `--mm:orc`
  # to understand how to trace the object graph.
  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]) =
  # do nothing for self-assignments:
  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 `=dup`*[T](a: myseq[T]): myseq[T] {.nodestroy.} =
  # an optimized version of `=wasMoved(tmp); `=copy(tmp, src)`
  # usually present if a custom `=copy` hook is overridden
  result = myseq[T](len: a.len, cap: a.cap, data: nil)
  if a.data != nil:
    result.data = cast[typeof(result.data)](alloc(result.cap * sizeof(T)))
    for i in 0..<result.len:
      result.data[i] = `=dup`(a.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)
  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 = myseq[T](
    len: elems.len,
    cap: elems.len,
    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

Хук отслеживания жизненного цикла

Управление памятью для стандартных типов string и seq Nim, а также других стандартных коллекций, осуществляется с помощью так называемых «хуков отслеживания жизненного цикла», которые являются особыми операторами, связанными с типом.

Для каждого (обобщенного или конкретного) типа объекта T (T также может быть типом distinct) существует 6 разных хуков, которые вызываются компилятором неявно.

(Примечание: слово «хук» здесь не подразумевает никакой динамической привязки или косвенных обращений во время выполнения, неявные вызовы статически связаны и потенциально встроены.)

`=destroy` хук

Хук =destroy освобождает связанную с объектом память и освобождает другие связанные ресурсы. Переменные уничтожаются с помощью этого хука, когда они выходят из области видимости или когда процедура, в которой они были объявлены, собирается вернуть значение.

В хуке =destroy разрешается параметр типа var T или T. Принятие типа var T устарело. Прототип этого хука для типа T должен быть:

proc `=destroy`(x: T)

Общий шаблон в =destroy выглядит так:

proc `=destroy`(x: T) =
  # first check if 'x' was moved to somewhere else:
  if x.field != nil:
    freeResource(x.field)

Деструктор неявно помечен как .raises: []; деструктор не должен генерировать исключения. Для обратной совместимости компилятор выдает предупреждение для деструктора =destroy, который генерирует исключение.

Деструктор =destroy может явно указать исключения, которые он может генерировать, если таковые имеются, но это малополезно, так как поведение деструктора, генерирующего исключения, определяется реализацией. Более поздние версии спецификации языка могут более точно рассмотреть этот случай.

`=wasMoved` хук

Хук =wasMoved устанавливает объект в состояние, которое сигнализирует деструктору, что уничтожать нечего.

Прототип этого хука для типа T должен быть:

proc `=wasMoved`(x: var T)

Обычно некоторое поле указателя внутри объекта устанавливается в nil:

proc `=wasMoved`(x: var T) =
  x.field = nil

`=sink` хук

Хук =sink перемещает объект, ресурсы воруются из источника и передаются получателю. Гарантируется, что деструктор источника не освободит ресурсы после этого, установив объект в его значение по умолчанию (состояние, в котором объект был первоначально).

Указание объекта 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` хук

Обычное присваивание в Nim концептуально копирует значения. Хук =copy вызывается для присваиваний, которые нельзя преобразовать в операции =sink.

Прототип этого хука для типа T должен быть:

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

Общий шаблон в =copy выглядит так:

proc `=copy`(dest: var T; source: T) =
  # protect against self-assignments:
  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` хук

Пользовательский тип контейнера может поддерживать сборщик циклов Nim --mm:orc с помощью хука =trace. Если контейнер не реализует =trace, циклические структуры данных, созданные с помощью контейнера, могут утекать память или ресурсы, но безопасность памяти не нарушается.

Прототип этого хука для типа T должен быть:

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

env используется ORC для отслеживания его внутреннего состояния, его следует передавать в вызовы встроенной операции =trace.

Как правило, пользовательский =trace потребуется только в том случае, если используется также пользовательский =destroy, который вручную освобождает выделенные ресурсы, и только тогда, когда существует вероятность циклических ссылок из элементов внутри вручную выделенных ресурсов, когда желательно, чтобы --mm:orc смог разорвать и собрать эти циклические ресурсы. В настоящее время, однако, существует взаимная проблема использования, в том, что тот из =destroy/=trace, который используется первым, автоматически создаст версию другого, которая затем будет конфликтовать с созданием второго из пары. Обходной путь для этой проблемы заключается в предварительной декларации второго из "хуков", чтобы предотвратить автоматическое создание.

Общий шаблон использования =destroy с =trace выглядит так:

type
  Test[T] = object
    size: Natural
    arr: ptr UncheckedArray[T] # raw pointer field

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: Test[T]) =
  if dest.arr != nil:
    for i in 0 ..< dest.size: dest.arr[i].`=destroy`
    dealloc dest.arr

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)

# following may be other custom "hooks" as required...

Примечание: ХУКи =trace (которые используются только --mm:orc) в настоящее время являются более экспериментальными и менее отработанными, чем другие хуки.

`=dup` хук

Хук =dup дублирует объект. =dup(x) можно рассматривать как оптимизацию, заменяющую операцию wasMoved(dest); =copy(dest, x).

Прототип этого хука для типа T должен быть:

proc `=dup`(x: T): T

Общий шаблон реализации =dup выглядит так:

type
  Ref[T] = object
    data: ptr T
    rc: ptr int

proc `=dup`[T](x: Ref[T]): Ref[T] =
  result = x
  if x.rc != nil:
    inc x.rc[]

Семантика перемещения

«Перемещение» можно рассматривать как оптимизированную операцию копирования. Если источник операции копирования больше не используется, копирование можно заменить перемещением. В этом документе используется обозначение lastReadOf(x) для описания того, что x не используется после этого. Это свойство вычисляется с помощью статического анализа потока управления, но также может быть явно принуждено с помощью system.move.

Можно запросить, может ли анализ выполнить перемещение с помощью system.ensureMove.

move принуждает операцию перемещения и вызывает =wasMoved, в то время как ensureMove — это аннотация, которая подразумевает отсутствие операций во время выполнения. Аннотация ensureMove приводит к статической ошибке, если компилятор не может доказать, что перемещение будет безопасным.

Например:

proc main(normalParam: string; sinkParam: sink string) =
  var x = "abc"
  # valid:
  let valid = ensureMove x
  # invalid:
  let invalid = ensureMove normalParam
  # valid:
  let alsoValid = ensureMove sinkParam

Обмен

Необходимость проверки самоприсваиваний, а также необходимость уничтожения предыдущих объектов внутри =copy и =sink является сильным указанием на то, чтобы рассматривать system.swap как встроенный собственный примитив, который просто меняет местами каждое поле в вовлеченных объектах через copyMem или сопоставимый механизм. Иными словами, swap(a, b) не реализуется как let tmp = move(b); b = move(a); a = move(tmp).

Это имеет дальнейшие последствия:

Объекты, содержащие указатели, которые указывают на один и тот же объект, не поддерживаются моделью Nim. В противном случае переключенные объекты окажутся в несогласованном состоянии.
Seq могут использовать realloc в реализации.

Параметры-стоки

Для перемещения переменной в коллекцию обычно используются параметры-стоки. Место, переданное параметру-стоку, не должно использоваться после этого. Это гарантируется статическим анализом над графом потока управления. Если нельзя доказать, что это последнее использование места, вместо этого выполняется копирование, а затем эта копия передается параметру-стоку.

Параметр-сток может быть потреблен один раз в теле процедуры, но не обязан потребляться вообще. Причина в том, что такие сигнатуры, как proc put(t: var Table; k: sink Key, v: sink Value) должны быть возможны без дополнительных перегрузок, и put может не принять владение над k, если k уже существует в таблице. Параметры-стоки обеспечивают аффинную систему типов, а не линейную.

Применяемый статический анализ ограничен и касается только локальных переменных; однако поля объектов и кортежей рассматриваются как отдельные сущности:

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

proc main =
  let tup = (Obj(), Obj())
  consume tup[0]
  # ok, only tup[0] was consumed, tup[1] is still alive:
  echo tup[1]

Иногда требуется явно move значение в его конечное положение:

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

Реализация имеет право, но не обязана реализовывать еще больше оптимизаций перемещения (и текущая реализация этого не делает).

Вывод параметров-стоков

Текущая реализация может выполнять ограниченную форму вывода параметров-стоков. Но это должно быть включено с помощью --sinkInference:on, либо в командной строке, либо с помощью директивы push.

Чтобы включить его для части кода, можно использовать {.push sinkInference: on.} ... {.pop.}.

Директива .nosinks может использоваться для отключения этого вывода для одной процедуры:

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

Подробности алгоритма вывода в настоящее время не документированы.

Правила переписывания

Примечание: существуют два разрешенных стратегии реализации:

Полученная finally секция может быть одной секцией, которая обернута вокруг всего тела процедуры.
Полученная finally секция обернута вокруг окружающего блока.

Текущая реализация использует стратегию (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 = `=dup`(y);
f_sink(tmp))


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

Конструирование объектов и массивов

Конструирование объектов и массивов рассматривается как вызов функции, где функция имеет sink параметры.

Удаление деструктора

=wasMoved(x) за которым следует операция =destroy(x) взаимно компенсируют друг друга. Реализация может использовать это для повышения эффективности и размера кода. Текущая реализация выполняет эту оптимизацию.

Самоприсваивания

=sink в сочетании с =wasMoved могут обрабатывать самоприсваивания, но это тонко.

Простой случай 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 # moves a into result
  else:
    result = b # moves b into result

proc main =
  var x = "abc"
  var y = "xyz"
  # possible self-assignment:
  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)

Как можно вручную проверить, это преобразование верно для самоприсваиваний.

Тип lent

proc p(x: sink T) означает, что процедура p берет во владение x. Чтобы устранить еще больше пар создание/копирование <-> уничтожение, тип возвращаемого значения процедуры можно аннотировать как lent T. Это полезно для аксессоров "getter", которые стремятся предоставить неизменяемый вид на контейнер.

Аннотации 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)
  # converted into:
  `=sink`(result.kids, kids); `=wasMoved`(kids)
  `=destroy`(kids)

proc `[]`*(x: Tree; i: int): lent Tree =
  result = x.kids[i]
  # borrows from 'x', this is transformed into:
  # result = addr x.kids[i]
  # This means 'lent' is like 'var T' a hidden pointer.
  # Unlike 'var' this hidden pointer cannot be used to mutate the object.

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

proc main =
  # everything turned into moves:
  let t = construct(@[construct(@[]), construct(@[])])
  echo t[0] # accessor does not copy the element!

Директива cursor

В режимах --mm:arc|orc тип Nim ref реализуется с помощью тех же "крючков" времени выполнения, а значит, через счетчик ссылок. Это означает, что циклические структуры не могут быть освобождены сразу (--mm:orc поставляется с коллектором циклов). С помощью директивы cursor можно разрывать циклы декларативно:

type
  Node = ref object
    left: Node # owning ref
    right {.cursor.}: Node # non-owning ref

Но обратите внимание, что это не weak_ptr C++, это означает, что правое поле не участвует в подсчёте ссылок, это обычный указатель без проверок во время выполнения.

Автоматический подсчёт ссылок также имеет недостаток, заключающийся в том, что он вносит издержки при итерировании по связанным структурам. Директива cursor также может использоваться для избежания этих издержек:

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

Фактически, cursor в более общем смысле предотвращает пары создание/уничтожение объектов и поэтому может быть полезен в других контекстах. Альтернативным решением было бы использование сырых указателей (ptr), что более громоздко и также более опасно для эволюции Nim: Позже компилятор может попытаться доказать безопасность директив cursor, но для ptr компилятор должен молчать о возможных проблемах.

Вывод курсора / исключение копирования

Текущая реализация также выполняет вывод курсора. Вывод курсора — это форма исключения копирования.

Чтобы понять, как и когда это можно сделать, задайте себе вопрос: в dest = src когда нам действительно нужно материализовать полную копию? - Только если dest или src изменяются после этого. Если dest — это локальная переменная, которую легко проанализировать. И если src — это место, полученное из формального параметра, мы также знаем, что оно не изменяется! Другими словами, мы выполняем анализ копирования-записи во время компиляции.

Это означает, что "заимствованные" представления можно писать естественно и без явных указателей на указатели:

proc main(tab: Table[string, string]) =
  let v = tab["key"] # inferred as cursor because 'tab' is not mutated.
  # no copy into 'v', no destruction of 'v'.
  use(v)
  useItAgain(v)

Поднятие крючков

Крючки типа кортежа (A, B, ...) генерируются путем поднятия крючков участвующих типов A, B, ... к типу кортежа. Другими словами, копия x = y реализуется как x[0] = y[0]; x[1] = y[1]; ..., аналогично для =sink и =destroy.

Другие основанные на значениях составные типы, такие как object и array обрабатываются соответствующим образом. Для object компилятором можно переопределить сгенерированные крючки. Это также может быть важно для использования альтернативного обхода связанной структуры данных, который более эффективен, или для предотвращения глубоких рекурсий.

Генерация крючков

Возможность переопределения крючка приводит к проблеме упорядочения фаз:

type
  Foo[T] = object

proc main =
  var f: Foo[int]
  # error: destructor for 'f' called here before
  # it was seen in this module.

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

Решение заключается в определении proc `=destroy`[T](f: Foo[T]) до его использования. Компилятор генерирует неявные крючки для всех типов в стратегических местах, чтобы явно предоставленный крючок, который приходит слишком «поздно», можно было надёжно обнаружить. Эти стратегические места были получены из правил переписывания и таковы:

В конструкте let/var x = ... (связывание var/let) крючки генерируются для typeof(x).
В x = ... (присваивание) крючки генерируются для typeof(x).
В f(...) (вызов функции) крючки генерируются для typeof(f(...)).
Для каждого параметра-стока 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: Tree) {.nodestroy.} =
  # use an explicit stack so that we do not get stack overflows:
  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)
    # free the memory explicitly:
    `=dispose`(x)
  # notice how even the destructor for 's' is not called implicitly
  # anymore thanks to .nodestroy, so we have to call it on our own:
  `=destroy`(s)

Как видно из примера, это решение едва ли достаточно и в конечном итоге должно быть заменено лучшим решением.

Копирование при записи

Строковые литералы реализованы как "копирование при записи". При присваивании строкового литерала переменной копия литерала не создается. Вместо этого переменная просто указывает на литерал. Литерал совместно используется между различными переменными, которые указывают на него. Операция копирования откладывается до первого записи.

Например:

var x = "abc"  # no copy
var y = x      # no copy
y[0] = 'h'     # copy

Абстракция терпит неудачу для addr x, потому что неизвестно, будет ли адрес использоваться для изменений. prepareMutation необходимо вызвать перед операцией "адрес". Например:

var x = "abc"
var y = x

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

Деструкторы Nim и семантика перемещения

О документе

Пример

Хук отслеживания жизненного цикла

=destroy хук

=wasMoved хук

=sink хук

=copy хук

=trace хук

=dup хук

Семантика перемещения

Обмен

Параметры-стоки

Вывод параметров-стоков

Правила переписывания

Конструирование объектов и массивов

Удаление деструктора

Самоприсваивания

Тип lent

Директива cursor

Вывод курсора / исключение копирования

Поднятие крючков

Генерация крючков

Директива nodestroy

Копирование при записи

`=destroy` хук

`=wasMoved` хук

`=sink` хук

`=copy` хук

`=trace` хук

`=dup` хук