Почему чисто функциональные языки не используют подсчет ссылок?

Question

В чисто функциональных языках данные неизменны. При подсчете ссылок создание цикла ссылок требует изменения уже созданных данных. Кажется, что чисто функциональные языки могут использовать подсчет ссылок, не беспокоясь о возможности циклов. Я прав? Если так, то почему бы и нет?

Я понимаю, что подсчет ссылок во многих случаях медленнее, чем сборщик мусора, но, по крайней мере, он сокращает время паузы. Было бы неплохо иметь возможность использовать подсчет ссылок в тех случаях, когда время паузы плохое.

Answer 1

Относительно других управляемых языков, таких как Java и C #, чисто функциональные языки выделяются как сумасшедшие . Они также выделяют объекты разных размеров. Самая быстрая из известных стратегий распределения заключается в выделении из смежного свободного пространства (иногда называемого «детской») и резервировании аппаратного регистра для указания следующего доступного свободного пространства. Выделение из кучи становится таким же быстрым, как выделение из стека.

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

Подсчет ссылок имеет тенденцию действительно хорошо работать в таких ситуациях:

• Почти вся кучная память используется для хранения живых объектов.
• Распределение и назначение указателя нечасты по сравнению с другими операциями.
• Управлять ссылками можно на другом процессоре или компьютере.

Чтобы понять, как работают лучшие высокопроизводительные системы подсчета голосов, посмотрите работы Дэвида Бэкона и Эреза Петранка .

Answer 2

Ваш вопрос основан на ошибочном предположении. Вполне возможно иметь круговые ссылки и неизменные данные. Рассмотрим следующий пример C #, который использует неизменяемые данные для создания циклической ссылки.

class Node { 
  public readonly Node other;
  public Node() { 
    other = new Node(this);
  }
  public Node(Node node) {
    other = node;
  }
}

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

Редактировать ephemient

В ответ на комментарий ... в Хаскеле это тривиально

data Node a = Node { other :: Node a }
recursiveNode = Node { other = recursiveNode }

и больше никаких усилий в SML.

datatype 'a node = NODE of unit -> 'a node
val recursiveNode : unit node =
    let fun mkRecursiveNode () = NODE mkRecursiveNode
    in mkRecursiveNode () end

Мутация не требуется.

Answer 3

Думаю, есть несколько вещей.

• Там - это циклов : "let rec" во многих языках позволяет создавать "круговые" структуры. Кроме того, неизменность обычно не подразумевает циклов, но это нарушает правило.
• Реф-счет плох в списках : я не знаю, что счетчик ссылок хорошо работает, например, с. структуры длинных односвязных списков, которые вы часто найдете в FP (например, медленные, необходимо обеспечить хвостовую рекурсию, ...)
• Другие стратегии имеют преимущества : Как вы намекаете, другие стратегии GC обычно лучше для локальности памяти

(Когда-то я думал, что, может быть, действительно «знал» об этом, но сейчас я пытаюсь вспомнить / спекулировать, поэтому не принимайте это как какой-либо авторитет.)

Answer 4

Я прав?

Не совсем. Вы можете создавать циклические структуры данных, используя чисто функциональное программирование, просто определяя взаимно-рекурсивные значения одновременно. Например, в OCaml:

let rec xs = 0::ys and ys = 1::xs

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

Если так, то почему бы и нет?

Некоторые языки запрещают циклы и используют подсчет ссылок. Эрланг и Математика являются примерами.

Например, в Mathematica, когда вы ссылаетесь на значение, вы делаете его глубокую копию, поэтому изменение оригинала не приводит к изменению копии:

In[1] := xs = {1, 2, 3}
Out[1] = {1, 2, 3}

In[2] := ys = xs
Out[2] = {1, 2, 3}

In[3] := xs[[1]] = 5
Out[3] = 5

In[4] := xs
Out[4] = {5, 2, 3}

In[5] := ys
Out[5] = {1, 2, 3}

Answer 5

Рассмотрим эту аллегорию , рассказанную о Дэвиде Муне , изобретателе Lisp Machine :

Однажды студент пришел на Луну и сказал: «Я понимаю, как сделать лучший сборщик мусора. Мы должны вести подсчет указателей для каждого минуса».

Луна терпеливо рассказала студенту следующую историю:

"Однажды студент пришел на Луну и сказал:« Я понимаю, как сделать лучший сборщик мусора ...

Answer 6

Подсчет ссылок НАМНОГО медленнее, чем сборщик мусора, потому что это плохо для процессора. И GC большую часть времени может ожидать простоя, а также GC может быть параллельным (в другом потоке). Вот в чем проблема - GC наименее злой, и множество попыток показали это.