Search code examples
c++gccboostboost-geometryr-tree

boost::rtree is affected by gcc compiler greatly

Since gcc 3.4.5 is used in the whole company, I have to use rtree of boost 1.57 because rtree of boost 1.59 has compile problem. I just use rtree in following way:

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;

typedef bg::model::point<double, 2, bg::cs::cartesian> point;
typedef bg::model::box<point> box;
typedef std::pair<box, size_t> value;

// create the rtree using default constructor
bgi::rtree<value, bgi::linear<500> > rtree;

// create some values
ifstream ifs(bbox_filename);
if (!ifs.is_open()) return;

std::vector<box> boxes;

boost::timer t;

// ... (read box from test file)

std::cout << "read bbox file: " << t.elapsed() << " sec." << std::endl;

t.restart();
for (size_t i = 0; i < boxes.size(); ++i)
{
    // insert new value
    rtree.insert(std::make_pair(boxes[i], i));
}
std::cout << "build rtree with " << boxes.size() << " boxes in total: " << t.elapsed() << " sec." << std::endl;

In my use case, the element number would be tens of millions, the query speed is fast and acceptable, but the speed of building rtree is very slow (O2 is enabled of course).

When I compiled the same test program with gcc 4.4.7 and compare the testing result , I found it's because of gcc version.

test environment:

CentOS 6.6
Intel(R) Xeon(R) CPU E5-2670 0 @ 2.60GHz

test log for gcc 4.4.7:

read bbox file: 22.13 sec.
build rtree with 42517937 boxes in total: 163.28 sec.

test log for gcc 3.4.5:

read bbox file: 22.28 sec.
build rtree with 42517937 boxes in total: 468.73 sec.

It seems test program compiled by gcc 3.4.5 takes about 3 times of time to build rtree than 4.4.7.

Is there anyone who met this problem before? Any advice to improve the performance under gcc 3.4.5? (I cannot choose compiler currently:()

Solution

  • Thanks for everyone's help and the post packing algorithm in rtree in boost.

    After using packing algorithm (range constructor), the performance of building rtree is improved greatly.

    std::vector<value> boxes;

boost::timer t;

// ... (read box from test file)

std::cout << "read bbox file: " << t.elapsed() << " sec." << std::endl;

t.restart();
bgi::rtree<value, bgi::linear<500> > rtree(boxes);
std::cout << "build rtree with " << boxes.size() << " boxes in total: " << t.elapsed() << " sec." << std::endl;

    test log for gcc 4.4.7 + packing algorithm:

    read bbox file: 23.07 sec.
build rtree with 42517937 boxes in total: 8.15 sec.

    test log for gcc 3.4.5 + packing algorithm:

    read bbox file: 23.06 sec.
build rtree with 42517937 boxes in total: 10.94 sec.

    Now the runtime difference between gcc 3.4.5 and 4.4.7 is acceptable.

    PS: During my test, the runtime of building rtree without O2 and packing algorithm could be 1000 times slower. Hope this post could give someone who uses boost::rtree later some hint.