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

О документе

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

Цель этого документа – предоставить точное описание работы семантики перемещения и деструкторов в 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[i])
    dealloc(x.data)

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 `=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: resize(x)
  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

Хэндлеры отслеживания жизненного цикла

Управление памятью для стандартных типов string и seq Nim, а также других стандартных коллекций, выполняется с помощью так называемых «хэндлеров отслеживания жизненного цикла» или «типозависимых операторов». Для каждого типа объекта (обобщённого или конкретного) T (T также может быть типом distinct), компилятор неявно вызывает три различных хэндлера.

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

`=destroy` хэндлер

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

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

proc `=destroy`(x: var T)

Общая схема в =destroy выглядит следующим образом:

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

`=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` хэндлер

Обычная операция присваивания концептуально копирует значения. Хэндлер =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.} нет =.

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

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

Обмен

Необходимость проверки на самоприсваивание, а также необходимость уничтожения предыдущих объектов внутри =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; `=copy`(tmp, 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 = 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 . Это полезно для «методов получения», которые стремятся обеспечить неизменяемый вид на контейнер.

Псевдонимы 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

В режимах --gc:arc|orc тип Nim ref реализуется с помощью тех же хэндлеров времени выполнения и, следовательно, со счётчиком ссылок. Это означает, что циклические структуры не могут быть освобождены немедленно (--gc: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: var Foo[T]) =
  discard

Решение заключается в определении proc `=destroy`[T](f: var 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: var 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 explicit:
    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)

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

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

О документе

Пример

Хэндлеры отслеживания жизненного цикла

=destroy хэндлер

=sink хэндлер

=copy хэндлер

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

Обмен

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

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

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

Создание объектов и массивов

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

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

Тип lent

Аннотация .cursor

Вывод указателей / удаление копирования

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

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

Директива nodestroy

`=destroy` хэндлер

`=sink` хэндлер

`=copy` хэндлер