Hi everyone, Thanks very much for the robust discussion!
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: https://github.com/imagej/imagej-ops/commit/25c68c62a69a0fa82fc41908c537615b6b964215 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. I think that will get us unstuck for now, so we can keep moving forward with component releases. Cheers, Curtis On Thu, Oct 30, 2014 at 1:44 PM, Albert Cardona <cardo...@janelia.hhmi.org> wrote: > Hi Tobias, > > 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? > > 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. > > Albert > > > > > On 10/30/2014 02:39 PM, Tobias Pietzsch wrote: > >> Hi Stephan, >> >> 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? >> 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. >> I’m happy to discuss ideas in this direction, but I don’t think it is a >> viable short-term solution. >> >> For practical reasons, I would stick with “You are safe as long as >> multiple threads write to different pixels”. >> 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. >> >> best regards, >> Tobias >> >> On 30 Oct 2014, at 18:57, Stephan Saalfeld <saalfe...@janelia.hhmi.org> >> wrote: >> >> 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 <saalfe...@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 >>>>>> >>>>> >>>>> >>>> >>> >> > -- > -- > Please avoid top-posting, and please make sure to reply-to-all! > > Mailing list web interface: http://groups.google.com/group/fiji-devel > > --- You received this message because you are subscribed to the Google > Groups "Fiji-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to fiji-devel+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. >
_______________________________________________ ImageJ-devel mailing list ImageJ-devel@imagej.net http://imagej.net/mailman/listinfo/imagej-devel
