避免调用 Floor()

Question

我正在编写一段代码，需要处理不一定在 0 到 1 范围内的 uvs（2D 纹理坐标）。例如，有时我会得到 au 分量为 1.2 的 uv。为了处理这个问题，我正在实现一个包装，通过执行以下操作来导致平铺：

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

这样做会导致 1.2 变成 0.2，这是所需的结果。它还可以处理负面情况，例如 -0.4 变为 0.6。

然而，这些对发言权的调用相当慢。我已经使用 Intel VTune 分析了我的应用程序，并且我花费了大量的周期来执行此底层操作。

在对这个问题进行了一些背景阅读之后，我提出了以下函数，该函数速度更快一些，但仍然有很多不足之处（我仍然会受到类型转换惩罚等）。

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

我已经看到了一些通过内联汇编完成的技巧，但似乎没有任何东西可以完全正确地工作或有任何显着的速度改进。

有谁知道处理这种情况的任何技巧？

Answer 1

老问题，但我遇到了它，这让我有点抽搐，因为它还没有得到令人满意的答案。

TL;DR：*不要**为此使用内联汇编、内在函数或任何其他给定的解决方案！相反，使用快速/不安全的数学优化进行编译（g++ 中的“-ffast-math -funsafe-math-optimizations -fno-math-errno”）。 Floor() 如此慢的原因是，如果转换溢出（FLT_MAX 不适合任何大小的标量整数类型），它会更改全局状态，这也使得向量化变得不可能，除非禁用严格的 IEEE-754 兼容性，无论如何你可能不应该依赖它。使用这些标志进行编译会禁用问题行为。

一些备注：

1. 带有标量寄存器的内联汇编不可矢量化，这会极大地抑制优化编译时的性能。它还要求当前存储在向量寄存器中的任何相关值都溢出到堆栈并重新加载到标量寄存器中，这违背了手动优化的目的。

   使用标

2. 在我的机器上，使用 SSE cvttss2si 和您概述的方法进行内联汇编实际上比带有编译器优化的简单 for 循环慢。
   这可能是因为如果您允许编译器将整个代码块矢量化在一起，那么您的编译器将更好地分配寄存器并避免管道停顿。对于像这样的一小段代码，内部依赖链很少，几乎没有寄存器溢出的可能性，它几乎没有机会比 asm() 包围的手工优化代码做得更糟。

3. 内联汇编不可移植，在 Visual Studio 64 位版本中不受支持，并且极其难以阅读。内在函数也面临与上面列出的相同的警告。

4. 所有其他列出的方法都是不正确的，这可以说比缓慢更糟糕，并且它们在每种情况下都给出了如此边际的性能改进，以至于它不能证明该方法的粗糙性是合理的。 (int)(x+16.0)-16.0 太糟糕了，我什至都不会碰它，但你的方法也是错误的，因为它给了 Floor(-1) 作为-2。当数学代码对性能至关重要以至于标准库无法为您完成这项工作时，在数学代码中包含分支也是一个非常糟糕的主意。所以你的（不正确的）方式应该看起来更像 ((int) x) - (x<0.0)，也许有一个中间，这样你就不必执行 fpu 移动两次。分支可能会导致缓存未命中，这将完全抵消性能的任何提升；另外，如果禁用 math errno，则转换为 int 是任何 Floor() 实现的最大剩余瓶颈。如果您/真​​的/不关心获得负整数的正确值，这可能是一个合理的近似值，但除非您非常了解您的用例，否则我不会冒险。

5. 我尝试使用按位转换和通过位掩码舍入，就像 SUN 的 newlib 实现在 fmodf 中所做的那样，但它花了很长时间才能正确，并且在我的机器上慢了好几倍，即使没有相关的编译器优化标志。很可能，他们为某些古老的 CPU 编写了该代码，其中浮点运算相对非常昂贵，并且没有矢量扩展，更不用说矢量转换操作了； AFAIK 在任何常见架构上都不再出现这种情况。 SUN 也是 Quake 3 使用的快速逆 sqrt() 例程的诞生地；现在大多数架构上都有相关的说明。微优化的最大陷阱之一是它们很快就会过时。

Answer 2

那么您想要一个非常快速的 float->int 转换吗？ AFAIK int->float 转换速度很快，但至少在 MSVC++ 上，float->int 转换会调用一个小辅助函数 ftol()，它会执行一些复杂的操作以确保完成符合标准的转换。如果您不需要如此严格的转换，则可以进行一些汇编黑客操作，假设您使用的是 x86 兼容的 CPU。

这是一个快速浮点到整数的函数，它使用 MSVC++ 内联汇编语法（无论如何它应该给你正确的想法）：

inline int ftoi_fast(float f)
{
    int i;

    __asm
    {
        fld f
        fistp i
    }

    return i;
}

在 MSVC++ 64 位上，你需要一个外部 .asm 文件，因为 64 位编译器拒绝内联汇编。该函数基本上使用原始 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 指令，速度更快一点。

其中之一应该涵盖昂贵的浮点到整数的情况，并且任何整数到浮点的转换应该仍然很便宜。很抱歉在这里针对微软，但这是我完成类似性能工作的地方，并且通过这种方式我获得了很大的收获。如果可移植性/其他编译器是一个问题，您将不得不考虑其他问题，但这些函数编译为可能需要 <5 个时钟的两条指令，而不是需要 100 个以上时钟的辅助函数。

Answer 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，您可能会发现在进行条件 int 转换之前添加 16.0f 可以加快速度，因为它使您的条件可预测，或者您的编译器可能会这样做。使用条件分支以外的其他方法来执行此操作，在这种情况下，如果不进行测试并查看生成的程序集，就很难说它是有用的。）

Answer 4

如果您使用的是 Visual C++，请检查“启用内部函数”编译器设置。如果启用，它应该会使大多数数学函数更快（包括下限）。缺点是边缘情况（如 NaN）的处理可能不正确，但对于游戏来说，您可能不在乎。

Answer 5

如果范围很小，另一个愚蠢的想法可能会起作用......

使用按位运算从浮点数中提取指数，然后使用查找表找到一个掩码，从尾数中擦除不需要的位。使用它来找到地板（擦除点下方的位）以避免重新规范化问题。

编辑我删除了这个“太愚蠢了，加上+ve与-ve问题”。既然它无论如何都被投票了，它就不会被删除，我将把它留给其他人来决定它有多愚蠢。

Answer 6

u、v 值的最大输入范围是多少？如果它的范围相当小，例如 -5.0 到 +5.0，那么重复加/减 1.0 直到进入范围会更快，而不是调用昂贵的函数（例如下限）。

Answer 7

如果可能出现的值的范围足够小，也许您可​​以对下限值进行二分搜索。例如，如果值 -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
  }
}

我对此不做任何保证 - 我不知道比较的效率与地板相比如何 - 但它可能值得尝试。

Answer 8

这并不能解决铸造成本问题，但在数学上应该是正确的：

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

Answer 9

如果您正在循环并使用 u 和 v 作为索引坐标，则不要使用 float 来获取坐标，而是保持 float 和 int 的值相同并将它们一起递增。这将为您提供一个相应的整数，以便在需要时使用。