尝试降低几乎但不完全整数的数字类的速度开销

Question

我已经实现了一个 C++ 类，其行为与标准 int 类型非常相似。不同之处在于它有一个额外的概念“epsilon”，它表示一些远小于 1 但大于 0 的微小值。一种将其视为具有 32 个 MSB 的非常宽的定点数（整数部分）、32 个 LSB（epsilon 部分）以及中间大量的零。 （注意：这一类和普通定点数之间的一大区别是，有两个符号，而不是一个：“value”和“epsilon”可以彼此独立地为负数，而对于定点，有一个符号表示整个数字。）

下面的类可以工作，但在整个程序中引入了大约 2 倍的速度损失。 （该程序包含与此类无关的代码，因此此类的实际速度损失可能远大于 2 倍。）我无法粘贴使用此类的代码，但我可以说以下内容：

+、-、+=、<、> 和 >= 是唯一频繁使用的运算符。 setEpsilon() 和 getInt() 的使用极为罕见。 * 也很少见，甚至根本不需要考虑 epsilon 值。

这是类：

#include <limits>

struct int32Uepsilon {
typedef int32Uepsilon Self;

int32Uepsilon () { _value = 0;
                   _eps   = 0; }
int32Uepsilon (const int &i) { _value = i;
                               _eps   = 0; }
void setEpsilon() { _eps = 1; }
Self operator+(const Self &rhs) const { Self result = *this;
                                      result._value += rhs._value;
                                      result._eps   += rhs._eps;
                                      return result; }
Self operator-(const Self &rhs) const { Self result = *this;
                                      result._value -= rhs._value;
                                      result._eps   -= rhs._eps;
                                      return result; }
Self operator-(               ) const { Self result = *this;
                                      result._value = -result._value;
                                      result._eps   = -result._eps;
                                      return result; }
Self operator*(const Self &rhs) const { return this->getInt() * rhs.getInt(); } // XXX: discards epsilon

bool operator<(const Self &rhs) const { return (_value < rhs._value) ||
                                             (_value == rhs._value && _eps < rhs._eps); }
bool operator>(const Self &rhs) const { return (_value > rhs._value) ||
                                             (_value == rhs._value && _eps > rhs._eps); }
bool operator>=(const Self &rhs) const { return (_value >= rhs._value) ||
                                             (_value == rhs._value && _eps >= rhs._eps); }

Self &operator+=(const Self &rhs) { this->_value += rhs._value;
                                  this->_eps   += rhs._eps;
                                  return *this; }
Self &operator-=(const Self &rhs) { this->_value -= rhs._value;
                                  this->_eps   -= rhs._eps;
                                  return *this; }
int getInt() const { return(_value); }

private:
  int _value;
  int _eps;
};

namespace std {
template<>
struct numeric_limits<int32Uepsilon> {
  static const bool is_signed  = true;
  static int max() { return 2147483647; }
}
};

上面的代码可以工作，但速度很慢。有人对如何提高性能有任何想法吗？我可以提供一些可能有用的提示/细节：

• 32 位绝对不足以同时容纳 _value 和 _eps。在实际应用中，最多可达24~28位 使用 _value 并使用最多 20 位的 _eps。
• 我无法测量使用 int32_t 和 int64_t 之间的显着性能差异， 所以内存开销本身可能不是这里的问题。
• 对 _eps 进行饱和加法/减法会很酷，但实际上并不是必需的。
• 注意，_value 和 _eps 的符号不一定相同！这打破了我的第一次尝试 加快这堂课的进度。
• 内联汇编没问题，只要它能在运行 Linux 的 Core i7 系统上与 GCC 配合使用！

Answer 1

可以尝试的一件事是根据 operator+= 定义例如 operator+ 的规范实践：

Self operator+(const Self &rhs) const { return Self(*this) += rhs; }

这有助于 返回值优化，它消除了按值返回所需的复制构造函数。

此外，它还减少了代码维护！

Answer 2

2 倍的速度损失似乎并不是不合理，因为所有操作都完成了两次。

您可以使用 MMX/SSE2 指令将 value 和 epsilon 打包到两个寄存器中，并仅并行执行这两个操作一次。或者，在 64 位架构上，您可以将两个值打包在一个 int64 中，如下所示：[32 位值][12 个零][20 位 eps]。比较将通过单个操作自动进行，加法和减法需要将 eps 的结转屏蔽为填充零。使用MMX进行加法和减法（然后自动屏蔽）和普通整数比较进行比较是没有障碍的。

顺便说一句，你的operator-=似乎有问题：在this->_eps -= rhs._eps中，this->eps可能会变成负数。难道你不应该调整 eps 并减少该值吗？ eps 的溢出行为是什么？它会转化为价值吗？

Answer 3

我的（部分）解决方案是在您的解决方案中使用一个整数运算，而不是两个，正如Oli Charlesworth在评论中指出的那样。

您可以这样做：使用 int64_t 来存储 _eps 和 _value。在下面的示例中，_value 由 bit0-to-bit31 表示，_eps 由 bit32-to-bit63 表示代码>.

struct int32Uepsilon 
{

   typedef int32Uepsilon Self;

   int64_t value;

   int32Uepsilon () { value = 0 }
   int32Uepsilon (const int i) {  value = i; }
   void setEpsilon() 
   {  
      //equivent to _eps = 1
      value = ((int64_t)1 << 32) + (value & 0xFFFFFFFF); 
   }
   Self operator+(const Self &rhs) const 
   { 
     Self result = *this;
    //this adds lower 32 bits to lower 32 bits, upper 32 bits to upper 32 bits!
     result.value += rhs.value; 
     return result; 
   }
   //....
   int getValue() { return value & 0xFFFFFFFF; }
   int getEpsilon() { return value >> 32; }
};

如果没有溢出，那么+可以高效可靠地完成。这只是一个开始。尝试思考是否可以使用某些位操作可靠地完成其他操作。

---

简单的加法演示。请阅读评论

int main() 
{
    int64_t x =  ((int64_t)2 << 32) + 4;     //eps = 2,  value = 4
    int64_t y =  ((int64_t)65 << 32) +7897;  //eps = 65, value = 7897
    int64_t z =  x + y ; //in z, eps = (2+65) = 67, value = (4 + 7897) = 7901 
    cout << (x >> 32) << ", " << (x & 0xFFFFFFFF) << endl;  
    cout << (y >> 32) << ", " << (y & 0xFFFFFFFF) << endl;  
    cout << (z >> 32) << ", " << (z & 0xFFFFFFFF) << endl;  
    return 0;
}

输出：

2, 4    
65, 7897   
67, 7901

如预期。

Ideone 演示：http://www.ideone.com/GjSnJ

---

而不是 x + y，您可以使用x | y 甚至更快的操作。

Answer 4

谢谢大家的意见。最后我使用内联汇编来实现+、-和+=。令人惊讶的是，GCC 无法自行矢量化这些微小函数，尽管使用 __builtin_ia32_paddd() 内置函数有所帮助。最终，整体程序开销（与使用裸 int 相比）从 100% 减少到 50%。查看生成的程序集，结果似乎是最佳的，至少在我看来是这样。据我快速阅读英特尔手册可知，没有任何东西可以帮助进行比较操作。 （有向量比较指令，但它们在这里都没有帮助。）