?

Log in

Базовые операции над списками в Хаскелле и F# - Лямбда - функциональное программирование [entries|archive|friends|userinfo]
Лямбда - функциональное программирование

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Базовые операции над списками в Хаскелле и F# [Mar. 10th, 2007|03:02 pm]
Лямбда - функциональное программирование

ru_lambda

[geniepro]
Решил я сравниить, с какой скоростью работают основные операции над списками в Хаскелле и F#.
В-общем, сделал я простенькие функции, которые просто копируют входной список:

F# :
let rec dummy (ls : int list) : int list = 
	match ls with
	|  []   ->  []
	| x::xs -> x::(dummy (dummy xs))

let rec dummy2 (ls : int list) : int list = 
	let rec dum w ys = 
		match ys with
		|  []   -> w
		| x::xs -> dum (w@[x]) (dummy2 xs)
	in  dum [] ls

Haskell :
dummy :: [Int] -> [Int]
dummy   []   = []
dummy (x:xs) = x:dummy (dummy xs)

dummy2 :: [Int] -> [Int]
dummy2 = dum []
  where
    dum w   []   = w
    dum w (x:xs) = dum (w++[x]) (dummy2 xs)

И пропустил через эти функции простые списки целых чисел [1..23] .. [1..25].
Забавные результаты получил:
                  [1..23]    [1..24]    [1..25]
F#       dummy    0.6 sec    1.3 sec    2.6 sec
F#       dummy2   1.2 sec    2.4 sec    4.7 sec

Haskell  dummy   16.5 sec     swap       swap
Haskell  dummy2   1.7 sec    3.4 sec    6.8 sec

То, что эти функции соответствуют своим названиям - и так ясно. Никому в здравом уме не придёт в голову их специально делать, но тем не менее мало ли как получится...

Но вот мне любопытно - более продвинутый вариант (dummy2) на Хаскелле, как и ожидалось, выполняется гораздо быстрее (на порядок), а вот на F# - в два раза медленнее...
Почему так?

И самое главное, хотя dummy2 на Хаскелле выполняется всего в 1.4 раза медленнее, чем на F# (что весьма неплохо для лентяя Хаскелла), но dummy на Хаскелле работает просто катастрофически медленно, тогда как на F# - очень даже хорошо...
Почему? В чём дело?

И как бороться с такими случаями? Ведь наверняка иногда вынужденно будет получаться что-то типа dummy на Хаскелле...
linkReply

Comments:
[User Picture]From: thesz
2007-03-10 10:29 am (UTC)
dummy3 :: [Int] -> [Int]
dummy3 = dum []
  where
    dum w   []   = reverse w
    dum w (x:xs) = dum (x:w) (dummy3 xs)
Про скорость операций со списками хорошо расписано в Haskell Wiki.

Например, почему нельзя делать w++[x]. ;)

Кстати, результаты:
*Main> dummy [1..21]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]
(16.97 secs, 157120860 bytes)
*Main> dummy2 [1..21]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]
(2.42 secs, 151470452 bytes)
*Main> dummy3 [1..21]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]
(1.78 secs, 84642856 bytes)
*Main>
(Reply) (Thread)
[User Picture]From: geniepro
2007-03-10 11:26 am (UTC)

Мдя, потрясно.

Вариант dummy3 на F#
let rec dummy3 (ls : int list) : int list = 
	let rec dum w ys = 
		match ys with
		|  []   -> List.rev w
		| x::xs -> dum (x::w) (dummy3 xs)
	in  dum [] ls

работает теперь чуть медленнее, чем он же на Хаскелле ([1..25] 5.0 сек F#, 4.9 сек Хаскелл).
И как это понимать? :о))
Видимо, GHC затачивали именно под такие варианты функций...

> Про скорость операций со списками хорошо расписано в Haskell Wiki.
> Например, почему нельзя делать w++[x]. ;)

Да я знаю, что это нехорошая мысль, но тем не менее решил проверить...

Тем не менее остаётся непонятным, почему самый ужастный вариант (dummy) так отлично отрабатывает на F#...
(Reply) (Parent) (Thread)
From: ex_soundwell971
2007-03-10 11:56 am (UTC)

Re: Мдя, потрясно.

Надо полагать, в ФШарповском компайлере есть распознавание и протачивание подобных вещей более эффективным, нежели ваш, способом.

