Geometry Index GCC arch x86-64-v3

[sandman7920]

When GCC compiles idx.qbegin(bgi::nearest(searchPoint, 5)) with -march=x86-64-v3, generated code is ~= 50% slower than x86-64-v2

Sniped:

for (size_t i = 0, end = records.size(); i < end; ++i) {
    const auto &r = records[i];
    const auto searchPoint = Point(r.lon, r.lat);
    for (auto it = idx.qbegin(bgi::nearest(searchPoint, 5)); it != idx.qend(); ++it) {
        if (it->second == i) {
            continue;
        }

        const auto d = bg::distance(it->first, searchPoint, haversine);
        if (d >= 100) {
            break;
        }

        if (d > 0.000001) {
            proximity.emplace_back(i, it->second);
            break;
        }
    }
}

I have tested with several boost versions, 1.69.0 is not affected, and also clang is not affected.
I suspect this is a GCC bug.

Some test results:

./gcc_boost_1.69_v2
load data took :     29.079 ms
index fill took:    450.315 ms
query all took :   4308.570 ms

in proximity: 11323

./gcc_boost_1.69_v3
load data took :     28.881 ms
index fill took:    467.378 ms
query all took :   4291.138 ms

in proximity: 11323

./gcc_boost_1.75_v2
load data took :     28.809 ms
index fill took:    452.619 ms
query all took :   3626.386 ms

in proximity: 11328

./gcc_boost_1.75_v3
load data took :     28.892 ms
index fill took:    490.710 ms
query all took :   6523.559 ms

./gcc_boost_1.90_v2
load data took :     29.007 ms
index fill took:    448.897 ms
query all took :   3645.700 ms

in proximity: 11328

./gcc_boost_1.90_v3
load data took :     29.016 ms
index fill took:    498.888 ms
query all took :   6531.580 ms

in proximity: 11328

main.cpp

data.csv

[tinko92]

Thanks for the report. I vaguely remember some discussion about AVX hurting performance in some cases because it can lead to downclocking (iirc that may have been machine-dependent too). Notably your "in proximity" counts changes at the first affected version (Is this change in behaviour a concern for you too, by the way? Or are those 5 points within reasonable rounding uncertainty?). The change in count suggests some formula change that may change what kind of instructions GCC emits.

I will try to replicate it and trace it to a change. What GCC version did you use?

[sandman7920]

The 5 points difference is a reasonable rounding error, I suspect they are from haversine implementation in 1.69

The tests were done with GCC 15 on AMD Ryzen 7 3700X, but if I remember correctly, I have tested on different GCC versions in Docker with the same results.

[sandman7920]

I did a fresh series of tests, all compiled with -march=x86-64-v3.
GCC 11.4.0 on a clean Ubuntu 22.04 container and GCC 15.2.1 on my Arch workstation.

The performance hit on GCC 15 is not so severe (except boost 1.87.0).

The first affected version is 1.79.0

t_boost_1_70_0_gcc11
load data took :     28.470 ms
index fill took:    617.656 ms
query all took :   4520.818 ms

in proximity: 11323
================================
t_boost_1_70_0_gcc15
load data took :     28.840 ms
index fill took:    489.461 ms
query all took :   4232.731 ms

in proximity: 11323
================================
t_boost_1_71_0_gcc11
load data took :     28.494 ms
index fill took:    632.622 ms
query all took :   3977.999 ms

in proximity: 11328
================================
t_boost_1_71_0_gcc15
load data took :     29.182 ms
index fill took:    492.233 ms
query all took :   3719.880 ms

in proximity: 11328
================================
t_boost_1_72_0_gcc11
load data took :     28.453 ms
index fill took:    622.433 ms
query all took :   3982.973 ms

in proximity: 11328
================================
t_boost_1_72_0_gcc15
load data took :     29.078 ms
index fill took:    501.836 ms
query all took :   3797.354 ms

in proximity: 11328
================================
t_boost_1_75_0_gcc11
load data took :     29.028 ms
index fill took:    654.918 ms
query all took :   4010.032 ms

in proximity: 11328
================================
t_boost_1_75_0_gcc15
load data took :     30.039 ms
index fill took:    493.110 ms
query all took :   3753.627 ms

