Инструменты для анализа производительности программы на Haskell

Question

Решая некоторые задачи Project Euler для изучения Haskell (так что в настоящее время я полностью новичок), я подошел к Задача 12 .Я написал это (наивное) решение:

--Get Number of Divisors of n
numDivs :: Integer -> Integer
numDivs n = toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2

--Generate a List of Triangular Values
triaList :: [Integer]
triaList =  [foldr (+) 0 [1..n] | n <- [1..]]

--The same recursive
triaList2 = go 0 1
  where go cs n = (cs+n):go (cs+n) (n+1)

--Finds the first triangular Value with more than n Divisors
sol :: Integer -> Integer
sol n = head $ filter (\x -> numDivs(x)>n) triaList2

Это решение для n=500 (sol 500) чрезвычайно медленное (работает более 2 часов), поэтому я удивился, как выяснить, почему это решениетак медленно.Существуют ли какие-либо команды, которые сообщают мне, на что тратится большая часть времени вычислений, чтобы я знал, какая часть моей программы на haskell медленная?Что-то вроде простого профилировщика.

Чтобы прояснить ситуацию, я не прошу о более быстром решении, а о способе найти это решение.Как начать, если у вас нет знаний по haskell?

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

Спасибо

Answer 1

как узнать, почему это решение так медленно. Есть ли какие-либо команды, которые сообщают мне, на что тратится большая часть времени вычислений, поэтому я знаю, какая часть моей программы на haskell медленная?

Точно! GHC предоставляет много отличных инструментов, в том числе:

• статистика времени выполнения
• профилирование времени
• профилирование кучи
• анализ потока
• анализ керна.
• сравнительный бенчмаркинг
• настройка ГХ

Учебник по использованию профилирования времени и пространства является частью части Real World Haskell .

GC Статистика

Во-первых, убедитесь, что вы компилируете с помощью ghc -O2. И вы можете убедиться, что это современный GHC (например, GHC 6.12.x)

Первое, что мы можем сделать, это проверить, что сборка мусора не является проблемой. Запустите вашу программу с помощью + RTS -s

$ time ./A +RTS -s
./A +RTS -s 
749700
   9,961,432,992 bytes allocated in the heap
       2,463,072 bytes copied during GC
          29,200 bytes maximum residency (1 sample(s))
         187,336 bytes maximum slop
               **2 MB** total memory in use (0 MB lost due to fragmentation)

  Generation 0: 19002 collections,     0 parallel,  0.11s,  0.15s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time   13.15s  ( 13.32s elapsed)
  GC    time    0.11s  (  0.15s elapsed)
  RP    time    0.00s  (  0.00s elapsed)
  PROF  time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time   13.26s  ( 13.47s elapsed)

  %GC time       **0.8%**  (1.1% elapsed)

  Alloc rate    757,764,753 bytes per MUT second

  Productivity  99.2% of total user, 97.6% of total elapsed

./A +RTS -s  13.26s user 0.05s system 98% cpu 13.479 total

Что уже дает нам много информации: у вас всего 2M кучи, а GC занимает 0,8% времени. Поэтому не нужно беспокоиться о том, что распределение - это проблема.

Профили времени

Получение профиля времени для вашей программы очень просто: скомпилируйте с -prof -auto-all

 $ ghc -O2 --make A.hs -prof -auto-all
 [1 of 1] Compiling Main             ( A.hs, A.o )
 Linking A ...

А, для N = 200:

$ time ./A +RTS -p                   
749700
./A +RTS -p  13.23s user 0.06s system 98% cpu 13.547 total

, который создает файл A.prof, содержащий:

    Sun Jul 18 10:08 2010 Time and Allocation Profiling Report  (Final)

       A +RTS -p -RTS

    total time  =     13.18 secs   (659 ticks @ 20 ms)
    total alloc = 4,904,116,696 bytes  (excludes profiling overheads)

COST CENTRE          MODULE         %time %alloc

numDivs            Main         100.0  100.0

Указывает, что все ваше время тратится в numDivs, а также является источником всех ваших выделений.

Профили кучи

