Рассуждение о производительности в Хаскеле

Question

Следующие две программы на Haskell для вычисления n-го члена последовательности Фибоначчи имеют очень разные характеристики производительности:

fib1 n =
  case n of
    0 -> 1
    1 -> 1
    x -> (fib1 (x-1)) + (fib1 (x-2))

fib2 n = fibArr !! n where
  fibArr = 1:1:[a + b | (a, b) <- zip fibArr (tail fibArr)]

Они очень близки к математически идентичным, но fib2 использует нотацию списка для запоминания промежуточных результатов, тогда как fib1 имеет явную рекурсию. Несмотря на возможность кэширования промежуточных результатов в fib1, время выполнения становится проблемой даже для fib1 25, предполагая, что рекурсивные шаги всегда оцениваются. Вносит ли ссылочная прозрачность что-либо в производительность Haskell? Как я могу знать заранее, будет ли это или нет?

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

---

Резюме: Я принимаю ответ 3lectrologos, потому что тот момент, что вы не столько рассуждаете о производительности языка, сколько об оптимизации вашего компилятора, кажется чрезвычайно важным в Haskell - тем более чем на любом другом языке, с которым я знаком. Я склонен сказать, что важность компилятора является фактором, который отличает рассуждения о производительности в ленивых, функциональных языках от рассуждений о производительности любого другого типа.

---

Приложение: Любой, кто встречается по этому вопросу, может захотеть посмотреть слайды из Йохан Тибелл поговорить о высокой производительности Haskell .

Answer 1

В вашем конкретном примере Фибоначчи не очень трудно понять, почему второй должен работать быстрее (хотя вы не указали, что такое f2).

Это в основном алгоритмическая проблема:

• fib1 реализует чисто рекурсивный алгоритм и (насколько я знаю) у Haskell нет механизма "неявного запоминания".
• fib2 использует явное запоминание (используя список fibArr для хранения ранее вычисленных значений.

В общем, гораздо сложнее сделать предположения о производительности для ленивого языка, такого как Haskell, чем для энергичного. Тем не менее, если вы поймете лежащие в основе механизмы (особенно для лени) и наберете некоторый опыт , вы сможете сделать некоторые "предсказания" о производительности.

Ссылочная прозрачность повышает (потенциально) производительность (как минимум) двумя способами:

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

Если вы хотите больше узнать о причинах выбора дизайна (лень, чистота) в Haskell, я бы предложил прочитать это .

Answer 2

В Хаскеле и ленивых языках вообще сложно рассуждать о производительности, хотя и не невозможно. Некоторые приемы описаны в структурах данных Purely Function Криса Окасаки (также доступна онлайн в предыдущей версии).

Другим способом обеспечения производительности является исправление порядка оценки, используя аннотации или стиль передачи продолжения . Таким образом, вы получаете контроль, когда все оценивается.

В вашем примере вы можете вычислить числа «снизу вверх» и передать два предыдущих числа для каждой итерации:

fib n = fib_iter(1,1,n)
    where
      fib_iter(a,b,0) = a
      fib_iter(a,b,1) = a
      fib_iter(a,b,n) = fib_iter(a+b,a,n-1)

В результате получается алгоритм линейного времени.

Всякий раз, когда у вас есть алгоритм динамического программирования, где каждый результат опирается на N предыдущих результатов, вы можете использовать эту технику. В противном случае вам, возможно, придется использовать массив или что-то совершенно другое.

Answer 3

Ваша реализация fib2 использует мемоизацию, но каждый раз, когда вы вызываете fib2, она перестраивает «весь» результат. Включите профилирование времени и размера ghci:

Prelude> :set +s

Если бы он делал запоминание «между» вызовами, последующие вызовы были бы быстрее и не использовали бы память. Позвоните на номер 2 20000 и убедитесь сами.

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

-- the infinite list of all fibs numbers.
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

memoFib n = fibs !! n

на самом деле используют запоминание, как вы видите. Если вы запустите memoFib 20000 дважды, вы увидите время и пространство, занятое в первый раз, тогда второй вызов будет мгновенным и не займет память. Никакая магия и никакие скрытые воспоминания, такие как комментарий, не могли бы намекать.

Теперь о вашем первоначальном вопросе: оптимизация и рассуждения о производительности в Haskell ...

Я бы не назвал себя экспертом в Haskell, я использую его только 3 года, 2 из которых на своем рабочем месте, но мне все же пришлось оптимизировать и понять, как рассуждать о его производительности.

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

Проверьте это сравнение foldl против foldr

foldl на самом деле хранит «как» вычислить значение, то есть оно лениво. В некоторых случаях вы экономите время и пространство, будучи ленивыми, как «бесконечные» выдумки. Бесконечные "выдумки" не генерируют их все, но знают как. Когда вы знаете, что вам понадобится значение, вы можете просто получить его «строго», говоря… Вот где аннотации строгости полезны, чтобы вернуть вам контроль.

Я вспоминаю, что читал много раз, что в lisp вы должны "минимизировать" потребление.

Понимание того, что строго оценивается и как заставить это сделать, важно, но так же важно понимать, сколько «мусора» вы делаете для памяти. Помните, что Haskell является неизменным, это означает, что обновление «переменной» фактически создает копию с модификацией. Добавление с (:) значительно эффективнее, чем с (++), потому что (:) не копирует память в противоположность (++). Всякий раз, когда обновляется большой атомарный блок (даже для одного символа), весь блок должен быть скопирован для представления «обновленной» версии. То, как вы структурируете данные и обновляете их, может сильно повлиять на производительность. Профилировщик GHC ваш друг и поможет вам определить их. Конечно, сборщик мусора работает быстро, но если он не работает, то быстрее!

Приветствия

Answer 4

Помимо проблемы с запоминанием, fib1 также использует рекурсию без разговора. Рекурсию Tailcall можно автоматически преобразовать в простое goto и выполнить очень хорошо, но рекурсия в fib1 не может быть оптимизирована таким образом, потому что вам нужен стековый фрейм из каждого экземпляра fib1 для вычисления результата. Если вы переписали fib1 для передачи промежуточного итога в качестве аргумента, что позволило бы использовать хвостовой вызов вместо необходимости сохранять фрейм стека для окончательного добавления, производительность значительно улучшится. Но не так много, как запоминающийся пример, конечно:)

Answer 5

Поскольку распределение является основным расходом на любом функциональном языке, важной частью понимания производительности является понимание того, когда объекты распределяются, как долго они живут, когда они умирают и когда они возвращаются. Чтобы получить эту информацию, вам нужен heap profiler . Это важный инструмент, и, к счастью, GHC поставляется с хорошим.

Для получения дополнительной информации читайте документы Колина Рансимана .