[ImageJ-devel] Local Neighborhood stuff
Tobias Pietzsch
pietzsch at mpi-cbg.de
Mon Aug 20 07:42:32 CDT 2012
Hi Stephan,
I think, having the ConcurrencySafe interface is a reasonable
suggestion. I vote for adding the combined interfaces instead of
returning generic interface combinations because that would involve
changing code in lots of places and probably get us into trouble with
the non-Eclipse world...
For simplicity, maybe we should do it the other way around, that is,
have "ConcurrencyUnsafeRandomAccessible" and then have RandomAccessible
extend that (and ConcurrencySafe, but maybe that interface is not even
required).
This way we would have to change relatively little code.
If we want the fullest support for the concurrency-unsafe Accessibles,
there would still be a lot of code duplication, i.e., OutOfBounds and
Views duplicated for safe and unsafe variants (view on a safe Accessible
is itself safe). Therefore I would rather suggest that we make the
unsafe Accessibles second-class citizens for now. Only intented for
inner loops and such. The main point is to prevent people from
accidentally using non-safe methods on these inner Accessibles and that
would be achieved.
best regards,
Tobias
On 08/20/2012 12:56 PM, Stephan Saalfeld wrote:
> Hi Tobias and all,
>
> great---thanks for spending time on that.
>
> The most important design question in my opinion is what Tobias has now
> called the `Safe' vs. `UnSafe' concept. As far as I remember from
> previous discussions we do not have a final answer yet to that problem
> and I sucked in posting the discussion to the Wiki. So I suggest to
> discuss it here now it becomes relevant.
>
> The problem:
>
> Both, accessors (e.g. Cursor) and proxy types (e.g. NativeType) are
> stateful. How should they be used in concurrent (e.g. multi-threaded)
> code? So far, the contract in ImgLib2 is: one accessor should not be
> used concurrently, concurrent threads should each acquire a unique
> accessor which, if required, provides a unique proxy type. The inverse
> contract is that if you have an accessible (e.g. IterableInterval), then
> you can write concurrent code by requesting a unique accessor for each
> thread. This becomes problematic when accessibles are `nested', i.e.
> the proxy type is an accessible. The contract holds at all nested
> levels when using what Tobias has implemented as the `Safe' solution.
> It holds only at the top nesting level when using the `UnSafe' solution
> where the `inner' accessible uses one single accessor instance. Why
> then doing it? Because it is faster. Iterating a 4-neighborhood for
> each pixel in a 2d image would be slower when creating a new accessor at
> each pixel-location. Why is it problematic? Because methods working
> with an accessible as input can be applied to the inner accessibles,
> may be implemented concurrently (e.g. apply convolution to a
> neighborhood), and do not know at which `nesting' level they are called
> (it also sucks to require thinking about that).
>
> Nesting accessibles is clearly a good thing and basically the reason why
> ImgLib2 is designed as it is. For `small' accessibles, it is necessary
> to break the current contract that an accessible generates independent
> accessors, because they would be slow otherwise. So that contract is
> broken.
>
> My current idea to solve this issue at compile time is by introducing
> the empty interface ConcurrencySafe and require each accessible that
> generates independent accessors to implement this interface. Methods
> that depend on that must then require their input to implement this
> interface, e.g.
>
> <A extends RandomAccessible<T> & ConcurrencySafe>
> void convolve(A a, A b){ ... }
>
> Since it doesn't interfere with existing code, it would enable to slowly
> add this `security' constraint slowly over time while keeping things
> running.
>
> It also means that the safe and unsafe factories would return a generic
> interface combination and it can become a bit convoluted to keep that
> information for passing such an object into another method using the
> buggy Oracle compiler...
>
> An Oracle-friendly option would be to embed that interface into the
> interface hierarchy and create the full bunch of concurrency safe
> extensions of existing interfaces:
> ConcurrencySafeRandomAccessible extends RandomAccessible
> ConcurrencySafeIterableInterval extends IterableInterval ...
>
> Obviously, the JDK is not doing this and instead throws Exceptions for
> an enormous synchronization and testing overhead at runtime (compare
> Vector and ArrayList).
>
> What do you think?
>
> Best,
> Stephan
>
>
>
> On Fri, 2012-08-17 at 16:24 +0200, Tobias Pietzsch wrote:
>> Hi,
>>
>> the last two days, I finally took some time to take a deeper look at
>> the Local Neighborhoods. About a year ago, I discussed with Stephan
>> Saalfeld the idea that Neighborhood systems could just be nested
>> Accessibles. I did a lot of exploratory implementation and it all lead
>> naturally back to this idea. It just feels very "Imglib-like". I think
>> it's the way to go.
>>
>> I made a proof-of-concept implementation which I just pushed to branch
>> "tobias-neighborhood-experiments". After playing around a lot, I have
>> basically come up with the following design:
>>
>>
>> Neighborhood<T>
>> ===============
>> The interface Neighborhood<T> extends Localizable, IterableInterval<T>.
>> It is _not_ Positionable. It is simply at a fixed location.
>>
>>
>> Cursor/RandomAccess< Neighborhood<T> >
>> ========================================
>> To move a neighborhood around, we use standard accessor interfaces.
>> Assume you have a RandomAccess<Neighborhood<T>> a.
>> Using a.setPosition() you can position the center of the neighborhood.
>> Using a.get() you obtain a Neighborhood<T> (which you can then iterate).
>>
>> In many ways, the Neighborhood is like a NativeType. It is just a
>> reference into an underlying structure. If you have a Cursor<T> of
>> a NativeType, then the result T t = cursor.get() will be invalidated
>> when you advance the cursor. The same holds for Cursor<Neighborhood<T>>.
>> When you move the cursor, the neighborhood Neighborhood<T> n =
>> cursor.get() will be invalidated when you advance the cursor.
>>
>>
>> IterableInterval/RandomAccessible< Neighborhood<T> >
>> ====================================================
>> Of course, once you have the Accessors, it's easy to put the into
>> Accessibles and benefit from all the goodies that are in ImgLib already.
>> For example, if you have implemented a RandomAccess<Neighborhood<T>>
>> it is straightforward to wrap it into a RandomAccessible and use
>> Views.iterable() to get a Cursor over Neighborhood<T>.
>>
>> This results is pure syntactic sugar and lets you write sexy code like
>> this:
>> for ( Neighborhood<T> n : neighborhoods )
>> for ( T t : n )
>> ...
>>
>> Shape
>> =====
>> At the top level is the interface "Shape". This is basically a factory
>> for Accessibles on Neighborhoods. Every type of neighborhood should
>> provide such a factory. There are four methods. The first is
>>
>> public <T> IterableInterval<Neighborhood<T>>
>> neighborhoods( final RandomAccessibleInterval<T> source );
>>
>> This will give you an IteratableInterval over all neighborhoods in the
>> source image. Augmenting the above example, in actual code it is used
>> like this:
>> Img<FloatType> img;
>> long radius;
>> HyperSphereShape shape = new HyperSphereShape( radius );
>> for ( Neighborhood<FloatType> n : shape.neighborhoods( img ) )
>> for ( FloatType t : n )
>> ...
>>
>> The second method is
>>
>> public <T> RandomAccessibleInterval<Neighborhood<T>>
>> neighborhoodsRandomAccessible(
>> final RandomAccessibleInterval<T> source );
>>
>> which gives you a RandomAccessibleInterval over all neighborhoods.
>> Then there are "safe" variants of these two methods, which I will
>> discuss later because it goes a bit deeper into the details...
>>
>> Examples
>> ========
>> I have fully implemented RectangleShape which supports
>> (hyper-)rectangular neighborhoods. This is rather involved, because
>> it supports both neighborhoods that skip the center pixel and such
>> that don't; it has both an implementation of Cursor<Neighborhood<T>>
>> and RandomAccess<Neighborhood<T>> for optimal speed; and so on...
>>
>> There is an incomplete implementation of HyperSphereShape, which
>> despite being incomplete should be a better example to look at first.
>> Basically I just copied and pasted from HyperSphereCursor.
>> In this case, there is only a RandomAccess<Neighborhood<T>>. The
>> Cursor is simply build using Views.iterable().
>>
>> Unfortunately, the code is still largely undocumented. I put effort
>> into documenting the Shape interface, but that's it basically :(
>>
>> As an example for how to use Neighborhoods, please see
>> net.imglib2.algorithm.region.localneighborhood.MinFilterExample
>> in the imglib2-tests sub-project.
>> Actually, just let me paste a fragement here. This implements a
>> minimum filter using arbitrary neighborhood Shape:
>>
>> public static <T extends Type<T> & Comparable<T> > void
>> minFilter( final RandomAccessibleInterval<T> input,
>> final RandomAccessibleInterval<T> output,
>> final Shape shape )
>> {
>> final RandomAccess< T > out = output.randomAccess();
>> for (final Neighborhood<T> neighborhood : shape.neighborhoods(input))
>> {
>> out.setPosition( neighborhood );
>> final T o = out.get();
>> o.set( neighborhood.firstElement() );
>> for ( final T i : neighborhood )
>> if ( i.compareTo( o ) < 0 )
>> o.set( i );
>> }
>> }
>>
>> Beautiful, isn't it?
>>
>> Safe vs Unsafe Neighborhoods
>> ============================
>> About the "safe" variants of the methods in Shape. The above "unsafe"
>> variants behave as follows: A Neighborhood<T> that you obtained from the
>> returned accessible will re-use a single Cursor instance. That is:
>> Neighborhood<T> n = shape.neighborhoods( img ).firstElement();
>> Cursor<T> c1 = n.cursor();
>> Cursor<T> c2 = n.cursor();
>> Here, c1 and c2 will be the same object! This is necessary to make
>> the nested loops shown above really fast. Otherwise here,
>> for ( Neighborhood<T> n : neighborhoods )
>> for ( T t : n )
>> in every iteration of the outer loop, a new Cursor would be created for
>> the inner loop.
>> I decided to make the "unsafe" option the default, i.e., the methods are
>> called Shape.neighborhoods() and Shape.neighborhoodsSafe() instead of
>> Shape.neighborhoodsUnsafe() and Shape.neighborhoods(). I'm open to
>> change that, though.
>>
>> If you require a different behaviour, you can use the
>> Shape.neighborhoodsSafe and neighborhoodsRandomAccessibleSafe methods.
>> There are also other options which are described in the javadoc of the
>> Shape interface. Please have a look!
>>
>> Performance
>> ===========
>> It can be made quite fast, actually. I have implemented a find-local-
>> maxima benchmark (see LocalMaximaBenchmark) that compares several
>> implementations of (3x3x...x3) Neighborhood.
>>
>> To count local maxima in a 200x200x200 float image, I get
>> 683 ms using RectangleShape vs
>> 877 ms using the old LocalNeighborhoodCursor
>>
>>
>>
>> As you might have noticed, I have completely neclected the copyOn() and
>> updateSource() methods we discussed before. I don't really see the need
>> for them in the above design.
>>
>> Ok, I hope you will have a look at the code
>> (branch "tobias-neighborhood-experiments") and tell me what you think.
>>
>> best regards,
>> Tobias
>>
>>
>> On 07/27/2012 05:35 PM, Jean-Yves Tinevez wrote:
>>>
>>> Hi all
>>>
>>> I pushed some changes to the test branch: I removed the realpositionable
>>> stuff, and tried to draft the mother interface from our discussions.
>>>
>>> But I got stuck at the copyOn method. If I try to make it as generic as
>>> I can (copy on a different RandomAccessible type and on a different
>>> type), concrete implementations that are more specific (like the
>>> buffered rectangle) fail on bad type bounds. I could use some help there.
>>>
>>> Best
>>> jy
>>>
>>>
>>
>>
>> _______________________________________________
>> ImageJ-devel mailing list
>> ImageJ-devel at imagej.net
>> http://imagej.net/mailman/listinfo/imagej-devel
>
More information about the ImageJ-devel
mailing list