在Haskell中优化光线跟踪

几周前，我的同事埃亚尔·卡勒登(EYAL Kalerdon)在Rust分享了他在一个周末实现光线跟踪的方法，这激励了我也尝试一下。然而，我选择了Haskell，因为我认为我不仅会学习光线跟踪技术，还会学习一门新的语言。多年来，Haskell一直是我最喜欢的语言之一，但我从来没有机会真正用它编写代码。

无论如何，实现非常简单，因为我唯一的工作就是将文章中的C++实现移植到Haskell(我们都遵循了这篇文章)。

在本文中，我将执行一个名为ray-tracers的程序，该程序由3个参数参数化，将在命令行上传递，所有其他参数(如aspectRatio、相机设置)都硬编码在程序中。可执行光线跟踪器采用以下参数：

我们将尝试不同的图像宽度值，保持其他两个参数不变，即。在所有的实验中，分别为100和50。请注意，图像高度由程序计算为：

第一个版本ray-tracers-0.1.0很天真，尽管我有意识地没有对代码的任何部分进行任何优化(尽管它是用-O2编译的)，例如，VEC是按照列表实现的，因为标准的列表操作可以用来快速实现其他功能等等。

我做出这些设计决定是为了看看这个朴素的实现执行得有多好，并对使程序执行得非常好所需的更改有一个概念。我还想将执行代码的可读性与朴素的实现进行比较。那么让我们看看它的表现如何。

卡布姆！结果，我们的朴素程序在image-width设置为100的情况下达到了默认的堆栈大小，我发现GHC有一个开放的bug，它说+rts-k2m-rts不会真正将堆栈大小增加到2m。所以我们必须在这个限度内工作。让我们用较小的图像宽度运行几次。

正如我们所看到的，对于不同的图像宽度值，每秒的像素数统计数据大致相同。在此基础上，我们可以推断出384x216图像大约需要33分钟，这太糟糕了-即使它是用-O2编译的。因此，在本文的其余部分，我们将看到此场景是如何改进的。🤞

我们的目标是以一步一步的方式逐步优化代码，并看到每个阶段的结果-我还会共享提交，这样您就可以看到每个阶段的不同之处。在比较性能时，我们将使用38410050作为程序的命令行参数。但是，出于检查和其他目的，我们可能会使用较小的大小，以便程序快速运行。

我将在我的MacBook Pro上运行所有测试，它具有以下配置：

程序运行缓慢的一个明显原因是因为它当前是单线程的。但是，仅仅因为单线程性能差而使程序多线程是不太明智的。如果单线程程序消耗了太多内存，那么多线程程序将在更短的时间跨度内消耗更多内存，从而进一步降低性能。

所以我将-rtsopts添加到GHC-options中。它将使我们能够在运行程序时控制运行时系统(RTS)的行为。因此，我使用-rtsopts重新构建了程序并运行它，将+rts-s rts作为参数传递给运行时系统。其余的参数被传递给我们的程序。选项-s将告诉RTS在终端本身上显示一些有用的统计信息，如下所示。

最有趣的信息是此行：使用中的总内存为1653MB。这是我们的程序消耗和使用的实际内存。1653MB对于40x22大小的图像来说太高了，不是吗？除此之外，还要注意GC花费的时间超过4秒-几乎占程序总时间(20秒)的20%。这实际上是有道理的-您消耗的内存越多，GC需要做的回收工作就越多。

Haskell是一种不严格的语言-大多数表达式的求值方式都不正确。取而代之的是，编译器创建数据块来表示未计算的表达式，因此复合表达式(如a+b*c-d)不会减少到它们的值。相反，它们使结构类似于图形，并进一步组合成更大的图形，消耗了过多的内存并在此过程中减慢了程序的运行速度。这解释了我们在上一节中看到的1653MB内存使用率数字。

无论如何，如果不知道结果最终会被使用，懒惰计算是好的。但如果我们知道结果会被使用，那么懒惰可能是一种诅咒。对我们来说，就是这样！

因此，让我们强制表达式完全计算表达式，这样我们就不会消耗太多内存。为此，我使用了DeepSeq库，它提供了许多功能，其中一个被恰当地命名为force。它使用起来很简单：只需在要计算的表达式前面强制执行即可。

这两个函数是我们创建几乎所有Tunk的地方。这很好，因为我们有几个地方可以进行编辑-基本上是7个力和3个较小但有影响的添加，然后结果(对于相同的宽度)是：

现在内存降到只有2M了！太不可思议了！还要注意GC所花费的时间，生产率达到了97.8%，这是非常好的。除此之外，在时间和每秒像素数方面也没有什么改进。

几乎98%的工作效率，8M内存，花费了1422秒(即24M)，这实际上是有意义的，因为每秒的像素数有所提高。所以我们从33m(外推)提高到24m。

您可能想知道实现此改进所需的实际更改大小。那么，您可以在提交的链接中亲自查看。

