[Insight-developers] iterator without index efficiency problem

[Luis Ibanez]

Hi Gaetan,

Thanks for running again the tests and reporting your findings.


Your guess about the Neighborhood iterator being slow in thin regions
is correct. This is actually due to the fact that it will spend most
of the computation time evaluating the boundaries.  Neighborhood
iterators do a fast walk on the region that is completly contained
in the image (without boundary problems), and they do a slower walk
on the borderline regions of the image (where the boundary has to
be checked pixel by pixel).


I'm wondering if the ImageRegionIterator (without index) could be
accelerated by maintaining internally only one of the directions
of the index (the one that is the thinest).  Such change would
probably justify to introduce yet another Iterator into ITK, for
dealing with this particular case. Which is fine. From the initial
design of iterators, the expectation was to have many different
types of iterators that will respond to very specific conditions
of usage.



    Luis



----------------------
Gaetan Lehmann wrote:
> 
> I've just re ran the timing test, but I changed the dimension instead 
> of  the number of threads
> To reply to Luis, the tests are run 50 fold, so I think there shouldn't 
> be  any cache problem.
> 
> [glehmann at topaze build]$ ./perf ../images/ESCells.img
> #dim    sum     accSum  mean    accMean
> 0       0.0363  0.014   0.036   0.0139
> 1       0.0567  0.447   0.0558  0.447
> 2       0.083   0.465   0.0837  0.465
> 
> sum and mean use iterator with index, while accSum and accMean use and  
> iterator without index.
> The size of the image is [371, 371, 34], and thus, timing perf of axe 0  
> and 1 can be compared.
> On dimension 2, the image have about 10 fold less pixels, but get worth  
> performance than for the dimension 2 !
> 
> There is surely something to do to optimize the iterators when the  
> requested region is thin. Some filters may waste lots of time in the 
> case  of thin region. I haven't tested it, but perhap's it's also the 
> case for  faces and neighborhood iterator ?
> Or for 3D filters applied to a 3D images which have only one pixel on 1  
> dimension, like the output of the AccumulateImageFilter ?
> 
> Gaetan
> 
> On Mon, 20 Feb 2006 16:42:26 +0100, Miller, James V (GE, Research)  
> <millerjv at crd.ge.com> wrote:
> 
>> Gaetan,
>>
>> I was just looking through the projection code. It looks like the 
>> code  is iterating
>> over regions which are one pixel wide/tall/deep depending on the  
>> projection direction.
>> Do you have a sense for whether the timings of the iterators are  
>> different for all the projection directions?
>>
>> The overhead in the ImageRegionIterator is in the wrapping from row to
>> row in the region.  For long rows, the overhead is essentially  
>> amortorized,
>> adding little overhead to each pixel. But if the region is only walking a
>> row of length 1, the overhead of row wrapping is applied to very pixel.
>>
>> Jim
>>
>>
>>
>> -----Original Message-----
>> From: insight-developers-bounces+millerjv=crd.ge.com at itk.org
>> [mailto:insight-developers-bounces+millerjv=crd.ge.com at itk.org]On Behalf
>> Of Gaetan Lehmann
>> Sent: Monday, February 20, 2006 10:22 AM
>> To: Miller, James V (GE, Research); insight-developers at itk.org
>> Subject: Re: [Insight-developers] iterator without index efficiency
>> problem
>>
>>
>>
>> I forgot to say that the timing test should be run with the command line
>>
>> ./perf ../images/ESCells.img
>>
>> and that the result were very similar before switching to iterator with
>> index.
>>
>> Gaetan
>>
>> On Mon, 20 Feb 2006 15:16:07 +0100, Miller, James V (GE, Research)
>> <millerjv at crd.ge.com> wrote:
>>
>>> Gaetan,
>>>
>>> Where are your timing comparisons between the iterator types?
>>>
>>> We have studied the performance of the iterators several times.  The  
>>> last
>>> in depth study was a several years ago.  Maybe something has changed.
>>>
>>> In previous studies, we ran both sets of iterators over a common task.
>>> While the program did report a difference in iterator timings, if we
>>> switched which iterator performed the task first, the timings would
>>> flip, leading to a different conclusion.
>>>
>>> To accumulate over different dimensions, you might want to consider the
>>> ImageLinearConstIteratorWithIndex.  Depending on how you are  
>>> accumulating
>>> the information along a direction, this iterator may be more effecient
>>> than
>>> a ImageRegionIterator or a ImageRegionIteratorWithIndex.
>>>
>>> I'll out together a test on the iterator performance so that we can
>>> benchmark the iterators.
>>>
>>> Jim
>>>
>>> -----Original Message-----
>>> From: insight-developers-bounces+millerjv=crd.ge.com at itk.org
>>> [mailto:insight-developers-bounces+millerjv=crd.ge.com at itk.org]On Behalf
>>> Of Gaetan Lehmann
>>> Sent: Monday, February 20, 2006 7:57 AM
>>> To: insight-developers at itk.org
>>> Subject: [Insight-developers] iterator without index efficiency problem
>>>
>>>
>>>
>>> Hi,
>>>
>>> I have noted a huge difference fo efficiency between the iterator 
>>> with  or
>>> without index: the iterator with index is more efficient than the one
>>> without index.
>>> Is it a known problem ?
>>> I'm using ITK2.4.1. Is is still valid in ITK cvs ? If yes, it should be
>>> fixed before the 2.6 release.
>>> I have noticed that while working of projections. Timing test can be ran
>>> to reproduce that.
>>> http://insight-journal.org/view_reviews.php?back=index.php&pubid=71
>>>
>>> Reagards,
>>>
>>> Gaetan
>>>
>>
>>
>>
> 
> 
>