[Insight-developers] Iterators, SmartPointers, B-Splines

[Miller, James V (Research)]

Bill and I were looking at the performance of the B-Spline registration code
yesterday. Running through Quantify, we noticed that most of the time was
spent in TransformPoint() with a large percentage of that time spent in
mutex operations.
 
The BSpline transform TransformPoint() method creates N iterators to walk
the N B-Spline coefficient images. Only the region of the coefficient images
that influence the position of the particular point is traversed.  This is a
nice reuse of the Image class and the ImageRegionIterators.
 
But every time TransformPoint is called, N iterators are created, an image
is passed to each iterator, and iterator caches the image pointer in a
SmartPointer.  Storing the image pointer in the SmartPointer causes a mutex
to lock, the reference count on the image to be incremented, and the mutex
to be unlocked.  On exiting TransformPoint, the mutex is again locked, the
reference count of the image to be decremented, and the mutex again
unlocked. The B-Spline transform code cannot cache the iterators as ivars,
because multiple threads may try to call TransformPoint on the same B-spline
transform.  ResampleImageFilter is one example of this.
 
I propose that we consider changing the Iterators so that the image pointer
is not cached in a SmartPointer.  Iterators are typically "short lived"
objects, created for the specific purposes of walking a particular image.
We can argue that the image is probably going to hang around for the length
of time that the iterator is used.   For instance, in the GenerateData()
method of a filter, we know the input and output images should not disappear
during the execution of the GenerateData() method.  So iterators
created/destructed in GenerateData() do not need to hold onto a separate
SmartPointer to the image.
 
Having an iterator hold a SmartPointer to the image is not really as safe as
it sounds.  Most iterators also cache pointers to the buffer.  However,
there is nothing to stop someone from swapping the PixelContainer on an
image while an iterator is traversing the image. There is also nothing to
stop someone from call Initialize() on an image while an iterator is
traversing the image. Either of these operations would invalidate the
iterator.  Most of the containers/iterators in STL have similar
restrictions.  For instance, an iterator to an std::vector "may" become
invalid if you call push_back() while walking the iterator. (push_back may
cause the vector to resize).
 
I did some quick timings on the B-Spline code and DeformableRegistration6
runs 25% faster if iterators do not keep SmartPointers.
 
Here are some options:

1.	Replace the use of SmartPointers in the Iterators with raw pointers.
2.	Replace the use of SmartPointers in the Iterators with WeakPointers.
WeakPointer is the pointer class used to break the reference cycle between
DataObject and ProcessObject.  It encapsulates a raw pointer like
SmartPointer does but does not call Register()/UnRegister(). The benefit
WeakPointers have over raw pointers is that they draw explicit attention to
the fact they are not SmartPointers.  They also set the pointer to zero
before destructing (helps with some minor memory bugs). Also, since
WeakPointers are stack objects similar to SmartPointers, developers will not
try to "delete" a pointer they were only caching. When a class has an ivar
that caches a raw pointer, coders are tempted to call "delete" on that
memory at destructor time.
3.	Replace the mutex in SmartPointers with lock free constructs.  Intel
processors have a few atomic instructions to test and set variables.  I
imagine most modern processors have similar instructions.  We could create
an abstraction and implement a lock free reference count mechanism for each
processor/OS combination. This would still allow iterators to have a
SmartPointer to the image they reference without all the overhead of a
mutex.  However, even a lock free reference count would be slower than using
raw pointers or WeakPointers.
4.	Add an API to the iterators so that they can be constructed with AND
without SmartPointer semantics.  Where iterators are used in inner loops, we
can replace the standard iterator calls with calls that do not use
SmartPointers.

I know some of the ImageFunctions use iterators and neighborhood iterators
internally.  Those ImageFunctions would also benefit from removing the
SmartPointers from the Iterator code.  We may also want to look at the use
of the ImageFunctions in general to see whether any of those are being
created in algorithm inner loops (ImageFunctions also cache a pointer to an
image in a SmartPointer).
 
Is anyone aware of places in ITK where we an object or filter caches
Iterators.  We would have to be careful in those cases to make sure the
Image still exists when the cached Iterators are used.
 
Comments?
 
 

Jim Miller 
_____________________________________
Visualization & Computer Vision
GE Research
Bldg. KW, Room C218B
P.O. Box 8, Schenectady NY 12301

millerjv at research.ge.com <mailto:millerjv at research.ge.com> 

james.miller at research.ge.com
(518) 387-4005, Dial Comm: 8*833-4005, 
Cell: (518) 505-7065, Fax: (518) 387-6981 

 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.itk.org/mailman/private/insight-developers/attachments/20041027/19d9ec68/attachment.htm