避免调用floor()函数

12

我正在处理一段代码,在其中需要处理不一定在0到1范围内的UV坐标(2D纹理坐标)。举个例子,有时我会得到一个具有u分量为1.2的UV坐标。为了处理这种情况,我正在实现一个包裹(wrapping)功能,通过以下方式实现重复平铺:

u -= floor(u)
v -= floor(v)

这样做会使1.2变为0.2,这是期望的结果。它还处理了负数情况,例如-0.4变为0.6。

然而,这些floor函数调用相当慢。我使用Intel VTune对我的应用程序进行了分析,并且我花费了大量的周期来执行此floor操作。

在对该问题进行一些背景阅读后,我得出了以下函数,它略微更快,但仍然有很多需要改进的空间(我仍然会遇到类型转换惩罚等问题)。

int inline fasterfloor( const float x ) { return x > 0 ? (int) x : (int) x - 1; }

我看到过一些使用内联汇编完成的技巧,但似乎没有任何一个能完全正确工作或有显著的速度提升。

有没有人知道如何处理这种情况的技巧?


你能修复那些导致无效数值的问题吗? - Bill
使用*reinterpret_cast<int32_t*>(&u)和某种位运算(假设IEEE浮点格式)可能是在裸C++中最快的方法,但这会失去一些可移植性。 - Tronic
坐标可以是负数吗?此外,当您没有找到任何具有“任何显着速度改进”的东西时,是否曾经想过这可能只是因为如果存在明显更快的方法,那么编译器首先会使用它呢? ;) - jalf
9个回答

13

虽然是老问题,但我却遇到了,并对没有得到令人满意的答案感到有些不满。

总之,不要使用内联汇编、内建函数或其他给出的解决方案!相反,使用快速/不安全的数学优化(在g++中使用“-ffast-math -funsafe-math-optimizations -fno-math-errno”)。floor()的运行速度之所以如此慢,是因为如果转换会导致溢出(FLT_MAX无法适应任何大小的标量整数类型),它会更改全局状态,这也使得它无法向量化,除非你禁用严格的IEEE-754兼容性,但你应该尽可能不依赖它。使用这些标志进行编译可以禁用这个问题。

一些备注:

  1. 使用标量寄存器的内联汇编不可向量化,这严重限制了编译时的性能。它还要求任何存储在矢量寄存器中的相关值都必须溢出到堆栈中并重新加载到标量寄存器中,这违背了手动优化的目的。

  2. 使用SSE cvttss2si 的内联汇编,按照你提供的方法,实际上比一个简单的for循环加上编译器优化更慢。

    这可能是因为如果允许它将整个代码块向量化在一起,编译器将更好地分配寄存器并避免流水线停顿。对于像这样具有很少内部依赖链和几乎没有机会发生寄存器溢出的短代码片段,它几乎不可能比被asm()包围的手动优化代码表现更差。
  3. 内联汇编是不可移植的,在Visual Studio 64位版本中不受支持,并且极难阅读。内建函数也遭受同样的警告以及上述提到的问题。

所有其他列出的方法都是错误的,这可能比速度慢更糟糕,并且在每种情况下它们所提供的微小性能改进不足以证明该方法的粗糙性。 (int)(x+16.0)-16.0 是如此糟糕以至于我甚至不想碰它,但你的方法也是错误的,因为它会将 floor(-1) 计算成 -2。在数学代码中包含分支逻辑是非常不好的想法,特别是当性能至关重要时,即使是标准库也做不到。所以你的(不正确的)方法应该像 ((int) x) - (x<0.0) 这样,最好使用中间变量来避免重复执行 FPU 移动两次。分支逻辑可能会导致缓存未命中,完全抵消任何性能提升;另外,如果禁用 math errno,则强制类型转换为 int 是任何 floor() 实现中最大的瓶颈。如果你真的不在乎负整数的正确值,那么它可能是一个合理的近似值,但我不会冒风险,除非你非常了解自己的使用情况。
我尝试使用位操作强制类型转换和通过掩码进行四舍五入,就像 SUN 的 newlib 实现在 fmodf 中所做的那样,但是需要很长时间才能弄清楚,在我的机器上慢了几倍,即使没有相关的编译器优化标志。很可能他们为某个古老的 CPU 编写了这段代码,其中浮点运算相对非常昂贵,并且没有向量扩展,更别提向量转换操作了;在任何通用架构上都不再是这种情况(据我所知)。SUN 也是 Quake 3 使用的快速反平方根()例程的发源地;现在大多数体系结构都有一条指令来实现它。微小优化的最大陷阱之一就是它们很快就会过时。

