Arrangement: Use Compact Container for DCEL by sgiraudot · Pull Request #5408 · CGAL/cgal

sgiraudot · 2021-01-28T13:57:46Z

Summary of Changes

The DCEL data structure currently uses In_place_list. Although using the fast_pool_allocator already speeds this structure up, I experimented with the Compact Container and noticed it was more efficient.

using CC instead of in place lists improves timings up to 15% (5% in average)
most structures benefit from pointer squatting except for the face and inner CCB classes which are given an additional pointer. Other structures have 2 pointers removed (from In_place_list_base), and thus the memory usage is decreased
using fast_pool_allocator remains more efficient than std::allocator

By running the testsuite locally, I got errors from iterators constructed from 0. I replaced that by nullptr and it fixed the problems.

Release Management

Affected package(s): Arrangement and dependent packages (Surface Sweep, Boolean Operations, etc.)

gdamiand · 2021-01-28T15:14:25Z

Arrangement_on_surface_2/include/CGAL/Arr_dcel_base.h

 */
 template <class V, class H, class F>
-class Arr_inner_ccb : public In_place_list_base<Arr_inner_ccb<V,H,F> >
+class Arr_inner_ccb : public Compact_container_base


You can use pointer p_f instead of using Compact_container_base (you will save one pointer per element).

You are right indeed.

The reason I did not use it is that it will already be squatted when https://github.com/CGAL/cgal/pull/5166/files is merged (as I'm working on an experiment branch with all optimizations, I did not modify this part). I could modify this PR and revert back in the other one, but it's probably a waste of time.

gdamiand · 2021-01-28T15:19:31Z

Arrangement_on_surface_2/include/CGAL/Arr_dcel_base.h

