[Haskell] Жуткие тормоза на простой задаче

nikola1956

Вчера начал изучать Haskell для общего развития, так как понравился красивый синтаксис языка по сравнению с другими функциональными языками программирования (Scala, Clojure, OCaml).
Решил написать тестовый модуль:


module PerfectNumbers where



isPerfect x = x == (divisorSum x) - x 



divisorSum x = sum [d  |  d  <-  [1..x],  x `mod` d  ==  0]

Загружаю этот модуль в командной строке Windows (предварительно установил на комп Haskell Platform):
 

Prelude> :load PerfectNumbers

Запускаю:


*PerfectNumbers> [x  |  x <- [1..5000],  isPerfect x]

Выдает:


[6,28,496]

Но работает больше минуты ! :ooo:
А в случае, когда вместо 5000 стоит 100000, использует больше гигабайта оперативной памяти и зависает более, чем на полчаса.
Не понятно, то ли я некорректно использую Haskell, то ли Haskell сам по себе тормозной, то ли сама идея функционального программирования (использовать неизменяемые области памяти и вообще свободнее тратить оперативную память) — ущербна для подобного рода "объемных" задач?

doublemother

Я эти ваши хаскелли не знаю, поэтому написал на окамле:
let range start stop =

    let rec range_ acc s = function

        | f when s = f -> s :: acc

        | x -> range_ (x :: acc) s (x-1) in

    if start < stop then range_ [] start stop else List.rev (range_ []

    stop start);;



let divisorSum x =

    let rec divisorSumAcc acc = function

        | 1 -> acc + 1

        | y -> divisorSumAcc (acc + if x mod y == 0 then y else 0) (y - 1) in

    divisorSumAcc 0 x;;



let isPerfect x = x == (divisorSum x) - x;;



List.filter isPerfect (range 1 5000);;

Ушло 0.515 секунды. Это без компиляции в нативный код. С ней — 0.157 секунды.
Для 100000 получается 3m16.936s и 1m1.231s соответственно.
Память не кушает от слова «совсем».
Выводы оставим нашим маленьким радиослушателям.

nikola1956

Ну этот алгоритм не такой короткий и прямолинейный, как у меня (13 строчек вместо трех). И, кажется, используется рекурсия. Можно попробовать реализовать подобное на Haskell-е и сравнить с Вашими результатами! :)

doublemother

Акей, переписал, чтобы было не по-людски, а как это у вас модно:
let (-->) start stop =

    let rec range_ acc s = function

        | f when s = f -> s :: acc 

        | x -> range_ (x :: acc) s (x-1) in

    if start < stop then range_ [] start stop else List.rev (range_ [] stop start);;



let divisorSum x = 

    let ssum y = if x mod y == 0 then y else 0 in

    List.fold_left (+) 0 (List.map ssum (1-->x;;



let isPerfect x = x == (divisorSum x) - x;;



List.filter isPerfect (1-->5000);;

Первая длинная функция нужна, потому что в окамле нет встроенного генератора списка.
Для 5000 стало:
- в байткоде 1.510с
- нативный код 0.311с
Хотя я не очень понимаю, чем хвостовая рекурсия не Ъ у реальных пацанов.

nikola1956

Для 5000 стало:
- в байткоде 1.510с
- нативный код 0.311с
Спасибо за ответ! :)
Свой код на Haskell я тоже переписал, в виде рекурсии (как у Вас но результаты стали еще хуже :o
Пока разбираюсь, в чем дело. Может быть я неправильно использую компилятор (GHC) или интерпретатор ... :confused:

matvey61

или интерпретатор ...
или ошибка в генетическом коде?

nikola1956

Для 5000 стало:
- в байткоде 1.510с
- нативный код 0.311с
Разобрался! Все тормоза были не из-за Haskell-а, а из-за его интерпретатора (ghci)!
Скомпилированный exe-файл для случая 5000 чисел выполняется меньше 10 секунд! :)
******
Весь Haskell-код состоит из двух файлов:
Main.hs 


module Main where

import PerfectNumbers



main  =  print ( perfList 5000 )

PerfectNumbers.hs 


perfList n = [x | x  <- [1..n],  isPerfect x]



isPerfect x  =  x == (divisorSum x) - x 



divisorSum x = sum [d | d  <- [1..x],  x `mod` d == 0]

А компиляция в PerfectNumbers.exe осуществляется так:


>ghc -o PerfectNumbers Main.hs

karkar

Включи оптимизацию!
Вот такой файл:
 
isPerfect x = x == (divisorSum x) - x 

divisorSum x = sum [d  |  d  <-  [1..x],  x `mod` d  ==  0]

perfList n = [x | x  <- [1..n],  isPerfect x]

main  =  print ( perfList 5000 )

Собранный командой
ghc -O2 pn.hs -o pn.exe
у меня отрабатывает за 0.55 секунды на ноуте с Core 2 Duo 2.0 GHz. GHC старый, 6.12.

karkar

Занятно, на Clean 2.3 аналогичный код:


module test

import StdEnv



isPerfect x = x == (divisorSum x) - x 

divisorSum x = sum [d  \\  d  <-  [1..x] | x rem d == 0]

perfList n = [x \\ x  <- [1..n] | isPerfect x]

Start = perfList 5000

отрабатывает за 0.13 секунды. И exe-шник всего 59 КБ против 907 КБ хаскельного.

karkar

Ну и до кучи вариант на окамле со списками:
open ExtLib

let nums x = List.init x +) 1)

let divisorSum x = List.fold_left (+) 0 (List.filter (fun d -> x mod d = 0) (nums x

let isPerfect x = x == (divisorSum x) - x

let perfList n = List.filter isPerfect (nums n);;

List.iter (Printf.printf "%d ") (perfList 5000);;

0.57 секунды, 393 КБ.
То же самое на Enum'aх (без создания списков в памяти):
let nums x = Enum.init x +) 1)

