Проблема производительности с проблемой Эйлера и рекурсия на типах Int64 - PullRequest
13 голосов
/ 30 апреля 2011

В настоящее время я изучаю 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). Согласно комментариям, проблема не возникает при компиляции под другими конфигурациями. Это заставляет меня думать, что в выпуске Windows тип Int64 не работает.

Ответы [ 6 ]

9 голосов
/ 30 апреля 2011

Хм, я установил свежую платформу 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.

7 голосов
/ 30 апреля 2011

Хм, это интересно.Поэтому я просто скомпилировал обе ваши программы и опробовал их:

% 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 секунд

Было бы интересно узнать, какую версию компилятора вы используете.

6 голосов
/ 30 апреля 2011

В вашем вопросе есть пара интересных вещей.

Вы должны использовать -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-битные аппаратные средства, если это возможно.

4 голосов
/ 30 апреля 2011

Обычный флаг оптимизации для соответствующего кода: -O2. То, что вы использовали, -O, делает очень мало. -O3 не делает ничего (вообще?) Больше, чем -O2 - он даже включал экспериментальные «оптимизации», которые часто делали программы заметно медленнее.

С -O2 я получаю конкурентоспособность с Java:

tommd@Mavlo:Test$ uname -r -m
2.6.37 x86_64
tommd@Mavlo:Test$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.0.3

tommd@Mavlo:Test$ ghc -O2 so.hs
[1 of 1] Compiling Main             ( so.hs, so.o )
Linking so ...
tommd@Mavlo:Test$ time ./so
843298604

real    0m4.948s
user    0m4.896s
sys     0m0.000s

И Java примерно на 1 секунду быстрее (20%):

tommd@Mavlo:Test$ time java ArcLength
843298604
3880

real    0m3.961s
user    0m3.936s
sys     0m0.024s

Но интересная вещь о GHC состоит в том, что у него много разных бэкэндов. По умолчанию он использует собственный генератор кода (NCG), который мы рассчитали выше. Есть также бэкэнд LLVM, который часто работает лучше ... но не здесь:

tommd@Mavlo:Test$ ghc -O2 so.hs -fllvm -fforce-recomp
[1 of 1] Compiling Main             ( so.hs, so.o )
Linking so ...
tommd@Mavlo: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 ...
tommd@Mavlo:Test$ time ./so
843298604

real    0m4.099s
user    0m4.088s
sys     0m0.000s

Есть также старый генератор "via-c", который использует C в качестве промежуточного языка. Это хорошо в этом случае:

tommd@Mavlo: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 ...
ttommd@Mavlo:Test$ ti
tommd@Mavlo:Test$ time ./so
843298604

real    0m3.982s
user    0m3.972s
sys     0m0.000s

Надеемся, что NCG будет улучшен, чтобы соответствовать via-c для этого случая, прежде чем они удалят этот бэкэнд.

2 голосов
/ 30 апреля 2011

dberg, я чувствую, что все это плохо началось с неудачного флага -O. Просто чтобы подчеркнуть мнение, сделанное другими, для обычной компиляции и тестирования, сделайте как я и вставьте это в свой .bashrc или что-то еще:

alias ggg="ghc --make -O2"
alias gggg="echo 'Glorious Glasgow for Great Good!' && ghc --make -O2 --fforce-recomp"
1 голос
/ 30 апреля 2011

Я немного поиграл с кодом, и эта версия, кажется, работает быстрее, чем версия Java на моем ноутбуке (3,55 с 4.63 с):

{-# 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
...