В вашем вопросе есть пара интересных вещей.
Вы должны использовать -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)
Взгляд в ядро
Мы быстро взглянем на ядро, с использованием ghc-core
,и он показывает очень хороший цикл распакованного типа:
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-битных целыхСначала попробуйте выполнить обновление до GHC 7.0.3, а затем попробуйте некоторые другие бэкэнды генератора кода, затем, если у вас все еще есть проблема с Int64
, отправьте отчет об ошибке в GHC trac.
В целом подтвердив, что ондействительно, это затраты на выполнение этих вызовов C в 32-битной эмуляции 64-битных целых, мы можем заменить Int64
на Integer
, который реализован с вызовами C к GMP на каждой машине, и, действительно, время выполнения увеличивается от 3 секунд доболее минуты.
Урок: используйте 64-битные аппаратные средства, если это возможно.