19

我有一行代码，它消耗了我应用程序运行时间的 25% - 30%。它是 std::set 的小于比较器（该集合是用红黑树实现的）。它在 28 秒内被调用了大约 1.8 亿次。

struct Entry {
  const float _cost;
  const long _id;

  // some other vars

    Entry(float cost, float id) : _cost(cost), _id(id) {
    } 
};



template<class T>
struct lt_entry: public binary_function <T, T, bool>
{
    bool operator()(const T &l, const T &r) const
    {
        // Most readable shape
        if(l._cost != r._cost) {
            return r._cost < l._cost;
        } else {
            return l._id < r._id;
        }
    }
};

条目应按成本排序，如果成本相同，则按其 id 排序。对于最小值的每次提取，我都有很多插入。我考虑过使用 Fibonacci-Heaps，但有人告诉我，它们在理论上很好，但会受到高常数的影响并且实现起来相当复杂。并且由于插入在 O(log(n)) 中，因此运行时间增加在 n 较大时几乎是恒定的。所以我认为坚持一套是可以的。

为了提高性能，我尝试用不同的形状来表达它：

return l._cost < r._cost || r._cost > l._cost || l._id < r._id;

return l._cost < r._cost || (l._cost == r._cost && l._id < r._id);

即使这样：

typedef union {
    float _f;
    int _i;
} flint;

//...

flint diff;
diff._f = (l._cost - r._cost);
return (diff._i && diff._i >> 31) || l._id < r._id;

但是编译器似乎已经足够聪明了，因为我无法改进运行时。

我也考虑过SSE，但是这个问题确实不太适用于SSE...

程序集看起来有点像这样：

movss  (%rbx),%xmm1
mov    $0x1,%r8d
movss  0x20(%rdx),%xmm0
ucomiss %xmm1,%xmm0
ja     0x410600 <_ZNSt8_Rb_tree[..]+96>
ucomiss %xmm0,%xmm1
jp     0x4105fd <_ZNSt8_Rb_[..]_+93>
jne    0x4105fd <_ZNSt8_Rb_[..]_+93>
mov    0x28(%rdx),%rax
cmp    %rax,0x8(%rbx)
jb     0x410600 <_ZNSt8_Rb_[..]_+96>
xor    %r8d,%r8d

我对汇编语言有一点经验，但不是很多。

我认为挤出一些性能是最好的（唯一？）点，但这真的值得付出努力吗？你能看到任何可以节省一些周期的捷径吗？

代码将运行的平台是在多核英特尔机器上使用 gcc 4.6 (-stl=c++0x) 的 ubuntu 12。唯一可用的库是 boost、openmp 和 tbb。30 秒的基准测试是在我使用了 4 年的旧笔记本电脑（core 2 duo）上进行的。

我真的被困在这个上，它看起来很简单，但需要那么多时间。几天以来，我一直在绞尽脑汁思考如何改进这条线......

你能给我一个如何改进这部分的建议，还是它已经处于最佳状态？

编辑 1：使用 Jerrys 的建议后，我实现了约 4.5 秒的加速。编辑 2：在尝试提升斐波那契堆之后，比较到 174 次 Mio 调用小于函数。

4

5 回答 5

11

我很难相信：

a) 比较功能在 30 秒内运行 1.8 亿次

和

b) 比较函数使用 25% 的 cpu 时间

都是真的。即使是 Core 2 Duo 也应该能够在不到一秒的时间内轻松运行 1.8 亿次比较（毕竟，声称它可以做 12,000 MIPS 之类的事情，如果这真的意味着什么的话）。所以我倾向于相信分析软件的比较中还有其他一些东西。（例如，为新元素分配内存。）

但是，您至少应该考虑 std::set 不是您正在寻找的数据结构的可能性。如果您在实际需要排序值（或最大值，甚至）之前进行了数百万次插入，那么您最好将这些值放入一个向量中，这在时间和空间上都是一种更便宜的数据结构，并且排序按需提供。

