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

Я сравнивал для разных языков разные скорости для выполнения следующей программы: для я от 1 до 1000000 сумм продукта я * (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 one:

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 #?

Ответы

Ответ 1

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

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

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

Ответ 2

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

И обратите внимание, что вы можете сделать еще лучше в Haskell, благодаря слиянию циклов. Записывая функцию create в качестве перечисления, компилятор может объединить шаг create и цикл fold в один цикл, который не выделяет промежуточных структур данных. Способность делать общий синтез, подобный этому, уникальна для 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

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

Ответ 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, которым нужно оптимизировать чистый код, который вы пишете). В любом случае, если у вас есть какие-то тесты, вы можете попробовать!

Ответ 4

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

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

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

Ответ 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})