@@ -91,6 +91,9 @@ template <typename Point_> class Arr_vertex_base {
  /*! Destructor. */
  virtual ~Arr_vertex_base() {}


I know this is not your code, but seeing this destructor I am wondering if polymorphism is really used here ?
If not (this must be checked), virtual methods can be avoided in order to save memory.

maxGimeno · 2021-02-19T07:57:05Z

errors :

I think it's all the same error but it needs to be checked

EDIT: Also this runtime error : https://cgal.geometryfactory.com/CGAL/testsuite/CGAL-5.3-Ic-66/Arrangement_on_surface_2_Examples/TestReport_Blake_Windows_MSVCPreview-Release-64bits.gz

lrineau · 2021-02-19T08:47:02Z

STL_Extension/include/CGAL/Compact_container.h

+    CC_iterator(pointer ptr) : m_ptr(ptr) { }
+


This new constructor is the culprit for all the compilation errors.
See for example https://cgal.geometryfactory.com/CGAL/testsuite/CGAL-5.3-Ic-66/Linear_cell_complex_Demo/TestReport_lrineau_ArchLinux-CXX17-Release.gz

In file included from /home/cgal_tester/build/src/cmake/platforms/ArchLinux-CXX17-Release/test/Linear_cell_complex_Demo/MainWindow.cpp:22: /home/cgal_tester/build/src/cmake/platforms/ArchLinux-CXX17-Release/test/Linear_cell_complex_Demo/import_moka.h: In constructor ‘CGAL::GDart::GDart()’: /home/cgal_tester/build/src/cmake/platforms/ArchLinux-CXX17-Release/test/Linear_cell_complex_Demo/import_moka.h:23:30: error: call of overloaded ‘CC_iterator(NULL)’ is ambiguous 23 | GDart() : dh(NULL), vh(NULL) | ^ In file included from /mnt/testsuite/include/CGAL/Triangulation_data_structure_2.h:33, from /mnt/testsuite/include/CGAL/Triangulation_2.h:32, from /mnt/testsuite/include/CGAL/Constrained_triangulation_2.h:25, from /mnt/testsuite/include/CGAL/Constrained_Delaunay_triangulation_2.h:20, from /home/cgal_tester/build/src/cmake/platforms/ArchLinux-CXX17-Release/test/Linear_cell_complex_Demo/typedefs.h:20, from /home/cgal_tester/build/src/cmake/platforms/ArchLinux-CXX17-Release/test/Linear_cell_complex_Demo/MainWindow.h:16, from /home/cgal_tester/build/src/cmake/platforms/ArchLinux-CXX17-Release/test/Linear_cell_complex_Demo/MainWindow.cpp:14: /mnt/testsuite/include/CGAL/Compact_container.h:906:5: note: candidate: ‘CGAL::internal::CC_iterator<DSC, Const>::CC_iterator(std::nullptr_t) [with DSC = CGAL::Compact_container<CGAL::Dart<3, CGAL::CMap_linear_cell_complex_storage_1<3, 3, CGAL::Linear_cell_complex_traits<3, CGAL::Epick>, Myitems, std::allocator<int>, CGAL::Boolean_tag<false> >, CGAL::Void, CGAL::Boolean_tag<false> >, std::allocator<CGAL::Dart<3, CGAL::CMap_linear_cell_complex_storage_1<3, 3, CGAL::Linear_cell_complex_traits<3, CGAL::Epick>, Myitems, std::allocator<int>, CGAL::Boolean_tag<false> >, CGAL::Void, CGAL::Boolean_tag<false> > >, CGAL::Default, CGAL::Default>; bool Const = false; std::nullptr_t = std::nullptr_t]’ 906 | CC_iterator (std::nullptr_t /*CGAL_assertion_code(n)*/) | ^~~~~~~~~~~ /mnt/testsuite/include/CGAL/Compact_container.h:878:5: note: candidate: ‘CGAL::internal::CC_iterator<DSC, Const>::CC_iterator(CGAL::internal::CC_iterator<DSC, Const>::pointer) [with DSC = CGAL::Compact_container<CGAL::Dart<3, CGAL::CMap_linear_cell_complex_storage_1<3, 3, CGAL::Linear_cell_complex_traits<3, CGAL::Epick>, Myitems, std::allocator<int>, CGAL::Boolean_tag<false> >, CGAL::Void, CGAL::Boolean_tag<false> >, std::allocator<CGAL::Dart<3, CGAL::CMap_linear_cell_complex_storage_1<3, 3, CGAL::Linear_cell_complex_traits<3, CGAL::Epick>, Myitems, std::allocator<int>, CGAL::Boolean_tag<false> >, CGAL::Void, CGAL::Boolean_tag<false> > >, CGAL::Default, CGAL::Default>; bool Const = false; CGAL::internal::CC_iterator<DSC, Const>::pointer = CGAL::Dart<3, CGAL::CMap_linear_cell_complex_storage_1<3, 3, CGAL::Linear_cell_complex_traits<3, CGAL::Epick>, Myitems, std::allocator<int>, CGAL::Boolean_tag<false> >, CGAL::Void, CGAL::Boolean_tag<false> >*]’ 878 | CC_iterator(pointer ptr) : m_ptr(ptr) { } | ^~~~~~~~~~~ /mnt/testsuite/include/CGAL/Compact_container.h:855:9: note: candidate: ‘constexpr CGAL::internal::CC_iterator<CGAL::Compact_container<CGAL::Dart<3, CGAL::CMap_linear_cell_complex_storage_1<3, 3, CGAL::Linear_cell_complex_traits<3, CGAL::Epick>, Myitems, std::allocator<int>, CGAL::Boolean_tag<false> >, CGAL::Void, CGAL::Boolean_tag<false> >, std::allocator<CGAL::Dart<3, CGAL::CMap_linear_cell_complex_storage_1<3, 3, CGAL::Linear_cell_complex_traits<3, CGAL::Epick>, Myitems, std::allocator<int>, CGAL::Boolean_tag<false> >, CGAL::Void, CGAL::Boolean_tag<false> > >, CGAL::Default, CGAL::Default>, false>::CC_iterator(const CGAL::internal::CC_iterator<CGAL::Compact_container<CGAL::Dart<3, CGAL::CMap_linear_cell_complex_storage_1<3, 3, CGAL::Linear_cell_complex_traits<3, CGAL::Epick>, Myitems, std::allocator<int>, CGAL::Boolean_tag<false> >, CGAL::Void, CGAL::Boolean_tag<false> >, std::allocator<CGAL::Dart<3, CGAL::CMap_linear_cell_complex_storage_1<3, 3, CGAL::Linear_cell_complex_traits<3, CGAL::Epick>, Myitems, std::allocator<int>, CGAL::Boolean_tag<false> >, CGAL::Void, CGAL::Boolean_tag<false> > >, CGAL::Default, CGAL::Default>, false>&)’ 855 | class CC_iterator | ^~~~~~~~~~~

There is already a constructor from pointers, but it is private, and take an extra int for disambiguation. See https://github.com/sgiraudot/cgal/blob/6bbd72cfde33f76eba3cf692ba969ad3735d802c/STL_Extension/include/CGAL/Compact_container.h#L950-L962.

Where in this PR is the new constructor needed?

It's needed pretty much everywhere: the original implementation assumes that iterators can be created from pointers are the underlying structure is In_place_list. Is there any reason why this constructor should be private? The CC_iterator is pretty much just a pointer, and it's quite handy to be able to construct one from the other.

My guess is that was to avoid errors with implicit conversions, in the past before C++11 explicit constructors. I think the constructor from a pointer could be made public, but not documented, but only if it is explicit.

sgiraudot · 2021-03-24T08:16:01Z

Alright, so as suggested by Laurent, I made the constructor from a pointer explicit. It did require some changes in the arrangement iterators. I also replaced NULL by nullptr in the LCC demo, otherwise the call was ambiguous.

maxGimeno · 2021-03-25T08:12:18Z

Errors : Most of the red squares in https://cgal.geometryfactory.com/CGAL/testsuite/results-5.3-Ic-90.shtml

sgiraudot · 2021-03-25T08:42:34Z

I'll look into it, sorry about the mess :(

lrineau · 2021-03-25T09:07:38Z

Errors : Most of the red squares in cgal.geometryfactory.com/CGAL/testsuite/results-5.3-Ic-90.shtml

No. The culprit is 9f9e1e2 from PR #5233 (I have bisected). That is the one responsible for all the compilation errors about boost::any destructor:

/usr/include/boost/any.hpp: In instantiation of 'class boost::any::holder<CGAL::Segment_2<CGAL::Cartesian<double> > >':
/usr/include/boost/any.hpp:253:17:   required from 'ValueType* boost::any_cast(boost::any*) [with ValueType = CGAL::Segment_2<CGAL::Cartesian<double> >]'
/mnt/testsuite/include/CGAL/Object.h:87:43:   required from 'bool CGAL::Object::assign(T&) const [with T = CGAL::Segment_2<CGAL::Cartesian<double> >]'
/mnt/testsuite/include/CGAL/Object.h:157:20:   required from 'bool CGAL::assign(T&, const CGAL::Object&) [with T = CGAL::Segment_2<CGAL::Cartesian<double> >]'
.../test/Triangulation_2/include/CGAL/_test_cls_delaunay_triangulation_2.h:379:24:   required from 'void _test_delaunay_duality(const Del&) [with Del = CGAL::Delaunay_triangulation_2<CGAL::Cartesian<double> >]'
.../test/Triangulation_2/include/CGAL/_test_cls_delaunay_triangulation_2.h:201:26:   required from 'void _test_cls_delaunay_triangulation_2(const Del&) [with Del = CGAL::Delaunay_triangulation_2<CGAL::Cartesian<double> >]'
.../test/Triangulation_2/test_delaunay_triangulation_2.cpp:70:46:   required from here
/usr/include/boost/any.hpp:169:15: error: looser exception specification on overriding virtual function 'virtual boost::any::holder<CGAL::Segment_2<CGAL::Cartesian<double> > >::~holder() noexcept (false)'
  169 |         class holder
      |               ^~~~~~
/usr/include/boost/any.hpp:156:21: note: overridden function is 'virtual boost::any::placeholder::~placeholder() noexcept'
  156 |             virtual ~placeholder()
      |                     ^

lrineau · 2021-03-25T09:10:39Z

There are errors though, like https://cgal.geometryfactory.com/CGAL/testsuite/CGAL-5.3-Ic-90/Polygon_Demo/TestReport_lrineau_Fedora-with-LEDA.gz that seem to be related to the change of Compact_container iterators.

sgiraudot · 2021-03-25T09:11:03Z

Thanks Laurent!

lrineau · 2021-03-25T10:25:41Z

Sorry, I forgot to do the github change-base hack after rebasing, it's done now.

By rebase you mean that you still merge master by as the first child. Github has modified its behavior, as regards merges of master. Now we recommend a plain merge of cgal/master to refresh an old branch. See the FAQ (it has been modified in July 2019, you can see the old version).

sgiraudot · 2021-03-25T10:28:01Z

Oh okay, I missed that… I used to do git rebase and then switched to reset --hard cgal/master + merge branch. I'll merge directly master from now on, thanks.

maxGimeno · 2021-03-26T07:34:36Z

runtime error: https://cgal.geometryfactory.com/CGAL/testsuite/CGAL-5.3-Ic-91/Arrangement_on_surface_2_Examples/TestReport_Blake_Windows_MSVCPreview-Release-64bits.gz

sgiraudot · 2021-03-29T13:02:08Z

I fixed the bug (it was just the way a loop was written which made an iterator to end() being incremented, which is not allowed with the compact container iterators).

maxGimeno · 2021-04-06T07:00:16Z

warnings: https://cgal.geometryfactory.com/CGAL/testsuite/CGAL-5.3-Ic-98/Minkowski_sum_2_Examples/TestReport_lrineau_ArchLinux-CXX17-Release.gz

sgiraudot · 2021-04-20T06:59:26Z

This warning does not seem to come from my PR, I can reproduce it without Arrangement at all anyway: https://gist.github.com/sgiraudot/4699588a5e31cd753c28eb87f64ab110

maxGimeno · 2021-04-28T13:14:42Z

Successfully tested in https://cgal.geometryfactory.com/CGAL/testsuite/results-5.3-Ic-114.shtml

sgiraudot · 2021-05-03T06:48:55Z

Just a quick note in case someone runs into this PR in the future: contrary to what I originally claimed, this PR does not introduce a memory overhead. Some structures do need an additional pointer for the Compact Container, but all structures used to need 2 pointers from the In_place_list_base structure which are removed. So in total, the memory usage is decreased, not increased (I updated the PR's description accordingly).

From Efi's tests:

Before:
sizeof vertex: 48
sizeof halfedge: 72
sizeof face: 104

After:
sizeof vertex: 32
sizeof halfedge: 56
sizeof face: 96

sgiraudot added 3 commits January 28, 2021 10:30

Use Compact Container in DCEL base instead of in place list

80e9915

Clean up and use fast pool allocator (faster)

2e98995

Fix default constructor of iterators

6bbd72c

sgiraudot added Enhancement Pkg::Arrangement_on_surface_2 tested manually on Linux labels Jan 28, 2021

gdamiand reviewed Jan 28, 2021

View reviewed changes

MaelRL added the Ready to be tested label Feb 8, 2021

maxGimeno added Under Testing Tests failing and removed Under Testing labels Feb 18, 2021

MaelRL removed the Ready to be tested label Feb 19, 2021

lrineau reviewed Feb 19, 2021

View reviewed changes

maxGimeno added this to the 5.3-beta milestone Feb 22, 2021

sgiraudot added 2 commits March 24, 2021 08:25

Fix CC_iterator by making constructor from pointer explicit

3448035

Use nullptr instead of NULL to fix ambiguous construction

afc6e4c

maxGimeno added Ready to be tested Under Testing Tests failing and removed Tests failing Under Testing labels Mar 24, 2021

Rebase

3cf1853

maxGimeno added Tests failing and removed Under Testing labels Mar 26, 2021

Fix example (avoid incrementing end())

c11d631

maxGimeno added Under Testing and removed Tests failing labels Mar 29, 2021

Resolve ambiguous call to operator== by overloading it with base type

4e4a93d

maxGimeno added Tests failing (warning) and removed Under Testing labels Apr 6, 2021

maxGimeno added Under Testing and removed Tests failing (warning) labels Apr 20, 2021

maxGimeno added the Tested label Apr 28, 2021

lrineau self-assigned this Apr 28, 2021

lrineau added the rm only: ready for master For the release team only: that indicates that a PR is about to be merged in 'master' label Apr 28, 2021

lrineau merged commit 7ba37d8 into CGAL:master Apr 28, 2021

lrineau removed Ready to be tested Under Testing rm only: ready for master For the release team only: that indicates that a PR is about to be merged in 'master' labels Apr 28, 2021

lrineau deleted the Arrangement-Compact_container_based_DCEL-GF branch April 28, 2021 13:30

lrineau added Merged_in_5.3-beta1 Merged_in_5.3 labels Jul 2, 2021

sloriot mentioned this pull request Oct 29, 2021

Performance degradation of boolean set operation when upgrade CGAL from 5.2.3 to 5.3. #6092

Closed

sloriot mentioned this pull request Nov 9, 2021

Fix issues with new containers for arrangement cells #6094

Merged

		@@ -91,6 +91,9 @@ template <typename Point_> class Arr_vertex_base {
		/! Destructor. /
		virtual ~Arr_vertex_base() {}

Conversation

sgiraudot commented Jan 28, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Summary of Changes

Release Management

Uh oh!

gdamiand Jan 28, 2021

Choose a reason for hiding this comment

Uh oh!

sgiraudot Feb 1, 2021

Choose a reason for hiding this comment

Uh oh!

gdamiand Jan 28, 2021

Choose a reason for hiding this comment

Uh oh!

maxGimeno commented Feb 19, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

lrineau Feb 19, 2021

Choose a reason for hiding this comment

Uh oh!

sgiraudot Feb 23, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

lrineau Feb 23, 2021

Choose a reason for hiding this comment

Uh oh!

sgiraudot commented Mar 24, 2021

Uh oh!

maxGimeno commented Mar 25, 2021

Uh oh!

sgiraudot commented Mar 25, 2021

Uh oh!

lrineau commented Mar 25, 2021

Uh oh!

lrineau commented Mar 25, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sgiraudot commented Mar 25, 2021

Uh oh!

lrineau commented Mar 25, 2021

Uh oh!

sgiraudot commented Mar 25, 2021

Uh oh!

maxGimeno commented Mar 26, 2021

Uh oh!

sgiraudot commented Mar 29, 2021

Uh oh!

maxGimeno commented Apr 6, 2021

Uh oh!

sgiraudot commented Apr 20, 2021

Uh oh!

maxGimeno commented Apr 28, 2021

Uh oh!

sgiraudot commented May 3, 2021

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

sgiraudot commented Jan 28, 2021 •

edited

Loading

maxGimeno commented Feb 19, 2021 •

edited

Loading

sgiraudot Feb 23, 2021 •

edited

Loading

lrineau commented Mar 25, 2021 •

edited

Loading