let divisorSum x = Enum.fold (+) 0 (Enum.filter (fun d -> x mod d = 0) (nums x

let isPerfect x = x == (divisorSum x) - x

let perfList n = Enum.filter isPerfect (nums n);;

Enum.iter (Printf.printf "%d ") (perfList 5000);;

0.25 секунды.

tokuchu

И exe-шник всего 59 КБ против 907 КБ хаскельного.
Тут сравнивать не совсем корректно, т.к. хаскель туда похоже много чего по умолчанию запихивает. Т.е. если код будет не 3 строчки, а 300, то хаскельный exe-шник в 100 раз не увеличится. Может местны тру-хаскел-хакеры знают как это уменьшить?

nikola1956

ghc -O2 pn.hs -o pn.exe
Попробовал так откомпилировать два файла (Main.hs и PerfectNumbers.hs). Получил те же 10 секунд для n = 5000. Но когда соединил два файла в один, тогда полученный при компиляции exe-шник отработал за 4 секунды на моем AMD Athlon 64 3000+. При этом 4 секунды получается для обоих способов компиляции (Вашего и моего).
Довольно странный результат. Может быть дело в отложенных вычислениях, которые воспринимаются компилятором в контексте только одного Haskell-модуля? Т.е. если в самом модуле написано: perfList 5000, то отложенные вычисления иначе влияют на работу программы?

karkar

[телепат-моде он]
Попробуй явно указать типы (Int'ы и их списки). Есть подозрение, что так он слишком обобщенный код генерит.

karkar

Тут сравнивать не совсем корректно, т.к. хаскель туда похоже много чего по умолчанию запихивает. Т.е. если код будет не 3 строчки, а 300, то хаскельный exe-шник в 100 раз не увеличится.
Совершенно верно, у хаскеля рантайм намного сложнее и оттого толще. У клина простой и большей частью написанный на асме (в частности, там два разных сборщика мусора, и каждый написан на нескольких разновидностях асма - под разные платформы). В 100 раз не увеличится, но в среднем GHC все равно намного жирнее генерит код. Бороться частично можно strip'ом, частично хитрой сборкой используемых библиотек.

nikola1956

Попробуй явно указать типы (Int'ы и их списки).
Здорово, спасибо! :)
Теперь для n = 5000 программа выполняется за 0,8 секунды !

apl13

Т.е. если код будет не 3 строчки, а 300, то хаскельный exe-шник в 100 раз не увеличится. Может местны тру-хаскел-хакеры знают как это уменьшить?
ghc -no-implicit-prelude

? :ooo:

matvey61

прогайте на фортране, компильте с O3 и будет вам счастие.

apl13

Панч-карты — выбор мужей! :bud:

matvey61

Панч-карты — выбор мужей!
не юродствуй, в отличие от панч-карт фортран вполне ок, да и код ifort с оптимизациями генерит реально быстрый.

apl13

Ну таки да.
Кто бы сомневался.
Вся история фортрана наталкивает на мысль о его скорости.
И о том, что программы сложнее интегрирования двумерной разностной схемы на нем писать отдает самоубийством.

matvey61

действительно, видимо поэтому:
http://www.msg.ameslab.gov/gamess/

karkar

Убедил, можешь запостить тут свое решение на фортране, только чур не больше 8 строк, а то уже не будет счастие.

zontik

Его решения, конечно, не подскажу, вот лобовая атака:
 
PROGRAM SAMPLE

INTEGER, DIMENSION (5000) :: a = (/(k,k=1,5000)/)

DO 6, I=1,5000

IF (SUM (a, MASK=MOD(I,a) == 0) - I == I) THEN

WRITE (*,'(I5)') I

END IF

6 CONTINUE

END

Компилировал gfortran, без оптимизаций
 
 -rwxrwxr-x  1 oks oks 28810 июля  15 21:34 a.out

Вот время:
 


perseus:~/work/Fortran$ /usr/bin/time -v ./a.out

    6

   28

  496

        Command being timed: "./a.out"

        User time (seconds): 0.15

        System time (seconds): 0.00

        Percent of CPU this job got: 98%

        Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.15

        Average shared text size (kbytes): 0

        Average unshared data size (kbytes): 0

        Average stack size (kbytes): 0

        Average total size (kbytes): 0

        Maximum resident set size (kbytes): 3488

        Average resident set size (kbytes): 0

        Major (requiring I/O) page faults: 0

        Minor (reclaiming a frame) page faults: 274

        Voluntary context switches: 1

        Involuntary context switches: 21

        Swaps: 0

        File system inputs: 0

        File system outputs: 0

        Socket messages sent: 0

        Socket messages received: 0

        Signals delivered: 0

        Page size (bytes): 4096

        Exit status: 0

Update: кажется, это фортран 90 получился, на 77 так не получится написать.

karkar

А с оптимизацией? (выше ключик -O3 предлагали) Без нее выигрыша не видно пока.

zontik

Ага, -О3 не влияет совсем, я сразу проверил, и -ffast-math, и real вместо int, и -fassociative-math.
Думаю, чудодейственность фортрана сильно преувеличена. Либо есть какой-то хак, про который я не в курсе.
Настоящие сварщики, может быть, скажут, что ifort надо использовать и OpenMP добавить.

matvey61

Что-то он медленно как-то считает, должно быть быстрее. то, что надо юзать именно ifort и распараллелить хотя бы в openmp инфа 100500%. а что за проц у тебя бтв?
БТВ, можно ничего не изобретать и не писать для этой задачи самому, ибо гугл выдает вполне себе уже готовый код.
Оставить комментарий
Имя или ник:
Комментарий: