В настоящее время я изучаю 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 и провел несколько тестов производительности. Сначала я изменил n на 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.
arcLength' x y !norm2 !acc?norm2иaccне всегда передаются строго, потому что они могут не понадобиться при выполнении первой ветви. Кстати, на моей машине это занимает всего 6 секунд. - person fuz schedule 30.04.2011-O2- типичный флаг для оптимизации GHC. -O не делает слишком много, iirc. - person Thomas M. DuBuisson schedule 30.04.2011Int64) в 32-битной Windows. Можете ли вы обновитьlibgmp, обновить GHC до 7.0.3 или протестировать на 64-битной Windows? - person Don Stewart schedule 30.04.2011