search

GUDHI / gudhi-devel

The GUDHI library is a generic open source C++ library, with a Python interface, for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.
https://gudhi.inria.fr/
MIT License
245 stars 65 forks source link

Use TDS_full_cell_mirror_storage_policy for static dimension as benchmark shows with CGAL 6.0 #1050

Closed VincentRouvreau closed 1 month ago

VincentRouvreau commented 2 months ago

Tested with #1049 on a temporary branch.

The benchmark (the one that is already in Alpha_complex and using benchmark_points_on_torus_dD) results:

// CGAL master - 6.0                                                  // CGAL master - 6.0 + CGAL::TDS_full_cell_mirror_storage_policy
+ Epick_d static dimension version                                    + Epick_d static dimension version
  Alpha complex dD on torus with 25000 points.                          Alpha complex dD on torus with 25000 points.
    benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.343s      benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.306s
    benchmark_points_on_torus_dD - complex creation: 0.291s               benchmark_points_on_torus_dD - complex creation: 0.299s
    benchmark_points_on_torus_dD - nb simplices = 1546293                 benchmark_points_on_torus_dD - nb simplices = 1551895
  Alpha complex dD on torus with 125000 points.                         Alpha complex dD on torus with 125000 points.
    benchmark_points_on_torus_dD - Alpha complex 3d creation: 2.207s      benchmark_points_on_torus_dD - Alpha complex 3d creation: 1.96s
    benchmark_points_on_torus_dD - complex creation: 2.393s               benchmark_points_on_torus_dD - complex creation: 2.47s
    benchmark_points_on_torus_dD - nb simplices = 9049571                 benchmark_points_on_torus_dD - nb simplices = 9041611
+ Epick_d dynamic dimension version                                   + Epick_d dynamic dimension version
  Alpha complex dD on torus with 25000 points.                          Alpha complex dD on torus with 25000 points.
    benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.836s      benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.822s
    benchmark_points_on_torus_dD - complex creation: 0.303s               benchmark_points_on_torus_dD - complex creation: 0.296s
    benchmark_points_on_torus_dD - nb simplices = 1550711                 benchmark_points_on_torus_dD - nb simplices = 1549971
  Alpha complex dD on torus with 125000 points.                         Alpha complex dD on torus with 125000 points.
    benchmark_points_on_torus_dD - Alpha complex 3d creation: 6.092s      benchmark_points_on_torus_dD - Alpha complex 3d creation: 6.091s
    benchmark_points_on_torus_dD - complex creation: 2.551s               benchmark_points_on_torus_dD - complex creation: 2.597s
    benchmark_points_on_torus_dD - nb simplices = 9057759                 benchmark_points_on_torus_dD - nb simplices = 9062213
+ Epeck_d static dimension version                                    + Epeck_d static dimension version
  Alpha complex dD on torus with 25000 points.                          Alpha complex dD on torus with 25000 points.
    benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.451s      benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.411s
    benchmark_points_on_torus_dD - complex creation: 0.275s               benchmark_points_on_torus_dD - complex creation: 0.28s
    benchmark_points_on_torus_dD - nb simplices = 1544141                 benchmark_points_on_torus_dD - nb simplices = 1555751
  Alpha complex dD on torus with 125000 points.                         Alpha complex dD on torus with 125000 points.
    benchmark_points_on_torus_dD - Alpha complex 3d creation: 2.996s      benchmark_points_on_torus_dD - Alpha complex 3d creation: 2.997s
    benchmark_points_on_torus_dD - complex creation: 2.252s               benchmark_points_on_torus_dD - complex creation: 2.274s
    benchmark_points_on_torus_dD - nb simplices = 9056937                 benchmark_points_on_torus_dD - nb simplices = 9050971
+ Epeck_d dynamic dimension version                                   + Epeck_d dynamic dimension version
  Alpha complex dD on torus with 25000 points.                          Alpha complex dD on torus with 25000 points.
    benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.644s      benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.672s
    benchmark_points_on_torus_dD - complex creation: 0.286s               benchmark_points_on_torus_dD - complex creation: 0.298s
    benchmark_points_on_torus_dD - nb simplices = 1549789                 benchmark_points_on_torus_dD - nb simplices = 1551985
  Alpha complex dD on torus with 125000 points.                         Alpha complex dD on torus with 125000 points.
    benchmark_points_on_torus_dD - Alpha complex 3d creation: 4.872s      benchmark_points_on_torus_dD - Alpha complex 3d creation: 5.153s
    benchmark_points_on_torus_dD - complex creation: 2.359s               benchmark_points_on_torus_dD - complex creation: 2.417s
    benchmark_points_on_torus_dD - nb simplices = 9038101                 benchmark_points_on_torus_dD - nb simplices = 9046073

