在x86上,哪个指令可以实现无分支的FP最小值和最大值?

9

引用一下(感谢作者开发和分享算法!):

https://tavianator.com/fast-branchless-raybounding-box-intersections/

由于现代浮点指令集可以在没有分支的情况下计算最小值和最大值

作者提供的相应代码如下:

dmnsn_min(double a, double b)
{
  return a < b ? a : b;
}

我熟悉例如_mm_max_ps,但那是一个向量指令。上面的代码明显是以标量形式使用的。
问题:
  • x86上的标量无分支minmax指令是什么?它是一系列指令吗?
  • 可以安全地假设它会被应用,或者我该如何调用它?
  • 是否值得关注min/max的无分支性?据我所知,对于射线追踪器和/或其他可视化软件,给定射线-盒交集例程,没有可靠的模式供分支预测器选择,因此消除分支是有意义的。我对此正确吗?
  • 最重要的是,所讨论的算法是围绕与(+/-)INFINITY进行比较而构建的。这在我们正在讨论的(未知的)指令和浮点标准方面可靠吗?
以防万一:我熟悉C ++中min和max函数的使用,认为它相关但不完全是我的问题。

4
_mm_max_ps 有一个标量等效函数 _mm_max_ss - harold
1
好的,这是为了展示指令的存在。编译器可以在需要时随时使用它。 - harold
1
@iksemyonov 请查看godbolt上标量使用的示例。 - njuffa
1
有关FPU,请参见“fcomi”和“fcmov”。 - Jester
1
@PeterCordes 由于OP没有询问fmin()fmax()的行为,我没有向他们建议,尽管个人而言,那是我的首选(它是最直接的C代码,我习惯于在平台上工作,其中映射到一个机器指令;很惊讶地发现这对于x86仍然不是真实的)。我也没有对你的答案有任何意见,所以我认为我们是“激烈的一致” :-) - njuffa
显示剩余9条评论
2个回答

34
警告:小心编译器在严格FP模式下将_mm_min_ps/_mm_max_ps(以及_pd)内嵌函数视为可交换,即使汇编指令不是这样。特别是GCC似乎有这个错误:PR72867,这个错误已经在GCC7中修复,但对于_mm_min_ss等标量内嵌函数可能会再次出现或永远不会被修复(_mm_max_ss在clang和gcc之间有不同的行为,GCC bugzilla PR99497)。
GCC知道汇编指令本身的工作原理,在使用它们来实现纯标量代码中的严格FP语义时没有这个问题,只有在使用C/C++内嵌函数时才会出现。
不幸的是,并没有一条指令可以实现fmin(a,b)(保证NaN传播),因此您必须在易于检测问题与更高性能之间做出选择。

大多数矢量 FP 指令都有标量对应物MINSS / MAXSS / MINSD / MAXSD 是你需要的指令。它们按照您预期的方式处理 +/-Infinity。

MINSS a,b 完全 根据 IEEE 规则实现了 (a<b) ? a : b,这意味着它保留源操作数 b 的值,并在 NaN 和 Infinities 时做出了相应处理。(即,在无法比较的情况下,b 保留。) 这意味着 C++ 编译器可以将它们用于 std::min(b,a)std::max(b,a),因为这些函数基于同一表达式。请注意 std:: 函数的操作数顺序为 b,a,与 x86 asm 的 Intel 语法相反,但与 AT&T 语法匹配。

MAXSS a,b 是将 ba 进行比较,并返回较大的值,如果两个数相等,则返回其中任意一个。与此同时,b 保持不变。类似于 std::max(b,a)

使用 x = std::min(arr[i], x); 对数组进行循环(即使用 minss 或者 maxss xmm0, [rsi]),如果内存中存在 NaN,将会获取该 NaN,并且将其后面的非 NaN 元素作为结果返回。因此,你通常不希望这样做,因为它只适用于不包含 NaN 的数组。但是,这意味着您可以在循环外部使用 float v = NAN;,而不是使用第一个元素或 FLT_MAX 或 +Infinity,这可能简化处理可能为空的列表的方式。在汇编代码中,它还是很方便的,可以使用 pcmpeqd xmm0,xmm0 进行初始化以生成一个全为 1 的位模式(负 QNAN),但不幸的是 GCC 的 NAN 使用了不同的位模式。

