分析Haskell程序的缓慢性能

Question

我试图用蛮力的方法解决ITA Software的"Word Nubmers"难题.看起来我的Haskell版本比C#/ C++版本慢10多倍.

答案

感谢Bryan O'Sullivan的回答,我能够"纠正"我的程序达到可接受的性能.你可以阅读他的代码比我的清洁得多.我将在这里概述要点.

• Int是Int64在Linux上GHC 64.除非你unsafeCoerce,你应该使用Int.这样可以省去fromIntegral.这样做Int64在Windows 32位GHC只是该死缓慢,避免它.(这实际上不是GHC的错.正如我在下面的博客文章中提到的,32位程序中的64位整数一般都很慢(至少在Windows中))
• -fllvm或-fvia-C表演.
• 宁愿quotRem到divMod,quotRem已经足够了.这让我加速了20%.
• 一般情况下,倾向于Data.Vector以Data.Array作为"阵列"
• 大量使用包装工人模式.

以上几点足以让我比原版大约100%的提升.

在我的博客文章中,我详细介绍了如何将原始程序与Bryan的程序相匹配的逐步说明示例.这里还提到了其他一些观点.

原来的问题

(这可能听起来像"你能为我做的工作"一文,但我认为这样一个具体的例子会非常有启发性,因为剖析Haskell的表现通常被视为一个神话)

(正如评论中所指出的,我认为我误解了这个问题.但是谁在乎,我们可以专注于不同问题的表现)

这是我对该问题的快速回顾的版本:

A wordNumber is defined as

wordNumber 1 = "one"
wordNumber 2 = "onetwo"
wordNumber 3 = "onethree"
wordNumber 15 = "onetwothreefourfivesixseveneightnineteneleventwelvethirteenfourteenfifteen"
...

Problem: Find the 51-billion-th letter of (wordNumber Infinity); assume that letter is found at 'wordNumber x', also find 'sum [1..x]'

从命令的角度来看,一个天真的算法将是2个计数器,一个用于数字之和,一个用于长度之和.继续计算每个wordNumber的长度,并"break"以返回结果.

强制性的暴力方法在C#中实现:http://ideone.com/JjCb3.在我的电脑上找到答案大约需要1.5分钟.还有一个C++实现在我的计算机上运行45秒.

然后我实现了一个蛮力的Haskell版本:http://ideone.com/ngfFq.它无法在我的机器上完成5分钟的计算.(反讽:它的行数多于C#版本)

以下是-pHaskell程序的概况:http://hpaste.org/49934

问题:如何使它与C#版本相比具有相同的性能？我有明显的错误吗？

(注意:我完全清楚强制它不是解决这个问题的正确方法.我主要感兴趣的是使Haskell版本的性能与C#版本相当.现在它至少慢了5倍,所以很明显我失踪了明显的东西)

(注2:它似乎没有空间泄漏.程序在我的计算机上以恒定内存(大约2MB)运行)

(注3:我用`ghc -O2 WordNumber.hs编译)

为了使问题更易于读者阅读,我提供了两个版本的"要点".

// C#
long sumNum = 0;
long sumLen = 0;

long target = 51000000000;
long i = 1;

for (; i < 999999999; i++)
{
    // WordiLength(1)   = 3   "one"
    // WordiLength(101) = 13  "onehundredone"
    long newLength = sumLen + WordiLength(i);
    if (newLength >= target)
        break;

    sumNum += i;
    sumLen = newLength;
}
Console.WriteLine(Wordify(i)[Convert.ToInt32(target - sumLen - 1)]);

-

-- Haskell
-- This has become totally ugly during my squeeze for 
-- performance

-- Tail recursive
-- n-th number (51000000000 in our problem) -> accumulated result -> list of 'zipped' left to try
-- accumulated has the format (sum of numbers, current lengths of the whole chain, the current number)
solve :: Int64 -> (Int64, Int64, Int64) -> [(Int64, Int64)] -> (Int64, Int64, Int64)
solve !n !acc@(!sumNum, !sumLen, !curr) ((!num, !len):xs)
    | sumLen' >= n = (sumNum', sumLen, num)
    | otherwise = solve n (sumNum', sumLen', num) xs
    where
        sumNum' = sumNum + num
        sumLen' = sumLen + len

-- wordLength 1   = 3    "one"
-- wordLength 101 = 13   "onehundredone"
wordLength :: Int64 -> Int64
-- wordLength = ...

solution :: Int64 -> (Int64, Char)
solution !x =
    let (sumNum, sumLen, n) = solve x (0,0,1) (map (\n -> (n, wordLength n)) [1..])
    in (sumNum, (wordify n) !! (fromIntegral $ x - sumLen - 1))

Answer 1

我写了一个包含C++版本(来自Haskell-cafe消息的副本,修复了错误)和Haskell翻译的要点.

请注意,这两者在结构上几乎完全相同.编译时-fllvm,Haskell代码的运行速度大约是C++代码的一半,这非常好.

现在让我们将我的Haskell wordLength代码与你的代码进行比较.你传递了一个额外的不必要的参数,这是不必要的(你在编写我翻译的C++代码时显然已经知道了).此外,大量的爆炸模式表明恐慌; 他们几乎都没用.

你的solve功能也很困惑.

• 您以三种不同的方式传递参数:常规Int,3元组和列表!哇.

• 这个函数的行为必然不是很规律,所以当你通过使用列表来提供计数器时你没有任何风格,你可能会强制GHC分配内存.换句话说,这会混淆代码并使其变慢.

• 通过使用三个参数的元组(没有明显的原因),你再次努力迫使GHC为循环中的每一步分配内存,如果你直接传递参数就可以避免这样做.

• 只有你的n参数以合理的方式处理,但你不需要一个爆炸模式.

• 该只需要一个爆炸模式参数sumNum,因为你从来没有检查它的值,直到循环结束后.GHC的严格分析仪将与其他人打交道.所有其他爆炸模式充其量都是不必要的,最糟糕的是误导.

Answer 2

以下是我在快速调查中可以提出的两点建议:

1. 请注意,Int64当您使用32位版本的GHC时,使用速度非常慢,这是目前Haskell平台的默认设置.这也是之前性能问题的主要恶棍(我还提供了一些细节).

2. 由于原因,我不太明白该divMod功能似乎没有内联.结果,数字在堆上返回.当单独使用div和mod单独wordLength'执行时,它应该完全在堆栈上执行.

可悲的是,我目前没有64位GHC来测试这是否足以解决问题.