[vtkusers] Why is vtkDelaunay2D so slow in VC++ 2005

[Godofredo]

Yeah, sure there's quite a difference in hardware. Mine's a Pentium M 2G with
1MB of cache and 1GB of ram. The test should be done in the same conditions.
I'll have to test it on linux (or another compiler) and study differences.  

santana wrote:
> 
> 
> 
> 
>   
> 
> 
> Hi Godofredo, 
> I added your data into the plot, posted to same place
> http://quaoar.sr.unh.edu/vtkDelaunay2D/ 
> I am not sure it is a fair comparison, since our hardware setup is
> probably quite different, I am running a dual proc, dual core 2G
> opteron each core has 1M of cache and each proc has 2G of ram. What is
> your setup? 
> Burlen 
> 
> 
> 
> Godofredo wrote:
> 
>   Hi santana, I've run some timing test on VC ++ 2005. You can compare
> them
> with the ones you posted (by the way, nice job!!). As you can see, I'm
> working in the "linear" region because of the slowness of the algorithm
> and
> also because that will be the size range my input data will have. I cannot
> post a graph like yours but I post here the values so you can get an idea:
> 
> Number of points             vtkDelaunay2d time (seconds)
> 
> 402290                                        103
> 364985                                          95
> 339443                                          84
> 300141                                          74                       
> 273696                                          68
> 255287                                          62
> 232500                                          55
> 210868                                          49
> 194717                                          46
> 180700                                          41
> 163726                                          37
> 148096                                          33
> 125223                                          25
> 76458                                            15
> 
> If I understand your plot, it takes your program about 13 seconds to
> triangulate 512^2 = 262144 points. As you can see, it takes mine about 65
> seconds to complete the same task. This has been done in debug mode but,
> as
> I've said in a previous post, I don't appreciate much difference between
> release and debug modes. 
> 
> 
> santana wrote:
>   
>   
>     
> 
> 
> 
> Hi, Godofredo, I ran some timing tests on vtkdelaunay2D this morning
> after your post and found that vtkDelaunay2D performance is actually
> O(n^2) when compiled for debug. See
> http://quaoar.sr.unh.edu/vtkDelaunay2D/   for the details. I am running a
> linux box with the latest stable VTK. These results should give a
> reference point to compare your VC++ build against. 
> burlen 
> 
> Godofredo wrote:
> 
>   Hi, I haven't tried it yet under another platform. Sure it's slow by
> itself
> but I don't think that it should be that slow. Take a look at this
> unanswered post (quite old) regarding to VC7 vs VC6 and vtkDelaunay2D:
> 
> http://public.kitware.com/pipermail/vtkusers/2002-December/064429.html  
> 
> As soon I've time, I'll try under another platform to evaluate the
> algorithm
> performance. Meanwhile any comment is wellcomed. Thanks to all.
> 
> 
> santana wrote:
>   
>   
>     Hi, Delaunay is slow algorithm in general, it has to work point by
> point 
> and make a search through the point set with each insertion. I am not 
> sure about VTK but I have seen the time complexity of other 
> implementations is O(n*log(n)). It sounds like you by hand approach is 
> O(n) so would be much faster. You mentioned that you think it is related 
> to VC++ 2005 but I think it is the delaunay algorithm itself rather than 
> the platform which is the problem. have you tried under another platform?
> Burlen
> 
> 
> Godofredo wrote:
>     
>     
>       Hi to all, I've been doing some triangulations with big datasets and
> found
> out that vtkDelaunay2D is extremely slow in VC++ 2005. I've done the
> triangulation by hand (as my data came from a range scanner I just join
> the 
> verts in order) and It takes only seconds to triangulate what with
> vtkDelaunay2D takes almost 2 minutes. I've found in the forums a post
> that
> talked about the same problem but had no replys. Anyone could put some
> light
> into this? Many thanks.
>   
>       
>     
>     _______________________________________________
> This is the private VTK discussion list. 
> Please keep messages on-topic. Check the FAQ at:
> http://www.vtk.org/Wiki/VTK_FAQ  
> Follow this link to subscribe/unsubscribe:
> http://www.vtk.org/mailman/listinfo/vtkusers  
> 
> 
> -----
> http://quaoar.sr.unh.edu   
> 
>     
>   
>   
>   
> 
> 
> 
> 
> 
> _______________________________________________
> This is the private VTK discussion list. 
> Please keep messages on-topic. Check the FAQ at:
> http://www.vtk.org/Wiki/VTK_FAQ 
> Follow this link to subscribe/unsubscribe:
> http://www.vtk.org/mailman/listinfo/vtkusers 
> 
> 
> -----
> http://quaoar.sr.unh.edu  
> 
>     
>   
>   
>   
> 
> 
> 
> 
> 
> _______________________________________________
> This is the private VTK discussion list. 
> Please keep messages on-topic. Check the FAQ at:
> http://www.vtk.org/Wiki/VTK_FAQ
> Follow this link to subscribe/unsubscribe:
> http://www.vtk.org/mailman/listinfo/vtkusers
> 
> 
> -----
> http://quaoar.sr.unh.edu 
> 

-- 
View this message in context: http://www.nabble.com/Why-is-vtkDelaunay2D-so-slow-in-VC%2B%2B-2005-tp14576119p14612313.html
Sent from the VTK - Users mailing list archive at Nabble.com.