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

StackOverflow https://stackoverflow.com/questions/791437

Вопрос

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

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

Это было полезно?

Решение

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

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

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

Редактировать с помощью эфемерный

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

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

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

Другие советы

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

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

Подсчет ссылок, как правило, действительно эффективен в подобных ситуациях:

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

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

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

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

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

Рассмотреть эта аллегория рассказал о Дэвид Мун, изобретатель Шепелявящая Машина:

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

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

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

Ам прав?

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

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

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

Если да, то почему они этого не делают?

Некоторые языки действительно запрещают циклы и используют подсчет ссылок.Примерами являются Erlang и Mathematica.

Например, в 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}

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top