[Insight-developers] itkScalarImageKmeansImageFilter3DTest timeouts

[Luis Ibanez]

Hi Hans, Bill,


           Some more findings on this topic.


Further profiling revealed that by replacing the QuickSelect()
method in the itkKdTreeGenerator.txx with the NthElement() method,
the performance of building the tree for a set of points improved
by about two orders of magnitude.

Here are the numbers (time units are seconds):


    Number        Time With       Time With
    of Points     QuickSelect     NthElement

     10^3          0.01             0.00 (too small for "time")
     40^3          3.03             0.13
     60^3         33.69             0.56
     70^3        103.00             1.01


Based on this finding,

the change has been committed to the itkKdTreeGenerator.txx
http://www.itk.org/cgi-bin/viewcvs.cgi/Code/Numerics/Statistics/itkKdTreeGenerator.txx?root=Insight&r1=1.21&r2=1.22&sortby=date

and a note has been added to bug entry 7481.
http://public.kitware.com/Bug/view.php?id=7481

The bad news is that this still doesn't reduce the computation
time of the ScalarKMeansImageFilter.


By now, it seems safe to conclude that:


    a) QuickSelect in StatisticsAlgorithms has a bug
       (at least a performance one)


    b) The ScalarKMeansImageFilter has a performance
       bug as well.



I'm now profiling the ScalarKMeans filter with gprof.
The main suspect is still an unusually high rank for
SmartPointer operations....



     Luis


----------------------
Luis Ibanez wrote:
> 
> Hi Bill, Hans,
> 
> 
> I'm looking at this problem,
> and here is what I have found so far:
> 
> 
> A) The code is not going into an infinite loop,
>    but it is certainly requiring a *very long* time to run.
> 
> 
>      One image of   10 x 10 x 10  takes   0.05  seconds
>      One image of   40 x 40 x 40  takes   4.37  seconds
>      One image of   60 x 60 x 60  takes  38.05  seconds
>      One image of   70 x 70 x 70  takes 115.44  seconds
> 
> 
>    As you can see the process is of order larger than O(n3).
> 
> 
> B) When going back to the versions of
> 
>         itkStatisticsAlgorithm.h     -r 1.9
>         itkStatisticsAlgorithm.txx   -r 1.19
> 
>    The test runs a lot faster but the output of the KdTree
>    generator is not correct. (e.g. the points are not in the
>    correct bins).  :-/
> 
>    The KMeans that are reported seem to be numerically reasonable,
>    but that seems to be rather a coincidence.
> 
>    Going back to these versions doesn't seem to be an option,
>    given that the computation is not correct.
> 
> 
> 
> C) I'm now using gprof to trace the functions that are taking
>    most of the time. It may still be that we are making many
>    unnecessary calls...
> 
>    I'm also trying to separate whether the problem is originated
>    in the ScalarImageToListAdaptor or in the KdTree itself.
>    Initial runs of gprof on the KMeans image filter reports a high
>    usage of SmartPointers, which in general is not a good sign...
> 
> 
> 
>      Luis
> 
> 
> --------------------
> Bill Lorensen wrote:
> 
>> Folks,
>>
>> The subject test has been timing out since it was checked in. This is
>> a known bug. Unfortunately, this failing test causes cdash e-mails to
>> be sent every day and for every checkin. I'm concerned that all of
>> these e-mails and test failures on the dashboard will hide new
>> problems. I have modified the CMakeLists.txt file to only report this
>> timeout on one dashboard: dash16.kitware. This way, the error will not
>> be forgotten (or maybe it already has been) and the excess e-mails
>> will be prevented.
>>
>> Bill
>>
>