13

在对上一个问题的评论中,我声称:

我有另一个基准表明 ghc-7.4.1+llvm 对严格数据字段的枚举进行解包。

事实上,经过一些实验,我相信,至少在一些简单的情况下,使用枚举至少与使用新类型的 Word8 一样快,并且实际上可能更节省内存(因此在更实际的应用程序中更快) (或 Int),即使在数据类型的严格字段中使用。正如我在上一个问题中所说,我在更现实(但仍然很小)的环境中经历了类似的现象。

谁能指出一些有关 ghc/llvm 对枚举进行哪些优化的相关参考资料?特别是,它真的将枚举的内部标签解包在严格的数据字段上吗?汇编输出和分析结果似乎表明情况确实如此,但对我来说,核心级别没有任何迹象。任何见解将不胜感激。

还有一个问题:枚举是否总是至少与相应 Integral 的新类型一样有效,在哪里使用它们才有意义?(请注意,枚举的行为也可以像 Integrals 一样。)如果不是,那么(希望实际有用的)异常是什么?Daniel Fischer 在他的回答中建议,对多构造函数数据类型的严格字段进行枚举可能会阻止某些优化。但是,我未能在两个构造函数的情况下验证这一点。将它们放入大型多构造函数数据类型时可能会有所不同?

我也很好奇以下基准测试中到底发生了什么。在所有四种情况下,在堆中分配的字节数大致相同。但是,对于枚举,GC 实际上复制较少,与新类型相比,最大驻留数更小。

(实际上我真正的问题是,当性能很重要时尝试将枚举转换为新类型是否值得?但我认为更具体一点可能更有帮助。)

这个问题的一个可能的含义是:如果你在你的程序中使用大量的 Int,实际上在一些非常小的子集上有所不同,那么将它们更改为枚举(而不是未装箱的类型!)可能是一种表现增益(但要注意严格)。

这是基准测试的摘要,后面是基准代码和用于在您的系统上进行测试的便捷生成文件。

基准测试
平均值:11.09113 ns,lb 11.06140 ns,ub 11.17545 ns,ci 0.950
标准开发:234.6722 ps,lb 72.31532 ps,ub 490.1156 ps,ci 0.950

基准测试
平均值:11.54242 ns,lb 11.51789 ns,ub 11.59720 ns,ci 0.950
标准开发:178.8556 ps,lb 73.05290 ps,ub 309.0252 ps,ci 0.950

基准测试
平均值:11.74964 ns,lb 11.52543 ns,ub 12.50447 ns,ci 0.950
标准开发:1.803095 ns,lb 207.2720 ps,ub 4.029809 ns,ci 0.950

基准测试
平均值:11.89797 ns,lb 11.86266 ns,ub 11.99105 ns,ci 0.950
标准开发:269.5795 ps,lb 81.65093 ps,ub 533.8658 ps,ci 0.950

