Re: What's left to do for ImgLib2

classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: What's left to do for ImgLib2

Tobias Pietzsch
Ok, just looking at the code of ApplyManualThresholdTest, I have a hunch of whats going wrong.
The test uses
final Img<BitType> out = bitmap();

I bet that for the new BitType from the Fractions branch nobody considered the possibility that two cursors might simultaneously write to bits of the same underlying long value.

One solution would be to use locks to synchronize all accesses to the underlying long[] array (this is for BitType, Unsigned12BitType, etc).
However, I fear that this will slow down things considerably.

Is anyone familiar enough with the Java Memory Model to provide an educated guess as to whether a lock-free approach would be feasible?
By lock-free I mean setting the value and then checking whether the value is actually what was expected (and if not, retry).
I’m cc’ing Albert and the imagej-devel and fiji-devel lists to increase the probability that someone might actually know…

best regards,
Tobias

On 30 Oct 2014, at 00:18, Tobias Pietzsch <[hidden email]> wrote:

Hi Curtis,

I’m trying to look at it, however I get the following maven error:

pietzsch@tomancak-mac-17:~/workspace/imagej-ops (imglib2-release)$ mvn -U clean install
[INFO] Scanning for projects...
[ERROR] The build could not read 1 project -> [Help 1]
[ERROR]
[ERROR]   The project net.imagej:imagej-ops:0.6.0-SNAPSHOT (/Users/pietzsch/workspace/imagej-ops/pom.xml) has 1 error
[ERROR]     Non-resolvable parent POM: Could not find artifact net.imagej:pom-imagej:pom:3.2 in imagej.public (http://maven.imagej.net/content/groups/public) and 'parent.relativePath' points at no local POM @ line 5, column 10 -> [Help 2]
[ERROR]
[ERROR] To see the full stack trace of the errors, re-run Maven with the -e switch.
[ERROR] Re-run Maven using the -X switch to enable full debug logging.
[ERROR]
[ERROR] For more information about the errors and possible solutions, please read the following articles:

How can I fix this?

best regards,
Tobias

On 29 Oct 2014, at 23:37, Curtis Rueden <[hidden email]> wrote:

Hi Tobi & all,

[Added Christian to CC, since this mail is mostly about OPS]

Still left to do:

1) Check out the imglib2-release branch of imglib2-tests and fix the compile errors.
2) Check out the imglib2-release branch of imglib2-script and fix the compile errors.
3) Check out the imglib2-release branch of imagej-ops and figure out why tests fail now.

I spent some hours working on imagej-ops this afternoon. With the latest imglib2 master branch, there is only one remaining test failure. (I guess Tobi's bug-fix fixed the other test failure...)

The problem is really deep, though: the ParallelMapI2I uses multiple cursors simultaneously to iterate over ArrayImgs, and it seems there is a race condition that causes the ApplyManualThresholdTest to intermittently fail.

I have to head out for the day, but if anyone else wants to take a crack at it, I added a WIP to the topic branch that illustrates the issue. Setting a breakpoint on the "WTF" line will stop the code if/when the problem occurs.


On my machine, the problem seems to occur ~40% of the time, depending on the location and quantity of print statements.

Regards,
Curtis


On Mon, Oct 27, 2014 at 11:37 AM, Curtis Rueden <[hidden email]> wrote:
Hi Tobi,

I fixed the remaining errors.

Thanks!

> Curtis, maybe we can do this via Skype tomorrow (i.e. Monday)?

I am available every day from ~9:30am - 4:30pm. I am available via GChat ([hidden email]), IRC (#imagejdev and #fiji-devel on freenode) and Skype (curtis_rueden).

> I’ll continue working on these tomorrow.

Thanks again! I'll work on documentation today, then.

Regards,
Curtis

On Sun, Oct 26, 2014 at 6:51 PM, Tobias Pietzsch <[hidden email]> wrote:
Hi,

On 25 Oct 2014, at 01:02, Curtis Rueden <[hidden email]> wrote:

Tobias asked if there is anything others could do to help, so here is a list (in my opinion of priority order):

1) Check out the imglib2-release branch of imglib2-tutorials and fix the compile errors.

I fixed the remaining errors.
To run these examples I had to do two additional things (not committed because they shouldn’t be required soon)

1.) I had to add an empty class net.imglib2.img.basictypeaccess.array.BitArray to make scifio able to open the images.
This is because at some point scifio does an “instanceof BitArray” check and BitArray isn’t there anymore. These checks should be removed for next scifio version.