А dummy2 с dummy3 несколько сложнее, вот компайлер и не может их вытянуть.
(Reply) (Parent) (Thread)
[User Picture]From: thesz
2007-03-10 02:50 pm (UTC)

Re: Мдя, потрясно.

Кстати, у меня некомпилированный код.

Мало ли, как это все ghc соптимизит...

Поэтому это не ghc затачивали, это язык так устроен. ;)

Кстати, вот с ключом оптимизации -O3:
Prelude Main> dummy [1..21]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]
(6.58 secs, 240431144 bytes)
Prelude Main> dummy2 [1..21]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]
(2.48 secs, 176560184 bytes)
Prelude Main> dummy3 [1..21]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]
(1.83 secs, 92583784 bytes)
Prelude Main>
(Reply) (Parent) (Thread)
[User Picture]From: thesz
2007-03-10 03:00 pm (UTC)

Re: Мдя, потрясно.

Для энергичного языка первый вариант самый лучший. Там сплошные вызовы функций, которые в энергичном функциональном языке весьма дешевы.
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]From: thesz
2011-02-02 08:49 pm (UTC)
Комментарий выше - спам.
(Reply) (Parent) (Thread)
[User Picture]From: dying_sphynx
2007-03-11 07:37 pm (UTC)
Простите за некоторый оффтопик, но как вы сделали, чтобы так вот время и память выводились? :) Что-то man ghci пока ничего мне не дал...
Спасибо!
(Reply) (Parent) (Thread)
[User Picture]From: thesz
2007-03-11 09:48 pm (UTC)
Сейчас-сейчас:
Prelude> :?
 Commands available from the prompt:

   <stmt>                      evaluate/run 
   :add <filename> ...         add module(s) to the current target set
   :browse [*]<module>         display the names defined by 
   :cd <dir>                   change directory to 
   :def <cmd> <expr>           define a command :
   :help, :?                   display this list of commands
   :info [<name> ...]          display information about the given names
   :load <filename> ...        load module(s) and their dependents
   :module [+/-] [*]<mod> ...  set the context for expression evaluation
   :reload                     reload the current module set

   :set <option> ...           set options
   :set args <arg> ...         set the arguments returned by System.getArgs
   :set prog <progname>        set the value returned by System.getProgName

   :show modules               show the currently loaded modules
   :show bindings              show the current bindings made at the prompt

   :type <expr>                show the type of 
   :kind <type>                show the kind of 
   :undef <cmd>                undefine user-defined command :
   :unset <option> ...         unset options
   :quit                       exit GHCi
   :!<command>                 run the shell command 

 Options for ':set' and ':unset':

    +r            revert top-level expressions after each evaluation
    +s            print timing/memory stats after each evaluation
    +t            print type after evaluation
    -<flags>      most GHC command line flags can also be set here
                         (eg. -v2, -fglasgow-exts, etc.)