如果您因为担心冲突而确实需要该集合，那么您可以考虑使用 unordered_set，它稍微便宜一些，但不如向量便宜。（正是因为向量不能保证你的唯一性。）但老实说，看看那个结构定义，我很难相信唯一性对你很重要。

“基准”

在我的小型 Core i5 笔记本电脑上，我认为它与 OP 的机器不在同一个联盟中，我运行了一些测试，将 1000 万个随机唯一条目（只有两个比较字段）插入到 std::set 和 std: ：向量。最后，我对向量进行排序。

我这样做了两次；一次使用产生可能独特成本的随机生成器，一次使用产生两种不同成本的生成器（这应该会使比较变慢）。1000 万次插入导致的比较比 OP 报告的稍多。

              unique cost         discrete cost
           compares     time    compares     time
set       243002508    14.7s   241042920    15.6s   
vector    301036818     2.0s   302225452     2.3s

为了进一步隔离比较时间，我使用 std::sort 和 std::partial_sort 重新定义了向量基准，使用了 10 个元素（基本上是前 10 个元素的选择）和 10% 的元素（即一个百万）。较大的 partial_sort 的结果让我感到惊讶——谁会认为对向量的 10% 进行排序会比对所有向量进行排序要慢——但它们表明算法成本比比较成本重要得多：

                     unique cost         discrete cost
                  compares     time    compares     time
partial sort 10   10000598     0.6s    10000619     1.1s
partial sort 1M   77517081     2.3s    77567396     2.7s
full sort        301036818     2.0s   302225452     2.3s

结论：较长的比较时间是可见的，但容器操作占主导地位。在总共 52 秒的计算时间内，一千万组插入的总成本肯定是可见的。一千万个向量插入的总成本不太明显。

小记，它的价值：

我从那段汇编代码中得到的一件事是，将成本设为float. 它实际上为浮点数分配了 8 个字节，因此您不会节省任何内存，而且您的 CPU 进行单次浮点比较的速度不会比单次双精度比较快。只是说'（即，提防过早的优化）。

Downvoter，愿意解释一下吗？

于 2012-12-12T04:08:49.803 回答
11

一个简单的解决方案是预先计算一个排序标识符，该标识符由最重要的成本和其余的 id 组成。

例如，

struct Entry
{
    double cost_;
    long id_;
    long long sortingId_;

  // some other vars

    Entry( double cost, float id )
        : cost_( cost ), id_( id ), sortingId_( 1e9*100*cost + id )
    {} 
};

sortingId_根据您可以假设的值范围调整值。

然后，现在只需排序sortingId_。

或者作为相同想法的变体，如果您无法对数据做出适当的假设，请考虑特别为memcmp.

对于更高级别的解决方案，请记住std::set::insert带有提示参数的重载。如果您的数据已经接近排序，则可能会严重减少对比较器函数的调用次数。

您可能会考虑 a 是否std::unordered_set足够？即是否需要按排序顺序列出数据。或者，如果排序只是std::set元素插入的内部内容。

最后，对于其他读者（OP已明确表示他知道这一点），请记住MEASURE。

于 2012-12-12T04:10:00.340 回答
10

让我先说一下我要在这里概述的内容是脆弱的并且不是完全可移植的——但是在正确的情况下（这几乎是你指定的）我有理由确定它应该可以正常工作.

它依赖的一点是 IEEE 浮点数经过精心设计，因此如果您将它们的位模式视为整数，它们仍然会按正确的顺序排序（模数像 NaN 之类的东西，确实有没有“正确的顺序”）。

为了利用这一点，我们所做的就是打包 Entry，这样构成我们的密钥的两部分之间就没有填充。然后我们确保整个结构与 8 字节边界对齐。我还更改了_id以int32_t确保它保持 32 位，即使在 64 位系统/编译器上（这几乎肯定会为这种比较产生最好的代码）。

然后，我们转换结构的地址，以便我们可以将浮点数和整数一起视为一个 64 位整数。由于您使用的是 little-endian 处理器，为了支持我们需要将不太重要的部分（the id）放在第一位，而将更重要的部分（the cost）放在第二位，所以当我们将它们视为 64 位整数时，浮点部分将成为最高有效位，整数部分将成为较低有效位：