2.) I had to make a SNAPSHOT dependency on imglib2-core because in the current release there is a bug which I fixed in this commit https://github.com/imglib/imglib2/commit/fc0d3ebcd9256e60961180952c0383c47e63d111
So already it is time to release imglib2-core 2.0.2
It would be absolutely fantastic if you could walk me through how to do that. Curtis, maybe we can do this via Skype tomorrow (i.e. Monday)?

2) Check out the imglib2-release branch of imglib2-tests and fix the compile errors.
3) Check out the imglib2-release branch of imglib2-script and fix the compile errors.
4) Check out the imglib2-release branch of imagej-ops and figure out why tests fail now.

I’ll continue working on these tomorrow.

all the best,
Tobias

On 25 Oct 2014, at 01:02, Curtis Rueden <[hidden email]> wrote:

Hi guys,

Here is a status update on the ImgLib2 release.

The following components are released:

* imglib2 2.0.1
* imglib2-algorithm 0.1.0
* imglib2-algorithm-fft 0.1.0
* imglib2-algorithm-gpl 0.1.0
* imglib2-ij 2.0.0-beta-27
* imglib2-realtransform 2.0.0-beta-27
* imagej-common 0.10.0

The following components are not done yet:

* imglib2-script 0.1.0
* imglib2-tests
* imglib2-tutorials

(Note that for tests and tutorials, it is just a matter of updating the master branch, since we will never cut Maven release of those.)

* imagej-ops 0.6.0
* imagej-plugins-commands 0.3.0
* imagej-ui-swing 0.8.0
* scifio 0.17.0
* scifio-ome-xml 0.10.0

And probably others that will become obvious as we proceed further along.

You can glean much of this same information from the following URL:

Tobias asked if there is anything others could do to help, so here is a list (in my opinion of priority order):

1) Check out the imglib2-release branch of imglib2-tutorials and fix the compile errors.
2) Check out the imglib2-release branch of imglib2-tests and fix the compile errors.
3) Check out the imglib2-release branch of imglib2-script and fix the compile errors.
4) Check out the imglib2-release branch of imagej-ops and figure out why tests fail now.

Any help any of you can contribute toward the above goals would be greatly appreciated! I'll be back on the case on Monday. (I would not worry about the Git history, Tobi -- just fix the errors on each branch.)

Regards,
Curtis

P.S. Thorough docs on the component structure, development best practices, and related stuff will be coming soon to a http://imagej.net/Architecture near you.







_______________________________________________
ImageJ-devel mailing list
[hidden email]
http://imagej.net/mailman/listinfo/imagej-devel

