Quartz 5

HVM List Fold benchmark isnt faithful

Properties1
tagsbook

3 min read

HVM List Fold benchmark isnt faithful

2022-05-29

GitHub - Kindelia/HVM: A massively parallel, optimal functional runtime in Rust

// Folds over a list
(Fold Nil         c n) = n
(Fold (Cons x xs) c n) = (c x (Fold xs c n))
 
// A list from 0 to n
(Range 0 xs) = xs
(Range n xs) =
  let m = (- n 1)
  (Range m (Cons m xs))
 
// Sums a big list with fold
(Main n) =
  let size = (* n 1000000)
  let list = (Range size Nil)
  (Fold list λaλb(+ a b) 0)

lazyに書く

range 0 = Nil
range n = Cons n (range (n-1))

  • issue: Haskellで工夫すれば定数空間に収まるのでは?

    • 一般的な再帰は定数空間計算量に収まらない

  • issue: foldl と loop fusion を使えば100x fasterになるが

    • 例えば引き算は結合的じゃないので foldl 出来ない

  • プロトタイプで再帰においてはGHCと同じな点ですごい

  • HVM はVMであってコンパイラで無い, 実行時にfusionが行われる

    • のでSTGと比較するのが公平

  • 関数型ランタイムではallocationと GC が重要

    • HVMの有用性は並列性(multi-core)と最適性が利用できるならそうすること

  • 実際にlist sumを8回したのをタプルにするベンチマークはHVMの方が3x faster

  • なんかownerとissuerの議論がずれている気がするな

    • いや、issuerはGHCは思うより優れていることを主張したいだけか, HVMの並列化に価値があるものなのか

  • マルチコア化するのは Haskell でも あった

自分は Haskellのコンパイル時の最適化と実行時のアロケーション(Core/STG?)とかの詳細がわかっていない. 関数型ランタイムを作るのは大変そうだ, lazinessとかどうやって導入するんだ

Loop Fusion

Graph View

Backlinks