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

Tobias Pietzsch pietzsch at mpi-cbg.de
Thu Oct 30 12:29:32 CDT 2014

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,

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 455 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://imagej.net/pipermail/imagej-devel/attachments/20141030/b7ad1a21/attachment.pgp>

More information about the ImageJ-devel mailing list