为什么 boost.geometry.index.rtree 比 superliminal.RTree 慢

Question

我测试了 boost.geometry.index.rtree（提升 1.59 www.boost.org）和 superliminal.RTree（http://superliminal.com/sources/sources.htm#C_Code）。

令我惊讶的是，superliminal.RTree 比 boost.geometry.index.rtree 更快。

环境设置

将相同的空间索引数据添加到 superliminal.RTree 和 boost.geometry.index.rtree 对象。
测试同一个空间索引查询100次，得到耗时。
GCC 版本为 "gcc version 4.4.6 20110731 (Red Hat 4.4.6-4) (GCC) "，使用“-g -o2 -Wall -finline-functions”编译器标志。
使用 RTree < uint64_t, int, 2, int64_t>

提升代码

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

typedef bg::model::point < int, 2, bg::cs::cartesian > point_t; 
typedef bg::model::box < point_t > box_t; 
typedef std::pair < box_t, uint64_t > value_t; 
typedef bgi::rtree < value_t, bgi::quadratic < 8, 4 > > rtree_t;

结果是：

superliminal.RTree 0.029s

boost.geometry.index.rtree 0.12s.

Answer 1

很难说出为什么在您的情况下它变慢了，因为您没有共享代码，也没有说明两个 R 树实现的具体使用方式。您还没有提供有关您存储的数据的任何信息。当您比较算法或数据结构时，这些东西非常重要。

我只能猜测您使用 Superliminar R-tree 的方式与在附加测试文件中使用的方式相同，因此您将回调函数传递给 Search 成员函数。我猜你使用 Boost.Geometry R-tree 的方式与 快速入门 部分的文档中显示的方式相同，因此你传递的是 std::back_insert_iterator 进入 query 成员函数。那么让我们检查一下。

#include "RTree.h"

#include <vector>

#include <boost/geometry.hpp>
#include <boost/geometry/index/rtree.hpp>

#include <boost/timer.hpp>

struct Rect
{
  Rect()  {}

  Rect(int a_minX, int a_minY, int a_maxX, int a_maxY)
  {
    min[0] = a_minX;
    min[1] = a_minY;

    max[0] = a_maxX;
    max[1] = a_maxY;
  }

  int min[2];
  int max[2];
};

// used with Superliminar R-tree
std::vector<uint64_t> res;
bool MySearchCallback(uint64_t id, void* arg)
{
    res.push_back(id);
    return true;
}

int main()
{
    // randomize rectangles
    std::vector<Rect> rects;
    for (size_t i = 0 ; i < 300000 ; ++i)
    {
        int min_x = rand() % 10000;
        int min_y = rand() % 10000;
        int w = 1 + rand() % 100;
        int h = 1 + rand() % 100;
        rects.push_back(Rect(min_x, min_y, min_x+w, min_y+h));
    }

    // create the rectangle passed into the query
    Rect search_rect(4000, 4000, 6000, 6000);

    // create the Superliminar R-tree
    RTree<uint64_t, int, 2, int64_t> tree;

    // create the Boost.Geometry R-tree
    namespace bg = boost::geometry;
    namespace bgi = boost::geometry::index;
    typedef bg::model::point<int, 2, bg::cs::cartesian> point_t;
    typedef bg::model::box<point_t> box_t;
    typedef std::pair<box_t, uint64_t> value_t;
    bgi::rtree<value_t, bgi::quadratic<8, 4> > bg_tree;

    // Insert values
    for(size_t i = 0; i < rects.size(); i++)
    {
        Rect const& r = rects[i];
        tree.Insert(r.min, r.max, i);

        box_t b(point_t(r.min[0], r.min[1]), point_t(r.max[0], r.max[1]));
        bg_tree.insert(value_t(b, i));
    }

    // test Rtree
    {
        int sum = 0;
        boost::timer t;
        for (size_t i = 0 ; i < 100 ; ++i)
        {
            res.clear();
            sum += tree.Search(search_rect.min, search_rect.max, MySearchCallback, NULL);
        }
        double s = t.elapsed();
        std::cout << s << " " << sum << std::endl;
    }

    // test BG Rtree
    {
        box_t search_box(
            point_t(search_rect.min[0], search_rect.min[1]),
            point_t(search_rect.max[0], search_rect.max[1]));
        size_t sum = 0;
        boost::timer t;
        for (size_t i = 0 ; i < 100 ; ++i)
        {
            std::vector<value_t> res;
            sum += bg_tree.query(bgi::intersects(search_box), std::back_inserter(res));
        }
        double s = t.elapsed();
        std::cout << s << " " << sum << std::endl;
    }
}

结果（使用 GCC 4.8 -O2 -finline-functions）是：

0.014s for Superliminar R-tree
0.072s for Boost.Geometry R-tree

所以它们与您的相似，即一个快 ~5 倍。请注意，在这两种情况下，我都创建了一个容器来存储结果（Superliminar 的 ID 和 Boost.Geometry 的整个值）。问题是 R 树的使用方式不一样。

