Проблема производительности с проблемой Эйлера и рекурсия на типах Int64
В настоящее время я изучаю Haskell, используя проблемы проекта Euler как свою игровую площадку.
Я был поражен тем, насколько медленными мои программы в 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);
}
}
EDIT: после обсуждений в комментариях я сделал som модификации кода Haskell и сделал некоторые тесты производительности. Сначала я изменил n на 2 ^ 29, чтобы избежать переполнения. Затем я попробовал 6 разных версий: с Int64 или Int и с bangs до либо 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.
Ответы
Ответ 1
Hm, я установил новую платформу Haskell с 7.0.3 и получил примерно следующее ядро для вашей программы (-ddump-simpl):
Main.$warcLength' =
\ (ww_s1my :: GHC.Prim.Int64#) (ww1_s1mC :: GHC.Prim.Int64#)
(ww2_s1mG :: GHC.Prim.Int64#) (ww3_s1mK :: GHC.Prim.Int64#) ->
case {__pkg_ccall ghc-prim hs_gtInt64 [...]
ww_s1my ww1_s1mC GHC.Prim.realWorld#
[...]
Итак, GHC понял, что он может распаковать целые числа, что хорошо. Но этот вызов hs_getInt64 выглядит подозрительно похожим на вызов C. Глядя на выход ассемблера (-ddump-asm), мы видим такие вещи, как:
pushl %eax
movl 76(%esp),%eax
pushl %eax
call _hs_gtInt64
addl $16,%esp
Таким образом, это очень похоже на то, что каждая операция в Int64 превращается в полномасштабный вызов C в бэкэнд. Очевидно, что это медленный процесс.
исходный код GHC.IntWord64, похоже, подтверждает, что: в 32-битной сборке (например, в настоящее время поставляемой с платформой), у вас будет только эмуляция через интерфейс FFI.
Ответ 2
Хм, это интересно. Поэтому я просто скомпилировал обе ваши программы и опробовал их:
% java -version
java version "1.6.0_18"
OpenJDK Runtime Environment (IcedTea6 1.8.7) (6b18-1.8.7-2~squeeze1)
OpenJDK 64-Bit Server VM (build 14.0-b16, mixed mode)
% javac ArcLength.java
% java ArcLength
843298604
6630
Итак около 6.6 секунд для решения Java. Далее идет ghc с некоторой оптимизацией:
% ghc --version
The Glorious Glasgow Haskell Compilation System, version 6.12.1
% ghc --make -O arc.hs
% time ./arc
843298604
./arc 12.68s user 0.04s system 99% cpu 12.718 total
Менее 13 секунд для ghc -O
Попытка с некоторой дополнительной оптимизацией:
% ghc --make -O3
% time ./arc [13:16]
843298604
./arc 5.75s user 0.00s system 99% cpu 5.754 total
С дополнительными флагами оптимизации решение haskell заняло менее 6 секунд
Было бы интересно узнать, какой компилятор версии вы используете.
Ответ 3
В вашем вопросе есть несколько интересных вещей.
Вы должны использовать -O2 в первую очередь. Это просто улучшит работу (в данном случае, идентифицируя и удаляя лень, которая все еще присутствует в версии -O).
Во-вторых, ваш Haskell не совсем такой же, как Java (он выполняет разные тесты и ветки). Как и в случае с другими, запуск кода на моем Linux-сервере приводит к примерно 6-секундному времени выполнения. Кажется хорошо.
Убедитесь, что он совпадает с Java
Одна идея: пусть буквальная транскрипция вашей Java, с тем же потоком управления, операциями и типами.
import Data.Bits
import Data.Int
loop :: Int -> Int
loop n = go 0 (n-1) 0 0
where
go :: Int -> Int -> Int -> Int -> Int
go x y acc norm2
| x <= y = case () of { _
| norm2 < 0 -> go (x+1) y acc (norm2 + 2*x + 1)
| norm2 > 2 * (n-1) -> go (x-1) (y-1) acc (norm2 + 2 - 2 * (x+y))
| otherwise -> go (x+1) y (acc+1) (norm2 + 2*x + 1)
}
| otherwise = acc
main = print $ loop (1 `shiftL` 30)
Peek at the core
Мы быстро рассмотрим Core, с помощью ghc-core, и он показывает очень хороший цикл unboxed type:
main_$s$wgo
:: Int#
-> Int#
-> Int#
-> Int#
-> Int#
main_$s$wgo =
\ (sc_sQa :: Int#)
(sc1_sQb :: Int#)
(sc2_sQc :: Int#)
(sc3_sQd :: Int#) ->
case <=# sc3_sQd sc2_sQc of _ {
False -> sc1_sQb;
True ->
case <# sc_sQa 0 of _ {
False ->
case ># sc_sQa 2147483646 of _ {
False ->
main_$s$wgo
(+# (+# sc_sQa (*# 2 sc3_sQd)) 1)
(+# sc1_sQb 1)
sc2_sQc
(+# sc3_sQd 1);
True ->
main_$s$wgo
(-#
(+# sc_sQa 2)
(*# 2 (+# sc3_sQd sc2_sQc)))
sc1_sQb
(-# sc2_sQc 1)
(-# sc3_sQd 1)
};
True ->
main_$s$wgo
(+# (+# sc_sQa (*# 2 sc3_sQd)) 1)
sc1_sQb
sc2_sQc
(+# sc3_sQd 1)
то есть все распаковываются в регистры. Этот цикл отлично выглядит!
И отлично работает (Linux/x86-64/GHC 7.03):
./A 5.95s user 0.01s system 99% cpu 5.980 total
Проверка asm
Мы также получаем разумную сборку, как хороший цикл:
Main_mainzuzdszdwgo_info:
cmpq %rdi, %r8
jg .L8
.L3:
testq %r14, %r14
movq %r14, %rdx
js .L4
cmpq $2147483646, %r14
jle .L9
.L5:
leaq (%rdi,%r8), %r10
addq $2, %rdx
leaq -1(%rdi), %rdi
addq %r10, %r10
movq %rdx, %r14
leaq -1(%r8), %r8
subq %r10, %r14
jmp Main_mainzuzdszdwgo_info
.L9:
leaq 1(%r14,%r8,2), %r14
addq $1, %rsi
leaq 1(%r8), %r8
jmp Main_mainzuzdszdwgo_info
.L8:
movq %rsi, %rbx
jmp *0(%rbp)
.L4:
leaq 1(%r14,%r8,2), %r14
leaq 1(%r8), %r8
jmp Main_mainzuzdszdwgo_info
Использование бэкэнда -fvia-C.
Итак, это выглядит отлично!
Мое подозрение, как упоминалось выше, имеет отношение к версии libgmp, которую вы имеете на 32-битной Windows, генерирующей плохой код для 64-битных int. Сначала попробуйте обновить до GHC 7.0.3, а затем попробуйте использовать некоторые другие компоненты генератора кода, а затем, если у вас все еще есть проблема с Int64, отправьте сообщение об ошибке в трафик GHC.
Широко подтверждая, что действительно стоит делать эти вызовы C в 32-разрядной эмуляции 64-битных int, мы можем заменить Int64 на Integer, который реализован с помощью C-вызовов GMP на каждой машине и действительно, время работы от 3 секунд до более чем минуты.
Урок: используйте 64-битное оборудование, если это вообще возможно.
Ответ 4
Нормальный флаг оптимизации для соответствующего кода -O2. То, что вы использовали, -O, очень мало. -O3 не делает много (никаких?) больше, чем -O2 - он даже использовал для включения экспериментальных "оптимизаций", которые часто делали программы заметно медленнее.
С -O2 я получаю конкурентоспособность по производительности Java:
[email protected]:Test$ uname -r -m
2.6.37 x86_64
[email protected]:Test$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.0.3
[email protected]:Test$ ghc -O2 so.hs
[1 of 1] Compiling Main ( so.hs, so.o )
Linking so ...
[email protected]:Test$ time ./so
843298604
real 0m4.948s
user 0m4.896s
sys 0m0.000s
И Java примерно на 1 секунду быстрее (20%):
[email protected]:Test$ time java ArcLength
843298604
3880
real 0m3.961s
user 0m3.936s
sys 0m0.024s
Но интересная вещь о GHC заключается в том, что у нее много разных сторон. По умолчанию он использует генератор собственных кодов (NCG), который мы поставили выше. Там также есть LLVM-сервер, который часто делает лучше... но не здесь:
[email protected]:Test$ ghc -O2 so.hs -fllvm -fforce-recomp
[1 of 1] Compiling Main ( so.hs, so.o )
Linking so ...
[email protected]:Test$ time ./so
843298604
real 0m5.973s
user 0m5.968s
sys 0m0.000s
Но, как упоминалось в комментариях FUZxxl, LLVM делает намного лучше, когда вы добавляете несколько аннотаций строгости:
$ ghc -O2 -fllvm -fforce-recomp so.hs
[1 of 1] Compiling Main ( so.hs, so.o )
Linking so ...
[email protected]:Test$ time ./so
843298604
real 0m4.099s
user 0m4.088s
sys 0m0.000s
Также существует старый генератор "via-c", который использует C как промежуточный язык. В этом случае это хорошо:
[email protected]:Test$ ghc -O2 so.hs -fvia-c -fforce-recomp
[1 of 1] Compiling Main ( so.hs, so.o )
on the commandline:
Warning: The -fvia-c flag will be removed in a future GHC release
Linking so ...
[email protected]:Test$ ti
[email protected]:Test$ time ./so
843298604
real 0m3.982s
user 0m3.972s
sys 0m0.000s
Надеемся, что NCG будет улучшен, чтобы соответствовать с-c для этого случая, прежде чем удалять этот сервер.
Ответ 5
dberg, я чувствую, что все это закончилось неудачным началом с неудачным флагом -O. Просто для того, чтобы подчеркнуть точку, сделанную другими, для компиляции и тестирования компиляции, сделайте, как я, и вставьте это в свой .bashrc или что-то еще:
alias ggg="ghc --make -O2"
alias gggg="echo 'Glorious Glasgow for Great Good!' && ghc --make -O2 --fforce-recomp"
Ответ 6
Я немного играл с кодом, и эта версия работает быстрее, чем версия Java на моем ноутбуке (3.55s против 4.63s):
{-# LANGUAGE BangPatterns #-}
arcLength :: Int->Int
arcLength n = arcLength' 0 (n-1) 0 0 where
arcLength' :: Int -> Int -> Int -> Int -> Int
arcLength' !x !y !norm2 !acc
| x > y = acc
| norm2 > 2*(n-1) = arcLength' (x - 1) (y - 1) (norm2 - 2*(x + y) + 2) acc
| norm2 < 0 = arcLength' (succ x) y (norm2 + x*2 + 1) acc
| otherwise = arcLength' (succ x) y (norm2 + 2*x + 1) (acc + 1)
main = print $ arcLength (2^30)
:
$ ghc -O2 tmp1.hs -fforce-recomp
[1 of 1] Compiling Main ( tmp1.hs, tmp1.o )
Linking tmp1 ...
$ time ./tmp1
843298604
real 0m3.553s
user 0m3.539s
sys 0m0.006s