signature.asc (465 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [fiji-devel] Re: What's left to do for ImgLib2

Albert Cardona
Hi Tobias and ImgLib2ers,

the bit types are not thread safe. At some point it said so in the documentation at the top of the files--I think--but I cannot find that note now in the github repository version of the files. Perhaps we removed it: as far as I know, no numeric type is thread safe. Perhaps some may be incidentally thread safe, but they don't have to be. Coordinating multi-threaded access to the same Img requires a special-purpose approach, that can be ameliorated with e.g. proxy types that declare each method as synchronized. Declaring all type methods as synchronized adds overheads to the general case, which is not the best approach.

Regarding the lock-free approach: that reads like software transactional memory, and there are implementations out there. I wouldn't want to impose that kind of overhead, either, in the Type classes themselves.

As usual with threads, code that accesses a resource must consider the consequences and synchronize access where appropriate.

Albert


2014-10-29 19:34 GMT-04:00 Tobias Pietzsch <[hidden email]>:
Ok, just looking at the code of ApplyManualThresholdTest, I have a hunch of whats going wrong.
The test uses
final Img<BitType> out = bitmap();

I bet that for the new BitType from the Fractions branch nobody considered the possibility that two cursors might simultaneously write to bits of the same underlying long value.

One solution would be to use locks to synchronize all accesses to the underlying long[] array (this is for BitType, Unsigned12BitType, etc).
However, I fear that this will slow down things considerably.

Is anyone familiar enough with the Java Memory Model to provide an educated guess as to whether a lock-free approach would be feasible?
By lock-free I mean setting the value and then checking whether the value is actually what was expected (and if not, retry).
I’m cc’ing Albert and the imagej-devel and fiji-devel lists to increase the probability that someone might actually know…

best regards,
Tobias

On 30 Oct 2014, at 00:18, Tobias Pietzsch <[hidden email]> wrote:

Hi Curtis,

I’m trying to look at it, however I get the following maven error:

pietzsch@tomancak-mac-17:~/workspace/imagej-ops (imglib2-release)$ mvn -U clean install
[INFO] Scanning for projects...
[ERROR] The build could not read 1 project -> [Help 1]
[ERROR]
[ERROR]   The project net.imagej:imagej-ops:0.6.0-SNAPSHOT (/Users/pietzsch/workspace/imagej-ops/pom.xml) has 1 error
[ERROR]     Non-resolvable parent POM: Could not find artifact net.imagej:pom-imagej:pom:3.2 in imagej.public (http://maven.imagej.net/content/groups/public) and 'parent.relativePath' points at no local POM @ line 5, column 10 -> [Help 2]
[ERROR]
[ERROR] To see the full stack trace of the errors, re-run Maven with the -e switch.
[ERROR] Re-run Maven using the -X switch to enable full debug logging.
[ERROR]
[ERROR] For more information about the errors and possible solutions, please read the following articles:

How can I fix this?

best regards,
Tobias

On 29 Oct 2014, at 23:37, Curtis Rueden <[hidden email]> wrote:

Hi Tobi & all,

[Added Christian to CC, since this mail is mostly about OPS]

Still left to do:

1) Check out the imglib2-release branch of imglib2-tests and fix the compile errors.
2) Check out the imglib2-release branch of imglib2-script and fix the compile errors.
3) Check out the imglib2-release branch of imagej-ops and figure out why tests fail now.

I spent some hours working on imagej-ops this afternoon. With the latest imglib2 master branch, there is only one remaining test failure. (I guess Tobi's bug-fix fixed the other test failure...)

The problem is really deep, though: the ParallelMapI2I uses multiple cursors simultaneously to iterate over ArrayImgs, and it seems there is a race condition that causes the ApplyManualThresholdTest to intermittently fail.

I have to head out for the day, but if anyone else wants to take a crack at it, I added a WIP to the topic branch that illustrates the issue. Setting a breakpoint on the "WTF" line will stop the code if/when the problem occurs.


On my machine, the problem seems to occur ~40% of the time, depending on the location and quantity of print statements.

Regards,
Curtis


On Mon, Oct 27, 2014 at 11:37 AM, Curtis Rueden <[hidden email]> wrote:
Hi Tobi,

I fixed the remaining errors.

Thanks!

> Curtis, maybe we can do this via Skype tomorrow (i.e. Monday)?

I am available every day from ~9:30am - 4:30pm. I am available via GChat ([hidden email]), IRC (#imagejdev and #fiji-devel on freenode) and Skype (curtis_rueden).

> I’ll continue working on these tomorrow.

Thanks again! I'll work on documentation today, then.

Regards,
Curtis

On Sun, Oct 26, 2014 at 6:51 PM, Tobias Pietzsch <[hidden email]> wrote:
Hi,

On 25 Oct 2014, at 01:02, Curtis Rueden <[hidden email]> wrote:

Tobias asked if there is anything others could do to help, so here is a list (in my opinion of priority order):

1) Check out the imglib2-release branch of imglib2-tutorials and fix the compile errors.

I fixed the remaining errors.
To run these examples I had to do two additional things (not committed because they shouldn’t be required soon)

1.) I had to add an empty class net.imglib2.img.basictypeaccess.array.BitArray to make scifio able to open the images.
This is because at some point scifio does an “instanceof BitArray” check and BitArray isn’t there anymore. These checks should be removed for next scifio version.

