Extremely slow Face_count_stop_predicate

[nh2]

Hi, I just wanted to make you aware of a potential performance bug in Surface_mesh_simplification:

https://github.com/CGAL/cgal/blob/c4165fe5f9f97099bb91dc4e11708df014e9952f/Surface_mesh_simplification/include/CGAL/Surface_mesh_simplification/Policies/Edge_collapse/Face_count_stop_predicate.h#L41

I have the suspicion that exact_num_faces() is somehow O(faces) instead of constant-time reading an integer.

https://github.com/CGAL/cgal/blob/c4165fe5f9f97099bb91dc4e11708df014e9952f/BGL/include/CGAL/boost/graph/internal/helpers.h#L162-L167

I noticed that using Face_count_stop_predicate instead of Edge_count_stop_predicate makes simplification 10000x slower, and changing the line to

    const std::size_t current_face_count = profile.surface_mesh().number_of_faces();

Fixes it.

(There's the caveat that I'm using Face_count_stop_predicate.h from CGAL master (5.6.1+) with my local CGAL 5.5.2 where Face_count_stop_predicate.h didn't exist yet.)

Just in case this is a free 10000x speedup :)

[MaelRL]

Thanks for the detailed report.

This issue is tracked in https://github.com/CGAL/cgal/issues/5720, so I'll close this one, but it was a useful reminder.

[nh2]

Ah, I see, thanks!

Would it make sense to PR

-const std::size_t current_face_count = CGAL::internal::exact_num_faces(profile.surface_mesh()); 
+const std::size_t current_face_count = profile.surface_mesh().number_of_faces();

anyway until #5720 is solved, or would that make the interface less generic than desired, e.g. no longer implement the statement from https://doc.cgal.org/5.5.4/Surface_mesh_simplification/index.html#Surface_mesh_simplificationIntroduction that

The algorithm implemented here is generic in the sense that it does not require the surface mesh to be of a particular type but to be a model of the MutableFaceGraph and HalfedgeListGraph concepts.

?

[MaelRL]

It would break genericity because number_of_faces() is a member function of the CGAL::Surface_mesh class, and in theory you should be able to use the simplification package with any structure that implements the graph concepts that you have quoted and there is no reason for all data structures to have a member function called number_of_faces.

A quick (and maybe even proper - I need to look at it) fix would be to add an overload of exact_num_faces for CGAL::Surface_mesh(), which simply returns sm.number_of_faces() instead of the std::distance() generic implementation.

[MaelRL]

@nh2 The overloads were added in https://github.com/CGAL/cgal/pull/8215.