Вы также можете получить разбивку этих распределений, запустив + RTS -p -hy, который создает A.hp, который вы можете просмотреть, преобразовав его в файл postscript (hp2ps -c A.hp), производящая:

, который говорит нам, что нет ничего плохого в использовании вашей памяти: она размещается в постоянном пространстве.

Итак, ваша проблема в алгоритмической сложности numDivs:

toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2

Исправьте это, что составляет 100% вашего времени работы, а все остальное легко.

Оптимизация

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

numDivs n = fromIntegral $
    2 + (U.length $
        U.filter (\x -> fromIntegral n `rem` x == 0) $
        (U.enumFromN 2 ((fromIntegral n `div` 2) + 1) :: U.Vector Int))

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

Проверка этого, ghc -O2 - сделать Z.hs

$ time ./Z     
749700
./Z  3.73s user 0.01s system 99% cpu 3.753 total

Таким образом, он уменьшил время выполнения для N = 150 в 3,5 раза, не изменяя сам алгоритм.

Заключение

Ваша проблема в numDivs. Это 100% вашего времени работы и имеет ужасную сложность. Подумайте о numDivs и о том, как, например, для каждого N вы генерируете [2 .. n div 2 + 1] N раз. Попробуйте запомнить это, поскольку значения не меняются.

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

---

Addenda

Поскольку numDivs составляет 100% вашего времени работы, прикосновение к другим частям программы не будет иметь большого значения, однако в педагогических целях мы также можем переписать те, которые используют потоковое слияние.

Мы также можем переписать trialList и положиться на fusion, чтобы превратить его в цикл, который вы пишете вручную в trialList2, которая является функцией «сканирования префиксов» (она же scanl):

triaList = U.scanl (+) 0 (U.enumFrom 1 top)
    where
       top = 10^6

Аналогично для sol:

sol :: Int -> Int
sol n = U.head $ U.filter (\x -> numDivs x > n) triaList

С таким же общим временем выполнения, но немного более чистым кодом.

Answer 2

Ответ Дона великолепен, не будучи спойлером, поскольку дает прямое решение проблемы.
Здесь я хочу предложить небольшой инструмент , который я недавно написал.Это экономит ваше время для написания аннотаций SCC вручную, когда вам нужен более подробный профиль, чем по умолчанию ghc -prof -auto-all.Кроме того, он красочный!

Вот пример с кодом, который вы дали (*), зеленый в порядке, красный медленный:

Все время уходит на создание списка делителей,Это предлагает несколько вещей, которые вы можете сделать:
1. Ускорьте фильтрацию n rem x == 0, но поскольку это встроенная функция, возможно, она уже быстра.
2. Создайте более короткий список.Вы уже сделали что-то в этом направлении, проверив только до n quot 2.
3. Полностью отбросьте генерацию списка и используйте некоторую математику, чтобы получить более быстрое решение.Это обычный способ решения задач Эйлера.

(*) Я получил это, поместив ваш код в файл с именем eu13.hs, добавив основную функцию main = print $ sol 90.Затем выполняется visual-prof -px eu13.hs eu13, а результат - eu13.hs.html.

Answer 3

Примечание, связанное с Haskell: triaList2, конечно, быстрее, чем triaList, потому что последний выполняет много ненужных вычислений. Для вычисления n первых элементов triaList потребуется квадратичное время, но для triaList2 - линейное. Существует еще один элегантный (и эффективный) способ определения бесконечного ленивого списка номеров треугольников:

triaList = 1 : zipWith (+) triaList [2..]

Примечание по математике: нет необходимости проверять все делители до n / 2, достаточно проверить до sqrt (n).

Answer 4

Вы можете запустить вашу программу с флагами, чтобы включить профилирование времени. Примерно так:

./program +RTS -P -sprogram.stats -RTS

Это должно запустить программу и создать файл с именем program.stats, в котором будет указано, сколько времени было потрачено на каждую функцию Дополнительную информацию о профилировании с помощью GHC вы можете найти в руководстве пользователя GHC . Для бенчмаркинга есть библиотека Criterion. Я нашел в этом блоге есть полезное введение.