2.) I had to make a SNAPSHOT dependency on imglib2-core because in the current release there is a bug which I fixed in this commit https://github.com/imglib/imglib2/commit/fc0d3ebcd9256e60961180952c0383c47e63d111
So already it is time to release imglib2-core 2.0.2
It would be absolutely fantastic if you could walk me through how to do that. Curtis, maybe we can do this via Skype tomorrow (i.e. Monday)?

2) Check out the imglib2-release branch of imglib2-tests and fix the compile errors.
3) Check out the imglib2-release branch of imglib2-script and fix the compile errors.
4) Check out the imglib2-release branch of imagej-ops and figure out why tests fail now.

I’ll continue working on these tomorrow.

all the best,
Tobias

On 25 Oct 2014, at 01:02, Curtis Rueden <[hidden email]> wrote:

Hi guys,

Here is a status update on the ImgLib2 release.

The following components are released:

* imglib2 2.0.1
* imglib2-algorithm 0.1.0
* imglib2-algorithm-fft 0.1.0
* imglib2-algorithm-gpl 0.1.0
* imglib2-ij 2.0.0-beta-27
* imglib2-realtransform 2.0.0-beta-27
* imagej-common 0.10.0

The following components are not done yet:

* imglib2-script 0.1.0
* imglib2-tests
* imglib2-tutorials

(Note that for tests and tutorials, it is just a matter of updating the master branch, since we will never cut Maven release of those.)

* imagej-ops 0.6.0
* imagej-plugins-commands 0.3.0
* imagej-ui-swing 0.8.0
* scifio 0.17.0
* scifio-ome-xml 0.10.0

And probably others that will become obvious as we proceed further along.

You can glean much of this same information from the following URL:

Tobias asked if there is anything others could do to help, so here is a list (in my opinion of priority order):

1) Check out the imglib2-release branch of imglib2-tutorials and fix the compile errors.
2) Check out the imglib2-release branch of imglib2-tests and fix the compile errors.
3) Check out the imglib2-release branch of imglib2-script and fix the compile errors.
4) Check out the imglib2-release branch of imagej-ops and figure out why tests fail now.

Any help any of you can contribute toward the above goals would be greatly appreciated! I'll be back on the case on Monday. (I would not worry about the Git history, Tobi -- just fix the errors on each branch.)

Regards,
Curtis

P.S. Thorough docs on the component structure, development best practices, and related stuff will be coming soon to a http://imagej.net/Architecture near you.









--

_______________________________________________
ImageJ-devel mailing list
[hidden email]
http://imagej.net/mailman/listinfo/imagej-devel
Reply | Threaded
Open this post in threaded view
|

Lock-free bit fields, was Re: What's left to do for ImgLib2

Johannes Schindelin
In reply to this post by Tobias Pietzsch
Hi Tobias,

first of all: I am really happy that this discussion is now open, enabling
us to benefit from the entire expertise available in the ImageJ universe.

I would like to use the opportunity to provide a bit of background for
those readers who did not benefit from the extensive in-person discussions
at the hackathon, in particular because there is no public summary
available yet:

At the hackathon [*1*] the main goal was to get ImgLib2 out of beta (and
there was a *lot* of progress in that regard), and in the process a couple
of last-minute changes were introduced, amongst others a memory
optimization of the bit type containers. In particular, it changed from:

https://github.com/imglib/imglib2/blob/ffeee80%5E/core/src/main/java/net/imglib2/type/logic/BitType.java

to

https://github.com/imglib/imglib2/blob/fc0d3ebcd/src/main/java/net/imglib2/type/logic/BitType.java

That is, the BitAccess was replaced by a LongAccess. The BitAccess was
implemented by

https://github.com/imglib/imglib2/blob/ffeee80%5E/core/src/main/java/net/imglib2/img/basictypeaccess/array/BitArray.java

