Смысл статьи все-таки в другом. Если у вас уже есть реализация BLAS, возможно вам следует её адаптировать для достижения максимальной производительности.
Быстрее получается, если только вы при этом используете динамическое распределение потоков. Мы же по прежнему MKL обсуждаем? Насколько я понимаю, далеко не все процедуры в нём так реализованы.
А то, что по дефолту грузит все ядра - в этом как раз и есть главная проблема, которая и побудила меня на статью. Поведение по умолчанию может сильно проигрывать. По ссылке Intel как раз рекомендует менять значение переменно окружения KMP_HW_SUBSET, чтобы явно указывать, где исполнять вычисления.
Спасибо за статьи! С интересом прочитал обе. Особенно понравился стиль изложения с постепенным усложнением решения и пояснениями, в каких случаях это будет оправдано.
Отличное решение! Действительно, из моего поля зрения совсем ускользнуло наличие альтернативных реализаций для строк. Ваши решения проходят все тесты с большим запасом.
Единственное — во второй версии пришлось заменить <> на `mappend`, в противном случае компиляция заканчивалась с ошибкой. Предполагаю, что в GHC 7.10.2, который используется в системе тестирования, ещё не было этого оператора в ByteString.Builder.
Не подскажите, что за приложение вы использовали для визуализации результатов профилирования?
Спасибо за комментарий! Да, я реализовывал подобный подход с посимвольным чтением входных данных. К сожалению, это не дало какого-либо прироста производительности. Единственное, чего удалось добиться с его помощью — еще большего уменьшения используемой памяти: для сортировки подсчётом и boxed-массивов на 19 тесте получаем 8.61Mb вместо 10.25Mb, а для unboxed 984.00Kb.
Заголовок спойлера
import Data.Char (isSpace, isDigit, digitToInt)
import Data.List (foldl')
import Control.Monad
import System.IO
import Data.Array.Unboxed
getInt :: IO Int
getInt = hGetIntegral stdin
hGetIntegral :: Handle -> IO Int
hGetIntegral h = do
digits <- hGetDigits h
return $ read digits
hGetDigits :: Handle -> IO [Char]
hGetDigits h = g =<< hIsEOF h
where
g eof
| eof == True = return []
| otherwise = do
char <- hGetChar h
if isDigit char
then fmap (char:) (hGetDigits h)
else return []
foldM' :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
foldM' _ z [] = return z
foldM' f z (x:xs) = do
z' <- f z x
z' `seq` foldM' f z' xs
addToArray :: UArray Int Int -> Int -> UArray Int Int
addToArray arr number = accum (+) arr [(number, 1)]
fillArray :: UArray Int Int -> IO (UArray Int Int)
fillArray a = do
numb <- getInt
foldM' (\arr num -> addToArray arr <$> num) a (replicate numb getInt)
printPair (a, b) = replicateM_ b $ print a
main :: IO ()
main = do
t <- read <$> getLine :: IO Int
let a = array (0,100) [(i, 0) | i <- [0..100]]
res <- foldl' (>=>) return (replicate t fillArray) a
mapM_ printPair $ assocs res
Конечно можно предположить, что мы таким образом хоть и выиграли на чтении, но получили просадку в производительности на существенном большем количестве вызовов функции accum, но считаю это маловероятным. Тоже самое я пробовал с IOArray, который такой функции не имеет, и при его использовании приходится в обоих случаях оперировать с отдельными элементами — результат получился аналогичным.
Остаётся ещё оптимизация вывода результата, но я пока ничего не придумал в этом направлении.
По-хорошему, мне необходимо разобраться с профилированием программ на Haskell, чтобы выяснить какая именно часть кода работает большую часть времени. Надеюсь, что смогу этим заняться в обозримом будущем.
Смысл статьи все-таки в другом. Если у вас уже есть реализация BLAS, возможно вам следует её адаптировать для достижения максимальной производительности.
Быстрее получается, если только вы при этом используете динамическое распределение потоков. Мы же по прежнему MKL обсуждаем? Насколько я понимаю, далеко не все процедуры в нём так реализованы.
А то, что по дефолту грузит все ядра - в этом как раз и есть главная проблема, которая и побудила меня на статью. Поведение по умолчанию может сильно проигрывать. По ссылке Intel как раз рекомендует менять значение переменно окружения KMP_HW_SUBSET, чтобы явно указывать, где исполнять вычисления.
Буквально в этом же абзаце
Я не знаю, что это, если не рекомендация :)
Спасибо за статьи! С интересом прочитал обе. Особенно понравился стиль изложения с постепенным усложнением решения и пояснениями, в каких случаях это будет оправдано.
Единственное — во второй версии пришлось заменить <> на `mappend`, в противном случае компиляция заканчивалась с ошибкой. Предполагаю, что в GHC 7.10.2, который используется в системе тестирования, ещё не было этого оператора в ByteString.Builder.
Не подскажите, что за приложение вы использовали для визуализации результатов профилирования?
Спасибо за комментарий! Да, я реализовывал подобный подход с посимвольным чтением входных данных. К сожалению, это не дало какого-либо прироста производительности. Единственное, чего удалось добиться с его помощью — еще большего уменьшения используемой памяти: для сортировки подсчётом и boxed-массивов на 19 тесте получаем 8.61Mb вместо 10.25Mb, а для unboxed 984.00Kb.
Конечно можно предположить, что мы таким образом хоть и выиграли на чтении, но получили просадку в производительности на существенном большем количестве вызовов функции accum, но считаю это маловероятным. Тоже самое я пробовал с IOArray, который такой функции не имеет, и при его использовании приходится в обоих случаях оперировать с отдельными элементами — результат получился аналогичным.
Остаётся ещё оптимизация вывода результата, но я пока ничего не придумал в этом направлении.
По-хорошему, мне необходимо разобраться с профилированием программ на Haskell, чтобы выяснить какая именно часть кода работает большую часть времени. Надеюсь, что смогу этим заняться в обозримом будущем.