Создаются ли новые векторы, даже если старые больше не используются? - PullRequest
7 голосов
/ 12 июля 2011

Этот вопрос касается пакета Data.Vector.

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

Примечание: я знаю о Data.Vector.Mutable

Ответы [ 4 ]

13 голосов
/ 12 июля 2011

Нет, но может случиться что-то еще лучше.

Data.Vector создается с использованием "stream fusion" .Это означает, что если последовательность операций, которые вы выполняете для построения, а затем разрушения вектора, может быть слита, , то сам вектор никогда не будет даже построен , и ваш код превратится в оптимизированный цикл.

Fusion работает, превращая код, который будет строить векторы, в код, который собирает и разбивает потоки, а затем переводит потоки в форму, которую компилятор может видеть для выполнения оптимизации.

Итак, кодкоторый выглядит как

foo :: Int
foo = sum as
   where as, bs, cs, ds, es :: Vector Int
         as = map (*100) bs 
         bs = take 10 cs
         cs = zipWith (+) (generate 1000 id) ds
         ds = cons 1 $ cons 3 $ map (+2) es 
         es = replicate 24000 0

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

2 голосов
/ 12 июля 2011

Ну, как именно компилятор должен видеть, что "старый вектор нигде не используется"?Скажем, у нас есть функция, которая изменяет вектор:

changeIt :: Vector Int -> Int -> Vector Int
changeIt vec n = vec // [(0,n)]

Только из этого определения компилятор не может предположить, что vec представляет единственную ссылку на рассматриваемый вектор.Нам пришлось бы аннотировать функцию, чтобы ее можно было использовать только таким способом - который Haskell не поддерживает (но насколько мне известно, Clean делает).

Так что может мы делаем в Хаскеле?Допустим, у нас есть еще одна глупая функция:

changeItTwice vec n = changeIt (changeIt vec n) (n+1)

Теперь GHC может встроить changeIt и действительно «видеть», что никакая ссылка на промежуточную структуру не ускользает.Но обычно вы используете эту информацию для , а не для создания промежуточной структуры данных, вместо непосредственного генерирования конечного результата!

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

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

1 голос
/ 12 июля 2011

Не обязательно. Data.Vector использует stream fusion , поэтому в зависимости от вашего использования вектор может не создаваться вообще, и программа может компилироваться в эффективный цикл с постоянным пространством.

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

1 голос
/ 12 июля 2011

ИМХО это, безусловно, невозможно, так как сборщик мусора GHC может испортиться, если вы случайно измените объект (даже если он больше не используется). Это потому, что объект может быть перемещен в старшее поколение, а мутация может привести к появлению указателей для молодого поколения. Если теперь молодое поколение получает мусор, объект может двигаться, и, таким образом, указатель может стать недействительным.

AFAIK, все изменяемые объекты в Haskell расположены в специальной куче, которая по-разному обрабатывается GC, поэтому такие проблемы не могут возникнуть.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...