Unfortunately, after upgrading imagej-ops to the ImgLib2 release, the
regression tests started failing, and Tobias offered an explanation:

On Thu, 30 Oct 2014, Tobias Pietzsch wrote:

> The test uses
> final Img<BitType> out = bitmap();
>
> I bet that for the new BitType from the Fractions branch nobody
> considered the possibility that two cursors might simultaneously write
> to bits of the same underlying long value.

As the problem is intermittent and changes between test runs even on the
same computer, this is quite likely, especially given that the original
BitArray used locking explicitly:

https://github.com/imglib/imglib2/blob/ffeee80%5E/core/src/main/java/net/imglib2/img/basictypeaccess/array/BitArray.java#L85-L91

That the BitType is now thread-unsafe is therefore a regression introduced
just recently.

> One solution would be to use locks to synchronize all accesses to the
> underlying long[] array (this is for BitType, Unsigned12BitType, etc).
> However, I fear that this will slow down things considerably.

I agree that this would slow down operations as compared to the current
code (at the price of correctness *grins*), but it would not slow down
operations as compared to the BitArray which was used previously.

> Is anyone familiar enough with the Java Memory Model to provide an
> educated guess as to whether a lock-free approach would be feasible?

The best online resource on this issue I am aware of is
http://www.vogella.com/tutorials/JavaConcurrency/article.html#nonblocking
(while the best offline resource is "Java Concurrency In Practice").

It talks about the most common lock-free primitive, available in Java
since version 5.0: compare-and-swap (CAS). Unfortunately, this technique
would require us to switch to a different data type, as the operation is
not available on primitive types, let alone primitive type arrays.

Theoretically, we could paper over this issue by using the Unsafe class.
However, this class is marked as internal API for a good reason, and it
would not be advisable to make use of it to work around a fundamental
design issue.

> 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, i.e. surround the lines

https://github.com/imglib/imglib2/blob/fc0d3ebcd9256e60961180952c0383c47e63d111/src/main/java/net/imglib2/type/logic/BitType.java#L133-L137

with a `synchronized (dataAccess) { ... }` guard.

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 change

        // Clear the bits first, then or the masked value
        if ( value )
                dataAccess.setValue(i1, (dataAccess.getValue(i1) | (1l << shift) ) );
        else
                dataAccess.setValue(i1, (dataAccess.getValue(i1) & ~(1l << shift)) );

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) );
                        }
                }
        } else {
                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) );
                        }
                }
        }

However, apart from being ugly, it is a little bit too complicated to be
verified as correct easily even by myself.

As ImgLib2 has yet to attract any concurrency expert, I would be *really*
reluctant to destabilize ImgLib2 at this criticial time, and would rather
leave this for a future improvement at a time when we have concurrency
experts in our ranks.

Correctness trumps speed.

Ciao,
Johannes

Footnote *1*: The best public information so far is:
http://imagej.net/pipermail/imagej-devel/2014-October/002280.html

Footnote *2*:
https://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms

Footnote *3*: https://en.wikipedia.org/wiki/Optimistic_concurrency_control


_______________________________________________
ImageJ-devel mailing list
[hidden email]
http://imagej.net/mailman/listinfo/imagej-devel
Reply | Threaded
Open this post in threaded view
|

Re: Lock-free bit fields, was Re: What's left to do for ImgLib2

Tobias Pietzsch
Hi Johannes and Albert,

Albert, you really scared me for a moment. I thought all multi-threaded code we ever did for ImgLib2 is potentially broken now…
Fortunately it is not as bad as it seemed to me at first. NativeTypes are not thread-safe, yes, but only to the extend that results are undefined if two threads access the same index. Meaning the index of the Type, not of the underlying storage.
As Johannes points out, for the old BitType that statement was true, because write access was synchronized. Phew...

Johannes, thanks a lot for the detailed analysis!
I agree that the easiest and best way for now is to simply synchronize(dataAccess).
This will fix issues for now. We can (and should) work out a better way later.

I like the "Optimistic Concurrency Control” solution, but I also would not vouch for correctness.
We'll have to see what the overhead of the “read-value-again-to-check” operation is.

