Переполнение стека в OCaml и F #, но не в Haskell

Question

Я с удовольствием сравнивал разные языки по скорости выполнения следующей программы: для i от 1 до 1000000 сумм произведение i * (sqrt i)

Одна из моих реализаций (не единственная) - это создание списка [1..1000000] и последующее свертывание с определенной функцией.

Программа работает на Haskell отлично и быстро (даже при использовании foldl, а не foldl '), но переполнение стека в OCaml и F #.

Вот код Haskell:

test = foldl (\ a b -> a + b * (sqrt b)) 0

create 0 = []
create n = n:(create (n-1))

main = print (test (create 1000000))

А вот OCaml один:

let test = List.fold_left (fun a b -> a +. (float_of_int b) *. (sqrt (float_of_int b))) 0. ;;

let rec create = function
    | 0 -> []
    | n -> n::(create (n-1)) ;;

print_float (test (create 1000000));;

Почему переполнение стека реализации OCaml / F #?

Answer 1

Код Haskell для create оценивает список лениво, т. Е. Элементы необходимы для foldl. Весь список не нужен сразу.

Напротив, F # и OCaml строго оценивают список create, т. Е. Код пытается сгенерировать весь список за один раз, прежде чем передать его в fold_left.

Одна возможность в F # - использовать выражение seq в функции create: это генерирует список лениво так же, как Haskell. (Я не уверен, что OCaml имеет аналогичную функцию.)

Answer 2

Во-первых, если вы проводите сравнение производительности для числовых данных, списки - не лучший выбор. Попробуйте пакет типа vector для быстрых массивов.

И обратите внимание, что в Haskell вы можете добиться еще больших успехов благодаря циклическому синтезу Записав функцию create в качестве перечисления, компилятор может объединить шаг создания и цикл сгиба в один цикл, который не выделяет промежуточных структур данных. Способность делать общий синтез таким образом уникальна для GHC Haskell.

Я буду использовать векторную библиотеку (потоковое объединение циклов):

import qualified Data.Vector as V

test = V.foldl (\ a b -> a + b * sqrt b) 0

create n = (V.enumFromTo 1 n)

main = print (test (create 1000000))

Теперь, прежде чем, с вашим кодом, компилятор не может удалить все списки, и мы заканчиваем с внутренним циклом как:

$wlgo :: Double# -> [Double] -> Double#

$wlgo =
  \ (ww_sww :: Double#) (w_swy :: [Double]) ->
    case w_swy of _ {
      [] -> ww_sww;
      : x_aoY xs_aoZ ->
        case x_aoY of _ { D# x1_aql ->
        $wlgo
          (+##
             ww_sww (*## x1_aql (sqrtDouble# x1_aql)))
          xs_aoZ
        }
    }

$wcreate :: Double# -> [Double]

$wcreate =
  \ (ww_swp :: Double#) ->
    case ==## ww_swp 0.0 of _ {
      False ->
        :
          @ Double
          (D# ww_swp)
          ($wcreate (-## ww_swp 1.0));
      True -> [] @ Double
    }

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

$ time ./C
4.000004999999896e14
./C  0.06s user 0.00s system 98% cpu 0.058 total

Однако, при слиянии мы получаем только один цикл!

main_$s$wfoldlM_loop :: Double# -> Double# -> Double#

main_$s$wfoldlM_loop =
  \ (sc_sYc :: Double#) (sc1_sYd :: Double#) ->
    case <=## sc_sYc 1000000.5 of _ {
      False -> sc1_sYd;
      True ->
        main_$s$wfoldlM_loop
          (+## sc_sYc 1.0)
          (+##
             sc1_sYd (*## sc_sYc (sqrtDouble# sc_sYc)))

GHC сократил наши шаги создания и тестирования в один цикл без использования списков. Всего 2 дубля в регистрах. И с вдвое меньшим количеством циклов, он работает почти вдвое быстрее:

$ ghc D.hs -Odph -fvia-C -optc-O3 -optc-march=native -fexcess-precision --make
$ time ./D
4.000005000001039e14
./D  0.04s user 0.00s system 95% cpu 0.038 total

Это хороший пример силы, которую обеспечивают гарантии чистоты - компилятор может быть очень агрессивным при переписывании вашего кода.

Answer 3

Другой способ исправить код, чтобы он работал в F #, - это использовать выражения последовательности, которые также генерируются лениво и таким образом, чтобы не вызывать StackOverflow (это не будет работать в OCaml, потому что выражения последовательности F # конкретный). Вот код:

let test nums = Seq.fold (fun a b -> 
  a + (float b) * (sqrt (float b))) 0.0 nums

let rec create count = seq {
  match count with
  | 0 -> do ()
  | n -> yield n
         yield! create (n-1) }

printf "%f" (test (create 1000000));; 

Я не уверен в производительности, однако компилятор определенно выполняет оптимизацию в функции create, поэтому итерации по сгенерированной последовательности должны быть достаточно быстрыми. Однако целью выражений последовательностей является, главным образом, удобочитаемость (поскольку F # не является чистым, он дает вам много места для ручной оптимизации, если вам они действительно нужны, в отличие от Haskell, который должен оптимизировать чистый код, который вы пишете). В любом случае, если у вас есть несколько тестов, вы можете попробовать!

Answer 4

В этой форме ваша create функция не является хвостовой рекурсивной. Вы можете переписать его в хвостовой рекурсивной форме, которая не вызывает переполнение стека:

let rec create n l =
    match n with 
    | 0 -> l
    | n -> create (n-1) (n::l)

print_float (test (create 1000000 []));;

Answer 5

Программа работает на Haskell отлично (даже при использовании foldl, а не foldl '), но переполнение стека в OCaml и F #.

Ваш Haskell использует ленивые списки, но ваш OCaml / F # использует строгие списки, поэтому ваши программы несопоставимы.

FWIW, решение, использующее последовательности по требованию в F #:

Seq.sumBy (fun i -> let i = float i in i * sqrt i) (seq {1..1000000})