[polygon] Quadratic performance when handling any angle polygons
Hello, First: we are using boost 1.45.0 with gcc -O3 on Ubuntu 10.04. (Although similar problems appear with VS2008 on Windows 7). We have been observing performance with boost::polygon that is significantly worse than we were expecting when working with any angle polygons. Namely quadratic instead of the expected O(n log n). While profiling, I noticed that most of the time is spent in the overload of line_intersection::validate_scan at detail/scan_arbitrary.hpp:154 which is commented as: "//quadratic algorithm to do same work as optimal scan for cross checking". I have inlined our test program below, and some performance results measured by instruction count under "valgrind --tool=callgrind". Is this poor performance because our data is degenerate, or because a vestigal quadratic double check is still being applied? Regards, Josh Pieper Performance results for n=10..110 measured in instructions to complete the following test program: 10 2363923 20 4427849 30 8695564 40 15642559 50 25530188 60 39081335 70 57151093 80 79278939 90 107261217 100 140674559 110 164340087 -------------------------- #include <boost/lexical_cast.hpp> #include <boost/type.hpp> #include <boost/polygon/polygon.hpp> #include <boost/polygon/gmp_override.hpp> int main(int argc, char** argv) { typedef boost::polygon::point_data<int32_t> point_type; typedef boost::polygon::polygon_set_data<int32_t> polygon_set; typedef polygon_set::value_type value_type; int32_t sample_data[] = { -15417, -53418, 0, 0, -1, -15417, -53418, 37998, -68834, 1, 37998, -68834, 53415, -15416, 1, 0, 0, 53415, -15416, -1, -20188, -37532, 15869, 4788, -1, -20188, -37532, 22129, -73587, 1, 22129, -73587, 58187, -31268, 1, 15869, 4788, 58187, -31268, -1, -12388, -58060, -4666, -3001, -1, -12388, -58060, 42669, -65781, 1, 42669, -65781, 50390, -10722, 1, -4666, -3001, 50390, -10722, -1, -16452, -51370, 2015, 1078, -1, -16452, -51370, 35988, -69834, 1, 35988, -69834, 54455, -17386, 1, 2015, 1078, 54455, -17386, -1, -9812, -61108, -7737, -5548, -1, -9812, -61108, 45744, -63182, 1, 45744, -63182, 47819, -7623, 1, -7737, -5548, 47819, -7623, -1, -19695, -27418, 25940, 4341, -1, -19695, -27418, 12063, -73050, 1, 12063, -73050, 57697, -41291, 1, 25940, 4341, 57697, -41291, -1, -11871, -58680, -5330, -3460, -1, -11871, -58680, 43338, -65220, 1, 43338, -65220, 49879, -10000, 1, -5330, -3460, 49879, -10000, -1, -12303, -10547, -4768, -65638, 1, -4768, -65638, 50314, -58104, 1, 42779, -3013, 50314, -58104, -1, -12303, -10547, 42779, -3013, -1, -10105, -60739, -7415, -5202, -1, -10105, -60739, 45425, -63428, 1, 45425, -63428, 48115, -7891, 1, -7415, -5202, 48115, -7891, -1, -9937, -60912, -7600, -5360, -1, -9937, -60912, 45609, -63249, 1, 45609, -63249, 47946, -7697, 1, -7600, -5360, 47946, -7697, -1, -20348, -32184, 16794, -73555, 1, 16794, -73555, 58164, -36414, 1, 21022, 4957, 58164, -36414, -1, -20348, -32184, 21022, 4957, -1, -10796, -8606, -6653, -64049, 1, -6653, -64049, 48788, -59906, 1, 44644, -4463, 48788, -59906, -1, -10796, -8606, 44644, -4463, -1, -16263, -16858, 1613, -69511, 1, 1613, -69511, 54257, -51638, 1, 36381, 1014, 54257, -51638, -1, -16263, -16858, 36381, 1014, -1, -20298, -33057, 17817, -73534, 1, 17817, -73534, 58292, -35421, 1, 20177, 5056, 58292, -35421, -1, -20298, -33057, 20177, 5056, -1, -11941, -9961, -5271, -65159, 1, -5271, -65159, 49923, -58490, 1, 43253, -3292, 49923, -58490, -1, -11941, -9961, 43253, -3292, -1, -19046, -44168, 28939, -72250, 1, 28939, -72250, 57020, -24267, 1, 9035, 3815, 57020, -24267, -1, -19046, -44168, 9035, 3815, -1, -10926, -8703, -6528, -64127, 1, -6528, -64127, 48893, -59729, 1, 44495, -4305, 48893, -59729, -1, -10926, -8703, 44495, -4305, -1, -19113, -43924, 28699, -72304, 1, 28699, -72304, 57076, -24496, 1, 9263, 3883, 57076, -24496, -1, -19113, -43924, 9263, 3883, -1, -18256, -21581, 6351, -71437, 1, 6351, -71437, 56204, -46832, 1, 31598, 3024, 56204, -46832, -1, -18256, -21581, 31598, 3024, -1, -20282, -31991, 16756, -73456, 1, 16756, -73456, 58219, -36421, 1, 21181, 5045, 58219, -36421, -1, -20282, -31991, 21181, 5045, -1, -19379, -25528, 10293, -72546, 1, 10293, -72546, 57309, -42875, 1, 27637, 4143, 57309, -42875, -1, -19379, -25528, 27637, 4143, -1, -16209, -16633, 1396, -69371, 1, 1396, -69371, 54130, -51767, 1, 36526, 970, 54130, -51767, -1, -16209, -16633, 36526, 970, -1, -18570, -22483, 7245, -71726, 1, 7245, -71726, 56484, -45912, 1, 30669, 3330, 56484, -45912, -1, -18570, -22483, 30669, 3330, -1, -19900, -40189, 24948, -73049, 1, 24948, -73049, 57806, -28203, 1, 12958, 4657, 57806, -28203, -1, -19900, -40189, 12958, 4657, -1, -20322, -36011, 20774, -73460, 1, 20774, -73460, 58220, -32367, 1, 17124, 5082, 58220, -32367, -1, -20322, -36011, 17124, 5082, -1, -555, -68328, 53079, -53671, 1, 38424, -43, 53079, -53671, -1, -15210, -14699, 38424, -43, -1, -15210, -14699, -555, -68328, 1, 21671, -61840, 21718, -61835, 1, 14689, -61655, 21718, -61835, -1, 14689, -61655, 42185, -65881, 1, 42185, -65881, 50629, -10931, 1, 23134, -6705, 50629, -10931, -1, 16104, -6524, 23134, -6705, -1, 16057, -6529, 16104, -6524, -1, 16057, -6529, 21671, -61840, 1, -7903, -63005, 47680, -60927, 1, 45602, -5370, 47680, -60927, -1, -9981, -7449, 45602, -5370, -1, -9981, -7449, -7903, -63005, 1, }; value_type edge_list; size_t num_elements = sizeof(sample_data) / (sizeof(*sample_data) * 5); if (argc > 1) { num_elements = std::min(num_elements, boost::lexical_cast<size_t>(argv[1])); } for (size_t i = 0; i < num_elements; i++) { value_type::value_type edge_plus; int32_t* record = &sample_data[i * 5]; edge_plus.first.first = point_type(record[0], record[1]); edge_plus.first.second = point_type(record[2], record[3]); edge_plus.second = record[4]; edge_list.push_back(edge_plus); } polygon_set pset; pset.set(edge_list); pset.clean(); }
Josh Pieper wrote:
First: we are using boost 1.45.0 with gcc -O3 on Ubuntu 10.04. (Although similar problems appear with >VS2008 on Windows 7).
We have been observing performance with boost::polygon that is significantly worse than we were expecting when working with any angle polygons. Namely quadratic instead of the expected O(n log n). While profiling, I noticed that most of the time is spent in the overload of line_intersection::validate_scan at detail/scan_arbitrary.hpp:154 which is commented as: "//quadratic algorithm to do same work as optimal scan for cross checking".
I have inlined our test program below, and some performance results measured by instruction count under "valgrind --tool=callgrind". Is this poor performance because our data is degenerate, or because a vestigal quadratic double check is still being applied?
So a couple things need explaining. The validate scan is worst case quatratic. The expected runtime of this function is O(n^1.5) if we assume that sqrt(n) edges intersect the sweepline at any given time. It was originally written to validate the bentley ottman sweepline algorithm I was working on but then I found it to be quite fast and put it into production usage without changing the name since it is an implementation detail. Moreover, you will notice that it is being called from a function with divide an conquer in the name. On top of the suboptimal validate_scan algorithm I am doing a divide and conquer. This approximates the optimal O(n log n) performance in the cases where the data is ammenible to divide and conquer (which is commonly the case.) Finally, your data appears to be randomly generated edges that you inflate by some small ammount in the edge_plus object, which is a worst case for line intersection. In randomly generated data the expected number of line intersections is O(n^2). Any line intersection will have O(n^2) (or worse) runtime wrt input points on randomly generated data. Whenever I state the algorithmic complexity of the algorithm I always specific that n is input points plus line intersection points. I also document that I use divide and conquer. There are pathological cases where divide and conquer doesn't help and even where the average number of line segments intersecting the sweepline is O(n) (think many parallel strips at 45 degrees). These cases are fairly artificial. In PCB or package layout where such data would commonly be seen divide and conquer usually is of benefit because 45 degree strips across the entire package or board isn't going to implement a circuit. Benchmarking polygon clipping can be tricky. It is just as easy to benchmark a best case input and conclude fantastic performance as to benchmark a worst case and conclude terrible performance. It is a little harder to get the real story. I suggest using application data and collecting requirements for performance for your application. The performance isn't poor unless it doesn't meet requirements on your application data or you have an alternative that is way faster. Regards, Luke
Lucas, Thank you for the detailed response. The data was actually from our application and the only reason I was investigating was because the application was performing poorly. However, as it turns out the application was faulty and generating polygons that were inappropriate. I had noticed the divide and conquer further up the stack, but as with most code unfamiliar to you, misunderstandings are easy to make so I wanted to make sure. Regards, Josh Pieper On Wed, Jan 19, 2011 at 12:37 PM, Simonson, Lucanus J < lucanus.j.simonson@intel.com> wrote:
Josh Pieper wrote:
First: we are using boost 1.45.0 with gcc -O3 on Ubuntu 10.04. (Although similar problems appear with >VS2008 on Windows 7).
We have been observing performance with boost::polygon that is significantly worse than we were expecting when working with any angle polygons. Namely quadratic instead of the expected O(n log n). While profiling, I noticed that most of the time is spent in the overload of line_intersection::validate_scan at detail/scan_arbitrary.hpp:154 which is commented as: "//quadratic algorithm to do same work as optimal scan for cross checking".
I have inlined our test program below, and some performance results measured by instruction count under "valgrind --tool=callgrind". Is this poor performance because our data is degenerate, or because a vestigal quadratic double check is still being applied?
So a couple things need explaining. The validate scan is worst case quatratic. The expected runtime of this function is O(n^1.5) if we assume that sqrt(n) edges intersect the sweepline at any given time. It was originally written to validate the bentley ottman sweepline algorithm I was working on but then I found it to be quite fast and put it into production usage without changing the name since it is an implementation detail. Moreover, you will notice that it is being called from a function with divide an conquer in the name. On top of the suboptimal validate_scan algorithm I am doing a divide and conquer. This approximates the optimal O(n log n) performance in the cases where the data is ammenible to divide and conquer (which is commonly the case.) Finally, your data appears to be randomly generated edges that you inflate by some small ammount in the edge_plus object, which is a worst case for line intersection. In randomly generated data the expected number of lin e intersections is O(n^2). Any line intersection will have O(n^2) (or worse) runtime wrt input points on randomly generated data. Whenever I state the algorithmic complexity of the algorithm I always specific that n is input points plus line intersection points. I also document that I use divide and conquer. There are pathological cases where divide and conquer doesn't help and even where the average number of line segments intersecting the sweepline is O(n) (think many parallel strips at 45 degrees). These cases are fairly artificial. In PCB or package layout where such data would commonly be seen divide and conquer usually is of benefit because 45 degree strips across the entire package or board isn't going to implement a circuit.
Benchmarking polygon clipping can be tricky. It is just as easy to benchmark a best case input and conclude fantastic performance as to benchmark a worst case and conclude terrible performance. It is a little harder to get the real story. I suggest using application data and collecting requirements for performance for your application. The performance isn't poor unless it doesn't meet requirements on your application data or you have an alternative that is way faster.
Regards, Luke
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (2)
-
Josh Pieper -
Simonson, Lucanus J