[Insight-developers] itkScalarImageKmeansImageFilter3DTest timeouts

[Luis Ibanez]

An extra bit,

This test showed up failing this morning on Windows platforms:
http://www.cdash.org/CDash/testSummary.php?project=2&name=itkScalarImageKmeansImageFilter3DTest&date=20080823

It turned out that the nii.gz files were added without the "-kb" binary
CVS flag. This has now been corrected. The test should now pass in the
continuous builds and they should be green on tomorrow's nightlies.

Of course,
we'll have to wait for tomorrow's dashboard to be sure...


    Luis


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