Prelude>
Соответственно, ":se +s" ;)
(Reply) (Parent) (Thread)
[User Picture]From: dying_sphynx
2007-03-11 09:53 pm (UTC)
Да, провтыкал :)
Спасибо ещё раз, пригодится!
(Reply) (Parent) (Thread)
From: eraplee
2007-04-04 09:20 pm (UTC)
а как это вы заставляете ghci время выполнения отображать? :)
(Reply) (Parent) (Thread)
[User Picture]From: thesz
2007-04-04 09:47 pm (UTC)
Я ему говорю ":se +s" ;)
(Reply) (Parent) (Thread)
From: eraplee
2007-04-04 09:49 pm (UTC)
большое спасибо ! :)
(Reply) (Parent) (Thread)
From: ex_ex_zhuzh
2007-03-10 10:33 am (UTC)
мне непонятно, как и что вы измеряли. если бы мне нужно было замерить производительность операции копирования списка, я бы использовал map id. это базовая операция копирования. а dummy [1..23] у меня приводит к stack space overflow при размере стека 64 мегабайта. никакая базовая операция к переполнению стека приводить не должна. если у меня в реальной программе встретится переполнение стека, я его буду нещадно уничтожать, а не измерять его производительность.
(Reply) (Thread)
[User Picture]From: geniepro
2007-03-10 11:36 am (UTC)
Да меня просто интересовало, как работают операции разбиения списков на голову и хвост, и как потом они собираются.
А dummy [1..23] я запускал со стеком около 100 метров (ключ +RTS -K100000000 )
Алгоритмы я специально такие запущенные выбрал. что бы на маленьких списках долго работали... :о))
(Reply) (Parent) (Thread)
[User Picture]From: thesz
2007-03-10 03:00 pm (UTC)
+RTS -K100M ;)
(Reply) (Parent) (Thread)
[User Picture]From: justbulat
2007-03-10 10:03 pm (UTC)
ошибаешься. никаких операций у тебя не получилось, ты просто создал кучу вложенных вызовов в стёке. я стриктизировал код - вот теперь он, возможно, делает то, что ты имел в виду. вообще, надо иметь в виду, что ленивые вычисления работают совсем иначе. считай, что в памяти есть огромный граф, представляющий вычисление, необходимое для получения твоего ответа. все замены в этом графе происходят согласно твоим определениям функций, их левые части заменяются на соответствующие правые. а управляет порядком замен (т.е. порядком вычислений) нужда. пока не возникнет нужды, ни одна подстановка производиться не будет. seq - это такой искусственный оператор, значением которого является правая часть, но прежде чем её возвратить, он требует вычисления верхнего уровня своей правой части, тем самым изменяя порядок вычислений. соответственно, его часто используют для оптимизации, когда программист знает, что в вычисленном виде значение займёт меньше места в памяти, нежели в в виде исходной формулы
(Reply) (Parent) (Thread)
From: ex_soundwell971
2007-03-10 10:51 am (UTC)
Рискну предположить, что Хаскель и ФШарп по разному оптимизируют и реализуют вложенные функции.
(Reply) (Thread)
[User Picture]From: geniepro
2007-03-10 11:43 am (UTC)
Вапще какая-то непонятка с этим Фшарпом - чем правильнее алгоритм, тем он медленнее работает. Чё за лажа?
(Reply) (Parent) (Thread)
From: ex_soundwell971
2007-03-10 11:52 am (UTC)
А что такое "правильный алгоритм"? ;-)
(Reply) (Parent) (Thread)
[User Picture]From: geniepro
2007-03-10 08:06 pm (UTC)
Ну, типа, функция с хвостовой рекурсией - более оптимальный алгоритм, чем та же самая, но без хвостовой рекурсии.
Варианты на F# нарушают эту древнюю истину! :о(
(Reply) (Parent) (Thread)
[User Picture]From: palm_mute
2007-03-10 08:43 pm (UTC)
В ленивом языке не все так однозначно. Функция без хвостовой рекурсии чаще всего легче читается, но главное, позволяет обрабатывать гигантские (даже бесконечные) списки лениво. Функция с хвостовой рекурсией обязательно должна прочитать весь входной список перед возвратом результата).
cons = (:)

mymap f [] = []
mymap f (x:xs) = cons (f x) (mymap f xs)

mymap' f l = aux [] l
    where aux acc [] = reverse acc
          aux acc (x:xs) = aux (cons (f x) acc) xs


*Main> take 10 $ mymap (+1) $ [1..1000000]
[2,3,4,5,6,7,8,9,10,11]
(0.00 secs, 524800 bytes)
*Main> take 10 $ mymap' (+1) $ [1..1000000]
[2,3,4,5,6,7,8,9,10,11]
(2.14 secs, 88516708 bytes)
*Main> 


Прим. Функция cons здесь нужна только для того, чтобы отличие хвостатой рекурсии от нехвостатой бросалось в глаза.
(Reply) (Parent) (Thread)
From: ex_soundwell971
2007-03-11 09:12 am (UTC)
Если вам нужен язык, в котором шустро работает код, заточенный под Хаскель, я думаю вы знаете, как он называется ;-)
(Reply) (Parent) (Thread)
[User Picture]From: palm_mute
2007-03-10 05:55 pm (UTC)
dummy и dummy2 не эквивалентны. dummy вызывает себя рекурсивно для хвоста 2 раза, в то время как версия с аккумулятором - 1 раз.
(Reply) (Thread)
[User Picture]From: geniepro
2007-03-10 07:50 pm (UTC)

dummy и dummy2 не эквивалентны. dummy вызывает себя рекурсивно для хвоста 2 раза, в то время как версия с аккумулятором - 1 раз.

То есть как это? И в той и в другой версии имеется вложенная рекурсия (типа как в функции Аккермана), так что вызывают они себя по два раза, и получается экспоненциальное количество вызовов...
(Reply) (Parent) (Thread)
[User Picture]From: palm_mute
2007-03-10 08:23 pm (UTC)
Я торможу, прошу прощения.
(Reply) (Parent) (Thread)
[User Picture]From: justbulat
2007-03-10 09:40 pm (UTC)
>И как бороться с такими случаями? Ведь наверняка иногда вынужденно будет получаться что-то типа dummy на Хаскелле...

