Стиль против производительности с использованием векторов

Question

Стиль против производительности с использованием векторов

Вот код:

{-# LANGUAGE FlexibleContexts #-}

import Data.Int
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Generic as V

{-# NOINLINE f #-} -- Note the 'NO'
--f :: (Num r, V.Vector v r) => v r -> v r -> v r
--f :: (V.Vector v Int64) => v Int64 -> v Int64 -> v Int64
--f :: (U.Unbox r, Num r) => U.Vector r -> U.Vector r -> U.Vector r
f :: U.Vector Int64 -> U.Vector Int64 -> U.Vector Int64
f = V.zipWith (+) -- or U.zipWith, it doesn't make a difference

main = do
    let iters = 100
        dim = 221184
        y = U.replicate dim 0 :: U.Vector Int64
    let ans = iterate ((f y)) y !! iters
    putStr $ (show $ U.sum ans)

Я собрал с ghc 7.6.2 а также -O2и потребовалось 1,7 секунды, чтобы бежать.

Я пробовал несколько разных версий f:

f x = U.zipWith (+) x
f x = (U.zipWith (+) x) . id
f x y = U.zipWith (+) x y

Версия 1 совпадает с оригинальной, а версии 2 и 3 работают менее чем за 0,09 секунды (и INLININGf ничего не меняет).

Я также заметил, что если я сделаю f полиморфный (с любой из трех указанных выше сигнатур), даже с "быстрым" определением (то есть 2 или 3), он замедляется... до ровно 1,7 секунды. Это заставляет меня задуматься о том, возможно, исходная проблема связана с (отсутствием) логического вывода типа, хотя я явно даю типы для типа Vector и типа элемента.

Я также заинтересован в добавлении целых чисел по модулю q:

newtype Zq q i = Zq {unZq :: i}

Как при добавлении Int64s, если я напишу функцию с каждым указанным типом,

h :: U.Vector (Zq Q17 Int64) -> U.Vector (Zq Q17 Int64) -> U.Vector (Zq Q17 Int64)

Я получаю на порядок лучшую производительность, чем если бы я оставил полиморфизм

h :: (Modulus q) => U.Vector (Zq q Int64) -> U.Vector (Zq q Int64) -> U.Vector (Zq q Int64)

Но я должен по крайней мере быть в состоянии удалить конкретный тип фантома! Это должно быть скомпилировано, так как я имею дело с newtype,

Вот мои вопросы:

Откуда идет замедление?
Что происходит в версиях 2 и 3 f это влияет на производительность в любом случае? Мне кажется ошибкой, что (что составляет) стиль кодирования может повлиять на производительность, как это. Есть ли другие примеры за пределами Vector, где частичное применение функции или другие стилистические решения влияют на производительность?
Почему полиморфизм замедляет меня на порядок, независимо от того, где находится полиморфизм (т.е. в векторном типе, в Num тип, оба или фантомный тип)? Я знаю, что полиморфизм делает код медленнее, но это смешно. Есть ли взломать вокруг этого?

РЕДАКТИРОВАТЬ 1
Я подал проблему на странице векторной библиотеки. Я нашел проблему GHC, касающуюся этой проблемы.
EDIT2
Я переписал вопрос после получения некоторого понимания ответа @kqr. Ниже оригинал для справки.

-------------- ОРИГИНАЛЬНЫЙ ВОПРОС --------------------

Вот код:

{-# LANGUAGE FlexibleContexts #-}

import Control.DeepSeq
import Data.Int
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Generic as V

{-# NOINLINE f #-} -- Note the 'NO'
--f :: (Num r, V.Vector v r) => v r -> v r -> v r
--f :: (V.Vector v Int64) => v Int64 -> v Int64 -> v Int64
--f :: (U.Unbox r, Num r) => U.Vector r -> U.Vector r -> U.Vector r
f :: U.Vector Int64 -> U.Vector Int64 -> U.Vector Int64
f = V.zipWith (+)

main = do
    let iters = 100
        dim = 221184
        y = U.replicate dim 0 :: U.Vector Int64
    let ans = iterate ((f y)) y !! iters
    putStr $ (show $ U.sum ans)

Я собрал с ghc 7.6.2 а также -O2и потребовалось 1,7 секунды, чтобы бежать.

Я пробовал несколько разных версий f:

f x = U.zipWith (+) x
f x = (U.zipWith (+) x) . U.force
f x = (U.zipWith (+) x) . Control.DeepSeq.force)
f x = (U.zipWith (+) x) . (\z -> z `seq` z)
f x = (U.zipWith (+) x) . id
f x y = U.zipWith (+) x y

Версия 1 совпадает с оригинальной, версия 2 запускается за 0,111 секунды, а версии 3-6 - менее 0,09 секунды (и INLININGf ничего не меняет).

Таким образом, замедление порядка величины происходит из-за лени, так как force помогло, но я не уверен, откуда берется лень. Распакованные типы не могут быть ленивыми, верно?

Я пытался написать строгую версию iterateдумая, что сам вектор должен быть ленивым

{-# INLINE iterate' #-}
iterate' :: (NFData a) => (a -> a) -> a -> [a]
iterate' f x =  x `seq` x : iterate' f (f x)

но с бессмысленной версией fэто совсем не помогло.

Я также заметил кое-что еще, что могло быть просто совпадением и красной селедкой: если я сделаю f полиморфный (с любой из трех указанных выше сигнатур), даже с "быстрым" определением, он замедляется... ровно до 1,7 секунды. Это заставляет меня задуматься о том, возможно ли, что первоначальная проблема связана с (отсутствием) логического вывода типа, хотя все должно быть правильно выведено.

Вот мои вопросы:

Откуда идет замедление?
Почему сочинять с force помочь, но используя строгий iterate не делает?
Почему U.force хуже чем DeepSeq.force? Я понятия не имею что U.force должен делать, но это звучит очень похоже DeepSeq.forceи, похоже, имеет аналогичный эффект.
Почему полиморфизм замедляет меня на порядок, независимо от того, где находится полиморфизм (т.е. в векторном типе, в Num типа или оба)?
Почему версии 5 и 6, ни одна из которых не должна иметь никаких последствий для строгости, так же быстро, как строгая функция?

Как отметил @kqr, проблема не в строгости. Так что что-то о том, как я пишу функцию, вызывает общее zipWith для использования, а не для конкретной версии. Это просто случайность между GHC и векторной библиотекой, или здесь можно сказать что-то более общее?

14

haskell lambda pointfree

Источник

user925978 06 ноя '13 в 04:09

1 ответ

Решение

Другие вопросы по тегам haskell lambda pointfree

user1463507 06 ноя '13 в 06:29 2013-11-06 06:29 · Accepted Answer · 2013-11-06 06:29

Хотя у меня нет точного ответа, который вы хотите, есть две вещи, которые могут вам помочь.

Первое, что x `seq` x и семантически, и вычислительно одно и то же x, Вики говорят о seq:

Распространенное заблуждение относительно seq в том, что seq x "оценивает" x, Ну вроде как. seq ничего не оценивает просто на основании наличия в исходном файле, все, что он делает, это вводит искусственную зависимость данных одного значения от другого: когда результат seq оценивается, первый аргумент также (вроде; см. ниже) должен быть оценен.
В качестве примера предположим, x :: Integer, затем seq x b ведет себя по существу как if x == 0 then b else b - безусловно равно b, но заставляет x по пути. В частности, выражение x `seq` x полностью избыточен и всегда имеет тот же эффект, что и просто x,

В первом абзаце говорится, что seq a b не значит что a будет магически оценен в этот момент, это означает, что a будет оценен, как только b нужно оценить. Это может произойти позже в программе или, может быть, вообще никогда. Когда вы смотрите на это в таком свете, очевидно, что seq x x это избыточность, потому что все, что он говорит, это "оценить x как только x нужно оценить."Что, конечно, что произойдет в любом случае, если вы только что написали x,

Это имеет два значения для вас:

~~Ваш "строгий"~~ iterate' ~~функция на самом деле не является более строгой, чем это было бы без~~ seq , ~~На самом деле, мне трудно представить, как~~ iterate ~~функция может стать более строгой, чем она есть.~~ ~~Вы не можете сделать хвост списка строгим, потому что он бесконечен.~~ ~~Главное, что вы можете сделать, это заставить "аккумулятор",~~ f x ~~, но это не дает значительного увеличения производительности в моей системе.[1]~~
Сотрите это. Ваш строгий iterate' делает то же самое, что и моя версия шаблона взрыва. Смотрите комментарии.
Пишу (\z -> z `seq` z) не дает вам строгой функции идентификации, которая, как я полагаю, является тем, к чему вы стремились. На самом деле, общая функция идентичности настолько строга, насколько вы можете себе представить, - она оценит ее результат, как только она понадобится.

Тем не менее, я посмотрел на ядро GHC генерирует для

U.zipWith (+) y

а также

U.zipWith (+) y . id

и есть только одна большая разница, которую может заметить мой неподготовленный глаз. Первый использует просто равнину Data.Vector.Generic.zipWith (вот где может возникнуть ваше совпадение полиморфизма - если GHC выберет zipWith он, конечно, будет работать так, как если бы код был полиморфным!), в то время как последний разбил этот единственный вызов функции почти на 90 строк кода монады состояния и распакованных типов машин.

Код монады состояния выглядит почти как циклы и деструктивные обновления, которые вы бы написали на императивном языке, поэтому я предполагаю, что он очень хорошо приспособлен к машине, на которой он работает. Если бы я не спешил, я бы посмотрел дольше, чтобы более точно понять, как это работает и почему GHC вдруг решил, что ему нужен жесткий цикл. Я прикрепил сгенерированное ядро к себе так же, как и к любому другому, кто хочет взглянуть. [2]

[1]: Направляя аккумулятор по пути: (Это то, что вы уже делаете, я неправильно понял код!)

{-# LANGUAGE BangPatterns #-}
iterate' f !x = x : iterate f (f x)

[2]: какое ядро U.zipWith (+) y . id переводится в.