in proximity: 11328
================================
t_boost_1_78_0_gcc11
load data took :     28.916 ms
index fill took:    617.550 ms
query all took :   3788.766 ms

in proximity: 11328
================================
t_boost_1_78_0_gcc15
load data took :     28.593 ms
index fill took:    493.826 ms
query all took :   3497.674 ms

in proximity: 11328
================================
t_boost_1_79_0_gcc11
load data took :     28.737 ms
index fill took:    647.893 ms
query all took :   6734.740 ms

in proximity: 11328
================================
t_boost_1_79_0_gcc15
load data took :     28.977 ms
index fill took:    507.003 ms
query all took :   4466.725 ms

in proximity: 11328
================================
t_boost_1_83_0_gcc11
load data took :     28.481 ms
index fill took:    642.893 ms
query all took :   6642.469 ms

in proximity: 11328
================================
t_boost_1_83_0_gcc15
load data took :     28.739 ms
index fill took:    500.158 ms
query all took :   4504.257 ms

in proximity: 11328
================================
t_boost_1_85_0_gcc11
load data took :     29.419 ms
index fill took:    654.861 ms
query all took :   6719.798 ms

in proximity: 11328
================================
t_boost_1_85_0_gcc15
load data took :     28.857 ms
index fill took:    509.649 ms
query all took :   4701.915 ms

in proximity: 11328
================================
t_boost_1_86_0_gcc11
load data took :     29.982 ms
index fill took:    643.873 ms
query all took :   6712.167 ms

in proximity: 11328
================================
t_boost_1_86_0_gcc15
load data took :     29.381 ms
index fill took:    506.492 ms
query all took :   4476.900 ms

in proximity: 11328
================================
t_boost_1_87_0_gcc11
load data took :     28.533 ms
index fill took:    645.859 ms
query all took :   6666.611 ms

in proximity: 11328
================================
t_boost_1_87_0_gcc15
load data took :     29.194 ms
index fill took:    537.570 ms
query all took :   6187.920 ms

in proximity: 11328
================================
t_boost_1_89_0_gcc11
load data took :     28.468 ms
index fill took:    669.389 ms
query all took :   6802.750 ms

in proximity: 11328
================================
t_boost_1_89_0_gcc15
load data took :     28.440 ms
index fill took:    519.922 ms
query all took :   4810.108 ms

in proximity: 11328
================================

[tinko92]

Thanks. I looked into it. Interestingly this doesn't occur with Clang which gives a clue: GCC will liberally transform suitable arithmetic into using FMA if available on the plattform, unlike Clang (which defaults to -ffp-contract=on behaviour). Counting the total newton iterations (adding a global size_t newton_iters before the BG includes and adding ++newton_iters; in geometry/include/boost/geometry/strategies/geographic/distance_cross_track.hpp, line 342) across your program yields
Newton Iters: 4746607 with x86-64-v3
Newton Iters: 2692413 with x86-64-v3 + -ffp-contract=on (or -mno-fma).

That suggests that there is something very numerically sensitive to FMA in the iteration (because substituting FMA somewhere should only change the result by 1e-15 times the magnitudes of the involved numbers, but here it changes behaviour a lot). E.g. something like sin(a) * cos(b) - cos(b) * sin(a) == 0 (even when spread across multiple expressions in code, fp-contract=fast behaviour can contract operations across expressions) would be true for all values without FMA but false with FMA for most values, and should be changed to something like abs(sin(a) * cos(b) - cos(b) * sin(a)) < 10 * eps . In an earlier test tuning down the inlining in an earlier test also eliminated the performance hit, so maybe some calculation across function boundaries.

On further checking the issue seems to be not in the Newton method itself but I'm getting overall more calls to the distance function, so it is in the rtree. Somehow a lot fewer nodes are pruned in the FMA version. This is a numerical instability due to a slight change in behviour, I'm not sure this should be considered a bug in Boost.Geometry, and I don't know if making the pruning more aggressive around edge cases would risk returning non-nearest neighbours.

I do not have time to look into it right now but will try to recheck later, unless someone who knows the rtree code better can more quickly find the issue.

Until the code is made more robust, you can pass -ffp-contract=on (arguably a generally sensible default, the default of clang) or -mno-fma as a compiler flag as a workaround to avoid the performance hit for your program.