Какой самый быстрый способ сравнить парную структуру

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

Я подозреваю, что ваш лог c неверен для начала. Как правило, вам следует не беспокоиться о производительности до тех пор, пока не будет установлена ​​правильность кода.

Предполагая, что node_a является более важным битом, вы должны проверить его полностью перед перемещением на node_b ^(а) . Другими словами, что-то вроде:

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) Это особенно true, если вы используете сравнение в функции сортировки, поскольку в противном случае это может нарушить ограничения, необходимые для сортировки.

В частности, ограничение, которое, если a < b равно true, a >= b должно быть ложным. Без этого сортировки, как правило, не работают должным образом, и в конечном итоге могут бездумно менять порядок вещей снова и снова.

Например, если у вас есть два элемента вида {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 выполняет слишком много работы, потому что ограничения были нарушены.