[Insight-developers] itkScalarImageKmeansImageFilter3DTest timeouts

[Luis Ibanez]

Hans, Bill,


More on this issue.

After tracking the calls with gprof, it turned out that the KmeansImage
filter uses the WeightedKdTreeGenerator, and that class was still using
the performance-wise-buggy QuicSelect() algorithm.

Replacing QuickSelect() with NthElement()
http://www.itk.org/cgi-bin/viewcvs.cgi/Code/Numerics/Statistics/itkWeightedCentroidKdTreeGenerator.txx?root=Insight&r1=1.9&r2=1.10&sortby=date

restored the performance of the ScalarKmeansImageFilter.

The test is now passing in 39 seconds on a Debian Linux,
Xeon 2.6Gh dual processor machine (zion).

The test has now been restored for all platforms.
http://www.itk.org/cgi-bin/viewcvs.cgi/Testing/Code/Algorithms/CMakeLists.txt?root=Insight&r1=1.266&r2=1.267&sortby=date


We should see tomorrow the effect on other builds,
and then we may be able to close this bug.


A new bug has been reported for the QuickSelect performance issue:
http://public.kitware.com/Bug/view.php?id=7528



Hans,

    thanks a lot for adding this test,
    and tracking the problem.



    Luis



---------------------
Luis Ibanez wrote:
> 
> 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
>>>
>>
>