As we can see, CGAL::TDS_full_cell_mirror_storage_policy enhances only the static versions of alpha.

mglisse commented 2 months ago

It is surprising that for Epeck_d static, the change helps with 25k points but not with 125k points...

VincentRouvreau commented 1 month ago

It is surprising that for Epeck_d static, the change helps with 25k points but not with 125k points...

I did the benchmark once again. As the number of simplices is not always the same with the random points method, it is not always easy to compare:

// CGAL 5.5.3 - GUDHI master                                        // CGAL 5.5.3 - GUDHI master + PR 1050
+ Fast static dimension version                                     + Fast static dimension version                                  
Alpha complex dD on torus with 25000 points.                        Alpha complex dD on torus with 25000 points.                     
benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.414s    benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.383s 
benchmark_points_on_torus_dD - complex creation: 1.233s             benchmark_points_on_torus_dD - complex creation: 1.222s          
benchmark_points_on_torus_dD - nb simplices = 1546965               benchmark_points_on_torus_dD - nb simplices = 1547821            
Alpha complex dD on torus with 125000 points.                       Alpha complex dD on torus with 125000 points.                    
benchmark_points_on_torus_dD - Alpha complex 3d creation: 2.719s    benchmark_points_on_torus_dD - Alpha complex 3d creation: 2.569s 
benchmark_points_on_torus_dD - complex creation: 9.754s             benchmark_points_on_torus_dD - complex creation: 9.227s          
benchmark_points_on_torus_dD - nb simplices = 9038901               benchmark_points_on_torus_dD - nb simplices = 9056079            
+ Fast dynamic dimension version                                    + Fast dynamic dimension version                                 
Alpha complex dD on torus with 25000 points.                        Alpha complex dD on torus with 25000 points.                     
benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.856s    benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.798s 
benchmark_points_on_torus_dD - complex creation: 1.586s             benchmark_points_on_torus_dD - complex creation: 1.54s           
benchmark_points_on_torus_dD - nb simplices = 1549945               benchmark_points_on_torus_dD - nb simplices = 1550647            
Alpha complex dD on torus with 125000 points.                       Alpha complex dD on torus with 125000 points.                    
benchmark_points_on_torus_dD - Alpha complex 3d creation: 6.301s    benchmark_points_on_torus_dD - Alpha complex 3d creation: 6.02s  
benchmark_points_on_torus_dD - complex creation: 11.251s            benchmark_points_on_torus_dD - complex creation: 11.286s         
benchmark_points_on_torus_dD - nb simplices = 9036767               benchmark_points_on_torus_dD - nb simplices = 9046231            
+ Exact static dimension version                                    + Exact static dimension version                                 
Alpha complex dD on torus with 25000 points.                        Alpha complex dD on torus with 25000 points.                     
benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.447s    benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.422s 
benchmark_points_on_torus_dD - complex creation: 1.71s              benchmark_points_on_torus_dD - complex creation: 1.706s          
benchmark_points_on_torus_dD - nb simplices = 1551357               benchmark_points_on_torus_dD - nb simplices = 1556341            
Alpha complex dD on torus with 125000 points.                       Alpha complex dD on torus with 125000 points.                    
benchmark_points_on_torus_dD - Alpha complex 3d creation: 3.223s    benchmark_points_on_torus_dD - Alpha complex 3d creation: 3.008s 
benchmark_points_on_torus_dD - complex creation: 12.482s            benchmark_points_on_torus_dD - complex creation: 12.456s         
benchmark_points_on_torus_dD - nb simplices = 9051919               benchmark_points_on_torus_dD - nb simplices = 9052801            
+ Exact dynamic dimension version                                   + Exact dynamic dimension version                                
Alpha complex dD on torus with 25000 points.                        Alpha complex dD on torus with 25000 points.                     
benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.69s     benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.66s  
benchmark_points_on_torus_dD - complex creation: 1.928s             benchmark_points_on_torus_dD - complex creation: 1.919s          
benchmark_points_on_torus_dD - nb simplices = 1551683               benchmark_points_on_torus_dD - nb simplices = 1540301            
Alpha complex dD on torus with 125000 points.                       Alpha complex dD on torus with 125000 points.                    
benchmark_points_on_torus_dD - Alpha complex 3d creation: 5.154s    benchmark_points_on_torus_dD - Alpha complex 3d creation: 5.279s 
benchmark_points_on_torus_dD - complex creation: 13.497s            benchmark_points_on_torus_dD - complex creation: 14.123s         
benchmark_points_on_torus_dD - nb simplices = 9044481               benchmark_points_on_torus_dD - nb simplices = 9063261            

