logo标签列表

Haskell性能：组合与应用？

haskellf#functional-programming
7
我看到一些有关函数组合和应用的相似之处和差异的问题，以及各种实现方式，但有一件事情开始让我有点困惑(在我所搜索的范围内还没有人问过)，那就是性能上的差异。
当我学习F#时，我爱上了管道运算符|>，它在Haskell中有其等价的反向应用&。但在我看来，F#的变体无疑更加美丽(我认为不止我一个人这么认为)。
现在，你可以很容易地将管道运算符加入到Haskell中：
(|>) x f = f x

并且它的效果非常好！问题已解决！
管道符（在F#和我们的Haskell技巧中）的一个重要区别是它不会组合函数，而是基于函数应用。它将左侧的值传递到右侧的函数中，而组合则取2个函数并返回另一个函数，该函数可以像任何常规函数一样使用。
至少对我来说，这使代码更加美观，因为您只需使用一个运算符即可引导整个函数中从参数到最终值的信息流，因为使用基本组合（或>>>）时，您无法将值放在左侧以通过“链”传递。
但从性能角度来看，从这些通用选项中查看，结果应完全相同：
f x = x |> func1 |> func2 |> someLambda |> someMap |> someFold |> show

f x = x & (func1 >>> func2 >>> someLambda >>> someMap >>> someFold >>> show)

f x = (func1 >>> func2 >>> someLambda >>> someMap >>> someFold >>> show) x

基于重复应用的方法和基于组合和单次应用的方法，哪种方法会更快呢？

5
你是否尝试过做测试来看哪个更快？ - AJF
@AJFarmar 我考虑过，但是在Haskell中有没有一种测量执行时间的方法呢？ - Rares Dima
3
如果在Haskell中没有测量执行时间的方法，你的问题"哪个更快"将无法回答。 - amalloy
10
几乎所有情况下，如果你使用优化编译，执行时间将完全相同，因为优化后的代码完全一样。如果不使用优化编译，我猜测第一个可能会更快，但如果你在意性能，为什么不使用优化编译呢？ - dfeuer
2
考虑运行criterion并编写一个小型基准测试。很可能，在进行优化后，您将不会发现任何差异。 - chi
即使没有优化，如果单个操作的成本远高于任何组合相关的开销，则性能差异也不会很大。如果在链中有地图、折叠和“show”，那很可能是这种情况。 - leftaroundabout
2个回答
10

只要(|>)和(>>>)被内联，就不应该有任何区别。让我们编写一个示例，其中使用了四个不同的函数，其中两个采用F#风格，另外两个采用Haskell风格：

import Data.Char (isUpper)

