[Insight-developers] itkScalarImageKmeansImageFilter3DTest timeouts

[Bill Lorensen]

Luis,

Looks like my Borland continuous starting passing after your -kb fix.

Bill

On Sat, Aug 23, 2008 at 11:01 AM, Luis Ibanez <luis.ibanez at kitware.com> wrote:
>
> 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
>>>>>
>>>>
>>>
>>
>