[ImageJ-devel] [fiji-devel] Lock-free bit fields, was Re: What's left to do for ImgLib2

[Stephan Saalfeld]

Hi Tobias,

I agree that the constraint is easier if the fraction reduces to an
integer.  However, it's not exactly the same for fraction=1 or
fraction>1 either.  It would be great if we could identify a common
scheme that covers all cases without much interference.

Is may be a disk-based, memory cached CellImg the same thing as a
fractioned NativeImg?  Writing into different pixels in the same cell
may lead to confusing results when written to disk.

What about a method in RandomAccess that returns an `unsafe' interval
for its location?  Generally, that would be (1^n), in case of fraction
types, it would be the box surrounding all pixels served by the same
primitive type (which is horrible at the end of a row or cell-row where
pixels in the next row are affected), and in case of cached cells it
could be the cell.

With a method of this flavor, we can make educated decisions on
construction time of the multi-threaded code that, internally, would not
synchronize, i.e. be fast.

Best,
Stephan




On Thu, 2014-10-30 at 18:29 +0100, Tobias Pietzsch wrote:
> Hi Stephan,
> 
> I think it would be nice to have getLock() but I also think it will be rarely needed in practice.
> 
> We must be careful not to conflate two problems here:
> 
> The first one is that writes to e.g. ComplexType are not atomic and therefore strange things may happen if two ComplexTypes are used that actually refer to the same ComplexType pixel value in the image.
> As Albert suggested, algorithms that need this feature need to take special care to synchronize access.
> However, for many parallelizable algorithms this is not actually a problem. In most image-to-image operations (e.g. FFT, convolution, etc…) every output pixel is written only once by only one thread. Threads maybe read the same input pixels, but reading is fine.
> The getLock() method would be a welcome addition for those algorithms that do not follow this pattern and need to synchronize.
> 
> The second problem is different. For BitType, writes to BitType pixels at different locations in the image may influence each other. And this should be avoided by default in my opinion.
> 
> I think: “You are safe as long as multiple threads write to different pixels” is a good contract to have.
> Diverging from that with BitType, Unsigned12BitType, etc would add overhead for many algorithms that is in most cases not required (e.g. for FloatType, ComplexDoubleType, etc. the synchronization overhead would be wasted).
> 
> best regards,
> Tobias
> 
> 
> 
> On 30 Oct 2014, at 16:18, Stephan Saalfeld <saalfelds at janelia.hhmi.org> wrote:
> 
> > Thanks for the articles!
> > 
> > I have more comments on the matter.  In fact, all types have the same
> > problem.  Even for a non-native ComplexType read and write would not be
> > atomic and thus not thread-safe.  The problem is that, for non-native
> > types, it is sufficient for multi-threaded code to synchronize on the
> > type instance itself.  For native types (e.g. ComplexDoubleType) and for
> > other proxy mechanisms such as Composites or ReadWriteConverters, this
> > doesn't work.  How about a getLock() (or getMonitor()) method as part of
> > Type whose purpose is to return a lock that enables synchronization on
> > that particular's type content.  Should that lock be constant for a
> > type's lifetime?  Proxy types for which access is atomic could return
> > themselves, just as Types that actually contain their content.
> > 
> > I like Tobias' proposal with a Hash of locks for NativeTypes, something
> > similar is necessary for other writable proxies.
> > 
> > Best,
> > Stephan
> > 
> > 
> > 
> > On Thu, 2014-10-30 at 14:51 +0100, Adrian Daerr wrote:
> >> Hi,
> >> 
> >>>> By lock-free I mean setting the value and then checking whether the
> >>>> value is actually what was expected (and if not, retry).
> >>> 
> >>> A naïve implementation of this technique could easily result in a very
> >>> nasty ping-pong effect: if one thread tries to clear a bit and the next
> >>> thread tries to set it, it is very to run into a trap when not leaving a
> >>> way for one thread to win.
> >>> 
> >>> The safest way to resolve this issue is to reinstate the lock-on-write
> >>> method that was in place earlier
> >> [..]
> >>> 
> >>> An alternative might be to give up lock-freedom in favor of wait-freedom
> >>> [*2*]. In this regard, a more performant version might be
> >> [..]
> >>> to use Optimistic Concurrency Control [*3*]:
> >> 
> >>> 	final long original = dataAccess.getValue(i1);
> >>> 	if ( value ) {
> >>> 		final long newValue = original | (1l << shift);
> >>> 		dataAccess.setValue(i1, newValue);
> >>> 		if ( newValue != dataAccess.getValue( i1 ) ) {
> >>> 			synchronized (dataAccess) {
> >>> 				dataAccess.setValue( i1, dataAccess.getValue(i1) | (1l << shift) );
> >>> 			}
> >>> 		}
> >>> 	}
> >> [snip]
> >> 
> >> Hum, I do not if this is really a comparable situation, but it looks a 
> >> lot like the double-checked locking (DCL) idiom, which is broken [1].
> >> 
> >> FWIW,
> >> cheers and good luck,
> >> Adrian
> >> 
> >> 
> >> [1]
> >> TL;DR : You cannot have as-if-serial semantics across threads unless you 
> >> use synchronized.
> >> 
> >> "Double-checked locking: Clever, but broken
> >> Do you know what synchronized really means?" By Brian Goetz
> >> http://www.javaworld.com/article/2074979/java-concurrency/double-checked-locking--clever--but-broken.html
> >> 
> >> and its follow-up article
> >> 
> >> "Can double-checked locking be fixed?
> >> No matter how you rig it, double-checked locking still fails" (also by 
> >> Brian Goetz)
> >> http://www.javaworld.com/article/2075306/java-concurrency/can-double-checked-locking-be-fixed-.html
> > 
>