performance - 分析 Haskell 程序的缓慢性能

Question

我试图解决ITA Software's "Word Nubmers" puzzle使用蛮力方法。看起来我的 Haskell 版本比 C#/C++ 版本慢 10 倍以上。

答案

感谢 Bryan O'Sullivan's answer ，我能够将我的程序“纠正”到可接受的性能。你可以阅读他的代码，这比我的要干净得多。我将在这里概述关键点。

Int是 Int64在 Linux GHC x64 上。除非你 unsafeCoerce ，你应该只使用 Int .这使您不必使用 fromIntegral .做Int64在 Windows 32 位 GHC 上只是 该死的慢，避免。 (这实际上不是 GHC 的错。正如我在下面的博客文章中提到的，32 位程序中的 64 位整数通常很慢(至少在 Windows 中))

-fllvm或 -fvia-C为了表现。

首选 quotRem至divMod , quotRem已经足够了。这给了我 20% 的速度。

一般来说，更喜欢 Data.Vector至Data.Array作为“数组”

自由地使用 wrapper-worker 模式。

以上几点足以让我比我的原始版本提高约 100%。

In my blog post ，我已经详细说明了如何将原始程序转换为与 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++ implementation在我的电脑上运行 45 秒。

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

这里是 -p Haskell 程序简介: 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++ version 的要点(您的 a Haskell-cafe message 的副本，已修复错误)和 Haskell translation .

请注意，两者在结构上几乎相同。使用 -fllvm 编译时，Haskell 代码的运行速度大约是 C++ 代码的一半，相当不错。

现在让我们比较一下我的 Haskell wordLength给你的代码。您传递了一个额外的不必要的参数，这是不必要的(您显然在编写我翻译的 C++ 代码时发现了这一点)。此外，大量的爆炸模式表明 panic ；它们几乎都是无用的。

您的 solve功能也很困惑。

您以三种不同的方式传递参数:常规 Int ，一个三元组和一个列表!哇。

这个函数的行为不一定很规律，所以当你通过使用列表来提供你的计数器在风格上没有任何收获时，你可能会强制 GHC 分配内存。换句话说，这会混淆代码并使其变慢。

通过对三个参数使用一个元组(没有明显的原因)，您再次努力强制 GHC 为循环中的每一步分配内存，而如果您直接传递参数，它可以避免这样做。

只有你的n参数以合理的方式处理，但您不需要在其上使用 bang 模式。

唯一需要 bang 模式的参数是 sumNum ，因为在循环结束之前你永远不会检查它的值。 GHC 的严格分析器将处理其他的。你所有其他的爆炸模式充其量是不必要的，最坏的情况是误导。