由于内存使用得到了控制，现在我们可以考虑使用线程和并行性。但在此之前，让我们启用跟踪并查看线程作用域在没有线程的情况下对我们的程序行为有什么要说的。要启用跟踪，请将-eventlog添加到GHC-options，重新构建，然后在运行时将-l传递给RTS，这将创建ray-tracers.eventlog。

它显示了两个绿色的条。正如标签上所说，较粗的条是关于活动的，较细的条是关于HEC 0的。那么它们到底是什么呢？嗯，HEC代表Haskell执行上下文，根据我们的理解，我们可以说1个HEC意味着1个核心。我的机器上有4个启用了超线程的内核，所以我应该有8个HEC，但是有一个HEC正在工作，这是有意义的，因为它是单线程的。接下来，活动只是所有核心的累积效应。我们在这里的兴趣区是：港灯。

重新构建，然后运行传递-N到RTS。此选项告诉RTS使用所有可用核心(机器上4个，HEC 8个)。您可以控制程序要使用的核心数量，如-n2，它将使用两个核心。在我的例子中，-N转换为-N4。

顺便说一句，GC花费的时间几乎是一样的，这是很好的，但是生产率已经从98%下降到了92.5%。然而，这可以用可能的锁/线程争用来解释，因为它现在是一个多线程程序。让我们来看看线程作用域中的事件日志：

看上去不错。所有内核都在忙于工作(绿色)，偶尔会被GC等待(浅米色)和GC工作(橙色)占用。上面的内容不够明显。因此，选择一个区域并重复放大，直到我们看到以下内容：

正如我们所看到的，长长的淡米色酒吧正在等着我们。不确定我们是否还能改进这一点。但是，知道有一个工具可以让我们如此详细地了解运行时，这是非常令人惊讶的。

在Haskell中，列表实际上是链表，换句话说，是基于节点的数据结构。基于节点的数据结构通常很慢，因为它们对缓存不友好-因此应该避免出现紧密循环。相反，如果我们使用基于记录的结构，如下所示：

除此之外，生产率再次回到97.5%。GC只用了2秒！

Haskell还允许我们在类型声明中强制严格。因此，我们不必总是依赖于像force、DeepSeq和seq这样的东西。这样的严格是用一个感叹号来声明的！--这就是所谓的“砰”声明。

我们由此获得了一些性能上的好处(大多数其他评估都是通过强制本身来强制执行的)。

是的，没错。累加参数有助于尾部递归。它似乎并不总是有效的，但结合其他因素，它有时会发挥作用，提供突然的性能提升。编译器和优化器可能会变得不可预测。

现在我们似乎已经到了一个关头，我们看不到任何明显的东西可以进一步优化。我想现在剖析将帮助我们找到隐藏的东西，这些东西在时间和可能的分配方面仍然非常昂贵。然而，我们的首要任务是时间。

我使用了第二种方法，然后像往常一样在运行时将-p传递给RTS。我还选择了图像宽度为20，因为支持性能分析的程序太慢，而且我们对性能本身并不真正感兴趣，而是对性能分析数据感兴趣。

无论如何，./ray-tracers+rts-p-rts 20 100 50生成了一个名为ray-tracers.prof的文件，其中包含每个函数的非常精细的数据，并且在顶部显示了由几个最昂贵的函数组成的摘要。所以我拿到了这个：

在我们的程序中，函数HIT有两个实现-一个是为Sphere实现的，另一个是为HittableList实现的。在上面的报告中，Sphere的成功被证明是最昂贵的。所以如果说有什么需要优化的话，那就是这个函数。现在，让我们在同一文件中搜索命中，以查看此函数的详细信息：

这里所选的行显示了详细信息：函数HIT已经被调用了28853776次(从右起第五列)，这意味着即使我们可以将该函数改进一些，直观地说，对整个程序的影响也是巨大的。

使用Random>；=1.2比Random-1.1快得多，因为现在StdGen(我们使用的)是基于SplitMix的。

还有一些其他改进，比如使代码更具类型安全性和可读性。通过所有这些更改，我们可以看到以下结果：

在这一点上，我们似乎做不了太多，因为我们似乎已经用完了我们可以使用的所有武器。但是等等，我们的武器库里还有东西：

默认情况下，GHC8.6.5编译器使用-Fasm作为后端。所以我切换到带有-fllvm标志的LLVM后端，并传递了一些优化标志，基本上是这样(提交)：

33M→24M→8M→93S→82S→27S→低于17S😆。

此外，生产率为98.8%，内存使用量为7MB，GC仅需0.194s。因此，通过所有这些改进，我发布了光线跟踪器-0.2.0。

尽管Haskell是一种非常高级的语言，但它仍然可以非常好地运行。Rust(1.43.1)中的实现在24秒内在我的机器上生成相同的图像，因此我不会责怪语言或实现本身。EYAL和我试图找出问题所在，EYAL使用的名为rayon的数据并行库似乎执行得不够好，由于许多人对线程利用不够好有类似的抱怨，rayon开发人员正在努力改进调度器：

一旦解决了这些性能问题并发布了新版本的板条箱，EYAL可能会更新代码，在此期间可能会改进很多东西，如果是这样的话，我还会在这个博客上提供最新的数字。所以请保持联系！