c++ - GCC 和 Clang 代码性能的巨大差异

Question

社区。我有这段代码可以在欧几里德 3D 空间中找到最近的一对点。这个问题既不是算法也不是它的实现或其他什么。问题是当使用 GCC 而不是 Clang 编译时，它的运行速度显着慢。最令人困惑的是，它在随机样本上的执行时间相当，而在某些特定样本上慢了 100 倍。 我怀疑 GCC 中可能存在错误，因为我想不出任何其他选择。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <fstream>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>

static std::mt19937 mmtw(std::chrono::steady_clock::now().time_since_epoch().count());
int64_t rng(int64_t x, int64_t y) {
  static std::uniform_int_distribution<int64_t> d;
  return d(mmtw) % (y - x + 1) + x;
}

constexpr static int MAXN = 1e5 + 10;

void solve(std::istream &in, std::ostream &out);

void generate(std::ostream &out) {
  constexpr int N = 1e5;
  out << N << '\n';
  int MIN = -1e6;
  int MAX = 1e6;
  for (int i = 0; i < N; ++i) {
    out << 0 << ' ';
    out << i << ' ';
    out << (i + 1) * int(1e4) << '\n';
  }
}

int main() {

  freopen("input.txt", "r", stdin);

  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  std::cerr.tie(nullptr);

  std::ofstream fout("input.txt");
  generate(fout);
  fout.close();

  solve(std::cin, std::cout);

  return 0;
}

struct point_t {
  int32_t x, y, z;
  int id;
  point_t() = default;
  point_t(int32_t x, int32_t y, int32_t z) : x(x), y(y), z(z) {}
  point_t operator +(const point_t &rhs) const {
    return point_t(x + rhs.x, y + rhs.y, z + rhs.z);
  }
  point_t operator -(const point_t &rhs) const {
    return point_t(x - rhs.x, y - rhs.y, z - rhs.z);
  }
  int64_t abs2() const {
    return 1LL * x * x + 1LL * y * y + 1LL * z * z;
  }
};

std::istream &operator >>(std::istream &in, point_t &pt) {
  return in >> pt.x >> pt.y >> pt.z;
}

inline bool cmp_x(const point_t &lhs, const point_t &rhs) {
  return lhs.x < rhs.x;
}

inline bool cmp_y(const point_t &lhs, const point_t &rhs) {
  return lhs.y < rhs.y;
}

inline bool cmp_z(const point_t &lhs, const point_t &rhs) {
  return lhs.z < rhs.z;
}

struct pair_t {
  int64_t distance_sq;
  point_t a {}, b {};
  pair_t() : distance_sq(std::numeric_limits<int64_t>::max()) {};
  pair_t(const point_t &a, const point_t &b) : distance_sq((a - b).abs2()), a(a), b(b) {}
  bool operator<(const pair_t &rhs) const {
    return distance_sq < rhs.distance_sq;
  }
};

template <typename T> inline T sqr(T arg) { return arg * arg; }

point_t pts[MAXN];

static pair_t ans = pair_t();

void recur_2D(point_t pts[], int size, int64_t threshold_sq) {
  if (size <= 3) {
    for (int i = 0; i < size; ++i) {
      for (int j = i + 1; j < size; ++j) {
        ans = std::min(ans, pair_t(pts[i], pts[j]));
      }
    }
    std::sort(pts, pts + size, cmp_y);
    return;
  }
  int mid = size / 2;
  int midx = pts[mid].x;
  recur_2D(pts, mid, threshold_sq);
  recur_2D(pts + mid, size - mid, threshold_sq);

  static point_t buffer[MAXN];
  std::merge(pts, pts + mid, pts + mid, pts + size, buffer, cmp_y);
  std::copy(buffer, buffer + size, pts);

  int buff_sz = 0;
  for (int i = 0; i < size; ++i) {
    if (sqr(pts[i].x - midx) >= threshold_sq) {
      continue;
    }
    int64_t x_sqr = sqr(pts[i].x - midx);
    for (int j = buff_sz - 1; j >= 0; --j) {
      if (sqr(pts[i].y - buffer[j].y) + x_sqr >= threshold_sq) {
        break;
      }
      ans = std::min(ans, pair_t(pts[i], buffer[j]));
    }
    buffer[buff_sz++] = pts[i];
  }
}

