<div dir="ltr"><div class="gmail_extra">Hi everyone,</div><div class="gmail_extra"><br></div><div class="gmail_extra">Thanks very much for the robust discussion!</div><div class="gmail_extra"><br></div><div class="gmail_extra">I don't have a strong opinion on the BitType concurrency issue, but just wanted to let you know how I am temporarily resolving this in the ImageJ OPS project:</div><div class="gmail_extra"><br></div><div class="gmail_extra"><a href="https://github.com/imagej/imagej-ops/commit/25c68c62a69a0fa82fc41908c537615b6b964215">https://github.com/imagej/imagej-ops/commit/25c68c62a69a0fa82fc41908c537615b6b964215</a><br></div><div class="gmail_extra"><br></div><div class="gmail_extra">This hardcodes the ApplyConstantThreshold op to use the single-threaded implementation rather than the faster multi-threaded one, until such time as the multithreading of BitType access is resolved.</div><div class="gmail_extra"><br></div><div class="gmail_extra">I think that will get us unstuck for now, so we can keep moving forward with component releases.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Cheers,</div><div class="gmail_extra">Curtis</div><div class="gmail_extra"><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Oct 30, 2014 at 1:44 PM, Albert Cardona <span dir="ltr"><<a href="mailto:cardonaa@janelia.hhmi.org" target="_blank">cardonaa@janelia.hhmi.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Hi Tobias,<br>
<br>
woudn't the easiest be to rename the current BitType instances as Unsynchronized+name, and then the actual class extend the corresponding unsynchronized class, with one method overriden to synchronize access to the pixels?<br>
<br>
This way one gets both: the default is safe (synchronized), and if one knows what one is doing, one can get the Unsynchronized* version to avoid the cost.<span class=""><font color="#888888"><br>
<br>
Albert</font></span><div class=""><div class="h5"><br>
<br>
<br>
<br>
On 10/30/2014 02:39 PM, Tobias Pietzsch wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Hi Stephan,<br>
<br>
Getting the ‘unsafe’ interval for a specific location is certainly possible. But how would that be effectively used in an algorithm if the interval changes from location to location?<br>
Alternatively, RandomAccessibles and IterableIntervals could offer methods to chop them up into ‘safe’ parts for multithreading. However there are many different ’safe' subdivision and it depends on the algorithm which one is preferrable. Also these subdivisions (as well as the ‘unsafe’ interval) would need to be propagated correctly through Views and RealViews which might get rather involved.<br>
I’m happy to discuss ideas in this direction, but I don’t think it is a viable short-term solution.<br>
<br>
For practical reasons, I would stick with “You are safe as long as multiple threads write to different pixels”.<br>
This is the contract that we have been implicitly following all along. A lot of code relies on it. Even if we come up with a nice alternative, we do not have the man-power to fix all code that relies on the old contract and that we would break along the way. Therefore my preferred short-term solution is to synchronize( dataAccess ){…} the fractioned-type writes, as Johannes suggested.<br>
<br>
best regards,<br>
Tobias<br>
<br>
On 30 Oct 2014, at 18:57, Stephan Saalfeld <<a href="mailto:saalfelds@janelia.hhmi.org" target="_blank">saalfelds@janelia.hhmi.org</a>> wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Hi Tobias,<br>
<br>
I agree that the constraint is easier if the fraction reduces to an<br>
integer. However, it's not exactly the same for fraction=1 or<br>
fraction>1 either. It would be great if we could identify a common<br>
scheme that covers all cases without much interference.<br>
<br>
Is may be a disk-based, memory cached CellImg the same thing as a<br>
fractioned NativeImg? Writing into different pixels in the same cell<br>
may lead to confusing results when written to disk.<br>
<br>
What about a method in RandomAccess that returns an `unsafe' interval<br>
for its location? Generally, that would be (1^n), in case of fraction<br>
types, it would be the box surrounding all pixels served by the same<br>
primitive type (which is horrible at the end of a row or cell-row where<br>
pixels in the next row are affected), and in case of cached cells it<br>
could be the cell.<br>
<br>
With a method of this flavor, we can make educated decisions on<br>
construction time of the multi-threaded code that, internally, would not<br>
synchronize, i.e. be fast.<br>
<br>
Best,<br>
Stephan<br>
<br>
<br>
<br>
<br>
On Thu, 2014-10-30 at 18:29 +0100, Tobias Pietzsch wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Hi Stephan,<br>
<br>
I think it would be nice to have getLock() but I also think it will be rarely needed in practice.<br>
<br>
We must be careful not to conflate two problems here:<br>
<br>
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.<br>
As Albert suggested, algorithms that need this feature need to take special care to synchronize access.<br>
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.<br>
The getLock() method would be a welcome addition for those algorithms that do not follow this pattern and need to synchronize.<br>
<br>
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.<br>
<br>
I think: “You are safe as long as multiple threads write to different pixels” is a good contract to have.<br>
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).<br>
<br>
best regards,<br>
Tobias<br>
<br>
<br>
<br>
On 30 Oct 2014, at 16:18, Stephan Saalfeld <<a href="mailto:saalfelds@janelia.hhmi.org" target="_blank">saalfelds@janelia.hhmi.org</a>> wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Thanks for the articles!<br>
<br>
I have more comments on the matter. In fact, all types have the same<br>
problem. Even for a non-native ComplexType read and write would not be<br>
atomic and thus not thread-safe. The problem is that, for non-native<br>
types, it is sufficient for multi-threaded code to synchronize on the<br>
type instance itself. For native types (e.g. ComplexDoubleType) and for<br>
other proxy mechanisms such as Composites or ReadWriteConverters, this<br>
doesn't work. How about a getLock() (or getMonitor()) method as part of<br>
Type whose purpose is to return a lock that enables synchronization on<br>
that particular's type content. Should that lock be constant for a<br>
type's lifetime? Proxy types for which access is atomic could return<br>
themselves, just as Types that actually contain their content.<br>
<br>
I like Tobias' proposal with a Hash of locks for NativeTypes, something<br>
similar is necessary for other writable proxies.<br>
<br>
Best,<br>
Stephan<br>
<br>
<br>
<br>
On Thu, 2014-10-30 at 14:51 +0100, Adrian Daerr wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Hi,<br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
By lock-free I mean setting the value and then checking whether the<br>
value is actually what was expected (and if not, retry).<br>
</blockquote>
<br>
A naïve implementation of this technique could easily result in a very<br>
nasty ping-pong effect: if one thread tries to clear a bit and the next<br>
thread tries to set it, it is very to run into a trap when not leaving a<br>
way for one thread to win.<br>
<br>
The safest way to resolve this issue is to reinstate the lock-on-write<br>
method that was in place earlier<br>
</blockquote>
[..]<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<br>
An alternative might be to give up lock-freedom in favor of wait-freedom<br>
[*2*]. In this regard, a more performant version might be<br>
</blockquote>
[..]<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
to use Optimistic Concurrency Control [*3*]:<br>
</blockquote>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
final long original = dataAccess.getValue(i1);<br>
if ( value ) {<br>
final long newValue = original | (1l << shift);<br>
dataAccess.setValue(i1, newValue);<br>
if ( newValue != dataAccess.getValue( i1 ) ) {<br>
synchronized (dataAccess) {<br>
dataAccess.setValue( i1, dataAccess.getValue(i1) | (1l << shift) );<br>
}<br>
}<br>
}<br>
</blockquote>
[snip]<br>
<br>
Hum, I do not if this is really a comparable situation, but it looks a<br>
lot like the double-checked locking (DCL) idiom, which is broken [1].<br>
<br>
FWIW,<br>
cheers and good luck,<br>
Adrian<br>
<br>
<br>
[1]<br>
TL;DR : You cannot have as-if-serial semantics across threads unless you<br>
use synchronized.<br>
<br>
"Double-checked locking: Clever, but broken<br>
Do you know what synchronized really means?" By Brian Goetz<br>
<a href="http://www.javaworld.com/article/2074979/java-concurrency/double-checked-locking--clever--but-broken.html" target="_blank">http://www.javaworld.com/<u></u>article/2074979/java-<u></u>concurrency/double-checked-<u></u>locking--clever--but-broken.<u></u>html</a><br>
<br>
and its follow-up article<br>
<br>
"Can double-checked locking be fixed?<br>
No matter how you rig it, double-checked locking still fails" (also by<br>
Brian Goetz)<br>
<a href="http://www.javaworld.com/article/2075306/java-concurrency/can-double-checked-locking-be-fixed-.html" target="_blank">http://www.javaworld.com/<u></u>article/2075306/java-<u></u>concurrency/can-double-<u></u>checked-locking-be-fixed-.html</a><br>
</blockquote>
<br>
</blockquote>
<br>
</blockquote>
<br>
</blockquote>
<br>
</blockquote>
<br></div></div><div class=""><div class="h5">
-- <br>
-- <br>
Please avoid top-posting, and please make sure to reply-to-all!<br>
<br>
Mailing list web interface: <a href="http://groups.google.com/group/fiji-devel" target="_blank">http://groups.google.com/<u></u>group/fiji-devel</a><br>
<br>
--- You received this message because you are subscribed to the Google Groups "Fiji-devel" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:fiji-devel%2Bunsubscribe@googlegroups.com" target="_blank">fiji-devel+unsubscribe@<u></u>googlegroups.com</a>.<br>
For more options, visit <a href="https://groups.google.com/d/optout" target="_blank">https://groups.google.com/d/<u></u>optout</a>.<br>
</div></div></blockquote></div><br></div></div>