[Insight-developers] iterator without index efficiency problem

[Luis Ibanez]

Hi Gaetan,


We are aware of differences in performance between the
iterators with/without index; and they may may well be
due to the task that you are performing.



For example,


1) If you are just visiting the pixels and invoking Set/Get
    operations. Then the iterators without index should be
    faster.


2) If you are visiting the pixels and invoking GetIndex(),
    then the iterator with index should be faster.




This is simply due to the fact that the iterators with index
keep updating an internal index at each increment/decrement of
the iterator. Therefore, when you ask for the index, it is
already computed (and cached). The price of course is a bit of
extra computation at each increment.


The iterators without index, on the other hand, *do not keep*
an updated index. So, when you call GetIndex() on them, they
are forced to perform a full computation of the index based
on the current offset from the beginning of the memory buffer.




There is a continuous test for iterator performance,
that you may want to try.



It is:


          Insight/
              Testing/
                  Code/
                    Common/
                      itkIteratorTests.cxx



Last night output of this test can be seen in
the following link to the Dashboard:


http://www.itk.org/Testing/Dashboard/20060220-0100-Nightly/TestDetail/__Testing_Code_Common_itkIteratorTests.html




For example, in a Debian Linux machine with gcc 2.95:

Test output

Creating an image
Raw pointer using memset
	Time   = 0.02
	Pixels = 6859000
Raw pointer as a 1D array
	Time   = 0
	Pixels = 6859000
Raw pointer in 3 nested loops
	Time   = 0.01
	Pixels = 6859000
ImageRegionIterator
	Time   = 0.04
	Pixels = 6859000
ImageRegionIteratorWithIndex
	Time   = 0.07
	Pixels = 6859000
Iterator tests passed



Note that one of the interesting things we found
when running those benchmark experiments, is that
the *order* of the test matters. This is probably
due to a memory caching effect. So, please, when
you evaluate performance, make sure that you run
at least two rounds (or at least run the test in
both orders). One with the iterator with index first,
and the iterator without index second; and the other
test with the iterator without index first, and the
iterator with index on second.



This may or may not explain the differences in
performance that you are reporting, so please
post the source code of your test so we can
replicate your experiment.



BTW.

       This will make an excellent paper
       for the Insight Journal !


       Iterators are such a fundamental piece of ITK,
       that any effort invested in improving their
       performance will immediately reflect on the
       performance of the entire toolkit.





    Regards,



        Luis




----------------------
Gaetan Lehmann wrote:
> 
> 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
>>
> 
> 
>