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

Следующая программа вдохновлена ​​проблемой 331, но я изменил ее перед публикацией, чтобы ничего не испортить другим людям. Он вычисляет длину дуги дискретного круга, нарисованного на сетке 2 ^ 30 x 2 ^ 30. Это простая хвостовая рекурсивная реализация, и я удостоверяюсь, что обновления переменной накопления, отслеживающие длину дуги, являются строгими. Тем не менее, это занимает почти полторы минуты (скомпилировано с флагом -O с помощью ghc).

import Data.Int

arcLength :: Int64->Int64
arcLength n = arcLength' 0 (n-1) 0 0 where
    arcLength' x y norm2 acc
        | x > y = acc
        | norm2 < 0 = arcLength' (x + 1) y (norm2 + 2*x +1) acc
        | norm2 > 2*(n-1) = arcLength' (x - 1) (y-1) (norm2 - 2*(x + y) + 2) acc
        | otherwise = arcLength' (x + 1) y (norm2 + 2*x + 1) $! (acc + 1)

main = print $ arcLength (2^30)

Вот соответствующая реализация в Java. Это займет около 4,5 секунд.

public class ArcLength {
public static void main(String args[]) {
    long n = 1 << 30;
    long x = 0;
    long y = n-1;
    long acc = 0;
    long norm2 = 0;
    long time = System.currentTimeMillis();

    while(x <= y) {
        if (norm2 < 0) {
            norm2 += 2*x + 1;
            x++;
        } else if (norm2 > 2*(n-1)) {
            norm2 += 2 - 2*(x+y);
            x--;
            y--;
        } else {
            norm2 += 2*x + 1;
            x++;
            acc++;
        }
    }

    time = System.currentTimeMillis() - time;
    System.err.println(acc);
    System.err.println(time);
}

}

РЕДАКТИРОВАТЬ: После обсуждений в комментариях я сделал некоторые изменения в коде Haskell и сделал несколько тестов производительности. Сначала я изменил на 2 ^ 29, чтобы избежать переполнения. Затем я попробовал 6 разных версий: с Int64 или Int и с грохотом перед norm2 или обоими и norm2 и acc в объявленииarcLength' x y !norm2 !acc, Все скомпилированы с

ghc -O3 -prof -rtsopts -fforce-recomp -XBangPatterns arctest.hs

Вот результаты:

(Int !norm2 !acc)
total time  =        3.00 secs   (150 ticks @ 20 ms)
total alloc =       2,892 bytes  (excludes profiling overheads)

(Int norm2 !acc)
total time  =        3.56 secs   (178 ticks @ 20 ms)
total alloc =       2,892 bytes  (excludes profiling overheads)

(Int norm2 acc)
total time  =        3.56 secs   (178 ticks @ 20 ms)
total alloc =       2,892 bytes  (excludes profiling overheads)

(Int64 norm2 acc)
arctest.exe: out of memory

(Int64 norm2 !acc)
total time  =       48.46 secs   (2423 ticks @ 20 ms)
total alloc = 26,246,173,228 bytes  (excludes profiling overheads)

(Int64 !norm2 !acc)
total time  =       31.46 secs   (1573 ticks @ 20 ms)
total alloc =       3,032 bytes  (excludes profiling overheads)

Я использую GHC 7.0.2 под 64-битной Windows 7 (бинарный дистрибутив платформы Haskell). Согласно комментариям, проблема не возникает при компиляции под другими конфигурациями. Это заставляет меня думать, что тип Int64 сломан в выпуске Windows.