Haskell的C代码

Question

所以,我想将C代码的一部分转换为Haskell.我在C中编写了这个部分(这是我想要做的简化示例),但作为我在Haskell中的新手,我无法真正使它工作.

float g(int n, float a, float p, float s)
{
    int c;
    while (n>0)
    {
        c = n % 2;
        if (!c) s += p;
        else s -= p;
        p *= a;
        n--;
    }
    return s;
}

有人有任何想法/解决方案吗？

Answer 1

李的翻译已经相当不错了(好吧,他混淆了奇数和偶数案例⁽¹⁾),但他陷入了几个表演陷阱.

g n a p s =
  if n > 0
  then
    let c = n `mod` 2
        s' = (if c == 0 then (-) else (+)) s p
        p' = p * a
    in g (n-1) a p' s'        
  else s

1. 他用mod而不是rem.后者映射到机器分区,前者执行额外检查以确保非负结果.因此mod有点慢rem,如果要么满足需要 - 因为它们在两个参数都是非负的情况下产生相同的结果; 或者因为结果仅与0比较(这里满足两个条件) - rem是优选的.更好的是,使用更加惯用even(rem由于上述原因使用).但差别并不大.

2. 没有类型签名.这意味着代码是(类型 - 类)多态,因此不可能进行严格性分析,也不进行任何特化.如果代码在特定类型的同一模块中使用,GHC可以(并且通常会在启用优化的情况下)为该特定类型创建一个专用版本,允许严格性分析和其他一些优化(内联类方法等)(+). ),在这种情况下,一个人不支付多态性惩罚.但是如果使用站点位于不同的模块中,则不会发生这种情况.如果需要(类型 - 类)多态代码,则应标记它INLINABLE或INLINE(对于GHC <7),以便在.hi文件中公开其展开,并且可以在使用站点对该函数进行专门化和优化.

   由于g是递归的,所以不能内联[意思是,GHC不能内联它; 原则上它是可能的]在使用地点,这通常可以实现比仅仅专业化更多的优化.

   一种通常允许对递归函数进行更好优化的技术是工作者/包装器转换.一个创建一个调用递归(本地)worker的包装器,然后可以内联非递归包装器,并且当使用已知参数调用worker时,可以启用进一步优化,如常量折叠,或者在函数参数的情况下,内联.特别是当与静态参数转换相结合时,后者通常会产生巨大的影响(递归调用中永不改变的参数不作为参数传递给递归工作者).

   在这种情况下,我们只有一个类型的静态参数Float,因此使用SAT的工作者/包装器转换通常没有区别(根据经验,SAT是值得的.

   • static参数是一个函数
   • 几个非函数参数是静态的

   因此,根据这条规则,我们不应期望w/w + SAT有任何好处,而且一般来说,没有任何好处.这里我们有一个特殊情况,其中w/w + SAT可以产生很大的差异,那就是当因子a为1. GHC {-# RULES #-}对于各种类型消除乘法1,并且使用如此短的循环体,乘法更多或者每次迭代的次数减少有所不同,在应用了第3点和第4点后,运行时间减少了约40%.(对于浮点类型,没有RULES乘以0或者乘以,-1因为对于NaN,0*x = 0resp.(-1)*x = -x不适用.)对于所有其他a,w/w + SATed

   {-# INLINABLE g #-}
   g n a p s = worker n p s
     where
       worker n p s
         | n <= 0    = s
         | otherwise = let s' = if even n then s + p else s - p
                       in worker (n-1) a (p*a) s'
   

   与完成相同优化的顶级递归版本的执行速度不同.

3. 严格.GHC的严格分析仪很好,但并不完美.通过算法无法看到足够的确定函数

   • pif中的严格n >= 1 (假设加法 - (+)在两个参数中都是严格的)
   • 也严格aif n >= 2(假设(*)两个论点都严格)

   然后生产一个严格的工人.相反,你会得到一个使用unboxed Int#for n和unboxed Float#for 的工人s(我在Int -> Float -> Float -> Float -> Float这里使用的类型,对应于C),并且盒子Float用于a和p.因此,在每次迭代中,您将获得两次拆箱和重新装箱.这花费了(相对)大量的时间,因为除此之外,它只是一些简单的算术和测试.稍微帮助GHC,并使工人(或者g本身,如果你不做工人/包装变换)严格p(例如爆炸模式).这足以允许GHC生产一个使用未装箱值的工人.

4. 使用除法来测试奇偶校验(如果类型Int和使用LLVM后端,则不适用).

   GHC的优化器还没有达到低级别的位,所以本机代码生成器会发出一个除法指令

   x `rem` 2 == 0
   

   并且,当循环体的其余部分与此处一样便宜时,这会花费大量时间.已经教会LLVM的优化器用类型的位掩码替换它Int,因此ghc -O2 -fllvm您不需要手动执行此操作.使用本机代码生成器,替换为

   x .&. 1 == 0
   

   (import Data.Bits当然需要)产生显着的加速(在正常平台上,按位并且比分割快得多).

最后的结果

{-# INLINABLE g #-}
g n a p s = worker n p s
  where
    worker k !ap acc
        | k > 0 = worker (k-1) (ap*a) (if k .&. (1 :: Int) == 0 then acc + ap else acc - ap)
        | otherwise = acc

gcc -O3 -msse2 loop.c除了a = -1gcc用乘数替换乘法(假设所有NaNs等价)之外,其结果与测试值之间的差异不大(对于测试值).

⁽¹⁾他并不孤单,

c = n % 2;
if (!c) s += p;
else s -= p;

似乎真的很棘手,据我所知,每个人⁽²⁾都错了.

⁽²⁾有一个例外;)

Answer 2

作为第一步,让我们简化您的代码:

float g(int n, float a, float p, float s) {
    if (n <= 0) return s;

    float s2 = n % 2 == 0 ? s + p : s - p;
    return g(n - 1, a, a*p, s2)
}

我们已将您的原始函数转换为具有特定结构的递归函数.这是一个序列!我们可以方便地将其转换为Haskell:

gs :: Bool -> Float -> Float -> Float -> [Float]
gs nb a p s = s : gs (not nb) a (a*p) (if nb then s - p else s + p)

最后我们只需要索引这个列表:

g :: Integer -> Float -> Float -> Float -> Float
g n a p s = gs (even n) a p s !! (n - 1)

代码未经过测试,但应该可以使用.如果没有,它可能只是一个错误的错误.

Answer 3

以下是我将如何解决Haskell中的这个问题.首先,我观察到有几个循环合并为一个:我们是

1. 形成几何序列(其因子是p的适当负数版本)
2. 取序列的前缀
3. 总结结果

所以我的解决方案也遵循这个结构,只需要一点点s并且可以p进行测量,因为这就是你的代码所做的.在一个从头开始的版本中,我可能完全放弃这两个参数.

g n a p s = sum (s : take n (iterate (*(-a)) start)) where
    start | odd n     = -p
          | otherwise = p