производительность реализации матрицы haskell

Question

Я много слышал об удивительной производительности программ, написанных на Haskell, и хотел провести несколько тестов. Итак, я написал «библиотеку» для матричных операций, чтобы сравнить ее производительность с тем же материалом, написанным на чистом C. Прежде всего, я проверил производительность умножения 500000 матриц и заметил, что она ... бесконечна (т.е. заканчивается исключение нехватки памяти через 10 минут) После изучения haskell я смог избавиться от лени, и лучший результат, который мне удалось получить, примерно в 20 раз медленнее, чем его эквивалент в C. Итак, вопрос: не могли бы вы пересмотреть приведенный ниже код и сказать, можно ли еще улучшить его производительность? 20 раз все еще разочаровывает меня.

import Prelude hiding (foldr, foldl, product)
import Data.Monoid
import Data.Foldable

import Text.Printf
import System.CPUTime

import System.Environment

data Vector a = Vec3 a a a
              | Vec4 a a a a
                deriving Show

instance Foldable Vector where
  foldMap f (Vec3 a b c) = f a `mappend` f b `mappend` f c
  foldMap f (Vec4 a b c d) = f a `mappend` f b `mappend` f c `mappend` f d

data Matr a = Matr !a !a !a !a
                   !a !a !a !a
                   !a !a !a !a
                   !a !a !a !a

instance Show a => Show (Matr a) where
  show m = foldr f [] $ matrRows m
            where f a b = show a ++ "\n" ++ b

matrCols (Matr a0 b0 c0 d0 a1 b1 c1 d1 a2 b2 c2 d2 a3 b3 c3 d3)
              = [Vec4 a0 a1 a2 a3, Vec4 b0 b1 b2 b3, Vec4 c0 c1 c2 c3, Vec4 d0 d1 d2 d3]

matrRows (Matr a0 b0 c0 d0 a1 b1 c1 d1 a2 b2 c2 d2 a3 b3 c3 d3)
              = [Vec4 a0 b0 c0 d0, Vec4 a1 b1 c1 d1, Vec4 a2 b2 c2 d2, Vec4 a3 b3 c3 d3]

matrFromList [a0, b0, c0, d0, a1, b1, c1, d1, a2, b2, c2, d2, a3, b3, c3, d3]
        = Matr a0 b0 c0 d0
               a1 b1 c1 d1
               a2 b2 c2 d2
               a3 b3 c3 d3

matrId :: Matr Double
matrId  = Matr 1 0 0 0
               0 1 0 0
               0 0 1 0
               0 0 0 1

normalise (Vec4 x y z w) = Vec4 (x/w) (y/w) (z/w) 1

mult a b = matrFromList [f r c | r <- matrRows a, c <- matrCols b] where 
            f a b = foldr (+) 0 $ zipWith (*) (toList a) (toList b)

Answer 1

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

Теперь две конкретные проблемы:

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

struct vec {
  double *vec;
  int length;
}

Вы должны сделать что-то подобное в Haskell; Вот как, например, vector и bytestring реализованы.

Даже если вы не измените определение Vector, сделайте поля строгими. Вам также следует либо добавить UNPACK прагмы (в Vector и Matrix), либо скомпилировать с помощью -funbox-strict-fields.

2) Изменить mult на

mult a b = matrFromList [f r c | r <- matrRows a, c <- matrCols b] where 
            f a b = Data.List.foldl' (+) 0 $ zipWith (*) (toList a) (toList b)

Дополнительная строгость foldl' даст гораздо лучшую производительность в этом случае, чем foldr.

Одно только это изменение может иметь большое значение, но, не видя остальной части вашего кода, трудно сказать.

Answer 2

Отвечая на мой вопрос, просто чтобы поделиться новыми результатами, которые я получил вчера:

1. Я обновил ghc до последней версии, и производительность действительно стала не такой уж плохой (только в ~ 7 раз хуже).

2. Также я попытался реализовать матрицу глупым и простым способом (см. Листинг ниже) и получил действительно приемлемую производительность - только примерно в 2 раза медленнее, чем в эквиваленте C.

   data Matr a = Matr ( a, a, a, a
                      , a, a, a, a
                      , a, a, a, a
                      , a, a, a, a) 
   
   mult (Matr (!a0,  !b0,  !c0,  !d0,  
               !a1,  !b1,  !c1,  !d1,  
               !a2,  !b2,  !c2,  !d2,  
               !a3,  !b3,  !c3,  !d3))
        (Matr (!a0', !b0', !c0', !d0', 
               !a1', !b1', !c1', !d1', 
               !a2', !b2', !c2', !d2', 
               !a3', !b3', !c3', !d3'))
        = Matr ( a0'', b0'', c0'', d0''
               , a1'', b1'', c1'', d1''
               , a2'', b2'', c2'', d2''
               , a3'', b3'', c3'', d3'')
           where a0'' = a0 * a0' + b0 * a1' + c0 * a2' + d0 * a3'
                 b0'' = a0 * b0' + b0 * b1' + c0 * b2' + d0 * b3'
                 c0'' = a0 * c0' + b0 * c1' + c0 * c2' + d0 * c3'
                 d0'' = a0 * d0' + b0 * d1' + c0 * d2' + d0 * d3'
   
                 a1'' = a1 * a0' + b1 * a1' + c1 * a2' + d1 * a3'
                 b1'' = a1 * b0' + b1 * b1' + c1 * b2' + d1 * b3'
                 c1'' = a1 * c0' + b1 * c1' + c1 * c2' + d1 * c3'
                 d1'' = a1 * d0' + b1 * d1' + c1 * d2' + d1 * d3'
   
                 a2'' = a2 * a0' + b2 * a1' + c2 * a2' + d2 * a3'
                 b2'' = a2 * b0' + b2 * b1' + c2 * b2' + d2 * b3'
                 c2'' = a2 * c0' + b2 * c1' + c2 * c2' + d2 * c3'
                 d2'' = a2 * d0' + b2 * d1' + c2 * d2' + d2 * d3'
   
                 a3'' = a3 * a0' + b3 * a1' + c3 * a2' + d3 * a3'
                 b3'' = a3 * b0' + b3 * b1' + c3 * b2' + d3 * b3'
                 c3'' = a3 * c0' + b3 * c1' + c3 * c2' + d3 * c3'
                 d3'' = a3 * d0' + b3 * d1' + c3 * d2' + d3 * d3'