Iod*_*Pit 12 sse x86-64 simd avx microbenchmark
我有一些高度敏感的代码.使用SSEn和AVX的SIMD实现使用大约30条指令,而使用4096字节查找表的版本使用大约8条指令.在微基准测试中,查找表的速度提高了40%.如果我使用microbenchmark,试图使缓存无效100次迭代,它们看起来大致相同.在我的真实程序中,看起来非加载版本更快,但是很难获得可靠的良好测量,并且我已经进行了两种测量.
我只是想知道是否有一些好方法可以考虑哪种方法更适合使用,或者用于此类决策的标准基准测试技术.
Cod*_*ray 13
查找表在实际代码中很少有性能优势,特别是当它们大到4k字节时.现代处理器可以如此快速地执行计算,以便根据需要进行计算几乎总是更快,而不是尝试将它们缓存在查找表中.唯一的例外是计算过于昂贵.当你谈论30对8指令的差异时,情况显然不是这样的.
您的微基准测试表明基于LUT的方法更快的原因是因为整个LUT被加载到缓存中并且从未被驱逐.这使得它的使用有效地免费,因此您在执行8和30指令之间进行比较.好吧,你可以猜出哪一个会更快.:-)事实上,你确实猜到了这一点,并用显式缓存失效证明了这一点.
在现实世界的代码中,除非你正在处理一个非常短而紧密的循环,否则LUT将不可避免地从缓存中逐出(特别是如果它与这个一样大,或者如果你在两次调用之间执行大量代码对正在优化的代码),你将支付重新加载它的罚款.您似乎没有足够的操作需要同时执行,这样可以通过推测性负载减轻这种惩罚.
(大)LUT的其他隐藏成本是它们冒着从缓存中驱逐代码的风险,因为大多数现代处理器具有统一的数据和指令缓存.因此,即使基于LUT的实现稍微快一点,它也会非常强烈地降低其他所有内容的速度.微基准测试不会显示这一点.(但实际上对您的真实代码进行基准测试将会是可行的.如果不可行,请继续阅读.)
我的经验法则是,如果基于LUT的方法在实际基准测试中没有明显的性能胜过其他方法,我就不会使用它.听起来就是这种情况.如果基准测试结果都分不出来,没关系,所以挑选的实施不通过4K臃肿的代码.
Cody Gray已经涵盖了上面的大部分基础,所以我只想添加一些自己的想法.请注意,我对LUT的负面影响不如Cody:我认为你需要仔细分析缺点,而不是给他们一般的"大拇指向下".特别是,LUT越小,就越可能将苹果换成计算方法.
通常情况下,在运行中计算值非常昂贵,或者只需要很小的LUT.我确实使用相同的经验法则:如果LUT方法只有一点点快,我通常会选择计算方法,但有一些例外(例如,非常大的输入大小,使得LUT将是驻留并用于许多计算).
本节后面的大多数讨论都不是特定于SIMD的 - 它适用于标量和SIMD代码.在我们到达那里之前,让我们先谈谈LUT,因为它与SIMD有关.
对于SIMD代码,LUT具有一些优点并且还具有其他缺点.主要缺点是,在PSHUFB下面讨论的类型欺骗之外,没有与标量LUT代码等效的良好SIMD.也就是说,虽然您可以使用SIMD对每个指令进行N(其中N是SIMD宽度)并行独立计算,但通常不能进行N次查找.通常,您在SIMD代码中每个周期的限制次数与LUT代码相同,其中2 /周期是现代硬件的常用数量.
这种限制不仅仅是SIMD ISA中的一些疏忽 - 它是L1缓存设计方式的一个相当基本的结果:它们只有非常少的读端口(如上所述,2是常见的),每个增加的端口显着增加了L1大小,功耗,延迟等.所以你不会看到通用CPU很快就能从内存中提供16路负载.您经常会看到gather可用的指令,但它没有解决这个基本限制:您仍然会受到每周期2次加载限制的限制.你可以期待的最好的gather是它可以注意到两个负载在同一地址(或至少"足够接近"),以便它们可以被相同的负载6满足.
什么SIMD 不会让你做的是更广泛的负载.所以你可以一次加载32个连续字节.这通常对于直接矢量化标量查找没有用,但是它可以启用一些其他技巧(例如,矢量本身可以通过表,并且您使用"寄存器中的LUT"进行第二次查找,如下所述).
另一方面,LUT经常在SIMD代码中找到新的利基,因为:
您已经对代码进行了矢量化的事实意味着您可能期望中等或大的问题大小,这有助于分摊LUT的缓存成本.
除了标量代码之外,SIMD还喜欢加载大量的掩码和其他常量:但通常很难通过"计算"计算像随机掩码这样的东西,所以LUT通常很适合这里.
与标量兄弟不同,SIMD指令集通常无法直接加载立即常量,因此无论如何您经常从内存中加载固定常量.此时,通过执行查找而不是加载固定常量(您已经支付延迟惩罚等)来查看后续计算的某些部分是否可以折叠到负载中是有意义的.
SIMD指令集通常具有混洗/置换指令,这些指令可以重新用于"在寄存器内查找"功能,如下所述.
在SIMD代码中执行LUT时要记住的一件事是保持表小.如果可以,您希望避免使用16或32字节宽的表条目.除了缩小下表的技术之外,如果条目有规律性,你通常可以在这里使用广播或"解包"指令.在某些情况下(最近的x86),这些指令在替换普通负载时可能是"空闲的".
确实,微基准测试几乎总是不公平地支持基于LUT的方法 - 但是在很大程度上取决于所讨论的代码.像往常一样,决定的最佳方式就是两种方式分析现实世界的负荷.当然,这并不总是实用的,也会受到"增量决策问题"的影响1 ...
如果您根据基准做出一系列优化决策,每次基于实际基准采用"最佳"方法,以后的决策可能会使之前的决策无效.例如,假设您正在考虑对函数A使用LUT或计算.您可能会发现在实际基准测试中,LUT稍快一些,因此您可以实现它.第二天,你再次使用LUT vs计算方法测试函数B的新实现 - 你可能再次发现LUT比计算更好,所以你实现了 - 但如果你回去测试A,结果可能是不同! 现在A使用计算方法可能会更好,因为为函数B添加LUT会导致缓存争用增加.如果您以相反的顺序优化了功能,则不会出现问题2.
因此,原则上,功能A和B需要一起优化,并且相同的原理通常可以应用于整个程序.此外,您对A和B的决定也会影响一些假设的未来函数C,甚至还没有编写,也可能会进行一些查找,并且可能比A或B更好地利用有限的缓存空间.
所有这一切都表明,您不仅需要在现实场景中进行基准测试,还需要考虑现有功能甚至未来功能的影响.
当真实世界的测试不切实际或无效3时,或者您想要另一种方法来验证您的测试结果时,可能会试图从第一原理开始考虑LUT方法的性能范围.
例如,对于像200个周期的DRAM一样,将一些标记号码用于缓存未命中,然后您可以针对算法的各种迭代大小估计LUT的最坏情况性能.例如,如果LUT方法在高速缓存中命中时需要10个周期,而计算方法则需要20个周期,并且具有640字节的表(10个高速缓存行),那么您可能需要支付10*200 = 2,000的成本循环以引入整个LUT,因此您需要迭代至少约200次以支付该成本.您可能还希望将缓存未命中成本加倍,因为将LUT置于高速缓存中可能通常也会导致下游错过任何被驱逐的线路.
通过这种方式,您有时可以说:"是的,LUT由于缓存效应而具有X周期的最坏情况成本,但我们几乎总是支付回来,因为我们通常在节省Z周期/调用时调用方法Y次".
当然,这是一个粗略粗略的最坏情况估计.如果您了解应用程序的一些更详细的特性,例如整个工作集是否通常适合某个级别的缓存,您可以做出更好的估计.最后,您甚至可以考虑像cachegrind这样的工具来定量了解LUT和计算代码如何与缓存交互(但也许这个时间也可以更好地用于生成真实的测试用例).
在LUT与计算辩论中经常提到的一件事是对I $的影响.某些程序,特别是面向对象或分支的程序4 对指令缓存压力比数据缓存压力更敏感.如果基于计算的方法需要更多的静态指令(即代码端,而不是执行的指令计数),它可能稍微有利于LUT.例如,当决定展开或积极地向量化循环时,可以进行相同的论证.
不幸的是,这种效果本质上是"整个程序"和非线性的,因此很难衡量.也就是说,你可以多次选择更大但速度更快的代码,而没有明显的指令缓存惩罚,但是你越过了一些门槛,你就会有几个百分点的下降 - 这种谚语破坏了骆驼的反击.因此,很难孤立地衡量和做出正确的决定.
通常比较的是纯LUT与计算方法.通常有一个中间地带,你可以使用更小的LUT和一些计算.
此计算可能在查找之前进行,您可以将输入域映射到具有较小域的索引,以便映射到同一索引的所有输入具有相同的答案.一个简单的例子就是计算奇偶校验:您可以使用65K查找表"快速"(在微基准测试意义上!)执行此操作,但您也可以对输入进行xor-fold,input ^ (input >> 8)然后使用底部字节索引到256条目表.因此,您将表的大小减少了256倍,但需要更多指令(但仍然比完整计算方法快得多).
有时计算在查找之后发生.这通常采用以稍微更"压缩"的格式存储表并解压缩输出的形式.想象一下,例如,一些将字节映射到布尔值的函数.任何这样的功能都可以通过a实现lut bool[256],代价为256字节.但是,每个条目实际上只需要一位(总共32个字节),而不是一个字节 - 如果您愿意在查找后"解压缩",例如return bitwise_lut[value] & (1 << (value & 7)).
一个完全不同的混合方法是LUT和计算之间做出选择方法在运行时,根据问题的大小.例如,您可能有一种基于LUT的方法来解码某些base64编码数据,您知道这些数据速度很快,但在缓存上会产生非常重要的成本,并且可能会遇到预热,并且您可能采用基于计算的方法,即从长远来看速度较慢,但没有这样的问题.既然您预先了解了数据的大小,为什么不根据您计算或通过测试得出的某些交叉点选择最佳算法？
这可能看起来它给你两全其美,但它肯定不是免费的:你付出代价复杂的代价,测试复杂性,一个算法中的延迟错误的机会,而不是另一个,偶尔分支在初始检查时误预测,并增加了总代码大小.
现在很清楚,LUT算法性能的主要难以测量的因素是缓存影响.我们可以用它来减少它们之外的任何技巧吗？
原则上,对于非常小的LUT,您可以简单地将LUT放在与代码相同的高速缓存行中.如果您的LUT比缓存线稍小,这种方法效果最好; 具体来说,如果将其添加到函数的大小不会改变组合LUT +代码的缓存行总数,则效果最佳,但即使不是这种情况,也可能仍然具有小优势5.
我不确定为什么这个用得不多,也许还有一些我不知道的缺点.
在"放码附近的LUT"方法的极端版本是定位LUT 中的代码.在标量代码中,您可以通过将常量加载到寄存器中,然后执行类似变量shift和掩码的操作来选择寄存器中的元素.例如,您可以使用寄存器作为16元素布尔LUT来计算奇偶校验.
通常,N位通用寄存器可用于实现不超过N位的LUT .因此,64位寄存器可以为字节值实现8元素LUT,或者为布尔值实现64元素LUT等.
在x86-64 SIMD的世界中,您可以通过PSHUFB指令将此想法发挥到极致(首先在SSSE3中提供).在其128位SSE版本中,它有效地允许您在一个周期内执行16个并行的4位到8位查找.AVX2版本允许您并行执行32次此类查找.因此,您可以对类固醇进行查找,而不需要实际LUT的大多数缺点(即,表格保存在寄存器中 - 尽管您可能需要一个负载才能将其放在那里).
这仅适用于小型(16个元素的表) - 尽管您可以将其扩展到32,64等,元素表具有2,4,...,PSHUFB操作和相似数量的混合操作,但这仍然只是适用于相当小的桌子.
1也许您也可以称之为"路径依赖优化"或"非加性优化"问题.
2当然,知道在这种情况下优化B然后A会起作用更具学术价值而不是实际价值,因为没有一种好的方法可以提前知道正确的排序.
3这是你可能会想到的更常见的 - 它不仅仅是懒惰妨碍了有效的实际测试,还包括许多其他因素,例如(a)没有单一的"规范"负载,因为应用程序或库的使用方式非常不同上下文,(b)没有"规范"负载,因为应用程序未发布且实际使用模式尚不清楚,(c)无法测试未来可能尚未存在的硬件,(d)整个应用程序正在比所讨论的功能大得多,噪音中的差异就会消失,(e)由于数据隐私问题而无法复制真实案例(无法获取客户数据)等等.
我想到了编译器,浏览器和各种JIT代码.
5例如,通过使用由顺序预取引入的缓存行,否则可能会浪费,或者至少将代码和LUT定位在同一4K页面中,可能会节省TLB未命中.
6值得注意的是,在英特尔上,尽管至少有4个新芯片发布,gather但仍然没有这样做:即使加载的索引中存在重复,它仍然限制在每个周期最多2个负载.