Boost::geometry:: пересечение производительности в режиме отладки

Question

У меня есть вопрос о производительности boost::geometry::intersection в конфигурации Debug. Одна часть моего проекта имеет много (миллионов) пересечений многоугольника-многоугольника. И это очень-очень медленно в отладке по сравнению с выпуском. Поэтому мне нужно подождать много времени для устранения проблем после этой части "пересечения". Что я могу сделать, чтобы ускорить его в режиме отладки?

Пример кода простого консольного проекта Win32 в VS2010:

#include "stdafx.h"
#include <time.h>
#include <deque>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/foreach.hpp>

bool get_poly_intersection_area_S_2d(   const double *poly_x_1, const int poly_n_1,    const double *poly_x_2, const int poly_n_2, double *S)
{
    // intersects two 2d polygons using boost::geometry library
    // polygons are in 3d format [(x0, y0, 0.0) (x1, y1, 0.0) .... (xn, yn, 0.0) ]
    // S is resulting area of intersection
    // returns true if intersection exists (area > DBL_EPSILON) and false otherwise
    typedef boost::geometry::model::d2::point_xy<double> bg_point;
    typedef boost::geometry::model::polygon< bg_point, false, false > bg_polygon;

    *S = 0.0;

    bg_polygon bg_poly_1, bg_poly_2;

    // init boost 2d polygons by our double 3D polygons
    for(int i=0; i<poly_n_1; i++)
      bg_poly_1.outer().push_back(bg_point(poly_x_1[i*3], poly_x_1[i*3+1]));

    for(int i=0; i<poly_n_2; i++)
      bg_poly_2.outer().push_back(bg_point(poly_x_2[i*3], poly_x_2[i*3+1]));

    // correct polygons
    boost::geometry::correct(bg_poly_1);
    boost::geometry::correct(bg_poly_2);

    // call intersection
    std::deque<bg_polygon> output;
    bool res = boost::geometry::intersection(bg_poly_1, bg_poly_2, output);

    if(!res)
     return false;

    // for each polygon of intersection we add area
    BOOST_FOREACH(bg_polygon const& p, output)
    {
      double s = boost::geometry::area(p);
      *S += s;
    }

    // no intersection
    if(fabs(*S) <= DBL_EPSILON)
       return false;

    // intersection > DBL_EPSILON
    return true;
}

int _tmain(int argc, _TCHAR* argv[])
{
double p1[4 * 3] = {0,0,0, 2,0,0, 2,2,0, 0,2,0};
double p2[4 * 3] = {1,1,0, 3,1,0, 3,3,0, 1,3,0};

clock_t start_t, finish_t;
start_t = clock();
for(int i=0;i<5000; i++)
{
    double s;
    for(int k=0; k<4; k++)
    {
        p1[k*4] += i;
        p2[k*4] += i;
    }
    get_poly_intersection_area_S_2d(p1, 4, p2, 4, &s);
}
finish_t = clock();
printf("time=%.3f s\n", double(finish_t - start_t)/1000.);

return 0;
}

В режиме отладки это занимает 15 секунд, в версии 0,1 секунды. И здесь только 5000 пересечений полигонов. Для миллионов это будет намного медленнее.

Answer 1

На скорость Boost.Geometry сильно влияет скорость stl (vector, deque, map), которая значительно ниже в режиме отладки.

Вы можете попытаться решить это, например, по этим ссылкам:

Почему мой код STL работает так медленно, когда у меня подключен отладчик /IDE?

Почему этот код в 100 раз медленнее при отладке?

Особенно вторая ссылка предлагает установить _HAS_ITERATOR_DEBUGGING в 0, что может очень помочь, потому что итераторы интенсивно используются внутри Boost.Geometry

В качестве альтернативы вы можете попробовать использовать порт stl.

Answer 2

Лучший способ - найти способ воспроизвести проблему, которую вы отлаживаете, с помощью небольшого набора данных. Это помогает МНОГИМ способом, особенно при создании регрессионного теста, когда вы решили проблему.

Вы пишете: "отладка проблем после этой части пересечения"

Это подсказывает мне, что вы можете при желании сохранить выходные данные из части пересечения, чтобы вам нужно было запустить их только один раз, а затем иметь возможность загрузить сохраненный частичный результат и запустить остальную часть программы оттуда в режиме отладки.