C++优化if/else条件

Question

我有一行代码,占用了我应用程序运行时的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,但我被告知它们理论上很好,但是它们受到高常数的影响并且实现起来非常复杂.并且由于insert在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岁的笔记本电脑(核心2双核处理器)上进行的.

我真的被困在这个,看起来很简单,但需要花费很多时间.我几天以来一直在思考如何改进这条线......

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

编辑1:使用Jerrys建议后我达到了~4.5秒的加速.编辑2:尝试提升斐波那契堆后,比较转为174 Mio调用低于功能.

Answer 1

我很难相信:

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中: :向量.最后,我对矢量进行排序.

我这样做了两次; 曾经使用随机发电机产生可能的独特成本,而一次发电机产生两种不同的成本(这应该使比较更慢).与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秒的计算时间内,总共可以看到1000万套插入的总成本.千万个矢量插入的总成本相当不太明显.

小记,值得的:

我从汇编代码中得到的一件事就是你没有通过降低成本来保存任何东西float.它实际上为float分配了8个字节,因此你不会保存任何内存,并且你的cpu不会比单个双重比较更快地执行单个float比较.只是说'(即谨防过早优化).

Downvoter,关心解释？

Answer 2

一个简单的解决方案是预先计算一个排序标识符,其中包括最重要的成本和其余的成本.

例如,

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具有提示参数的重载.如果您的数据已经接近排序,则可能会严重减少对比较器功能的调用次数.

你可能会考虑一个是否std::unordered_set足够？即是否需要按排序顺序列出数据.或者,如果排序只是std::set元素插入的内部东西.

最后,对于其他读者(OP明确表示他已经意识到这一点),请记住测量.

Answer 3

让我先说一下这个事实,我在这里要概述的是脆弱的而且不是完全可移植的 - 但是在适当的情况下(这几乎是你指定的)我有理由相信它应该正常工作.

它依赖的一点是IEEE浮点数经过精心设计,因此如果将它们的位模式视为整数,它们仍然会按正确的顺序排序(模数为NaNs,其中确实存在没有"正确的秩序").

为了充分利用它,我们所做的就是打包Entry,这样就不会在组成我们键的两个部分之间填充.然后我们确保整个结构与8字节边界对齐.我也改变了_idto int32_t以确保它保持32位,即使在64位系统/编译器上(这几乎肯定会产生最佳代码用于此比较).

然后,我们转换结构的地址,以便我们可以将浮点数和整数一起视为一个64位整数.由于您使用的是小端处理器,为了支持我们需要先放置不太重要的部分(第一个id),然后放置更重要的部分(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再次打破比较.同样,如果某人删除了对齐的(8),代码可能会失去一些速度,因为它试图加载未与8字节边界对齐的8字节数量(在另一个处理器上,这可能会完全失败).[编辑:哎呀.@rici提醒我的东西,我打算在这里列出,却忘了:这只是正常工作时,无论是_id和cost是积极的.如果_cost是否定的,则IEEE浮点使用带符号的幅度表示这一事实将使比较混乱.如果a _id为负数,则其符号位将被视为数字中间的正常位,因此负数_id将显示为大于正数_id.

总结一下:这很脆弱.毫无疑问.尽管如此,它应该非常快 - 特别是如果你使用的是64位编译器,在这种情况下,我希望这种比较可以用于两次加载和一次比较.总而言之,您可能无法更快地完成比较 - 您可以做的就是尝试并行执行更多操作,优化内存使用模式等.