基准测试过滤器和分区

Question

我认为,我正在测试partition列表函数的性能并得到一些奇怪的结果.

我们有,partition p xs == (filter p xs, filter (not . p) xs)但我们选择了第一个实现,因为它只对列表执行单次遍历.然而,我得到的结果表明,使用使用两次遍历的实现可能更好.

这是显示我所看到的最小代码

import Criterion.Main
import System.Random
import Data.List (partition)

mypartition :: (a -> Bool) -> [a] -> ([a],[a])
mypartition p l = (filter p l, filter (not . p) l)



randList :: RandomGen g => g -> Integer -> [Integer]
randList gen 0 = []
randList gen n = x:xs
  where
    (x, gen') = random gen
    xs = randList gen' (n - 1)

main = do
  gen <- getStdGen
  let arg10000000 = randList gen 10000000
  defaultMain [
      bgroup "filters -- split list in half " [
        bench "partition100"         $ nf (partition (>= 50)) arg10000000
      , bench "mypartition100"       $ nf (mypartition (>= 50)) arg10000000
      ]
      ]

无论是否使用-O它都运行测试,两次我得到双遍遍更好.

我使用ghc-7.10.3与criterion-1.1.1.0

我的问题是:

• 这是预期的吗？

• 我正确使用Criterion吗？我知道懒惰可能很棘手,(filter p xs, filter (not . p) xs)如果使用元组的两个元素,它只会进行两次遍历.

• 这是否与Haskell中处理列表的方式有关？

非常感谢!

Answer 1

这个问题没有黑色或白色的答案.要剖析问题,请考虑以下代码:

import Control.DeepSeq
import Data.List (partition)
import System.Environment (getArgs)


mypartition :: (a -> Bool) -> [a] -> ([a],[a])
mypartition p l = (filter p l, filter (not . p) l)


main :: IO ()
main = do
  let cnt = 10000000
      xs = take cnt $ concat $ repeat [1 .. 100 :: Int]
  args <- getArgs
  putStrLn $ unwords $ "Args:" : args
  case args of
    [percent, fun]
      -> let p = (read percent >=)
         in case fun of
           "partition"      ->              print $ rnf $ partition   p xs
           "mypartition"    ->              print $ rnf $ mypartition p xs
           "partition-ds"   -> deepseq xs $ print $ rnf $ partition   p xs
           "mypartition-ds" -> deepseq xs $ print $ rnf $ mypartition p xs
           _ -> err
    _ -> err
  where
    err = putStrLn "Sorry, I do not understand."

我不使用Criterion来更好地控制评估顺序.为了获得时间,我使用+RTS -s运行时选项.使用不同的命令行选项执行不同的测试用例.第一个命令行选项定义谓词所包含的数据百分比.第二个命令行选项在不同的测试之间进行选择.

测试区分了两种情况:

1. 数据是懒惰生成的(第二个参数partition或mypartition).
2. 数据已在内存中完全评估(第二个参数partition-ds或mypartition-ds).

分区的结果始终从左到右进行计算,即从包含谓词所包含的所有元素的列表开始.

在情况1中partition具有以下优点:在输出列表的所有元素被生成之前,第一结果列表的元素被丢弃.如果谓词匹配许多元素,即第一个命令行参数很大,则情况1特别好.

在案例2中,partition无法发挥这一优势,因为所有元素都已经在内存中.

因为mypartition,在任何情况下,在评估第一个结果列表之后,所有元素都保存在内存中,因为再次需要它们来计算第二个结果列表.因此,这两种情况没有太大区别.

看起来,使用的内存越多,垃圾收集就越难.因此partition,如果谓词与许多元素匹配并且使用了惰性变体,则非常适合.

相反,如果谓词与许多元素不匹配或者所有元素已经在内存中,则mypartition表现更好,因为它的递归不会与成对相对应partition.

Stackoverflow问题" Irrefutable模式在递归时不会泄漏内存,但为什么？"可能会给出一些关于在递归中处理对的更多见解partition.