Вот код:

{-# 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 (+) xf x = (U.zipWith (+) x) . idf x y = U.zipWith (+) x y

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

Я также заметил, что если я сделаю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 и 3f это влияет на производительность в любом случае? Мне кажется ошибкой, что (что составляет) стиль кодирования может повлиять на производительность, как это. Есть ли другие примеры за пределами 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 (+) xf x = (U.zipWith (+) x) . U.forcef x = (U.zipWith (+) x) . Control.DeepSeq.force)f x = (U.zipWith (+) x) . (\z -> z `seq` z)f x = (U.zipWith (+) x) . idf x y = U.zipWith (+) x y

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

Таким образом, замедление порядка величины происходит из-за лени, так как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 и векторной библиотекой, или здесь можно сказать что-то более общее?