2
有些人懂这个。我希望能够牺牲声望一次性投票+10。 - v.oddou

12

所以你想进行一个非常快的浮点数转整数?据我所知,整数向浮点数转换很快,但至少在MSVC ++上,浮点数向整数转换会调用一个小的辅助函数ftol(),这个函数会做一些复杂的处理来确保进行符合标准的转换。如果您不需要如此严格的转换,可以使用一些汇编技巧,假设您使用的是兼容x86的CPU。

下面是一个用于将浮点数快速舍入为整数的函数,使用MSVC++内联汇编语法(它应该能给你正确的思路):

inline int ftoi_fast(float f)
{
    int i;

    __asm
    {
        fld f
        fistp i
    }

    return i;
}

在MSVC++ 64位中,由于64位编译器拒绝内联汇编,因此您需要一个外部的.asm文件。该函数基本上使用原始的x87 FPU指令来加载浮点数(fld),然后将其存储为整数(fistp)。请注意:您可以通过直接调整CPU上的寄存器来更改此处使用的舍入模式,但不要这样做,否则会破坏很多东西,包括MSVC对sin和cos的实现!

如果您可以假定CPU支持SSE(或者有一种简单的方法来生成支持SSE的代码路径),您也可以尝试:

#include <emmintrin.h>

inline int ftoi_sse1(float f)
{
    return _mm_cvtt_ss2si(_mm_load_ss(&f));     // SSE1 instructions for float->int
}

基本上是相同的操作(将浮点数加载,然后存储为整数),但使用的是 SSE 指令,这些指令稍微快一些。

其中之一应该涵盖了昂贵的浮点数转整数情况,同时任何整数到浮点数的转换都应该便宜。很抱歉,我在这里只提到了 Microsoft 特定的情况,但这是我进行类似性能优化工作的地方,我通过这种方式获得了很大的性能提升。如果可移植性/其他编译器是一个问题,你将不得不寻找其他方法,但这些函数编译成可能只需少于5个时钟周期的两条指令,而不是需要100多个时钟周期的辅助函数。


