c++ - 加、减和比较压缩整数

Question

我需要在大小相等的小整数数组上做大量简单的代数运算。这些操作仅包括三种:(i) 添加数组和 (ii) 按元素减去数组，以及 (iii) 比较一个数组中的所有元素是否不小于/大于另一个数组中的对应元素。

为了提高缓存局部性和计算速度，我将每个数组的小整数逐位填充到一定数量的 64 位整数中。使用的 64 位整数的数量由分配给数组元素的位数决定。让 a[j] 表示一个数组元素。我为 a[j] 设计的位包括 (i) 可以保存最大绝对值的位 a[j] 在计算过程中可能命中，(ii) 一个符号位，和 (iii) 符号位左边的一个位。最左边的位保留来自右边的可能进位，并在加法或减法后归零。

下面是一个对两个 64 位整数进行加法、减法和比较的玩具示例，每个整数包括五个小整数:前 10 位、后 5 位、后 10 位、后 13 位和接下来的 20 位。其余位无用并设置为 0。

// leftmostBitMask = 
// 0b0111111111011110111111111011111111111101111111111111111111000000
//   ^         ^    ^         ^            ^                  
// leftmost


std::size_t add(std::size_t x, std::size_t y, std::size_t leftmostBitMask)
{
  return (x + y) & leftmostBitMask;
}


std::size_t minus(std::size_t x, std::size_t y, std::size_t leftmostBitMask)
{
  return (x - y + ((~leftmostBitMask) << 1)) & leftmostBitMask;
}


bool notAllGreaterEqual(std::size_t x, std::size_t y, std::size_t leftmostBitMask)
{
  // return (minus(x, y, leftmostBitMask) & (leftmostBitMask >> 1)) == 0;
  return (x - y) & ((~leftmostBitMask) >> 1);
}

我的算法看起来很复杂，尤其是比较功能。有没有更快的解决方案？

谢谢!

顺便说一句，SIMD 不是我所描述的。我的问题是比 SIMD 低一级的优化。

更多背景:这个想法服务于多维空间中相当复杂的搜索算法。我们观察到不同维度的值大小之间存在巨大差异。例如，在计算一个重要的 6 维测试用例时，一个维度的绝对值可能达到 50000，而所有其他维度都远低于 1000。如果没有整数压缩，每个对象都需要一个大小为 6 的 32 位数组，而整数压缩会减少维度为 1(64 位整数)。这种减少促使我考虑填​​入整数..

Answer 1

经过仔细思考和全面模拟，问题中列出的算法在很大程度上被过度设计了。用于接收进位的最左边的位是不必要的。下面的代码有效:

// signBitMask = 
// 0b1000000000100001000000000100000000000010000000000000000000000000
//   ^         ^    ^         ^            ^                  
// sign bit


std::size_t add(std::size_t x, std::size_t y)
{
  return x + y;
}


std::size_t subtract(std::size_t x, std::size_t y)
{
  return x - y;
}


bool notAllGreaterEqual(std::size_t x, std::size_t y, std::size_t signBitMask)
{
  return (x - y) & signBitMask != 0;
}

这里的关键因素是对两个数组进行的每个比较都是基于 AND 的。我们要求 notAllGreaterEqual() 返回 true，只要 x 中的一个元素整数低于它在 y 中的对应元素。乍一看，上面的解决方案不太可能是真的:当一个负元素整数与一个正元素整数相加并且结果保持为正时会发生什么？符号位必须有结转。在这种情况下，连续的元素整数不是被污染了吗？答案是肯定的，但没关系。总的来说，notAllGreaterEqual() 仍将完全发挥其作用。不用逐位思考，可以很容易地用初等代数证明 notAllGreaterEqual() 是正确的。只有当我们想要从那些 64 位缓冲区中恢复整数数组时，问题才会出现。

创建 64 位缓冲区包括 (i) 将整数转换为 std::size_t，(ii) 将整数移位预先计算的位，以及 (iii) 添加移位后的整数。如果一个整数向右移动是负数，则必须在其左侧填充 1。