优化 1

让我们尝试通过以相同的方式存储相同的结果来消除两种 R 树在使用上的差异。为此，请删除临时 std::vector<value_t>。要实现回调，请将 std::back_insert_iterator 替换为名为 boost::function_output_iterator 的函数对象。在这两种情况下，都只将 ID 存储在 std::vector<uint64_t> 中，希望编译器能够优化代码。

#include "RTree.h"

#include <vector>

#include <boost/function_output_iterator.hpp>
#include <boost/geometry.hpp>
#include <boost/geometry/index/rtree.hpp>

#include <boost/timer.hpp>

struct Rect
{
  Rect()  {}

  Rect(int a_minX, int a_minY, int a_maxX, int a_maxY)
  {
    min[0] = a_minX;
    min[1] = a_minY;

    max[0] = a_maxX;
    max[1] = a_maxY;
  }

  int min[2];
  int max[2];
};

std::vector<uint64_t> res;

// used with Superliminar R-tree
bool MySearchCallback(uint64_t id, void* arg)
{
    res.push_back(id);
    return true;
}

// used with Boost.Geometry R-tree
struct MySearchCallback2
{
    template <typename Value>
    void operator()(Value const& v)
    {
        res.push_back(v.second);
    }
};

int main()
{
    // randomize rectangles
    std::vector<Rect> rects;
    for (size_t i = 0 ; i < 300000 ; ++i)
    {
        int min_x = rand() % 10000;
        int min_y = rand() % 10000;
        int w = 1 + rand() % 100;
        int h = 1 + rand() % 100;
        rects.push_back(Rect(min_x, min_y, min_x+w, min_y+h));
    }

    // create the rectangle passed into the query
    Rect search_rect(4000, 4000, 6000, 6000);

    // create the Superliminar R-tree
    RTree<uint64_t, int, 2, int64_t> tree;

    // create the Boost.Geometry R-tree
    namespace bg = boost::geometry;
    namespace bgi = boost::geometry::index;
    typedef bg::model::point<int, 2, bg::cs::cartesian> point_t;
    typedef bg::model::box<point_t> box_t;
    typedef std::pair<box_t, uint64_t> value_t;
    bgi::rtree<value_t, bgi::quadratic<8, 4> > bg_tree;

    // Insert values
    for(size_t i = 0; i < rects.size(); i++)
    {
        Rect const& r = rects[i];
        tree.Insert(r.min, r.max, i);

        box_t b(point_t(r.min[0], r.min[1]), point_t(r.max[0], r.max[1]));
        bg_tree.insert(value_t(b, i));
    }

    // test Rtree
    {
        int sum = 0;
        boost::timer t;
        for (size_t i = 0 ; i < 100 ; ++i)
        {
            res.clear();
            sum += tree.Search(search_rect.min, search_rect.max, MySearchCallback, NULL);
        }
        double s = t.elapsed();
        std::cout << s << " " << sum << std::endl;
    }

    // test BG Rtree
    {
        box_t search_box(
            point_t(search_rect.min[0], search_rect.min[1]),
            point_t(search_rect.max[0], search_rect.max[1]));
        size_t sum = 0;
        MySearchCallback2 callback;
        boost::timer t;
        for (size_t i = 0 ; i < 100 ; ++i)
        {
            res.clear();
            sum += bg_tree.query(bgi::intersects(search_box), boost::make_function_output_iterator(callback));
        }
        double s = t.elapsed();
        std::cout << s << " " << sum << std::endl;
    }
}

在这种情况下，结果是：

0.014s for Superliminar R-tree
0.033s for Boost.Geometry R-tree

优化 2

可以做的另一件事是禁用断言。 Boost.Geometry R 树中有一些。使用 -DNDEBUG 编译代码后，结果更接近：

0.014s for Superliminar R-tree
0.015s for Boost.Geometry R-tree

结论

在这个综合测试用例中，对于随机数据等，结果或多或少是相同的。同样，对你来说它们可能不同，我不知道你到底在做什么，所以我无法告诉你问题出在哪里。

这是一个非常简单的用例，如果测试更复杂的用例，结果可能会有所不同。换句话说，应该分析一个现实生活中的应用程序，看看是否存在瓶颈。

此外Boost.GeometryR-tree的代码要复杂得多。两个 R-tree 实现的接口是不同的，特别是两个 search/query 函数都需要不同的参数，并且肯定会以不同的方式处理它们。编译器可能会选择以不同方式优化代码。

P.S.

使用 Boost.Geometry R 树可以使用不同的拆分算法和打包算法，因此您可以试验哪一种最适合您的情况。要使用打包算法，您必须将一系列值传递给 rtree 构造函数。对于相同的数据和元素数量以及使用打包算法创建的 rtree，查询时间对我来说是 0.005s。

为什么 boost.geometry.index.rtree 比 superliminal.RTree 慢

Why boost.geometry.index.rtree is slower than superliminal.RTree

c

c++

r-tree

boost-geometry

环境设置

提升代码