优化开源纹理合成库

在2020年7月26日发布的背景信息接近2019年底时，我偶然发现了程序世代研究人员阿纳斯塔西娅·奥帕拉(Anastasia Opara)的这篇演讲。在演讲中，她提出了一种新颖的算法，例如基于纹理合成的算法。基于示例的纹理合成的目标是选取一个或多个示例纹理，并合成一个新的视觉上相似的输出纹理。

我真的对这个算法很好奇，想看看我能不能让它运行得更快，作为分析的练习。

踏上旅程，而我不打算详细介绍算法是如何工作的(如果你很好奇，请看阿纳斯塔西娅的演讲！)。理解基本思想是有帮助的。

我们从一个空的输出图像开始，并用示例图像中的几个随机像素作为种子。然后重复以下步骤，直到输出图像填满为止：1.在输出图像中选择一个空像素。我们称它为中心像素。2.找到输出图像中离中心最近的k个非空像素。注意：在前几个步骤中，整个输出图像中的像素可能少于k个。这k个像素相对于中心像素的位置定义了邻域。3.列出示例图像中最有希望的社区列表4.将示例图像中最有希望的候选社区与中心像素周围的社区进行比较，选择最相似的。5.用最佳匹配邻域中中心像素的颜色填充输出图像中的中心像素。

最后一个重要细节是，该算法并行填充多个空像素，以充分利用多核CPU的优势。

失误和微观优化现在是优化的时候了。我做的第一件事是用Xcode Instruments Profiler对几个样本输入运行程序(部分原因是它对我来说是新的)。我甚至找到了一个很酷的图书馆，它让使用锈迹斑斑的仪器变得更容易。使用仪器，我能够看到每条指令对整个程序运行时间的贡献。

能够看到每个指令的时间对我来说是完美的，因为我正在寻找微优化。我在这里使用“微优化”这个词是指一个非常小的变化，与它的规模相比，它的影响相对较大。尽管它们并不总是一个好主意，但微优化似乎是最好的起点，因为它们对我来说不是什么投资。我也不知道项目维护人员是否会对大型代码更改感到兴奋。

看着分析器的输出，我被画到了这一行，它看起来像是嵌套在我们的每像素一次循环中的不必要的数组大小调整操作。

关于解释上面的数字，一个重要的注意事项是，该算法分几次运行，并在多个线程之间进行划分。上图仅显示了一个过程，约占整个程序运行时间的12.6%。但是，每个遍都包含突出显示的指令，并且行为相似。为了粗略估计这一指令的真正影响，这些百分比应该乘以大约8的系数(100/12.6)。因此，突出显示的指令实际上约占整个程序运行时间的9.5%。

在我删除了不必要的数组大小调整指令之后，我再次通过分析器运行程序，似乎确认它快了大约10%，我认为这对于第一次尝试来说已经相当不错了。当然，分析器增加了程序的一些开销，因此为了真正确认我的优化起作用了，我需要在没有任何分析的情况下在几个示例上运行它。当我这样做的时候，我震惊地发现没有任何改善。

那到底是怎么回事？事实证明，我正在运行的Cargo-Instruments命令在缺省情况下以调试模式编译该程序，这关闭了显着的优化。当我在发布模式下构建程序时，不必要的数组大小调整会自动删除。我从中学到了两个非常重要的教训：首先，当你进行基准测试时，你必须仔细考虑你到底要做什么基准测试。其次，编译器非常智能，可以为您进行一些微优化。

我抓取了更多的配置文件，确保这次使用的是发布模式。在仔细研究了一些之后，我发现将源图像中的像素加载到中间缓冲区中花费了大量时间，这些缓冲区稍后用于算法的邻域比较步骤。

同样，使用与上一个性能分析部分相同的运行时调整，此函数似乎占用了总运行时的37.6%。我怀疑缓存未命中在这里是一个重要的原因，但是不管实际的问题来源是什么，我知道读取每个候选对象的邻域像素是很昂贵的。

当然，算法仍然需要做候选邻域比较，所以我不能完全消除读取每个候选邻域像素。对我来说幸运的是，项目中已经有了相关的优化，

该相关优化针对寻找最佳候选邻域时的实际比较步骤。在比较步骤中，通过汇总每个候选邻域的像素与目标邻域像素之间的差异(始终为正)，为每个候选邻域分配一个分数。事实证明，如果你已经知道到目前为止这位候选人的分数将高于最好的候选人的分数，那么你通常可以提前停止总结这些不同之处。