struct __attribute__ ((__packed__)) __attribute__((aligned(8)) Entry {
  // Do *not* reorder the following two fields or comparison will break.
  const int32_t _id;
  const float _cost;

  // some other vars

    Entry(long id, float cost) : _cost(cost), _id(id) {} 
};

然后我们有我们丑陋的小比较功能：

bool operator<(Entry const &a, Entry const &b) { 
   return *(int64_t const *)&a < *(int64_t const *)&b;
}

一旦我们正确定义了结构，比较就变得相当简单：只需获取每个结构的前 64 位，并将它们作为 64 位整数进行比较。

最后是一些测试代码，至少可以保证它对于某些值可以正常工作：

int main() { 
    Entry a(1236, 1.234f), b(1234, 1.235f), c(1235, 1.235f);

    std::cout << std::boolalpha;

    std::cout << (b<a) << "\n";
    std::cout << (a<b) << "\n";
    std::cout << (b<c) << "\n";
    std::cout << (c<b) << "\n";
    return 0;
}

至少对我来说，这会产生预期的结果：

false
true
true
false

现在，一些可能的问题：如果这两个项目在它们之间重新排列，或者结构的任何其他部分被放在它们之前或之间，那么比较肯定会中断。其次，我们完全依赖于每个剩余 32 位的项目的大小，因此当它们连接时，它们将是 64 位。第三，如果有人__packed__从结构定义中删除了属性，我们最终可能会在_id和_cost，再次打破比较。同样，如果有人删除了aligned(8)，代码可能会失去一些速度，因为它试图加载未与8 字节边界对齐的8 字节数量（在另一个处理器上，这可能会完全失败）。[编辑：哎呀。@rici 让我想起了我打算在这里列出的内容，但忘记了：这只有在_id和cost都是肯定的情况下才能正常工作。如果_cost为负数，则比较会因 IEEE 浮点使用有符号幅度表示这一事实而变得混乱。如果 an_id为负数，则其符号位将被视为数字中间的普通位，因此负数_id将显示为大于正数_id。]

总结一下：这是脆弱的。对此毫无疑问。尽管如此，它应该很快——尤其是如果您使用的是 64 位编译器，在这种情况下，我希望比较结果是两次加载和一次比较。长话短说，您可能根本无法使比较本身变得更快——您所能做的就是尝试并行执行更多操作、优化内存使用模式等。

于 2012-12-12T04:56:02.170 回答
1

对于最小值的每次提取，我都有很多插入。我考虑过使用 Fibonacci-Heaps，但有人告诉我，它们在理论上很好，但会受到高常数的影响并且实现起来相当复杂。并且由于插入在 O(log(n)) 中，因此运行时间增加在 n 较大时几乎是恒定的。所以我认为坚持一套是可以的。

这听起来像是一个典型的优先队列应用程序。您说您刚刚考虑使用斐波那契堆，所以我想这样的优先级队列实现足以满足您的需求（推送元素，并一次提取一个最小元素）。在您竭尽全力优化该比较功能的一两个时钟周期之前，我建议您尝试一些现成的优先级队列实现。像std::priority_queue，boost::d_ary_heap（或boost::d_ary_heap_indirect可变优先级队列），或任何其他提升堆结构。

我之前遇到过类似的情况，我在类似std::setA* 的算法中使用 a 代替优先级队列（并且还尝试了 sorted std::vectorwith std::inplace_mergefor 插入），切换到std::priority_queue对性能有很大的提升，然后再切换boost::d_ary_heap_indirect加倍努力。如果您还没有，我建议您至少尝试一下。

于 2012-12-12T07:00:38.180 回答
0

我本身没有答案 - 只有几个想法：

  1. 如果您使用的是 GCC，我会在启用并行模式的情况下运行一些基准测试
  2. 您确定您没有处理成本组件的非规范化数字吗？
于 2012-12-12T03:59:58.277 回答