In general I think the wastefulness in the synchronize(dataAccess) is not so much the locking, but that it locks the whole dataAccess.
This basically locks the whole image. No two threads can write bits of the same image, even if those bits are not in the same long[] array element.
We cannot reasonably have a separate lock object for each array index because that would have way too much (memory) overhead.
We could have a few lock objects and then use some hashcode of the index to choose one of them.
Several indices would share the same lock object but maybe a hash function can be chosen that avoids collisions for common access patterns?
In the end, the “Optimistic Concurrency Control” is probably more feasible. It can also be combined it with the index-hashcode approach.

best regards,
Tobias

On 30 Oct 2014, at 11:49, Johannes Schindelin <[hidden email]> wrote:

> Hi Tobias,
>
> first of all: I am really happy that this discussion is now open, enabling
> us to benefit from the entire expertise available in the ImageJ universe.
>
> I would like to use the opportunity to provide a bit of background for
> those readers who did not benefit from the extensive in-person discussions
> at the hackathon, in particular because there is no public summary
> available yet:
>
> At the hackathon [*1*] the main goal was to get ImgLib2 out of beta (and
> there was a *lot* of progress in that regard), and in the process a couple
> of last-minute changes were introduced, amongst others a memory
> optimization of the bit type containers. In particular, it changed from:
>
> https://github.com/imglib/imglib2/blob/ffeee80%5E/core/src/main/java/net/imglib2/type/logic/BitType.java
>
> to
>
> https://github.com/imglib/imglib2/blob/fc0d3ebcd/src/main/java/net/imglib2/type/logic/BitType.java
>
> That is, the BitAccess was replaced by a LongAccess. The BitAccess was
> implemented by
>
> https://github.com/imglib/imglib2/blob/ffeee80%5E/core/src/main/java/net/imglib2/img/basictypeaccess/array/BitArray.java
>
> Unfortunately, after upgrading imagej-ops to the ImgLib2 release, the
> regression tests started failing, and Tobias offered an explanation:
>
> On Thu, 30 Oct 2014, Tobias Pietzsch wrote:
>
>> The test uses
>> final Img<BitType> out = bitmap();
>>
>> I bet that for the new BitType from the Fractions branch nobody
>> considered the possibility that two cursors might simultaneously write
>> to bits of the same underlying long value.
>
> As the problem is intermittent and changes between test runs even on the
> same computer, this is quite likely, especially given that the original
> BitArray used locking explicitly:
>
> https://github.com/imglib/imglib2/blob/ffeee80%5E/core/src/main/java/net/imglib2/img/basictypeaccess/array/BitArray.java#L85-L91
>
> That the BitType is now thread-unsafe is therefore a regression introduced
> just recently.
>
>> One solution would be to use locks to synchronize all accesses to the
>> underlying long[] array (this is for BitType, Unsigned12BitType, etc).
>> However, I fear that this will slow down things considerably.
>
> I agree that this would slow down operations as compared to the current
> code (at the price of correctness *grins*), but it would not slow down
> operations as compared to the BitArray which was used previously.
>
>> Is anyone familiar enough with the Java Memory Model to provide an
>> educated guess as to whether a lock-free approach would be feasible?
>
> The best online resource on this issue I am aware of is
> http://www.vogella.com/tutorials/JavaConcurrency/article.html#nonblocking
> (while the best offline resource is "Java Concurrency In Practice").
>
> It talks about the most common lock-free primitive, available in Java
> since version 5.0: compare-and-swap (CAS). Unfortunately, this technique
> would require us to switch to a different data type, as the operation is
> not available on primitive types, let alone primitive type arrays.
>
> Theoretically, we could paper over this issue by using the Unsafe class.
> However, this class is marked as internal API for a good reason, and it
> would not be advisable to make use of it to work around a fundamental
> design issue.
>
>> 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, i.e. surround the lines
>
> https://github.com/imglib/imglib2/blob/fc0d3ebcd9256e60961180952c0383c47e63d111/src/main/java/net/imglib2/type/logic/BitType.java#L133-L137
>
> with a `synchronized (dataAccess) { ... }` guard.
>
> 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 change
>
> // Clear the bits first, then or the masked value
> if ( value )
> dataAccess.setValue(i1, (dataAccess.getValue(i1) | (1l << shift) ) );
> else
> dataAccess.setValue(i1, (dataAccess.getValue(i1) & ~(1l << shift)) );
>
> 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) );
> }
> }
> } else {
> 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) );
> }
> }
> }
>
> However, apart from being ugly, it is a little bit too complicated to be
> verified as correct easily even by myself.
>
> As ImgLib2 has yet to attract any concurrency expert, I would be *really*
> reluctant to destabilize ImgLib2 at this criticial time, and would rather
> leave this for a future improvement at a time when we have concurrency
> experts in our ranks.
>
> Correctness trumps speed.
>
> Ciao,
> Johannes
>
> Footnote *1*: The best public information so far is:
> http://imagej.net/pipermail/imagej-devel/2014-October/002280.html
>
> Footnote *2*:
> https://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms
>
> Footnote *3*: https://en.wikipedia.org/wiki/Optimistic_concurrency_control
>
> _______________________________________________
> ImageJ-devel mailing list
> [hidden email]
> http://imagej.net/mailman/listinfo/imagej-devel

