我有一些高性能代码。使用SSEn和AVX的SIMD实现需要约30条指令，而使用4096字节查找表的版本只需要约8条指令。在微基准测试中，查找表快了40%。如果我进行缓存无效化测试，每100次迭代，它们看起来差不多。在我的实际程序中，似乎非加载版本更快，但很难得到可靠的测量结果，而我的测量结果两种方式都有过。
我想知道是否有一些好的方法来考虑哪个更好使用，或者这种决策的标准基准测试技术。
2个回答
14
查找表在现实世界的代码中很少能提高性能，特别是当它们大到4k字节时。现代处理器执行计算非常快，因此通常比尝试将它们缓存在查找表中要更快，除非这些计算本身过于昂贵。这里的情况显然不是这样的，因为只涉及30个指令与8个指令之间的差异。
微基准测试表明基于LUT的方法更快的原因是整个LUT被加载到缓存中并且从未被驱逐。这使得它的使用实际上是免费的，因此您比较了执行8个和30个指令。您可以猜测哪个会更快。事实上，您已经猜到并通过显式缓存失效证明了这一点。
在现实世界的代码中，除非您处理非常短小、紧密的循环，否则LUT将不可避免地从缓存中驱逐出去（特别是如果它像这个LUT一样大，或者如果您在调用被优化代码之间执行了大量代码），您将需要重新加载它的代价。您似乎没有足够多的操作需要同时执行，以便通过推测性加载来缓解此代价。
（大）LUT的另一个隐藏成本是它们可能会将代码从缓存中驱逐出去，因为大多数现代处理器都有统一的数据和指令缓存。因此，即使基于LUT的实现略微更快，它也会很强地减慢其他所有东西的速度。一个微基准测试无法显示这一点。（但实际上，在可行的情况下，对您的实际代码进行基准测试总是件好事。如果不行，请继续阅读。）
我的经验法则是，如果在现实世界的基准测试中，基于LUT的方法并未明显提高性能，我就不会使用它。看起来在这个问题上也是如此。如果基准测试结果太接近无法判断，则无所谓，只需选择不会让您的代码膨胀4k的实现即可。
微基准测试表明基于LUT的方法更快的原因是整个LUT被加载到缓存中并且从未被驱逐。这使得它的使用实际上是免费的，因此您比较了执行8个和30个指令。您可以猜测哪个会更快。事实上，您已经猜到并通过显式缓存失效证明了这一点。
在现实世界的代码中，除非您处理非常短小、紧密的循环，否则LUT将不可避免地从缓存中驱逐出去（特别是如果它像这个LUT一样大，或者如果您在调用被优化代码之间执行了大量代码），您将需要重新加载它的代价。您似乎没有足够多的操作需要同时执行，以便通过推测性加载来缓解此代价。
（大）LUT的另一个隐藏成本是它们可能会将代码从缓存中驱逐出去，因为大多数现代处理器都有统一的数据和指令缓存。因此，即使基于LUT的实现略微更快，它也会很强地减慢其他所有东西的速度。一个微基准测试无法显示这一点。（但实际上，在可行的情况下，对您的实际代码进行基准测试总是件好事。如果不行，请继续阅读。）
我的经验法则是，如果在现实世界的基准测试中，基于LUT的方法并未明显提高性能，我就不会使用它。看起来在这个问题上也是如此。如果基准测试结果太接近无法判断，则无所谓，只需选择不会让您的代码膨胀4k的实现即可。
- Cody Gray
2
谢谢您的详细解释。如果您有任何方便的资源可以阅读，了解如何针对现代处理器进行此类优化，我将不胜感激。 - Tumbleweed53
2在 [tag:x86] tag wiki 中有很多资源。请查看“性能调整”部分，特别是 Agner Fog 的优化手册。虽然阅读起来相当密集，但并不是你一个下午就能读完或者第一次就能理解的东西。此外，在 Stack Overflow 上也有很多好的答案。其中一些链接在标签维基中，其他的则需要通过其他方式找到。@iodine - Cody Gray
9
Cody Gray已经涵盖了大部分内容，所以我只会加入一些自己的想法。请注意，我对LUT的看法并不像Cody那么消极：与其给它们一个普遍的“thumbs down”，我认为您需要仔细分析缺点。特别是，LUT越小，就越有可能将其与计算方法进行苹果对苹果的比较。
通常有些情况下，即时计算这些值非常昂贵，或者仅需要小型LUT。虽然在接近平局的情况下，我也使用相同的经验法则：如果LUT方法只是稍微快一点，我通常会选择计算方法，但也有一些例外情况（例如，输入大小非常大，使得LUT将保留并用于许多计算）。
SIMD
本节后面的大部分讨论都不是SIMD特定的-它适用于标量和SIMD代码。在我们到达那里之前，让我们谈一谈LUT，因为它与SIMD有关。
对于SIMD代码，LUT有一些优点，但也有额外的缺点。主要缺点是，在下面讨论的PSHUFB类型诡计之外，没有好的SIMD等价于标量LUT代码。也就是说，虽然你可以使用SIMD每个指令进行N（其中N是SIMD宽度）个并行独立计算，但通常不能进行N个查找。通常情况下，你在SIMD代码中每个周期的查找次数与LUT代码中的查找次数相同，现代硬件中2个/周期是一个常见的数字。
gather指令可用，但它无法克服这个基本限制：你仍然会受到每周期2次加载的限制。在gather中，你能够期望的最好情况是它能够注意到两个加载地址相同（或者至少“足够接近”），以便它们可以由同一次加载满足。6
而SIMD让你做的是更宽的加载。因此，你可以一次性加载32个连续字节。这通常对于直接向量化标量查找没有用处，但它可以启用一些其他技巧（例如，向量本身可以是一个表，你可以使用“寄存器中的LUT”之类的东西进行第二次查找，如下所述）。另一方面，在SIMD代码中，LUT通常会发现一个新的利基，因为：
您将代码向量化意味着您可能预计中等或大型问题规模，这有助于分摊LUT的缓存成本。
与标量代码相比，SIMD更喜欢加载许多掩码和其他常量：但是通过“计算”计算洗牌掩码等内容通常很困难，因此LUT通常是自然的选择。
SIMD指令集通常没有直接加载立即常量的方法，不像它们的标量兄弟，因此您通常会从内存中加载固定常量。在那时，如果某些后续计算的部分可以通过查找而不是加载固定常量来折叠到加载中，请看是否有意义（您已经支付了延迟惩罚等）。
SIMD指令集通常具有可重新用于“寄存器内查找”的洗牌/置换指令功能，如下所述。
在使用SIMD代码进行LUT时，请记住要保持表格的小型化，如果可以的话，应避免16或32字节宽的表格条目。除了下面缩小表格的技巧外，如果条目具有某些规律性，您还可以经常使用广播或“解包”指令。在某些情况下（最近的x86），这些指令可能是“免费”的，当替换普通加载时。
增量决策问题
确实，微基准测试几乎总是不公平地支持基于LUT的方法-但是它对特定代码的影响程度取决于很多因素。像往常一样，最好的方法是简单地对真实负载进行两种方式的分析。当然，这并不总是切实可行的，并且还存在“增量决策问题”1...
如果您基于基准测试做出一系列优化决策，并根据实际基准测试每次选择“最佳”方法，那么后续的决策可能会使早期的决策失效。例如，假设您正在考虑为函数A使用LUT或计算。您可能会发现，在实际基准测试中，LUT略快，因此您会实现它。第二天，您再次测试功能B的新实现，再次使用LUT与计算方法进行比较 - 您可能再次发现LUT比计算更好，因此您会实现它 - 但是如果您回头测试A，结果可能会不同！ 现在，由于为函数B添加了LUT导致缓存争用增加，因此A可能更适合使用计算方法。如果您按相反的顺序优化函数，则不会出现这个问题2。因此，原则上，函数A和B需要一起优化，这个原则通常也适用于整个程序。此外，您对A和B的决策还会影响一些假设未来的函数C，即使尚未编写，它也可能想要执行一些查找，并且可能比A或B更好地利用有限的缓存空间。
不仅需要在实际环境中进行基准测试，还需要考虑对现有和未来功能的影响。当实际测试不可行或无效时，或者您想验证测试结果的另一种方法时，可以尝试从第一原理估算LUT方法的性能范围。例如，将缓存丢失到DRAM的某个大致数字（如200个周期）作为例子，然后可以估算算法各种迭代大小下LUT的最坏性能。例如，如果LUT方法在命中缓存时需要10个周期，而计算方法需要20个周期，并且具有640字节（10个高速缓存行）的表，则您可能需要支付2000个周期的成本才能带入整个LUT，因此您需要至少迭代约200次才能收回成本。您可能还希望将缓存丢失成本翻倍，因为将LUT放入高速缓存中通常也会导致被驱逐线路的下游丢失。
以这种方式，有时您可以说：“是的，由于缓存效应，LUT的最坏情况成本为X个周期，但我们几乎总是在每次调用方法时节省Z个周期/调用，因此我们几乎总是能够弥补这些成本。” 当然，这只是一个粗略和简单的最坏情况估计。如果您了解应用程序的一些更详细的特征，例如整个工作集是否通常适合某个级别的缓存中，您可能能够做出一些更好的估计。最后，您甚至可以考虑使用cachegrind等工具，以获得有关LUT和计算代码与缓存交互的定量洞察（但也许那个时间也可以花在生成真实世界的测试用例上）。
I-Cache Misses
在LUT与计算之争中很少提到的一件事是对I $的影响。一些程序，特别是大型面向对象或分支程序4，比数据缓存压力更敏感于指令缓存压力。如果基于计算的方法需要更多的静态指令（即代码方面，而不是执行指令计数），则可能会在某种程度上偏向LUT。例如，在决定是否展开或积极向量化循环时可以使用相同的论点。不幸的是，这种影响本质上是“整个程序”的非线性效应，因此很难测量。也就是说，您可能会多次选择更大但更快的代码而没有明显的指令缓存惩罚，但然后您会越过某个阈值，您会得到几个百分点的下降-所谓的最后一根稻草。因此，它很难在孤立的情况下进行衡量和做出正确的决策。
混合方法
通常比较的是纯LUT与计算方法。通常有一种折中方法，可以使用较小的LUT与一些计算结合使用。
这种计算可能在查找之前进行，其中您将输入域映射到具有较小域的索引中，以便映射到相同索引的所有输入具有相同的答案。一个简单的例子是计算奇偶性：您可以使用一个65K查找表“快速”（在微基准意义上！）完成此操作，但您也可以仅对输入进行异或折叠，例如input ^ (input >> 8)，然后使用底部字节来索引256个条目的表。因此，您可以将表的大小缩小256倍，代价是多了几个指令（但仍比完整计算方法快得多）。有时计算发生在查找之后。这通常采用在稍微“压缩”一些格式中存储表格，然后解压输出的形式。例如，想象一下，一些将字节映射到布尔值的函数。任何这样的函数都可以通过
lut bool[256]实现，成本为256个字节。但是，每个条目实际上只需要一个位（总共32个字节），而不是一个字节 - 如果您愿意在查找后“解压缩”，则可以像return bitwise_lut[value] & (1 << (value & 7))这样做。一种完全不同的混合方法是在运行时基于问题规模在 LUT 和计算方法之间进行选择。例如，你可能有一个基于 LUT 的方法来解码某些 base64 编码数据，你知道它很快但会对缓存产生非平凡的开销，并且可能会出现预热缺失的情况。另一方面，你可能有一个基于计算的方法，虽然从长远来看速度较慢，但不存在上述问题。既然你已经知道了数据的大小，为什么不能根据你计算或通过测试得出的某个交叉点简单地选择最佳算法呢？
这似乎给您提供了两全其美的好处，但肯定不是免费的：您需要付出代码复杂度、测试复杂度、一个算法中可能存在而另一个算法中不存在的延迟错误的风险、初始检查时偶尔出现的分支误判以及增加的总代码大小。
减少缓存缺失
很明显，影响 LUT 算法性能的主要难以衡量的因素是缓存影响。除了上述方法，有没有其他技巧可以用来减少它们？将 LUT 放置在代码旁边
原则上，对于非常小的查找表（LUT），您可以将LUT放在与代码相同的缓存行中。如果您的LUT比缓存行稍小，则此方法效果最佳；具体而言，如果将其添加到函数的大小不会改变组合LUT +代码的总缓存行数，则效果最佳，但即使不是这种情况，它仍可能具有小优势5。我不确定为什么这种方法没有被更多使用，也许有我不知道的一些缺点。
GP和SIMD寄存器中的LUT
“将LUT放在代码附近”的极端版本是将LUT定位在代码中。在标量代码中，您可以通过将常量加载到寄存器中，然后执行类似于变量移位和掩码的操作来选择寄存器中的元素。例如，您可以使用一个寄存器作为16个元素的布尔LUT来计算奇偶校验。一般来说，一个N位的通用寄存器可以用来实现不超过N位的LUT。因此，64位寄存器可以为字节值实现8个元素的LUT，或为布尔值实现64个元素的LUT等。
在x86-64 SIMD世界中，您可以通过
PSHUFB指令（首次出现于SSSE3）将这个想法发挥到极致。在其128位SSE版本中，它实际上允许您在单个周期内执行16个并行的4位到8位查找。AVX2版本允许您同时执行32个这样的查找。因此，您可以进行高强度查找，而几乎没有真正LUT的大部分缺点（即表格保存在寄存器中 - 尽管您可能需要一次加载才能将其放入其中）。这仅适用于小型表（16个元素），尽管您可以通过使用2、4、...，
PSHUFB操作和相似数量的混合操作将其扩展到32、64等元素表，但这仍然只适用于相当小的表。
1或许你也可以称之为“路径依赖优化”或“非加性优化”问题。
2当然，知道在这种情况下优化B然后再优化A会起作用更多的是学术意义而非实际价值，因为没有好的方法事先知道正确的顺序。
3这比你想象的要常见得多——有效的真实世界测试不仅仅是懒惰所导致的，还可能包括许多其他因素，例如(a)没有单一的“规范”负载，因为应用程序或库在非常不同的上下文中使用，(b)没有“规范”负载，因为应用程序未发布，实际使用模式尚不清楚，(c)无法在未来的硬件上进行测试，甚至可能尚不存在，(d)整个应用程序比所涉及的函数要大得多，差异在噪声中被忽略了，(e)由于数据隐私问题（无法获取客户数据），无法复制现实世界的情况等等。
4编译器、浏览器和各种即时编译代码都会想到。
5 例如，通过使用由顺序预取带来的高速缓存行，否则可能会浪费，或者至少将代码和LUT定位在同一页4K中，可能可以节省TLB miss。
6 值得注意的是，在英特尔上，尽管已经发布了至少4个新芯片，gather仍然不支持此功能：即使加载的索引中存在重复，它最多也只能每个周期进行2次加载。
- BeeOnRope
8
2你提出了一些非常好的观点。我承认我可能有点偏见，不太喜欢基于LUT的方法，但这主要是因为我一遍又一遍地尝试过它们，却发现在实际应用中它们总是慢得不可避免。显然，如果计算非常昂贵，那么它们仍然是胜利者。但我发现，人们遵循的许多过时的优化建议都来自于几乎任何计算都很昂贵的时代。现在是重新考虑这些假设的时候了。 - Cody Gray
1一种混合方法可以大大缩小LUT的大小，这几乎肯定是值得考虑的，特别是当与您指出的其他SIMD技巧相结合时，我承认在我的答案中很大程度上忽略了这一点。由于这使LUT保持较小，因此可以缓解许多缺点，同时仍然保留至少一些其主要优点。至于为什么LUT经常不与代码放在一起，我怀疑这是因为在高级语言中难以保证，而且即使对于关键例程，很少有人再降到汇编语言水平。 - Cody Gray
2虽然我与Cody Gray对经典LUT的负面评估持相同看法（未来，我预计指令吞吐量将继续超过内存吞吐量），但我为提到寄存器中查找表而点赞。这种技术并不像应该被广泛知晓。 - njuffa
1@njuffa - 可能是指指令吞吐量超过内存吞吐量，尽管有趣的是，在过去几年中，由于指令吞吐量（每个线程）已经达到瓶颈，它一直相当静态。我也不确定“吞吐量”在这里是否是正确的度量标准 - LUT通常更敏感于DRAM延迟。无论如何，在LUT情况下，您通常会尝试将其排列在L1中，并且随着标量域中增加指令吞吐量，这一点一直很好地扩展。 - BeeOnRope
1在 SIMD 领域中，查找表（LUTs）明显落后了，因为突然间许多指令获得了 16 或 32 倍的加速，但你可以执行的加载数量并没有增加（而且，在 x86 上，当前的“gather”实现也无法帮助）。当然，你可以进行更宽的加载，但这并不能让你的 LUT 代码与 SIMD 同步扩展。 - BeeOnRope
显示剩余3条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接