一旦我理解了这一点，我就扩展了这个想法，通过删除中间缓冲区并仅在需要时读取像素来避免读取不必要的比较所需的像素，这似乎极大地减少了平均读取次数。我使用存储库中的参考图像作为输入，在几台具有几种输出大小的不同笔记本电脑上测试了我的优化。根据输出纹理大小、参考图像和我使用的计算机，我的性能似乎提高了大约15-25%。

量化性能影响比我想象的要难得多。程序有太多不同的参数可能会影响性能：参考图像的大小、输出图像的大小、线程的数量。硬件差异也是一个巨大的因素。如果我真的很严格，我会试着把一大堆图像和输出大小放在一起作为基准。由于时间和预算的限制，我没有组装一个非常严格的基准测试，但是我对性能测试问题的理解有了极大的提高。

一旦我确信我的微优化起作用了，我就提出了我的第一个拉请求。它被接受了，但令我惊讶的是，评论家们看到的性能收益远没有我看到的那么好。当他们中的一个在AMD线程裂解器(具有64个虚拟内核)上进行基准测试时，速度提升得如此之小，以至于可能只是噪音。

在这一点上，我决定使用我随处可见的一些Google Cloud免费试用积分来启动一些更大的机器进行测试。在使用64核的机器时，我注意到，就像在线程开膛手上一样，我的微优化并没有带来太多的性能提升。我使用不同的线程数量(从0到64)尝试了多个测试，发现随着线程数量的增加，优化带来的性能收益会下降。

所以在我看来有两种解释。首先，当有多个线程时，我的优化没有节省那么多时间。其次，还有另一个延迟来源，它随着线程数量的增加而增加，它变得如此之大，以至于淹没了我的优化带来的任何明显影响。事实证明，第二种解释是正确的。

延迟的另一个来源原来是线程争用。为了获得每个候选像素的k个最近邻居，该算法使用了一种称为r*树的数据结构。R*树提供了一种有效存储点以进行最近邻查找的方法。在这里，r*树的确切工作方式实际上并不特别重要。问题是整个映像中只有一棵r*树共享。为了防止出现争用情况，r*树被包装在读写锁中。这种类型的锁允许并行读取，但写入必须串行进行。当写入正在进行时，也不能进行读取。由于有大量线程，写入成为一个很大的瓶颈。查看程序运行时与内核数量的关系图也有助于说明这一效果。

我意识到的是，在填充了几个像素之后，k个最近的邻居中的一个距离候选像素非常远的可能性可以忽略不计。所以我把图像分解成r*树的网格。基本思想是，在两个接近的单元中的写入仍然可以阻塞，但是在两个相距较远的单元中的写入现在可以并行完成。更多细节可以在我的第二个拉取请求中提供。要查看此更改带来的改进，我们可以查看下面的合成速度之前/之后的图表：

这里需要注意的一点是，改进后的版本也不能线性扩展。在理想的世界里，也许会，但这里有几个复杂的因素在起作用。首先，该程序有一些初始化成本，并且必须连续合成前几个像素。这两个步骤不能并行化。其次，争论很复杂，可能会在很多地方突然出现。我相信我确实消除了一个很大的争论来源，但我相信还有更多的事情可以做。最后，该算法并不是令人尴尬的并行，最终必须在线程之间共享一定数量的信息。

技巧和权衡总的来说，我对这个项目的结果相当兴奋。然而，我认为值得注意的是，在优化过程中经常会有一些权衡。我在这个项目中看到的一个常见问题是以速度换取灵活性。以前的贡献者奥斯汀·琼斯(Austin Jones)也进行了一些显著的加速。其中之一是用查找表替换一些函数求值。这导致了很大的速度提升，但代价是将输入值的范围限制在每像素8位，因为更大的数字范围将导致查找表的大小爆炸。我的树形网格优化有点类似于结构是二维的。虽然我认为它可以扩展到三维，但如果Bookk想要库生成体素模型或其他东西，它至少要做一点改变。因此，这里的教训是，在您尝试大量优化功能之前，要等到您的功能已经板上钉钉。致谢虽然我在上面说了很多关于优化和剖析的事情，但我不是专家，总是希望了解更多，所以如果您认为有些地方不正确或有任何建议，请随时联系！也非常感谢登船工作室的人，他们对我们很好。