// CGAL 6.0.0 - GUDHI master                                        // CGAL 6.0.0 - GUDHI master + PR 1050
+ Fast static dimension version                                     + Fast static dimension version                                  
Alpha complex dD on torus with 25000 points.                        Alpha complex dD on torus with 25000 points.                     
benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.327s    benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.3s   
benchmark_points_on_torus_dD - complex creation: 1.255s             benchmark_points_on_torus_dD - complex creation: 1.218s          
benchmark_points_on_torus_dD - nb simplices = 1550447               benchmark_points_on_torus_dD - nb simplices = 1538991            
Alpha complex dD on torus with 125000 points.                       Alpha complex dD on torus with 125000 points.                    
benchmark_points_on_torus_dD - Alpha complex 3d creation: 2.265s    benchmark_points_on_torus_dD - Alpha complex 3d creation: 1.977s 
benchmark_points_on_torus_dD - complex creation: 9.63s              benchmark_points_on_torus_dD - complex creation: 9.219s          
benchmark_points_on_torus_dD - nb simplices = 9052629               benchmark_points_on_torus_dD - nb simplices = 9055601            
+ Fast dynamic dimension version                                    + Fast dynamic dimension version                                 
Alpha complex dD on torus with 25000 points.                        Alpha complex dD on torus with 25000 points.                     
benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.838s    benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.813s 
benchmark_points_on_torus_dD - complex creation: 1.496s             benchmark_points_on_torus_dD - complex creation: 1.594s          
benchmark_points_on_torus_dD - nb simplices = 1556109               benchmark_points_on_torus_dD - nb simplices = 1549237            
Alpha complex dD on torus with 125000 points.                       Alpha complex dD on torus with 125000 points.                    
benchmark_points_on_torus_dD - Alpha complex 3d creation: 5.955s    benchmark_points_on_torus_dD - Alpha complex 3d creation: 5.919s 
benchmark_points_on_torus_dD - complex creation: 11.411s            benchmark_points_on_torus_dD - complex creation: 11.688s         
benchmark_points_on_torus_dD - nb simplices = 9048643               benchmark_points_on_torus_dD - nb simplices = 9047417            
+ Exact static dimension version                                    + Exact static dimension version                                 
Alpha complex dD on torus with 25000 points.                        Alpha complex dD on torus with 25000 points.                     
benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.45s     benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.405s 
benchmark_points_on_torus_dD - complex creation: 1.761s             benchmark_points_on_torus_dD - complex creation: 1.749s          
benchmark_points_on_torus_dD - nb simplices = 1547727               benchmark_points_on_torus_dD - nb simplices = 1547097            
Alpha complex dD on torus with 125000 points.                       Alpha complex dD on torus with 125000 points.                    
benchmark_points_on_torus_dD - Alpha complex 3d creation: 3.263s    benchmark_points_on_torus_dD - Alpha complex 3d creation: 3.018s 
benchmark_points_on_torus_dD - complex creation: 12.607s            benchmark_points_on_torus_dD - complex creation: 12.429s         
benchmark_points_on_torus_dD - nb simplices = 9055613               benchmark_points_on_torus_dD - nb simplices = 9044619            
+ Exact dynamic dimension version                                   + Exact dynamic dimension version                                
Alpha complex dD on torus with 25000 points.                        Alpha complex dD on torus with 25000 points.                     
benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.675s    benchmark_points_on_torus_dD - Alpha complex 3d creation: 0.667s 
benchmark_points_on_torus_dD - complex creation: 2.007s             benchmark_points_on_torus_dD - complex creation: 1.868s          
benchmark_points_on_torus_dD - nb simplices = 1552593               benchmark_points_on_torus_dD - nb simplices = 1552797            
Alpha complex dD on torus with 125000 points.                       Alpha complex dD on torus with 125000 points.                    
benchmark_points_on_torus_dD - Alpha complex 3d creation: 5.206s    benchmark_points_on_torus_dD - Alpha complex 3d creation: 5.275s 
benchmark_points_on_torus_dD - complex creation: 13.823s            benchmark_points_on_torus_dD - complex creation: 13.375s         
benchmark_points_on_torus_dD - nb simplices = 9051151               benchmark_points_on_torus_dD - nb simplices = 9068847
VincentRouvreau commented 1 month ago

For symmetry, we could use Triangulation_ds_full_cell<> directly instead of Triangulation_full_cell<Geom_traits>

I did so on e01b763