[ImageJ-devel] Local Neighborhood stuff
Stephan Saalfeld
saalfeld at mpi-cbg.de
Mon Aug 20 08:00:34 CDT 2012
Good point. May be we can come up with a shorter phrase than
ConcurrencyUnsafe :) (Unsafe alone doesn't fit really). While I agree
that making the combo-interfaces is probably a good idea to prevent
Johannes from killing us, I would still like to have the Unsafe
interface something standalone such that it remains possible to
implement methods for the combination <A & Unsafe> instead of the
combined interface.
Cheers,
Stephan
On Mon, 2012-08-20 at 14:42 +0200, Tobias Pietzsch wrote:
> 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