演示/证明 在Godbolt编译器探索器上,包括展示v = std::min(v, arr[i]);(或max)忽略数组中的NaN,代价是需要加载到寄存器中,然后将其minss到该寄存器。
(注意,数组的最小值应使用向量而不是标量;最好使用多个累加器来隐藏FP延迟。最后,将其减少到一个向量,然后对其进行水平最小值,就像对数组求和或执行点积一样。)
不要尝试在标量浮点数上使用_mm_min_ss; 这个内置函数只能用于__m128操作数,并且Intel的内置函数没有任何方法将标量浮点数放入__m128的低元素中,而不清零高元素或以某种方式进行额外工作。 即使最终结果不依赖于上部元素中的任何内容,大多数编译器实际上仍会发出无用的指令来执行此操作。(Clang通常可以避免这种情况,通过死向量元素的内容应用as-if规则。) 没有像__m256 _mm256_castps128_ps256 (__m128 a)这样的东西,可以将浮点数强制转换为带有垃圾值的__m128。我认为这是一个设计缺陷。 :/

但幸运的是,你不需要手动执行此操作,编译器知道如何为您使用SSE/SSE2 min/max。 只需编写您的C代码即可。 你问题中的函数是理想的:如下所示(Godbolt链接):

// can and does inline to a single MINSD instruction, and can auto-vectorize easily
static inline double
dmnsn_min(double a, double b) {
  return a < b ? a : b;
}

注意它们与NaN的不对称行为:如果操作数无序,dest=src(即如果任一操作数为NaN,则它取第二个操作数)。这对于SIMD条件更新非常有用,见下文。
(如果a和b中有任何一个是NaN,则a和b是无序的。这意味着ab都为假。有关浮点数的许多丑陋细节,请参见Bruce Dawson's series of articles on floating point
相应的_mm_min_ss/_mm_min_ps内部函数可能具有或不具有此行为,这取决于编译器。 我认为内部函数应该具有与asm指令相同的操作数顺序语义,但gcc很长时间以来已将_mm_min_ps的操作数视为可交换甚至没有启用-ffast-math,从gcc4.4或更早版本开始。GCC 7最终对其进行了更改以匹配ICC和clang。

英特尔的在线内部函数查找器没有记录该函数的行为,但它可能不应该是详尽无遗的。汇编指令参考手册并未说明内部函数具备该属性;它只将_mm_min_ss列为MINSS的内部函数。

当我在谷歌上搜索"_mm_min_ps" NaN时,我发现this real code和其他一些关于使用内部函数处理NaN的讨论,因此许多人明显期望该内部函数的行为类似于汇编指令。(这是我昨天写代码时遇到的情况,我已经考虑撰写这篇自问自答的问答文章了。)

鉴于该长期存在的gcc漏洞,希望利用MINPS的NaN处理的可移植代码需要采取预防措施。许多现有Linux发行版上标准的gcc版本将在代码依赖于_mm_min_ps运算数的顺序时错误编译您的代码。因此,您可能需要一个#ifdef来检测实际的gcc(而不是clang等),并提供一种替代方案。或者首先以不同的方式处理:/,例如使用_mm_cmplt_ps和布尔AND/ANDNOT/OR。启用-ffast-math也使_mm_min_ps在所有编译器上都是可交换的。
通常情况下,编译器知道如何使用指令集来正确实现C语义。MINSS和MAXSS比分支更快,因此只需编写可以编译到其中之一的代码。
可交换的_mm_min_ps问题仅适用于内部函数:gcc确切地知道MINSS/MINPS的工作原理,并使用它们来正确实现严格的FP语义(当您不使用-ffast-math时)。
通常情况下,您无需采取任何特殊措施即可从编译器中获得良好的标量代码。但是,如果您关心编译器使用的指令,那么如果编译器没有这样做,您应该手动对代码进行矢量化。
(在极少数情况下,如果条件几乎总是走向一个方向并且延迟比吞吐量更重要,则分支可能是最佳选择。MINPS延迟约为3个周期,但完全预测的分支将添加0个周期到关键路径的依赖链中。)
在C++中,使用定义在std::minstd::max中的函数,它们是基于><定义的,并且不像fminfmax那样对NaN的行为有相同的要求。除非您需要其NaN行为,否则请避免使用fmin and fmax以提高性能。

在C语言中,我认为只需编写自己的minmax函数(如果安全的话可以使用宏)。


在 Godbolt 编译器资源管理器上使用 C 和汇编语言

float minfloat(float a, float b) {
  return (a<b) ? a : b;
}
# any decent compiler (gcc, clang, icc), without any -ffast-math or anything:
    minss   xmm0, xmm1
    ret

// C++
float minfloat_std(float a, float b) { return std::min(a,b); }
  # This implementation of std::min uses (b<a) : b : a;
  # So it can produce the result only in the register that b was in
  # This isn't worse (when inlined), just opposite
    minss   xmm1, xmm0
    movaps  xmm0, xmm1
    ret


float minfloat_fmin(float a, float b) { return fminf(a, b); }

# clang inlines fmin; other compilers just tailcall it.
minfloat_fmin(float, float):
    movaps  xmm2, xmm0
    cmpunordss      xmm2, xmm2
    movaps  xmm3, xmm2
    andps   xmm3, xmm1
    minss   xmm1, xmm0
    andnps  xmm2, xmm1
    orps    xmm2, xmm3
    movaps  xmm0, xmm2
    ret
   # Obviously you don't want this if you don't need it.

如果您想使用_mm_min_ss / _mm_min_ps,请编写代码,使编译器即使没有使用 -ffast-math 选项也能生成良好的汇编代码。
如果您不需要 NaN,或者希望特殊处理它们,请编写以下内容:
lowest = _mm_min_ps(lowest, some_loop_variable);

因此,即使没有AVX,也可以就地更新持有lowest的寄存器。


利用MINPS的NaN行为:

假设你的标量代码是这样的

if(some condition)
    lowest = min(lowest, x);

假设使用CMPPS可以向量化条件,因此您拥有一个元素向量,其中所有位都设置或全部清除。(或者,如果您只关心它们的符号而不关心负零,可能可以直接对浮点数进行ANDPS/ORPS/XORPS操作。这将在符号位中创建一个真值,其他位置为垃圾。BLENDVPS仅查看符号位,因此这可能非常有用。或者您可以使用PSRAD xmm, 31广播符号位。)
实现这一点的直接方法是根据条件掩码将x+Inf混合。或者执行newval = min(lowest, x);并将newval混合到lowest中。(使用BLENDVPS或AND/ANDNOT/OR)。
但是要诀在于全1位是NaN,按位或会传播它。所以:
__m128 inverse_condition = _mm_cmplt_ps(foo, bar);
__m128 x = whatever;


x = _mm_or_ps(x, condition);   // turn elements into NaN where the mask is all-ones
lowest = _mm_min_ps(x, lowest);  // NaN elements in x mean no change in lowest
//  REQUIRES NON-COMMUTATIVE _mm_min_ps: no -ffast-math
//  AND DOESN'T WORK AT ALL WITH MOST GCC VERSIONS.

只有SSE2,我们需要额外两个指令(ORPS和MOVAPS)来实现条件MINPS(除非循环展开可以使MOVAPS消失)。
如果没有SSE4.1 BLENDVPS,则使用ANDPS/ANDNPS/ORPS进行混合,再加上一个额外的MOVAPS。无论如何,ORPS比BLENDVPS更有效率(大多数CPU上为2个微操作)。

无语,感激不尽!如果可以的话,会给予赏金,而不是+10。等我完成一些使用这个光线盒例程的代码后再来阅读。是啊,低浮点数的问题也困扰着我,可惜我还不会AVX,不过很快就会学习了。 - iksemyonov
当然,让问题悬而未决只是一种习惯。在你回答后,让它悬而未决可能就没有太多意义了。我会负责接受答案的,不用担心 :) - iksemyonov
1
@Zboson:std::min和std::max可以处理NaN,但它们的处理方式与fmin不同。虽然很容易争论它们的处理方式是无用的。 - Peter Cordes
1
我想我的主要观点是,许多人认为他们不需要NAN,但实际上他们可能确实需要。但这只是一种直觉,所以我无法进一步辩论。 - Z boson
1
@Zboson:是的,我知道你的意思。NaN非常好,因为它会污染下游的所有内容,所以你会在结果中得到NaN,告诉你有问题。任何打败度量的东西都是一个劣势。 - Peter Cordes
显示剩余12条评论