{-# INLINE (|>) #-}
(|>) :: a -> (a -> b) -> b
(|>) x f = f x

{-# INLINE (>>>) #-}
(>>>) :: (a -> b) -> (b -> c) -> a -> c
(>>>) f g x = g (f x)

compositionF :: String -> String
compositionF = filter isUpper >>> length >>> show 

applicationF :: String -> String
applicationF x = x |> filter isUpper |> length |> show 

compositionH :: String -> String
compositionH = show . length . filter isUpper

applicationH :: String -> String
applicationH x = show $ length $ filter isUpper $ x

main :: IO ()
main = do
  getLine >>= putStrLn . compositionF  -- using the functions
  getLine >>= putStrLn . applicationF  -- to make sure that
  getLine >>= putStrLn . compositionH  -- we actually get the
  getLine >>= putStrLn . applicationH  -- corresponding GHC core

如果我们使用-ddump-simpl -dsuppress-all -O0编译代码，则会得到以下结果：

==================== Tidy Core ====================
Result size of Tidy Core = {terms: 82, types: 104, coercions: 0}

-- RHS size: {terms: 9, types: 11, coercions: 0}
>>>_rqe
>>>_rqe =
  \ @ a_a1cE @ b_a1cF @ c_a1cG f_aqr g_aqs x_aqt ->
    g_aqs (f_aqr x_aqt)

-- RHS size: {terms: 2, types: 0, coercions: 0}
$trModule1_r1gR
$trModule1_r1gR = TrNameS "main"#

-- RHS size: {terms: 2, types: 0, coercions: 0}
$trModule2_r1h6
$trModule2_r1h6 = TrNameS "Main"#

-- RHS size: {terms: 3, types: 0, coercions: 0}
$trModule
$trModule = Module $trModule1_r1gR $trModule2_r1h6

-- RHS size: {terms: 58, types: 73, coercions: 0}
main
main =
  >>
    $fMonadIO
    (>>=
       $fMonadIO
       getLine
       (. putStrLn
          (>>>_rqe
             (>>>_rqe (filter isUpper) (length $fFoldable[]))
             (show $fShowInt))))
    (>>
       $fMonadIO
       (>>=
          $fMonadIO
          getLine
          (. putStrLn
             (\ x_a10M ->
                show $fShowInt (length $fFoldable[] (filter isUpper x_a10M)))))
       (>>
          $fMonadIO
          (>>=
             $fMonadIO
             getLine
             (. putStrLn
                (. (show $fShowInt) (. (length $fFoldable[]) (filter isUpper)))))
          (>>=
             $fMonadIO
             getLine
             (. putStrLn
                (\ x_a10N ->
                   show $fShowInt (length $fFoldable[] (filter isUpper x_a10N)))))))

-- RHS size: {terms: 2, types: 1, coercions: 0}
main
main = runMainIO main

如果我们不启用优化，那么>>>就不会被内联。但是，如果我们启用了优化，你将看不到>>>或(.)。由于在这个阶段(.)没有被内联，所以我们的函数略有不同，但这是可以预料的。

如果我们在函数中添加{-# NOINLINE … #-}并启用优化，我们会发现这四个函数不会有任何差别：

$ ghc -ddump-simpl -dsuppress-all -O2 Example.hs
[1 of 1] Compiling Main             ( Example.hs, Example.o )

==================== Tidy Core ====================
Result size of Tidy Core = {terms: 261, types: 255, coercions: 29}

-- RHS size: {terms: 2, types: 0, coercions: 0}
$trModule2
$trModule2 = TrNameS "main"#

-- RHS size: {terms: 2, types: 0, coercions: 0}
$trModule1
$trModule1 = TrNameS "Main"#

-- RHS size: {terms: 3, types: 0, coercions: 0}
$trModule
$trModule = Module $trModule2 $trModule1

Rec {
-- RHS size: {terms: 29, types: 20, coercions: 0}
$sgo_r574
$sgo_r574 =
  \ sc_s55y sc1_s55x ->
    case sc1_s55x of _ {
      [] -> I# sc_s55y;
      : y_a2j9 ys_a2ja ->
        case y_a2j9 of _ { C# c#_a2hF ->
        case {__pkg_ccall base-4.9.1.0 u_iswupper Int#
                                     -> State# RealWorld -> (# State# RealWorld, Int# #)}_a2hE
               (ord# c#_a2hF) realWorld#
        of _ { (# ds_a2hJ, ds1_a2hK #) ->
        case ds1_a2hK of _ {
          __DEFAULT -> $sgo_r574 (+# sc_s55y 1#) ys_a2ja;
          0# -> $sgo_r574 sc_s55y ys_a2ja
        }
        }
        }
    }
end Rec }

-- RHS size: {terms: 15, types: 14, coercions: 0}
applicationH
applicationH =
  \ x_a12X ->
    case $sgo_r574 0# x_a12X of _ { I# ww3_a2iO ->
    case $wshowSignedInt 0# ww3_a2iO []
    of _ { (# ww5_a2iS, ww6_a2iT #) ->
    : ww5_a2iS ww6_a2iT
    }
    }

Rec {
-- RHS size: {terms: 29, types: 20, coercions: 0}
$sgo1_r575
$sgo1_r575 =
  \ sc_s55r sc1_s55q ->
    case sc1_s55q of _ {
      [] -> I# sc_s55r;
      : y_a2j9 ys_a2ja ->
        case y_a2j9 of _ { C# c#_a2hF ->
        case {__pkg_ccall base-4.9.1.0 u_iswupper Int#
                                     -> State# RealWorld -> (# State# RealWorld, Int# #)}_a2hE
               (ord# c#_a2hF) realWorld#
        of _ { (# ds_a2hJ, ds1_a2hK #) ->
        case ds1_a2hK of _ {
          __DEFAULT -> $sgo1_r575 (+# sc_s55r 1#) ys_a2ja;
          0# -> $sgo1_r575 sc_s55r ys_a2ja
        }
        }
        }
    }
end Rec }

-- RHS size: {terms: 15, types: 15, coercions: 0}
compositionH
compositionH =
  \ x_a1jF ->
    case $sgo1_r575 0# x_a1jF of _ { I# ww3_a2iO ->
    case $wshowSignedInt 0# ww3_a2iO []
    of _ { (# ww5_a2iS, ww6_a2iT #) ->
    : ww5_a2iS ww6_a2iT
    }
    }

Rec {
-- RHS size: {terms: 29, types: 20, coercions: 0}
$sgo2_r576
$sgo2_r576 =
  \ sc_s55k sc1_s55j ->
    case sc1_s55j of _ {
      [] -> I# sc_s55k;
      : y_a2j9 ys_a2ja ->
        case y_a2j9 of _ { C# c#_a2hF ->
        case {__pkg_ccall base-4.9.1.0 u_iswupper Int#
                                     -> State# RealWorld -> (# State# RealWorld, Int# #)}_a2hE
               (ord# c#_a2hF) realWorld#
        of _ { (# ds_a2hJ, ds1_a2hK #) ->
        case ds1_a2hK of _ {
          __DEFAULT -> $sgo2_r576 (+# sc_s55k 1#) ys_a2ja;
          0# -> $sgo2_r576 sc_s55k ys_a2ja
        }
        }
        }
    }
end Rec }

-- RHS size: {terms: 15, types: 15, coercions: 0}
compositionF
compositionF =
  \ x_a1jF ->
    case $sgo2_r576 0# x_a1jF of _ { I# ww3_a2iO ->
    case $wshowSignedInt 0# ww3_a2iO []
    of _ { (# ww5_a2iS, ww6_a2iT #) ->
    : ww5_a2iS ww6_a2iT
    }
    }

Rec {
-- RHS size: {terms: 29, types: 20, coercions: 0}
$sgo3_r577
$sgo3_r577 =
  \ sc_s55d sc1_s55c ->
    case sc1_s55c of _ {
      [] -> I# sc_s55d;
      : y_a2j9 ys_a2ja ->
        case y_a2j9 of _ { C# c#_a2hF ->
        case {__pkg_ccall base-4.9.1.0 u_iswupper Int#
                                     -> State# RealWorld -> (# State# RealWorld, Int# #)}_a2hE
               (ord# c#_a2hF) realWorld#
        of _ { (# ds_a2hJ, ds1_a2hK #) ->
        case ds1_a2hK of _ {
          __DEFAULT -> $sgo3_r577 (+# sc_s55d 1#) ys_a2ja;
          0# -> $sgo3_r577 sc_s55d ys_a2ja
        }
        }
        }
    }
end Rec }

-- RHS size: {terms: 15, types: 14, coercions: 0}
applicationF
applicationF =
  \ x_a12W ->
    case $sgo3_r577 0# x_a12W of _ { I# ww3_a2iO ->
    case $wshowSignedInt 0# ww3_a2iO []
    of _ { (# ww5_a2iS, ww6_a2iT #) ->
    : ww5_a2iS ww6_a2iT
    }
    }
...

所有的go函数都是完全相同的（变量名除外），而application*与composition*相同。因此，你可以放心地在Haskell中创建自己的F#预设，不应该存在任何性能问题。

5

我的回答与F#有关。

在大多数情况下，F#编译器能够将管道优化为相同的代码：

let f x = x |> (+) 1 |> (*) 2 |> (+) 2
let g x = x |> ((+) 1 >> (*) 2 >> (+) 2)

反编译f和g，我们可以看到编译器生成相同的结果:

public static int f(int x)
{
    return 2 + 2 * (1 + x);
}
public static int g(int x)
{
    return 2 + 2 * (1 + x);
}

但是我们可以从稍微复杂一些的流水线中看到它并不总是适用：

let f x = x |>  Array.map add1 |> Array.map mul2 |> Array.map add2 |> Array.reduce (+)
let g x = x |> (Array.map add1 >> Array.map mul2 >> Array.map add2 >> Array.reduce (+))

反编译显示出一些差异：

public static int f(int[] x)
{
  FSharpFunc<int, FSharpFunc<int, int>> arg_25_0 = new Program.f@9();
  if (x == null)
  {
    throw new ArgumentNullException("array");
  }
  int[] array = new int[x.Length];
  FSharpFunc<int, FSharpFunc<int, int>> fSharpFunc = arg_25_0;
  for (int i = 0; i < array.Length; i++)
  {
    array[i] = x[i] + 1;
  }
  FSharpFunc<int, FSharpFunc<int, int>> arg_6C_0 = fSharpFunc;
  int[] array2 = array;
  if (array2 == null)
  {
    throw new ArgumentNullException("array");
  }
  array = new int[array2.Length];
  fSharpFunc = arg_6C_0;
  for (int i = 0; i < array.Length; i++)
  {
    array[i] = array2[i] * 2;
  }
  FSharpFunc<int, FSharpFunc<int, int>> arg_B3_0 = fSharpFunc;
  int[] array3 = array;
  if (array3 != null)
  {
    array2 = new int[array3.Length];
    fSharpFunc = arg_B3_0;
    for (int i = 0; i < array2.Length; i++)
    {
      array2[i] = array3[i] + 2;
    }
    return ArrayModule.Reduce<int>(fSharpFunc, array2);
  }
  throw new ArgumentNullException("array");
}

public static int g(int[] x)
{
  FSharpFunc<int[], int[]> f = new Program.g@10-1();
  FSharpFunc<int[], int[]> fSharpFunc = new Program.g@10-3(f);
  FSharpFunc<int, FSharpFunc<int, int>> reduction = new Program.g@10-4();
  int[] array = fSharpFunc.Invoke(x);
  return ArrayModule.Reduce<int>(reduction, array);
}

对于f，F#内联了整个管道，除了最后的reduce。

对于g，管道是在构建之后再被调用。这意味着g可能比f略微慢一些，内存占用也更高一些。

在这个特定的例子中，如果我们创建数组对象并迭代它们，这可能不那么重要，但如果组合的函数在CPU和内存方面非常便宜，则建立和调用管道的成本可能会变得相当重要。

如果关键性能对您很重要，我建议获取一个好的反编译工具，以确保生成的代码不包含意外的开销。否则，任何一种方法都可以。

1
所有这些丑陋的 null 检查是来自于内联的 Array.map 函数，还是只有管道生成的？ - leftaroundabout
2
如果关键性能对您很重要，我建议获取一个好的反编译工具，以确保生成的代码不包含意外的开销。然后，请放置一个清晰的注释，解释代码为什么是这样的，以免有人过度热衷于重构它。 - scrwtp
@leftaroundabout 看起来它们是来自于 module Array 中使用 checkNonNull "array" array 的内联函数。更智能的编译器可以找出许多这些检查是不必要的并将其移除。如果我们很幸运，即时编译器会为我们消除它们。 - Just another metaprogrammer
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接