Повторное использование памяти неизменного состояния в нетерпеливой оценке? - PullRequest
1 голос
/ 01 марта 2011

Я изучаю чисто функциональный язык и сейчас думаю о некоторой неизменной реализации данных.

Вот псевдокод.

List a = [1 .. 10000]
List b = NewListWithoutLastElement a
b

При оценке b, b должно быть скопировано в стремлении / строгой реализации неизменяемых данных. Но в этом случае a больше нигде не используется, поэтому память «а» можно безопасно использовать повторно, чтобы избежать затрат на копирование.

Кроме того, программист может заставить компилятор всегда делать это, помечая тип List некоторым ключевым словом, означающим must-be-disposed-after-using. Что делает ошибку времени компиляции в логике, не может избежать затрат на копирование.

Это может значительно повысить производительность. Потому что его можно применить и к огромному графу объектов.

Как вы думаете? Любые реализации?

1 Ответ

1 голос
/ 01 марта 2011

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

Например:

let map2 f g x = f x, g x 

let apply f = 
  let a = [1 .. 10000]
  f a 

// in another file :

apply (map2 NewListWithoutLastElement NewListWithoutFirstElement)

Это довольно стандартно в функциональном коде, и нет способа поместить атрибут must-be-disposed-after-using в a, потому что ни одно конкретное местоположение не имеетдостаточно знаний об остальной части программы.Конечно, вы можете попытаться добавить эту информацию в систему типов, но вывод типа в этом случае совершенно не тривиален (не говоря уже о том, что типы вырастут довольно большими).

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

let a = binary_tree [ 1; 2; 5; 7; 9 ]
let result_1 = complex_computation_1 (insert a 6)
let result_2 = complex_computation_2 (remove a 5)

Чтобы разрешить повторное использование памяти в complex_computation_2, вам необходимо доказать, что complex_computation_1 не изменяет a, не хранит какую-либо часть a в result_1 и выполняется с помощью a к тому времени, когда complex_computation_2 начинает работать.Хотя два первых требования могут показаться самыми сложными, имейте в виду, что это чисто функциональный язык: третье требование фактически приводит к значительному падению производительности, поскольку complex_computation_1 и complex_computation_2 больше не могут выполняться в разных потоках!

На практике это не проблема в подавляющем большинстве функциональных языков по трем причинам:

  • У них специально для этого создан сборщик мусора.Для них быстрее просто выделить новую память и вернуть оставленную, а не пытаться повторно использовать существующую память.В подавляющем большинстве случаев это будет достаточно быстро.
  • У них есть структуры данных, которые уже реализуют обмен данными.Например, NewListWithoutFirstElement уже обеспечивает полное повторное использование памяти преобразованного списка без каких-либо усилий.Функциональным программистам (и, в действительности, любому виду программистов) довольно свойственно определять использование ими структур данных на основе соображений производительности, и переписать алгоритм «удалить последний» как алгоритм «сначала удалить» довольно просто.
  • Ленивая оценка уже делает нечто эквивалентное: хвост ленивого списка изначально является просто замыканием, которое может оценить хвост, если вам нужно - поэтому нет памяти для повторного использования.С другой стороны, это означает, что чтение элемента из b в вашем примере будет считывать один элемент из a, определять, является ли он последним, и возвращать его без необходимости хранения (ячейка cons, вероятно, будет расположена где-то втам, но это происходит все время в функциональных языках программирования, и недолговечные маленькие объекты прекрасно подходят для GC).
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...