Haskell - эффективный эквивалент цикла for?

Question

Я проводил несколько экспериментов, и вот что я нашел.Рассмотрим следующую программу на C:

int main()
{
   for(int i = 0;
       i < 1000000;
       ++i)
   {}
}

и следующую программу на Haskell:

import System.IO

loop :: Int -> IO ()
loop n = if 0 == n then return () else loop (n-1)

main = loop 1000000

Вот вывод time для вышеуказанной программы на C:

real    0m0.003s
user    0m0.000s
sys 0m0.000s

... и для программы на Haskell:

real    0m0.028s
user    0m0.027s
sys 0m0.000s

Сначала я подумал, что gcc обнаружил пустой цикл и оптимизировал его, но после увеличения количества итераций время выполнения программытакже увеличилось.Вот выходные данные time для обеих программ с числом итераций, установленным на 10000000:

C версия

real    0m0.024s
user    0m0.023s
sys 0m0.000s

Версия Haskell

real    0m0.245s
user    0m0.247s
sys 0m0.000s

Как видите, программа на Haskell работает в 10 раз медленнее.

Вопрос: какова эффективная альтернатива циклу for в Haskell?Как мы только что видели, простая рекурсия замедляет программу примерно в 10 раз (и это, вероятно, с выполненной оптимизацией хвостовой рекурсии).

Answer 1

Во-первых, вы бы перевели свой код C на это,

main = go 0
    where
        go :: Int -> IO ()
        go i | i < 1000000 = go (i+1)
             | otherwise   = return ()

, который ghc оптимизирует для пустой программы. Он перемещает окончательное значение в регистр, сравнивает его и возвращает ():

Main_zdwa_info: 
    cmpq    $1000000, %r14          # imm = 0xF4240
    movl    $1000000, %eax          # imm = 0xF4240
    cmovlq  %rax, %r14
    movq    (%rbp), %rax
    movl    $ghczmprim_GHCziUnit_Z0T_closure+1, %ebx
    jmpq    *%rax  # TAILCALL

который при запуске:

$ time ./A
./A  0.00s user 0.00s system 88% cpu 0.004 total

не занимает много времени.

---

В общем, однако, GHC испускает эквивалентных циклов, например, GCC , для хвостовых рекурсивных функций. В частности, вы захотите скомпилировать числовые тесты с ghc -O2 -fllvm для достижения наилучших результатов Если вы не хотите, чтобы ваши программы были оптимизированы, то ghc с радостью выполнит именно ту программу, которую вы укажете, что в данном случае потребует много лишней работы, которая будет удалена на более высоких уровнях оптимизации.

Для получения дополнительной информации об анализе низкоуровневой производительности программ на Haskell, проверьте RWH ch25.

Answer 2

Для циклических конструкций вам часто приходится писать в стиле Worker / Wrapper, чтобы помочь GHC находить оптимизации, а не повторяться на уровне внешних функций.

Григорий Джавадян сказал в комментарии, что оригинальная версия оптимизирована на -O3, я ожидаю, что эта версия будет обнаружена на -O2:

import System.IO

loop :: Int -> IO ()
loop n = go n
  where
    go n | n <= 0 = return ()
    go n          = go (n-1)

main = loop 1000000