_______________________________________________
ImageJ-devel mailing list
[hidden email]
http://imagej.net/mailman/listinfo/imagej-devel

signature.asc (465 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Lock-free bit fields, was Re: What's left to do for ImgLib2

Johannes Schindelin
Hi Tobias,

On Thu, 30 Oct 2014, Tobias Pietzsch wrote:

> We'll have to see what the overhead of the “read-value-again-to-check”
> operation is.

For the record: synchronization is *always* more expensive than a simple
read-value-again check. I am sure that it is relatively easy to use the
junit-benchmarks [*1*] to prove that.

Ciao,
Johannes

Footnote *1*: Please note that we forked junit-benchmarks because it
requires a relatively ugly fix to work with @Before/@After methods, a fix
so ugly that upstream preferred to keep the bug rather than accepting
something as Gollum-like. The artifact was already deployed as
org.scijava:junit-benchmarks:0.7.3-scijava and it requires an upgrade to
JUnit >= 4.11.


_______________________________________________
ImageJ-devel mailing list
[hidden email]
http://imagej.net/mailman/listinfo/imagej-devel
Reply | Threaded
Open this post in threaded view
|

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

Adrian Daerr
In reply to this post by Johannes Schindelin
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

_______________________________________________
ImageJ-devel mailing list
[hidden email]
http://imagej.net/mailman/listinfo/imagej-devel
Reply | Threaded
Open this post in threaded view
|

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

Stephan Saalfeld-2
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


_______________________________________________
ImageJ-devel mailing list
[hidden email]
http://imagej.net/mailman/listinfo/imagej-devel
Reply | Threaded
Open this post in threaded view
|

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

Johannes Schindelin
In reply to this post by Adrian Daerr
Dear Adrian,

On Thu, 30 Oct 2014, Adrian Daerr wrote:

> > 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*]:
>
> 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].

Thank you for your concerns. Let me take the time for a proper discussion
rather than just linking to two articles of a highly respected developer.

Let's recapitulate the Double-Checked Locking problem for a moment: any
non-synchronized access in Java is *not* guaranteed to have the same
ordered memory-access as *any* other thread. In other words, a set of
synchronized threads might read, modify and write a certain field
correctly, all the while *another* thread might *still* receive the
unmodified value *afterwards*.

Example:

        newValue = array[i] | 1;
        array[i] = newValue;
        if (array[i] != newValue) {
                synchronized (array) {
                        newValue = array[i] | 1;
                        array[i] = newValue;
                }
        }

Let's assume that thread Albert is in the synchronized block, having just
read the very same array element as thread Bene, but Bene is just
modifying the value as per the second line. The Java Memory Model states
that Bene's modification is not necessarily seen, nor blocked by Albert's
synchronized write access because Bene is unsynchronized. And Albert's
modification will not necessarily be seen by Bene in the if() statement,
either – because Bene is unsynchronized.