void recur_3D(point_t pts[], int size) {
  if (size <= 3) {
    for (int i = 0; i < size; ++i) {
      for (int j = i + 1; j < size; ++j) {
        ans = std::min(ans, pair_t(pts[i], pts[j]));
      }
    }
    std::sort(pts, pts + size, cmp_x);
    return;
  }

  int mid = size / 2;
  int midz = pts[mid].z;

  recur_3D(pts, mid);
  recur_3D(pts + mid, size - mid);

  static point_t buffer[MAXN];
  std::merge(pts, pts + mid, pts + mid, pts + size, buffer, cmp_x);
  std::copy(buffer, buffer + size, pts);

  int buff_sz = 0;
  for (int i = 0; i < size; ++i) {
    if (sqr(pts[i].z - midz) >= ans.distance_sq) {
      continue;
    }
    buffer[buff_sz++] = pts[i];
  }
  recur_2D(buffer, buff_sz, ans.distance_sq);
}

void solve(std::istream &in, std::ostream &out) {

  clock_t start = clock();

  int num_of_points;
  in >> num_of_points;

  for (int i = 0; i < num_of_points; ++i) {
    in >> pts[i];
    pts[i].id = i + 1;
  }

  std::sort(pts, pts + num_of_points, cmp_z);
  recur_3D(pts, num_of_points);
  out << ans.distance_sq << '\n';
  out << 1.0 * (clock() - start) / CLOCKS_PER_SEC << " s.\n";
}

此代码的链接:https://code.re/2yfPzjkD

它生成使代码非常慢的样本，然后测量算法执行时间。

我用

编译

g++ -DLOCAL -std=c++1z -O3 -Wno-everything main.cpp

与

clang++ -DLOCAL -std=c++1z -O3 -Wno-everything main.cpp

然后运行 ./main 同时在同一目录中有 input.txt。

Clang 编译的二进制文件在 0.053798 s. 中运行，而 GCC 二进制文件在 12.4276 s. 中运行。这些数字来自程序的输出，您可以看到 solve 函数。

我还验证了 https://wandbox.org/ 上的差异在不同的编译器版本上。 https://wandbox.org/permlink/YFEEWSKyos2dQf32 -- 铿锵 https://wandbox.org/permlink/XctarNHvd3I1B0x8 -- 海合会

请注意，我压缩了输入，因此不得不稍微更改 solve 中的读数。

在我的本地机器上我有这些编译器。

clang++ --version clang 版本 7.0.0 (tags/RELEASE_700/final)

g++ --version g++ (海湾合作委员会) 8.2.1 20180831

感觉就像我在没有编译器优化的情况下运行 GCC 代码。可能是什么原因？

更新。

还有一个版本在一开始只调用一次std::sort。 https://wandbox.org/permlink/i9Kd3GdewxSRwXsM

我也曾尝试用 -stdlib=libstdc++ 编译 Clang，打乱数据并认为 std::sort 的不同实现不是原因。

Answer 1

这只是未定义的行为。由于以下位置的有符号整数溢出，您的代码具有未定义的行为:

template <typename T> inline T sqr(T arg) { return arg * arg; }

您可以将其替换为:

template <typename T>
inline T sqr(T arg)
{
    assert(double(arg)*arg <= std::numeric_limits<T>::max());
    assert(double(arg)*arg >= std::numeric_limits<T>::min());
    return arg * arg;
}

并在调试器中捕获错误。它失败并从 recur_3D 调用 arg=-60000 行:

if (sqr(pts[i].z - midz) >= ans.distance_sq) {

这发生在 pts[i] = {x = 0, y = 0, z = 10000, id = 1} 和 midz=70000 时。

因为这是不守规矩的行为，所有的赌注都没有了。不同的编译以不同的方式利用“未定义的行为永远不会发生”的假设。这就是clang和gcc表现不同的原因，纯属“运气”。

考虑使用 UndefinedBehaviorSanitizer捕捉这些错误。我的 clang 安装中没有它，但 clang++ -fsanitize=signed-integer-overflow 应该可以解决问题。

修复这个函数可以让 clang 和 gcc 的速度相当。