2
彼得·科德斯的回答非常好,我只是想提供一些更短的逐点回答:
- x86上的标量无分支minmax指令是什么?它是一系列指令吗?
我指的是minss/minsd。即使没有这样的指令,其他架构也应该能够使用条件移动实现无分支。
- 可以安全地假设它将被应用,或者如何调用它? gccclang都会将(a < b) ? a : b优化为minss/minsd,所以我不需要使用内部函数。但不能确定其他编译器是否会这样做。
- 有必要关注min/max的无分支性吗?据我所知,对于光线跟踪器和/或其他可视化软件,给定光线 - 盒交集例程,没有可靠的模式供分支预测器选择,因此消除分支是有意义的。我的理解正确吗?
单个的a < b测试几乎是完全不可预测的,因此避免这些分支非常重要。像if (ray.dir.x != 0.0)这样的测试非常可预测,因此避免这些分支不那么重要,但它确实可以缩小代码大小并使其更容易向量化。最重要的部分可能是消除除法。
- 最重要的是,所讨论的算法是围绕与(+/-)无穷大进行比较构建的。就该指令和浮点标准而言,这是可靠的吗?
是的,minss/minsd的行为与(a < b) ? a : b完全相同,包括它们对无穷大和NaN的处理。
此外,我写了一篇关于NaN和min/max的后续文章,更详细地讨论了这个问题。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接