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

Я делал несколько экспериментов, и вот что я нашел. Рассмотрим следующую программу 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 раз (и это, вероятно, с помощью оптимизации хвостовой рекурсии).

Ответы

Ответ 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.

Ответ 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