So yes, the Double-Checked Locking problem applies here as well.

Ciao,
Johannes


_______________________________________________
ImageJ-devel mailing list
[hidden email]
http://imagej.net/mailman/listinfo/imagej-devel
Reply | Threaded
Open this post in threaded view
|

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

Tobias Pietzsch
In reply to this post by Stephan Saalfeld-2
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 <[hidden email]> 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
>

_______________________________________________
ImageJ-devel mailing list
[hidden email]
http://imagej.net/mailman/listinfo/imagej-devel

signature.asc (465 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

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

Stephan Saalfeld-2
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 <[hidden email]> 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
> >
>


_______________________________________________
ImageJ-devel mailing list
[hidden email]
http://imagej.net/mailman/listinfo/imagej-devel
Reply | Threaded
Open this post in threaded view
|

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

Adrian Daerr
In reply to this post by Johannes Schindelin
Hi Johannes,

> Thank you for your concerns. Let me take the time for a proper discussion
> rather than just linking to two articles of a highly respected developer.

Sorry my mail was really minimalistic. I had a lot of other stuff to do
and no time to go into details, but thought even just throwing in these
pointers might be usefull rather sooner than later.

> Let's recapitulate the Double-Checked Locking problem for a moment: any
> non-synchronized access in Java is *not* guaranteed to have the same
> ordered memory-access as *any* other thread.

The article I point to does seem to make exceptions, which is why I
hesitated in claiming that the DCL problem applies here as well. On the
second page of the first article for example, Brian Goetz says

| DCL also works with 32-bit primitive values. If the resource field in
| SomeClass were an integer (but not a long or a double), then
| SomeClass would behave as expected. However, you cannot use this
| behavior to fix the problems with DCL when you want to lazily
| initialize an object reference or more than one primitive value.

I doubt using DCL on array elements are within those lucky cases
however, even if they were a 32-bit primitive values. I have already
extended way beyond my competences though, so I'll stop here.

best regards,
Adrian

_______________________________________________
ImageJ-devel mailing list
[hidden email]
http://imagej.net/mailman/listinfo/imagej-devel
Reply | Threaded
Open this post in threaded view
|

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

Tobias Pietzsch
In reply to this post by Stephan Saalfeld-2
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 <[hidden email]> 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 <[hidden email]> 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
>>>
>>
>

_______________________________________________
ImageJ-devel mailing list
[hidden email]
http://imagej.net/mailman/listinfo/imagej-devel

signature.asc (465 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

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

Albert Cardona-2
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 <[hidden email]> 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 <[hidden email]> 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
>>>>
>>>
>>
>


_______________________________________________
ImageJ-devel mailing list
[hidden email]
http://imagej.net/mailman/listinfo/imagej-devel
Reply | Threaded
Open this post in threaded view
|

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

Curtis Rueden
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:


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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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 [hidden email].
For more options, visit https://groups.google.com/d/optout.


_______________________________________________
ImageJ-devel mailing list
[hidden email]
http://imagej.net/mailman/listinfo/imagej-devel
Reply | Threaded
Open this post in threaded view
|

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

Tobias Pietzsch
In reply to this post by Albert Cardona-2
Hi Albert,

I like that idea.
I’m not 100% sure, but I think it should be possible to have Views.synchronized(), Views.unsynchronized() methods that would change the Type between sychronized and unsynchronized versions (if available).
To properly define the signatures of these methods would probably require to make BitType an interface that is extended by the unsynchronized and synchronized implementations such that Views.(un)synchronize(RandomAccessible<T>) can return RandomAccessible<T>. This might incur additional cost for polymorphism if both BitType implementations are used at runtime but this might be alleviated using None, for example.

best regards,
Tobias


On 30 Oct 2014, at 19:44, Albert Cardona <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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
>>>>>
>>>>
>>>
>>
>

_______________________________________________
ImageJ-devel mailing list
[hidden email]
http://imagej.net/mailman/listinfo/imagej-devel

signature.asc (465 bytes) Download Attachment