c++ - 比较一对结构的最快方法是什么

Question

我的项目在结构比较中发现了性能瓶颈。
结构只是一对int

struct Edge
{
int node_a;
int node_b;
};

比较功能如下所示:

// my wrong code: do not see it, it will leads to UB
bool edgeCompare(const Edge &edge_a, const Edge &edge_b)
{
     if (edge_a.node_a < edge_b.node_a)
     {
         return true;
     }
     if (edge_a.node_b < edge_b.node_b)
     {
         return true;
     }
     else
     {
         return false;
     }
}

// correct code from @paxdiablo
bool edgeCompare(const Edge &edge_a, const Edge &edge_b) {
    if (edge_a.node_a < edge_b.node_a) return true;
    if (edge_a.node_a > edge_b.node_a) return false;

    // Only now are the node_a values equal, check node_b.

    return edge_a->node_b < edge_b->node_b;
}

我的问题是如何在比较功能上进行优化以使性能启动尽可能多？

可能可以使用某些技术，例如:减少分支预测失败或使用位计算？

谢谢你的时间。

Answer 1

我怀疑您的逻辑是错误的。通常，在建立代码正确性之前，您应该避免担心性能。

假设node_a是更重要的位，那么在继续使用node_b(a)之前，您应该先对其进行全面检查。换句话说，类似:

bool edgeCompare(const Edge &edge_a, const Edge &edge_b) {
    if (edge_a.node_a < edge_b.node_a) return true;
    if (edge_a.node_a > edge_b.node_a) return false; // need this as well.

    // Only now are the node_a values equal, so check node_b.

    return edge_a->node_b < edge_b->node_b;
}

另一个可能性是稍微更简洁:

bool edgeCompare(const Edge &edge_a, const Edge &edge_b) {
    // Use node_a if they're different, node_b otherwise.

    if (edge_a.node_a != edge_b.node_a) return
        return edge_a->node_a < edge_b->node_a;

    return edge_a->node_b < edge_b->node_b;
}

由于简化，它们都为您提供了较小的代码，但不一定更快，这取决于编译器对原始if的优化程度。

老实说，我不确定您会比它更快地得到它，您已经传递了const引用，因此应尽量减少压入堆栈的内容。

(a)如果在排序函数中使用比较，尤其如此，因为否则可能会违反排序所需的约束。

具体来说，如果a < b为true，则a >= b必须为false的约束。否则，排序往往无法正常工作，并且最终可能会无意识地一遍又一遍地交换事物的顺序。

例如，如果您具有{node_a, node_b}形式的两个元素，并且它们分别是{1, 7}和{2, 5}，则您发布的代码实际上是有效的:

if (edge_a.node_a < edge_b.node_a) return true; // 1
if (edge_a.node_b < edge_b.node_b) return true; // 2
return false;                                   // 3

将针对另一个进行检查时返回true:

{1, 7} < {2, 5} because 1 < 2 (case 1 above)
{2, 5} < {1, 7} because 2 < 1 is false but 5 < 7 (case 2 above)

如果您使用的sort函数由于违反了约束而正在执行过多工作，则可能是性能问题。