好的,所以枚举看起来至少不比新类型效率低
接下来,函数的堆配置文件
heapTest x = print $ head $ force $ reverse $ take 100000 $ iterate (force . succ') x

数据 D = A | 乙| C:
      在堆中分配了 10,892,604 字节
       GC 期间复制了 6,401,260 字节
       1,396,092 字节最大驻留(3 个样本)
          55,940 字节最大斜率
               6 MB 总内存正在使用(0 MB 由于碎片丢失)
  生产力占总用户的 47.8%,占总使用时间的 35.4%

新类型 E = E Word8:
      在堆中分配了 11,692,768 字节
       GC 期间复制了 8,909,632 个字节
       2,779,776 字节最大驻留(3 个样本)
          92,464 字节最大斜率
               7 MB 正在使用的总内存(0 MB 由于碎片而丢失)
  生产力占总用户的 36.9%,占总使用时间的 33.8%

数据 S = S !D:
      在堆中分配了 10,892,736 个字节
       GC 期间复制了 6,401,260 字节
       1,396,092 字节最大驻留(3 个样本)
          55,940 字节最大斜率
               6 MB 总内存正在使用(0 MB 由于碎片丢失)
  生产力占总用户的 48.7%,占总使用时间的 33.3%

数据 T = T {-# UNPACK #-} !E:
      在堆中分配了 11,692,968 字节
       GC 期间复制了 8,909,640 字节
       2,779,760 字节最大驻留(3 个样本)
          最大 92,536 字节斜率
               7 MB 正在使用的总内存(0 MB 由于碎片而丢失)
  生产力占总用户的 36.1%,占总使用时间的 31.6%

在两个构造函数的情况下可以获得类似的性能增益。

基准代码(另存为 EnumTest.hs):


{-# LANGUAGE CPP,MagicHash , BangPatterns ,GeneralizedNewtypeDeriving #-}
module Main(main,d,e,s,t,D(..),E(..),S(..),T(..))
where       
import GHC.Base  
import Data.List
import Data.Word
import Control.DeepSeq
import Criterion.Main

data    D = A | B | C  deriving(Eq,Ord,Show,Enum,Bounded)
newtype E = E Word8    deriving(Eq,Ord,Show,Enum)

data    S = S                !D deriving (Eq,Ord,Show) 
data    T = T {-# UNPACK #-} !E deriving (Eq,Ord,Show)

-- I assume the following definitions are all correct --- otherwise
-- the whole benchmark may be useless
instance NFData D where
  rnf !x         = ()
instance NFData E where
  rnf (E !x)     = ()
instance NFData S where
  rnf (S !x)     = ()
instance NFData T where
  rnf (T (E !x)) = ()  

instance Enum S where
  toEnum         = S . toEnum
  fromEnum (S x) = fromEnum x 
instance Enum T where
  toEnum         = T . toEnum
  fromEnum (T x) = fromEnum x 

instance Bounded E where
  minBound = E 0
  maxBound = E 2
instance Bounded S where
  minBound = S minBound
  maxBound = S maxBound
instance Bounded T where
  minBound = T minBound
  maxBound = T maxBound

succ' :: (Eq a,Enum a,Bounded a) => a -> a
succ' x | x == maxBound = minBound
          | otherwise        = succ x

-- Those numbers below are for easy browsing of the assembly code
d :: D -> Int#
d x = case x of
  A -> 1234#
  B -> 5678#
  C -> 9412#

e :: E -> Int#
e x = case x of     
  E 0 -> 1357#
  E 1 -> 2468#
  E _ -> 9914#

s :: S -> Int#
s x = case x of     
  S A -> 9876#
  S B -> 5432#
  S C -> 1097#

t :: T -> Int#
t x = case x of     
  T (E 0) -> 9630#
  T (E 1) -> 8529#
  T (E _) -> 7418#


benchmark :: IO ()
benchmark = defaultMain [ bench "d" $ whnf d' A
                        , bench "e" $ whnf e' (E 0)
                        , bench "s" $ whnf s' (S A) 
                        , bench "t" $ whnf t' (T (E 0))
                        ]
  where
    d' x = I# (d x)
    e' x = I# (e x)
    s' x = I# (s x)
    t' x = I# (t x)    

heapTest :: (NFData a,Show a,Eq a,Enum a,Bounded a) => a -> IO ()
heapTest x = print $ head $ force $ reverse $ take 100000 $ iterate (force . succ') x

main :: IO ()
main =    
#if   defined TEST_D
     heapTest (A :: D)
#elif defined TEST_E                
     heapTest (E 0 :: E)
#elif defined TEST_S
     heapTest (S A :: S)
#elif defined TEST_T                
     heapTest (T (E 0) :: T)
#else
     benchmark
#endif

-- A minor rant: 
-- For reliable statistics, I hope Criterion will run the code in *random order*,
-- at least for comparing functions with the same type. Elapsed times on my system are just too
-- noisy to conclude anything.

用于基准测试的 makefile:


GHC=/usr/bin/ghc
# If you dont't like the ATT syntax in the output assembly, use this: -fllvm -optlc --x86-asm-syntax=intel
GHC_DEBUG_FLAGS= -keep-s-file -keep-llvm-file  # -optlc --x86-asm-syntax=intel
GHCFLAGS=-O2 -funbox-strict-fields -rtsopts -fllvm -fwarn-missing-signatures
GHC_MAKE=$(GHC) --make $(GHCFLAGS)
GHC_PROF_MAKE=$(GHC)  -prof  -auto-all -caf-all --make $(GHCFLAGS)

all : benchmark enumtest_all

enumtest_d : EnumTest.hs
    $(GHC_MAKE) -o $@ $^ -DTEST_D

enumtest_e : EnumTest.hs
    $(GHC_MAKE) -o $@ $^ -DTEST_E

enumtest_s : EnumTest.hs
    $(GHC_MAKE) -o $@ $^ -DTEST_S

enumtest_t : EnumTest.hs
    $(GHC_MAKE) -o $@ $^ -DTEST_T

enumtest_all : enumtest_d enumtest_e enumtest_s enumtest_t
    for x in $^; do ./$$x +RTS -sstderr ;done

benchmark : EnumTest
    time ./$^

% : %.hs
    $(GHC_MAKE) -o $@ $^

%.core : %.hs
    $(GHC)  -S  $(GHCFLAGS)   $(GHC_DEBUG_FLAGS) -ddump-simpl -dsuppress-all -dsuppress-coercions -ddump-stranal $^ > $@

clean :
    rm *.hi *.o *.core *.s enumtest_? ; true

非常感谢你!

4

2 回答 2

8

第一的

Daniel Fischer 在他的回答中建议,对多构造函数数据类型的严格字段进行枚举可能会阻止某些优化。

你误解了。如果您有一个C类型的构造函数,无论该类型是否具有多个构造函数或只有一个,具有 type 的严格字段T,那么如果是围绕不可打包类型的新类型包装器C ... !T ...,则可以解压缩该严格字段,但不是TifT是一个枚举。原则上也应该可以解包类型值的构造函数标记T,但 GHC 只是不这样做(这可能是有原因的,它可能比我看到的更复杂)。然而,对于足够小的枚举类型,Mikhail Gushenkov 提到的指针标记应该具有或多或少相同的效果(也许不完全一样)。

但是对于具有超过 3 或 7 个(对于 64 位字)构造函数的枚举类型,在某些情况下必须遵循指针,差异应该会显现出来。

二、简答

实际上我真正的问题是,当性能很重要时,尝试将枚举转换为新类型是否值得?

有时。

转换是否真正提高性能以及提高多少,取决于您对这些值所做的事情。它还可能使您的程序变慢。它可能会使用更多内存(见下文)。

没有一般规则,每个案例都需要评估。有些模式 newtype-wrappedInt更快,有些模式更慢。一个典型的程序将包含两者的实例,并且必须找出哪个占主导地位。


现在到基准测试。

我冒昧地更改了基准测试中的参数,使用C代替AE 2代替E 0. 结果是这些新类型的速度稍快一些:

warming up
estimating clock resolution...
mean is 1.549612 us (640001 iterations)
found 4506 outliers among 639999 samples (0.7%)
  3639 (0.6%) high severe
estimating cost of a clock call...
mean is 39.24624 ns (12 iterations)
found 2 outliers among 12 samples (16.7%)
  1 (8.3%) low mild
  1 (8.3%) high severe

benchmarking d
mean: 12.12989 ns, lb 12.01136 ns, ub 12.32002 ns, ci 0.950
std dev: 755.9999 ps, lb 529.5348 ps, ub 1.034185 ns, ci 0.950
found 17 outliers among 100 samples (17.0%)
  17 (17.0%) high severe
variance introduced by outliers: 59.503%
variance is severely inflated by outliers

benchmarking e
mean: 10.82692 ns, lb 10.73286 ns, ub 10.98045 ns, ci 0.950
std dev: 604.1786 ps, lb 416.5018 ps, ub 871.0923 ps, ci 0.950
found 10 outliers among 100 samples (10.0%)
  4 (4.0%) high mild
  6 (6.0%) high severe
variance introduced by outliers: 53.482%
variance is severely inflated by outliers

benchmarking s
mean: 13.18192 ns, lb 13.11898 ns, ub 13.25911 ns, ci 0.950
std dev: 354.1332 ps, lb 300.2860 ps, ub 406.2424 ps, ci 0.950
found 13 outliers among 100 samples (13.0%)
  13 (13.0%) high mild
variance introduced by outliers: 20.952%
variance is moderately inflated by outliers

benchmarking t
mean: 11.16461 ns, lb 11.02716 ns, ub 11.37018 ns, ci 0.950
std dev: 853.2152 ps, lb 602.5197 ps, ub 1.086899 ns, ci 0.950
found 14 outliers among 100 samples (14.0%)
  3 (3.0%) high mild
  11 (11.0%) high severe
variance introduced by outliers: 68.689%
variance is severely inflated by outliers

因此,基准在这两种情况下都没有显着差异,总体结果取决于提供的论点。B分别。E 1,差异较小,但在我的运行中,新类型也在那里获胜。

但是请注意,clock调用的估计成本大约是其中任何一个的平均值的四倍,估计时钟分辨率超过 100 倍。我不相信这些结果是可靠的。考虑到我在系统上观察到的短期基准测试差异,我不相信任何运行时间少于 10 微秒的基准测试。我更喜欢运行更长时间的测试,因为结果更稳定并且产生的异常值更少。

关于

heapTest x = print $ head $ force $ reverse $ take 100000 $ iterate (force . succ') x

不幸iterate (force . succ')的是,在构造列表时不会强制列表的元素,因此您会获得一个 thunk 列表(深度增加),反转该列表的初始段,然后强制列表元素。

因此,其中完成的大部分工作和分配是 thunk 和列表的构建,然后是 thunk 的评估。如果您通过在生成元素时强制元素来防止构建大型 thunk,您将获得更有意义的结果,

iterate' :: (a -> a) -> a -> [a]
iterate' f !a = a : iterate' f (f a)

(爆炸模式 - WHNF - 足以完全评估所讨论类型的值)。

尽管如此,枚举变量和新类型变量之间的分配数字仍然存在明显且一致的差异,这也仍然存在于iterate'. 而且,如果不是反转初始段并采用其中head的那个,而是简单地采用list !! index,它变得更加令人印象深刻,因为其他数字(复制字节,最大驻留时间)然后很小。

原因是列表元素不能拆箱,所以列表单元格中包含指向元素值的指针,而枚举值是共享的(A整个程序中只有一个),所以这些指针都指向同一个对象,但整数不共享,因此每个列表单元都指向不同的对象。

分配的差异在您的系统上几乎正好是 800,000 字节,而在我的 1,600,000 上。

这就是 200,000 个单词所需要的,100,000 个Word8(或Word; Int,...)的分配需要(每个值,一个单词用于构造函数,一个用于 a Word#or Int#)。

于 2012-10-13T17:10:21.927 回答
7

在不查看编译器输出的情况下,我认为您的代码的新类型版本没有速度增加可能是由于指针标记。在 x86 上,GHC 在每个指针中保留 2 位用于有关指向闭包的信息。00 表示“未评估或未知”,其他 3 种情况对已评估构造函数的实际标记进行编码。此信息由垃圾收集器动态更新。由于您的测试数据类型中只有 3 个案例,它们总是适合标记位,因此模式匹配从不需要间接。尝试向您的数据类型添加更多案例,看看会发生什么。您可以在本文中找到有关动态指针标记的更多信息:

使用动态指针标记更快的惰性

Simon Marlow、Alexey Rodriguez Yakushev 和 Simon Peyton Jones,ICFP 2007。

于 2012-10-13T14:41:49.100 回答