所有关于32位(x86)构建的优秀建议。如果您可以接受其限制(即使用当前FPU舍入模式,可能是偶数舍入),则ftoi_fast函数比让编译器自动生成代码显着更快。 - Cody Gray
1
然而,对于64位(x64)构建来说,事情要容易得多。因为所有目标系统都支持SSE / SSE2指令,所以编译器将自动发出使用这些指令的代码,而不是调用ftol()函数。因此,在64位构建中,您无需执行使用外部ASM文件的所有工作;实际上,这样做可能会导致比编译器生成的代码稍慢的代码! - Cody Gray
2
请注意,x87现在已经过时了。此外,给定的两个函数都是截断函数,而不是向下取整。 - geometrian
我不得不点踩 :( 因为内联汇编会导致严重的悲观化。(重新排序屏障、内存栅栏、反自动向量化等等..) - v.oddou

3
您想要的操作可以使用fmod函数(对于浮点数而言,应使用fmodf函数)来表示:
#include <math.h>
u = fmodf(u, 1.0f);

很有可能您的编译器会以最有效的方式进行处理。如果您对最后一位的精度很在意,您是否能够设置负数值的下限,比如知道它们永远不会小于-16.0?如果可以,像这样做会为您节省一个条件语句,这在数据无法可靠地预测分支时非常有用:
u = (u + 16.0);  // Does not affect fractional part aside from roundoff errors.
u -= (int)u;     // Recovers fractional part if positive.

就此而言,根据您的数据外观和处理器类型,如果其中很大一部分是负数,但只有很小一部分低于16.0,则在进行条件整数转换之前添加16.0f可能会使您的条件可预测,从而提高速度。或者您的编译器可能会使用其他类型的条件分支来实现这个功能,那么它就没有用处了;除非进行测试并查看生成的汇编代码,否则很难说。


2

如果范围较小,另一个可能行得通的愚蠢想法是 ...

使用位操作从浮点数中提取指数,然后使用查找表查找掩码以从尾数中擦除不需要的位。使用此查找表可以找到最低值(清除小数点以下的位),以避免重新归一化问题。

编辑 我将其删除,因为它太愚蠢了,而且还存在正负问题。由于它被投票赞成了,所以我把它恢复了,让其他人决定它有多愚蠢。


2
并不是那么愚蠢;Newlib中的一个fmod实现(来自Sun)就是这样做的,所以显然至少在某个时候被认为是合理的事情。而且那还是使用任意模数而不是1.0!尽管如此,代码仍然相当复杂。 - Brooks Moses

2
如果您正在使用Visual C++,请检查“启用固有函数”编译器设置。如果启用,则应使大多数数学函数更快(包括floor)。缺点是处理边缘情况(如NaN)可能不正确,但对于游戏来说,您可能并不在意。

0

这个方法不能解决转换成本,但应该在数学上是正确的:

int inline fasterfloor( const float x ) { return x < 0 ? (int) x == x ? (int) x : (int) x -1 : (int) x; }

0

如果可能出现的值的范围非常小,也许你可以使用二分查找来确定底部的值。例如,如果可能出现的值满足 -2 <= x < 2...

if (u < 0.0)
{
  if (u < 1.0)
  {
    //  floor is 0
  }
  else
  {
    //  floor is 1
  }
}
else
{
  if (u < -1.0)
  {
    //  floor is -2
  }
  else
  {
    //  floor is -1
  }
}

我对此不做任何保证 - 我不知道比较效率与floor相比如何,但值得一试。


0
如果您正在循环并使用u和v作为索引坐标,而不是将浮点数取整以获取坐标,请同时保留相同值的浮点数和整数,并将它们一起递增。这将为您提供一个相应的整数,在需要时使用。

你能提供一个代码示例来说明你所描述的内容吗? - Adi Inbar

0
您的u、v值的最大输入范围是多少?如果它是一个相当小的范围,比如-5.0到+5.0,那么重复加/减1.0直到在范围内会比调用昂贵的函数如floor更快。

1
在许多情况下,可能比他当前的“fasterFloor”函数慢。 - Ponkadoodle
可能不会 - 在大多数CPU上,int<->float转换非常昂贵 - 添加/减去1.0只需要一个时钟周期。 - Paul R
是的,但是与条件语句一起使用可能效率不高。if (u>1) u -= 1 至少需要两条指令 - 比较、减法,以及根据架构如何处理条件语句可能需要额外的指令。 - Ponkadoodle
3
一些注释:这种类型的循环(其中结束条件取决于循环内计算的某些内容)通常无法进行流水线处理,在许多系统上会带来很大的性能损失。相比之下,如果有周围代码可用于流水线处理,int<->float转换则很容易进行流水线处理。然而,一般情况下,使用理论无法得到这些问题的可靠答案;要获得真正的答案,原始帖子作者需要对各个版本使用典型数据运行基准测试。 - Brooks Moses
1
哪一种方法更快,将取决于许多因素——输入值的分布、给定 CPU 上不同指令的相对成本、可以交错多少其他周围代码来吸收指令延迟等。正如已经指出的那样,在这种情况下,唯一要做的就是尝试各种解决方案并对它们进行基准测试,以便您可以做出基于证据而非投机的优化决策。 - Paul R

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