community. I have this piece of code that finds closest pair of points in Euclidean 3D space. This question is neither about the algorithm nor its implementation or whatever. The problem is that it runs significantly slower when compiled with GCC rather than Clang. Most confusingly, it has comparable execution time on random samples and like 100 times slower on some specific one. I suspect there can be a bug in GCC as I cannot think of any other option.
#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";
}
Link to this code: https://code.re/2yfPzjkD
It generates the sample that makes the code very slow and then measures algorithm execution time.
I compile with
g++ -DLOCAL -std=c++1z -O3 -Wno-everything main.cpp
and with
clang++ -DLOCAL -std=c++1z -O3 -Wno-everything main.cpp
and run
./main while having input.txt in the same directory.
The Clang-copiled binary runs in 0.053798 s. while the GCC one in 12.4276 s. . These numbers are from program's output, you can see that function solve.
I have also verified the difference on https://wandbox.org/ on different compiler versions. https://wandbox.org/permlink/YFEEWSKyos2dQf32 -- clang https://wandbox.org/permlink/XctarNHvd3I1B0x8 -- gcc
Note, I compressed input and thus had to change reading in solve a bit.
On my local machine I have these compilers.
clang++ --version
clang version 7.0.0 (tags/RELEASE_700/final)
g++ --version
g++ (GCC) 8.2.1 20180831
It feels like I run GCC code without compiler optimizations. What can be the reason?
UPD.
Also, there is a version that calls std::sort only once in the very beginning.
https://wandbox.org/permlink/i9Kd3GdewxSRwXsM
I have also tried to compile Clang with -stdlib=libstdc++, shuffling data and think that different implementations of std::sort are not cause.