[Paraview] Ridiculously slow D3 (a bug in vtkMergeCells)

[Takuya OSHIMA]

Guys, thanks for all the responses, the tracker entry and applying the
patch.

I'm afraid I'm not sure if I can provide a good test dataset since the
bug does not affect small cases (the point insertion should take
O(n^2) of time where n is the number of points, when the hasing is not
working) and relies on indeterminate values (there's always a
possibility that the problem doesn't reproduce), which is why I did
all the tracking down by myself. But I'll see if I can do something.

Takuya

Takuya OSHIMA, Ph.D.
Faculty of Engineering, Niigata University
8050 Ikarashi-Ninocho, Nishi-ku, Niigata, 950-2181, JAPAN

From: Zhanping Liu <zhanping.liu at kitware.com>
Subject: Re: [Paraview] Ridiculously slow D3 (a bug in vtkMergeCells)
Date: Wed, 30 Sep 2009 12:39:15 -0400

> *
> Takuya:
>  
>     The problem was reflected on Mantis (issue #009626) and the suggested fix
> was applied. If you have any test (and shareable datasets), please feel free
> to submit it via Mantis.
>  
>     Thanks for the report and the fix.
>  
>     -Zhanping
>    --
> Zhanping Liu, PhD
> Kitware, Inc.
> 28 Corporate Drive
> Clifton Park, NY 12065-8662
> Phone: 518-371-3971 x 138
> http://www.zhanpingliu.org
> On Wed, Sep 30, 2009 at 3:51 AM, Takuya OSHIMA <oshima at eng.niigata-u.ac.jp>
> wrote:
> 
>     Hi,
>    
>     I have had a problem of ridiculously slow D3 of PV 3.6.1/3.7-cvs under
>     some conditions. Most of the time the problem occurs when I have more
>     pvserver processes than the number of data pieces, in which case D3
>     takes two orders of magnitude more time than usual, despite that the
>     resulting repartitioned dataset looks fine.
>    
>     Attaching a performance analyzer (Apple's Shark) to the pvserver
>     processes revealed that, in one of the pvserver processes
>     vtkMergePoints::InsertUniquePoint() took up virtually all of the
>     processor time, as attached sharkOutput.jpg.
>    
>     It further turned out that this is because the instance of
>     vtkMergePoints is given indeterminate bounds by its caller
>     vtkMergeCells::MapPointsToIdsUsingLocator() and hence hashing based on
>     relative point coordinates in the bounds is not working. Here is a
>     proposed fix to the problem (the comment "points0->GetNumberOfPoints()
>     is equal to..." was taken from about 50 lines below the patched lines
>     in the same function. I believe it explains everything.).
>    
>     Index: vtkMergeCells.cxx
>     ===================================================================
>     RCS file: /cvsroot/ParaView3/ParaView3/VTK/Graphics/vtkMergeCells.cxx,v
>     retrieving revision 1.9
>     diff -u -r1.9 vtkMergeCells.cxx
>     --- vtkMergeCells.cxx   23 Jan 2009 03:25:07 -0000      1.9
>     +++ vtkMergeCells.cxx   30 Sep 2009 06:47:09 -0000
>     @@ -723,7 +723,12 @@
>         if (npoints0 > 0)
>           {
>           double tmpbounds[6];
>     +      // points0->GetNumberOfPoints() is equal to the upper bound
>     +      // on the points in the final merged grid.  We need to temporarily
>     +      // set it to the number of points added to the merged grid so far.
>     +      points0->GetData()->SetNumberOfTuples(npoints0);
>           grid->GetBounds(tmpbounds);
>     +      points0->GetData()->SetNumberOfTuples(this->TotalNumberOfPoints);
>    
>           bounds[0] = ((tmpbounds[0] < bounds[0]) ? tmpbounds[0] : bounds[0]);
>           bounds[2] = ((tmpbounds[2] < bounds[2]) ? tmpbounds[2] : bounds[2]);
> 
>     Regards,
>     Takuya
>    
>     Takuya OSHIMA, Ph.D.
>     Faculty of Engineering, Niigata University
>     8050 Ikarashi-Ninocho, Nishi-ku, Niigata, 950-2181, JAPAN
>    
>     _______________________________________________
>     Powered by www.kitware.com
>    
>     Visit other Kitware open-source projects at http://www.kitware.com/
>     opensource/opensource.html
>    
>     Please keep messages on-topic and check the ParaView Wiki at: http://
>     paraview.org/Wiki/ParaView
>    
>     Follow this link to subscribe/unsubscribe:
>     http://www.paraview.org/mailman/listinfo/paraview
>