dummy :: [Int] -> [Int]
dummy [] = []
dummy (x:xs) = let a = dummy xs in a `seq` (x:dummy a)

вообще, прежде чем бороться, надо сначала разобраться что тут собственно происходит :). если переполняется стёк - это уже какие-то проблемы в самом по себе алгоритме
(Reply) (Thread)
[User Picture]From: justbulat
2007-03-10 09:49 pm (UTC)
а вот так ещё быстрее, а главное - криптологичнее :)

dummy :: [Int] -> [Int]
dummy [] = []
dummy (x:xs) = (:) x $! dummy (dummy xs)
(Reply) (Parent) (Thread)
[User Picture]From: justbulat
2007-03-10 11:23 pm (UTC)
теперь мой анализ с помощью +RTS -sstderr

певрый вариант функции быстрее в 2-3 раза второго и третьего - хоть в хаскеле, хоть в f#. только твоя первоначальная реализация скрывала это, создавая в стеке кучу незавершённых вычислений. это приводило к выходу за пределы процессорного кеша, что в 4 раза увеличивало время работы. но ещё в 10 раз оно увеличивалось из-за GC. после стриктизации все эти проблемы исчезли

далее, второй-третий варианты требуют рекурсии с аккумулятором и затем либо его реверсирования, либо неэффективного накопления данных. поэтому они и работают медленней в обоих языках по сравнению с первым вариантом, где вычисления происходят напрямую, без всех этих хитростей. то, что аккумуляторы - слово модное, ещё не гарантирует что любой алгоритм от их применения станет быстрее :)

как показывает -sstderr, кол-во временных данных (bytes allocated in the heap), создаваемых dummy, вдвое меньше, чем для dummy3
(Reply) (Parent) (Thread)
[User Picture]From: geniepro
2007-03-11 12:55 pm (UTC)
Да, этот вариант работает ничуть не хуже, чем dummy на F#, даже как буд-то чуть-чуть быстрее (%10-15)! Очень интересно...

> только твоя первоначальная реализация скрывала это, создавая в стеке кучу незавершённых вычислений.

А я почему-то думал, что для таких простых случаев анализатор строгости в GHC должен всё заоптимизировать...

> то, что аккумуляторы - слово модное, ещё не гарантирует что любой алгоритм от их применения станет быстрее :)

Хм, над этим надо подумать. Раньше я встречал обратные примеры...
(Reply) (Parent) (Thread)
[User Picture]From: justbulat
2007-03-11 03:23 pm (UTC)
>А я почему-то думал, что для таких простых случаев анализатор строгости в GHC должен всё заоптимизировать...

это ведь не какая-то волшебгная технология для ускорения всех простых функций :) он имеет свои конкретные приницпы работы. если он может определить, что данные обязательно используются - то он может их вычислить раньше, чем они действительно понадобятся - вот и всё

>Хм, над этим надо подумать. Раньше я встречал обратные примеры...

примеры - да. но никто не говорил, что это всегда быстрее
(Reply) (Parent) (Thread)
From: serge_lipkin
2007-03-11 04:11 pm (UTC)
Причём здесь строгость как волшебная технология?
Какого чёрта супер-пупер кумпилятор буги-вуги языка не может врубиться, что
dummy (x:xs) = x:dummy (dummy xs) со списком не делает ничего?
(Reply) (Parent) (Thread)
[User Picture]From: justbulat
2007-03-11 04:14 pm (UTC)
>Причём здесь строгость как волшебная технология?

притом, что он ссылается на анлизатор строгости :)

>Какого чёрта супер-пупер кумпилятор буги-вуги языка не может врубиться, что

а ты сам, только взглянув на этот код, сразу понял, что и как он делает? :) ни одна система - ни человек, ни компьютер не обладает универсальностью
(Reply) (Parent) (Thread)
From: serge_lipkin
2007-03-11 05:32 pm (UTC)
Я не понял что он делает, но сразу же понял, что результат работы равен входному списку.
Собственно, нафига ж иначе за чистоту языка бороться, если потом компилятор не может этой чистотой воспользоваться? - Получаются одни грабли и никакого удовольствия.
(Reply) (Parent) (Thread)